LeetCode刷题1-10

LeetCode刷题
Word count: 3.4k   |   Reading time≈ 14 min

58.最后一个单词的长度①

题目：给你一个字符串s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。
单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

  1. charAt():检索字符串中指定位置的字符
    1
    2
    3
    String str = "Hello, World!";
    char ch = str.charAt(7); 
    System.out.println(ch);
  2. trim():函数是String类的一个方法。它用于去除字符串两端的空格。（注意只是两端的字符，中间的空格无法删除）
  3. split(“ ”):字符串按照指定的分隔符进行拆分，并返回拆分后的子字符串数组
  4. last()：方法的作用是返回集合中的最后一个元素。注意：只有Kotlin中有，java中没有

注意在java中：
length()：用于获取字符串的长度。length()是String类的一个方法，可以用于返回字符串中字符的数量。
length：用于获取数组的长度。length是数组的一个属性，可以用于返回数组(字符串数组也是)中元素的数量。

注意在Kotlin中：
String类的length是一个属性而不是方法。因此，可以直接通过splitWords.last().length来获取字符串的长度。

该题目考虑以下情况[]表示空格：
Annie[]study[][][]
用反向遍历法，从后往前遍历

66.加一②

题目：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

  1. java中倒置循环遍历数组： for(int i = last; i >= 0; i–)
  2. kotlin中倒置循环遍历数组：for(i in digits.indices.reversed())
    numbers.indices 是 numbers 数组的索引范围
    .reversed() 将索引范围进行反转，即倒序排列

思考：需要考虑进位

  1. 末尾无进位
  2. 末尾有进位
    ①(数字位数保持不变)在中间位置停止，当前位置加,1后为0，则前一位继续加1，直到不为0为止，如499+1=500
    ②(数字位数多1位)999+1=1000

67.二进制求和③

题目：给你两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。

  1. 在 Java 中，我们可以像这样使用 charAt() 方法来获取字符串中指定位置的字符，然后通过减去字符 ‘0’(ASCII码值为48)，获取该字符对应的数字。
    例如： 
    1
    2
    char c = '5';
    int digit = c - '0'
    字符 ‘5’ 的 ASCII 码值为 53，字符 ‘0’ 的 ASCII 码值为 48。
    因此，当我们将字符 ‘0’ 的 ASCII 码值从字符 c 的 ASCII 码值中减去时，就可以得到字符’5’对应的数字5。
  2. java中StringBuilder用法 
    1
    2
    3
    4
    5
    //创建对象
    StringBuilder sb = new StringBuilder();
    //append()里面可以追加任意类型
    //sb得到的是StringBuilder类型,需要toSting()才是字符串类型
    sb.append();
  3. java中获取字符串某一位置字符a.charAt(i)
    kotlin中获取字符串某一位置字符可以用a[i]
  4. java中有三元运算符 condition ? then : else
    Kotlin中没有三元运算符 val max = if (a > b) a else b

思考：
可以逐位计算两个二进制的和
将字符串 a 和 b 的每一位字符转化为数字先加到sum上，如果超过索引范围，则加0
sum % 2; sum对2取余，可以得到当前位置上二进制的值
sum / 2; sum对2取商，可以得到当前位置对下一位置是否有一个进位
循环结束后如果还有一个进位，则再追加一位
在StringBuilder中得到的是倒序的二进制字符串，需要倒置

69.x的平方根④

题目：给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5

java中
**Math.floor();**向下取整

二分查找

  1. 前提：数组A必须是有序的
    确定范围后用范围中间的值进行比较
  2. 定义左边界L,有边界R,确定搜索范围，循环执行二分查找(3、4两步)
  3. 获取中间索引M = Math.floor((L+R)/2)
  4. 中间索引值 A[M] 与待搜索的值 T 进行比较
  • 中间索引值A[M] == T表示找到
  • A[M] > T,继续向左边找，M - 1设置为右边界，重新查找
  • A[M] < T,继续向右边找，M + 1设置为左边界，重新查找
  1. 当 L > R时，表示没有找到，结束循环
  2. 解决整数溢出的方法：
    (1) 找中间值(L+R)/2时，如果 L 和 R 很大时，有可能会超出整数取值的最大值
    (尤其范围在右侧查找的情况)
    (l + r)/2 = l/2 + r/2
    = l - l/2 + r/2
    = l - (l/2 - r/2)
    = l - (l - r)/2
    = 1 + (r - l)/2

(2) 无符号的右移运算代替除法 → 更高效
(l + r) >>> 1; (还是相当于除以2)
7. 在二分查找算法中，中间位置的计算取决于搜索区间的性质。这里根据搜索区间是否为左闭右开来确定是否需要在计算中间位置时加上+1。

  • 搜索区间为左闭右开：如果搜索区间是左闭右开的，即右边界是开区间，那么计算中间位置时不需要加+1。
    例如：int mid = (left + right) / 2;
    这种情况适用于数组的索引范围或者是区间表示中不包括右边界的场景。
  • 搜索区间为左闭右闭：如果搜索区间是左闭右闭的，即右边界是闭区间，那么计算中间位置时需要加+1，以确保取到右边更接近中间的数。
    例如：int mid = left + (right - left + 1) / 2;
    这种情况适用于某些数据结构中，或者是区间表示中包括右边界的场景。

在该代码中，初始的搜索区间是 [0, arr.length)，即左闭右开区间，搜索的范围是 [0, arr.length-1]。因此，在计算中间位置时，我们使用 (left + right) / 2，而不需要加 +1 来调整中间位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int binarySearch(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;
        int m;
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[m] == target) {
                return m;
            }
            if (arr[m] > target) {
                r = m - 1;
            }
            if (arr[m] < target) {
                l = m + 1;
            }
        }
        return -1;
    }

左闭右闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
        int left = 1;
        int right = x/2;
        while(left < right) {
            **int mid = left + (right - left + 1)/2;**
            if(mid * mid == x){
                return mid;
            }
            if(mid > x/mid){
                right = mid - 1;
            }
            if(mid < x/mid){
                left = mid;
            }
        }
        return left;

    }
}

思考：
除了 0 和 1 的算数平方根是自己
一个数的平方根不会大于自己的1/2
问题转化为 → 在[0 - x/2]之间找一个特定的值

x - √x x/2
0 0 0
1 1 0.5
2 1 1
4 2 2
3 1 1.5
5 2 2.5
9 16 3

70.爬楼梯⑤

题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

递归 

1
2
3
4
5
6
7
8
class Solution {
    //递归方法
    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        return climbStairs(n-1) + climbStairs(n - 2);
    }
}

动态规划
解决最优化问题的一种方法
动态规划的转移方法
滚动数组法
f(n) = f(n-1) + f(n-2) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int climbStairs(int n) {
   /**
       p  n-2步
       q  n-1步
       r  目标n阶
   */
       int p = 0,q = 0,r = 1;
       for(int i = 1; i<=n ; i++){
           p = q;
           q = r;
           r = p+q;
       }
       return r;
   }

Kotlin 

1
2
3
4
5
6
7
8
9
10
11
fun climbStairs(n: Int): Int {
        if(n<2) return 1
        val step = IntArray(n + 1)
        step[0] = 1
        step[1] = 1
        for(i in 2 until n+1){
            step[i] = step[i-1] + step[i-2]
        }
        return step[n]

    }

思考：
n
1 1
2 1 1
2
3 1 1 1
1 2
2 1
4 1 1 1 1
2 2
1 1 2
1 2 1
2 1 1
递推公式：
dp(n) = dp(n-1) + dp(n-2)
最终到达n,有两种方法，从n-1再走1步，从n-2再走两步
dp(1) = 1
dp(2) = dp(1) + dp(0) = 2
dp(3) = dp(1) + dp(2) = 3
dp(4) = dp(3) + dp(2) = 5

83.删除排序链表中的重复元素⑥

题目：给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

思考：
是一个简单的 单向链表
删除重复元素：将当前指针，指向下下一个节点(绕过下一个节点)

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;
        ListNode cur = head;
        while(cur.next != null){
            if(cur.val == cur.next.val){
                cur.next = cur.next.next; //内容重复就跳到下下个节点
            }else{
                cur = cur.next;
            }
        }
        return head;
    }

88. 合并两个有序数组⑦

题目：给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6]
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
Array.sort():将数组中的数字按照升序排列

合并后直接排序

1
2
3
4
5
6
public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0; i<n; i++){
            nums1[m + i] = nums2[i]; 
        }
        Arrays.sort(nums1);
    }

双指针
注意
必须先判断指针是否到达边界 否则会出现数组下标越界的错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//双指针 将数组看做队列
   public void merge(int[] nums1, int m, int[] nums2, int n) {
       int p1 = 0;
       int p2 = 0;
       int cur;
       int [] sorted = new int[m + n];
       //注意 必须先判断指针是否到达边界
       //否则会出现数组下标越界的错误
       while(p1 < m || p2 < n){
            if(p1 == m){
               cur = nums2[p2++];
           }else if(p2 == n){
               cur = nums1[p1++];
           }else if(nums1[p1] < nums2[p2]){
               cur = nums1[p1++];
           }else{
               cur = nums2[p2++];
           }
          
          //注意cur = nums2[p2++];是先将p2位置的数给cur再加一的，赋值后p2已经加一指向下一个位置
           sorted[p1 + p2 -1] = cur;
       }
       for(int i = 0; i<m+n; i++){
           nums1[i] = sorted[i];
       }

   }

94.二叉树的中序遍历⑧

题目：给定一个二叉树的根节点 root ，返回它的 中序 遍历。
思考：二叉树的中序遍历是指按照左子树 -> 根节点 -> 右子树的顺序遍历二叉树(从最下方开始)。

前中后序遍历是针对根节点来说的

  1. 前序遍历：根节点 -> 左子树 -> 右子树(根左右 )
  2. 中序遍历：左子树 -> 根节点 -> 右子树(左根右)
  3. 后序遍历：左子树 -> 右子树 -> 根节点
    有一个巧妙的方法：在每个节点的左下右(分别对应前中后序的遍历)方分别画圆圈，从根节点开始画线，把整个数用连续的线包裹起来，点被连到的顺序就是其

思考：我们先递归遍历左子树，然后把当前结点的值加入到 List 实例中，最后再递归遍历右子树。这样可以确保在访问某个结点之前，先遍历它的左子树；在访问某个结点之后，再遍历它的右子树。最终，返回存储遍历结果的 List 实例 res。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

100.相同的树⑨

题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

101.对称二叉树⑩

题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。
对称二叉树.png

思考：
问题可以转化为给出两个二叉树，判断它们是不是镜像的

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left,root.right);
    }

    public boolean check(TreeNode p,TreeNode q){
        if(p==null && q==null) return true;
        if(p==null || q==null) return false;
        return p.val == q.val && check(p.left,q.right) && check(p.right,q.left);
    } 
}
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信