Leetcode精选75题

https://leetcode.cn/studyplan/leetcode-75/

1 数组/字符串

1.1 交替合并字符串

【交替合并字符串】

给你两个字符串word1和word2。请你从word1开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回合并后的字符串。

解题思路
- 求出两字符串长度最大值，以最大值遍历，每次遍历判断是否超出字符长度，未超出则拼接

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public class Solution {
    public String mergeAlternately(String word1, String word2) {
        int maxLen = Math.max(word1.length(), word2.length());
        StringBuilder str = new StringBuilder();
        for (int i=0; i<maxLen; i++) {
            if (i < word1.length()) {
                str.append(word1.charAt(i));
            }
            if (i < word2.length()) {
                str.append(word2.charAt(i));
            }
        }
        return str.toString();
    }
}
// 时间复杂度：O(n)

1.2 字符串的最大公因子

【字符串的最大公因子】

对于字符串s和t，只有在s = t + t + t + ... + t + t（t自身连接1次或多次）时，我们才认定 “t能除尽s”。

给定两个字符串str1和str2。返回最长字符串x，要求满足x能除尽str1且x能除尽str2。

解题思路
- 根据题目特性，求出str1和str2长度的最大公约数长度gcdLen（利用辗转相除法），此长度切割下来的字符串就是最大公约数字符gcdStr
- 再判断一下最大公约数字符gcdStr真能拼接出str1和str2

 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
28
29
30


public class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int gcdLen = gcdLen(str1.length(), str2.length());
        String gcdStr = str1.substring(0, gcdLen);
        if (checkGcd(str1, gcdStr) && checkGcd(str2, gcdStr)) {
            return gcdStr;
        }
        return "";
    }

    public int gcdLen(int a, int b) {
        int remainder = a % b;
        while (remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }

    public boolean checkGcd(String str, String gcdStr) {
        int multiple = str.length() / gcdStr.length();
        StringBuilder result = new StringBuilder();
        for (int i=0 ; i<multiple; i++) {
            result.append(gcdStr);
        }
        return str.equals(result.toString());
    }
}
// 时间复杂度：O(n)

1.3 拥有最多糖果的孩子

【拥有最多糖果的孩子】

有n个有糖果的孩子。给你一个数组 candies，其中candies[i]代表第i个孩子拥有的糖果数目，和一个整数extraCandies表示你所有的额外糖果的数量。

返回一个长度为n的布尔数组result，如果把所有的extraCandies给第i个孩子之后，他会拥有所有孩子中最多的糖果，那么result[i]为true，否则为false。

注意，允许有多个孩子同时拥有最多的糖果数目。

解题思路
- 求数组中的最大值，遍历数组把额外糖果数加上，超出最大值true，反之false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


public class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int maxCandie = candies[0];
        for (int i=1; i<candies.length; i++) {
            maxCandie = Math.max(maxCandie, candies[i]);
        }
        List<Boolean> result = new ArrayList<>();
        for (int candie : candies) {
            result.add(candie + extraCandies >= maxCandie);
        }
        return result;
    }
}
// 时间复杂度：O(n)

1.4 种花问题

【种花问题】

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组flowerbed表示花坛，由若干0和1组成，其中0表示没种植花，1表示种植了花。另有一个数n，能否在不打破种植规则的情况下种入n朵花？能则返回true，不能则返回false。

解题思路
- 总结每种空地能多少花的规律
- （1）空地左右两边有花，例10001，能种花的数量为(空地长度-1)/2
- （2）左or右边界没有花，例00001，能种花的数量为空地长度/2
- （3）空地完全没有花，例00000，能种花的数量为(空地长度+1)/2
- 总结以上规律后，利用指针计算出空地的长度，再而计算能种花的数量，最后对比n

 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 class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int prev = -1;
        int placeCount = 0;
        for (int i=0; i<flowerbed.length; i++) {
            if (flowerbed[i] == 1) {
                if (prev < 0) {
                    // 空地在左边界
                    placeCount += i / 2;
                } else {
                    // 空地在中间
                    placeCount += (i - prev - 2) / 2;
                }
                prev = i;
            }
        }
        if (prev < 0) {
            // 全是空地
            placeCount = (flowerbed.length + 1) / 2;
        } else {
            // 空地在右边界
            placeCount += (flowerbed.length - prev - 1) / 2;
        }
        return placeCount >= n;
    }
}
// 时间复杂度：O(n)

1.5 反转字符串中的元音字母

【反转字符串中的元音字母】

给你一个字符串s，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

解题思路：
- 字符串转字符数组，左右双指针寻找元音字母，进行数组交换

 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
28


public class Solution {
  public String reverseVowels(String s) {
    char[] charArray = s.toCharArray();
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
      while (left < s.length() && !isVowel(charArray[left])) {
        left ++;
      }
      while (right > -1 && !isVowel(charArray[right])) {
        right --;
      }
      if (left < right) {
        char temp = charArray[left];
        charArray[left] = charArray[right];
        charArray[right] = temp;
        left ++;
        right --;
      }
    }
    return new String(charArray);
  }

  public boolean isVowel(char c) {
    return "aoiueAOIUE".indexOf(c) >= 0;
  }
}
// 时间复杂度：O(n)

1.6 翻转字符串里的单词

【反转字符串中的单词】

给你一个字符串s，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

解题思路
- 前后双指针寻找单词，字符串切割后倒叙拼接

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public class Solution {
  public String reverseWords(String s) {
    int start = -1;
    StringBuilder result = new StringBuilder();
    for (int i=0; i<s.length(); i++) {
      // 空格，切割单词并反向拼接
      if (start != -1 && s.charAt(i) == ' ') {
        result.insert(0, s.substring(start, i) + " ");
        start = -1;
        continue;
      }
      // 非空格，记录单词起始位置
      if (start == -1 && s.charAt(i) != ' ') {
        start = i;
      }
    }
    // 边界处理
    if (start != -1) {
      result.insert(0, s.substring(start) + " ");
    }
    return result.substring(0, result.length()-1);
  }
}

1.7 除自身以外数组的乘积

【除自身以外数组的乘积】

给你一个整数数组nums，返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。

题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32位整数范围内。

请不要使用除法，且在O(n)时间复杂度内完成此题。

解题思路
- 因为题目禁止除法，以及禁止嵌套循环，需要思路非寻常解法
- 准备从左到右累乘的数组leftMul，以及从右到左累乘的数组rigthMul，隔一位进行累乘
- 最后结果就是leftMul[i] * rightMul[i]，相当与把num[i]的值改为1的累乘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftMul = new int[n];
        // 计算左乘数组
        leftMul[0] = 1;
        for (int i=1; i<n; i++) {
            leftMul[i] = nums[i-1] * leftMul[i-1];
        }
        // 计算右乘数组
        int[] rightMul = new int[n];
        rightMul[n-1] = 1;
        for (int i=n-2; i>-1; i--) {
            rightMul[i] = nums[i+1] * rightMul[i+1];
        }
        // 计算结果
        int[] result = new int[n];
        for (int i=0; i<n; i++) {
            result[i] = leftMul[i] * rightMul[i];
        }
        return result;
    }
}

1.8 递增的三元子序列

【递增的三元子序列】

给你一个整数数组nums，判断这个数组中是否存在长度为3的递增子序列。

如果存在这样的三元组下标(i, j, k)且满足i < j < k，使得nums[i] < nums[j] < nums[k]，返回true；否则，返回false。

解题思路
- 维护两个数组，从左到右的最小值数组leftMin，和从右到左的最大值数组rightMax
- 遍历数组，保证leftMin[i-1] < nums[i] < rightMax[i+1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        int[] rightMax = new int[n];
        rightMax[n-1] = nums[n-1];
        for (int i=1; i<n; i++) {
            leftMin[i] = Math.min(leftMin[i-1], nums[i]);
        }
        for (int i=n-2; i>-1; i--) {
            rightMax[i] = Math.max(rightMax[i+1], nums[i]);
        }
        for (int i=1; i<n-1; i++) {
            if (leftMin[i-1] < nums[i] && rightMax[i+1] > nums[i]) {
                return true;
            }
        }
        return false;
    }
}
// 时间复杂度：O(n)

1.9 压缩字符串

【压缩字符串】

给你一个字符数组chars，请使用下述算法压缩：

从一个空字符串s开始。对于chars中的每组连续重复字符：

如果这一组长度为1，则将字符追加到s中。

否则，需要向s追加字符，后跟这一组的长度。

压缩后得到的字符串s不应该直接返回，需要转储到字符数组chars中。需要注意的是，如果组长度为10或10以上，则在chars数组中会被拆分为多个字符。

请在修改完输入数组后，返回该数组的新长度。

解题思路：
- 准备两个变量，记录压缩后的字符长度strLen，同时也是改写字符数组的下标；记录重复字符的起始位置start
- 比较前后变量，不一致时，通过i-start+1计算出重复字符的长度，根据长度按规则改写字符数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public class Solution {
    public int compress(char[] chars) {
        int strLen = 0;
        int start = 0;
        for (int i=0; i<chars.length; i++) {
            if (i == chars.length -1 || chars[i] != chars[i+1]) {
                chars[strLen++] = chars[i];
                int size = i - start + 1;
                // 长度大于1，后面补充长度字符
                if (size > 1) {
                    char[] nums = String.valueOf(size).toCharArray();
                    for (char num : nums) {
                        chars[strLen++] = num;
                    }
                }
                start = i + 1;
            }
        }
        return strLen;
    }
}
// 时间复杂度：O(n)

2 双指针

2.1 移动零

【移动零】

给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

解题思路
- 两次循环，第一次循环找出非0的元素，按顺序改写到左边；第二次循环，把剩下的元素改写为0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public class Solution {
    public void moveZeroes(int[] nums) {
        int cur = 0;
        // 非0元素左移
        for (int i=0; i<nums.length; i++) {
            if (nums[i] != 0) {
                nums[cur++] = nums[i];
            }
        }
        // 剩下元素改写为0
        for (int i=cur; i<nums.length; i++) {
            nums[i] = 0;
        }
    }
}
// 时间复杂度：O(n)

2.2 判断子序列

【判断子序列】

给定字符串s和t，判断s是否为t的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

解题思路：
- 双指针分别移动匹配

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() > t.length()) {
            return false;
        }
        if (s.isEmpty()) {
            return true;
        }
        int charIdx = 0;
        for (int i=0; i<t.length(); i++) {
            if (t.charAt(i) != s.charAt(charIdx)) {
                continue;
            }
            charIdx ++;
            if (charIdx == s.length()) {
                return true;
            }
        }
        return false;
    }
}
// 时间复杂度：O(n)

2.3 盛最多水的容器

给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。

找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

解题思路：
- 左右边界双指针，开始计算水量，高度较小的指针往中间移动，直到高度比之前的要高，或两指针重合

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int size = 0;
        while (left < right) {
            int minHeight = Math.min(height[left], height[right]);
            size = Math.max(size, (right-left) * minHeight);
            if (height[left] < height[right]) {
                while (height[left] <= minHeight) {
                    left ++;
                }
            } else {
                while (height[right] <= minHeight) {
                    right --;
                }
            }
        }
        return size;
    }
}
// 时间复杂度：O(n)

2.4 K和数对的最大数目

【K和数对的最大数目】

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

解题思路：
- 对数组排序，左右边界双指针；两指针和大于K，右指针左移；反之左指针右移；相等则一起移动，并操作数+1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


public class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int step = 0;
        while (left < right) {
            if (nums[left] + nums[right] == k) {
                left ++;
                right --;
                step ++;
            } else if (nums[left] + nums[right] > k) {
                right --;
            } else {
                left ++;
            }
        }
        return step;
    }
}
// 时间复杂度：O(n)

3 滑动窗口

3.1 子数组最大平均数 I

【子数组最大平均数 I】

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。。

请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

解题思路：计算初始长度为k的数组总和sum，通过循环计算sum = sum + nums[i] - nums[i-k]每个长度为k的数组总和，求出最大数组后取平均值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i=0; i<k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i=k; i<nums.length; i++) {
            sum = sum + nums[i] - nums[i-k];
            maxSum = Math.max(maxSum, sum);
        }
        return 1.0 * maxSum / k;
    }
}
// 单循环，【时间复杂度：O(n)】

3.2 定长子串中元音的最大数目

【定长子串中元音的最大数目】

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的元音字母为（a, e, i, o, u）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public class Solution {
    public int maxVowels2(String s, int k) {
        int sum = 0;
        for (int i=0; i<k; i++) {
            sum += isVowel(s.charAt(i));
        }
        int max = sum;
        for (int i=k; i<s.length(); i++) {
            sum += isVowel(s.charAt(i)) - isVowel(s.charAt(i-k));
            max = Math.max(max, sum);
        }
        return max;
    }

    public int isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'u' || c == 'o' ? 1 : 0;
    }
}
// 单循环，【时间复杂度：O(n)】

4 哈希表/哈希集合

4.1 确定两个字符串是否接近

【确定两个字符串是否接近】

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串接近：

操作 1：交换任意两个现有字符。

例如，abcde -> aecdb

操作 2：将一个现有字符的每次出现转换为另一个现有字符，并对另一个字符执行相同的操作。

例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）

你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近，就返回 true ；否则，返回 false 。

解题思路
- 用26大小的数组，记录字符1和2的字母个数
- 对比两数组的字符是否存在
- 排序过后，对比两数组的数据是否相同，来实现操作2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for (char c : word1.toCharArray()) {
            count1[c - 'a']++;
        }
        for (char c : word2.toCharArray()) {
            count2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if ((count1[i] > 0 && count2[i] == 0) || (count1[i] == 0 && count2[i] > 0)) {
                return false;
            }
        }
        Arrays.sort(count1);
        Arrays.sort(count2);
        return Arrays.equals(count1, count2);
    }
}
// 时间复杂度：单层循环O(n)

5 栈

5.1 从字符串中移除星号

【从字符串中移除星号】

给你一个包含若干星号 * 的字符串 s 。

在一步操作中，你可以：

选中 s 中的一个星号。

移除星号左侧最近的那个非星号字符，并移除该星号自身。

返回移除所有星号之后的字符串。

解题思路：
- 可以使用栈的思路，遇到*就出栈，然后再遍历栈中数据
- 使用栈转字符串步骤比较麻烦，可以换个思路，遇到*，直接移除新字符串的最后一位

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    public String removeStars(String s) {
        StringBuilder res = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '*') {
                res.setLength(res.length()-1);
            } else {
                res.append(c);
            }
        }
        return res.toString();
    }
}
// 时间复杂度：单循环O(n)

6 队列

6.1 最近的请求次数

【最近的请求次数】

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。

int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证每次对 ping 的调用都使用比之前更大的 t 值。

解题思路：循环比较队首的时间是否小于t-3000，是则移除，最后返回队列大小即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class RecentCounter {
    private final Queue<Integer> counter;

    public RecentCounter() {
        counter = new ArrayDeque<>();
    }

    public int ping(int t) {
        counter.offer(t);
        while (counter.peek() < t-3000) {
            counter.poll();
        }
        return counter.size();
    }
}
// 时间复杂度：均摊 O(1)，每个元素至多入队出队各一次。

7 链表

7.1 删除链表的中间节点

【删除链表的中间节点】

给你一个链表的头节点 head 。删除链表的中间节点，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 [n / 2] 个节点（下标从 0 开始）。

解题思路：快慢指针，快指针走2，慢指针走1，走到最后时，慢指针就是中间节点

 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
28


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (Objects.isNull(head.next)) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        while (!Objects.isNull(fast) && !Objects.isNull(fast.next)) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = slow.next;
        return head;
    }
}
// 时间复杂度：O(n)

8 二叉树

8.1 叶子相似的树

叶子相似的树

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

解题思路：二叉树深度遍历

 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
28
29
30
31
32
33
34
35
36


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaf1List = new ArrayList<>();
        List<Integer> leaf2List = new ArrayList<>();
        this.getLeafList(root1, leaf1List);
        this.getLeafList(root2, leaf2List);
        return leaf1List.equals(leaf2List);
    }

    public void getLeafList(TreeNode node, List<Integer> leafList) {
        if (!Objects.isNull(node.left)) {
            this.getLeafList(node.left, leafList);
        }
        if (!Objects.isNull(node.right)) {
            this.getLeafList(node.right, leafList);
        }
        if (Objects.isNull(node.left) && Objects.isNull(node.right)) {
            leafList.add(node.val);
        }
    }
}

8.2 二叉树的右视图

二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思路：二叉树广度遍历，记录每层最右侧的数据

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (Objects.isNull(root)) {
            return Collections.emptyList();
        }
        List<Integer> rightList = new ArrayList<>();
        Queue<TreeNode> nodes = new ArrayDeque<>();
        nodes.offer(root);
        this.getRightList(nodes, rightList);
        return rightList;
    }
    
    public void getRightList(Queue<TreeNode> nodes, List<Integer> rightList) {
        if (Objects.isNull(nodes) || nodes.isEmpty()) {
            return;
        }
        int n = nodes.size();
        for (int i=0; i<n; i++) {
            TreeNode node = nodes.poll();
            if (!Objects.isNull(node.left)) {
                nodes.offer(node.left);
            }
            if (!Objects.isNull(node.right)) {
                nodes.offer(node.right);
            }
            if (i == n-1) {
                rightList.add(node.val);
            }
        }
        this.getRightList(nodes, rightList);
    }
}

8.3 二叉搜索树中的搜索

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

解题思路：二叉搜索树，左节点数据小于根节点，右节点数据大于根节点，以此规则进行检索即可

 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
28
29
30
31


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode node = root;
        while (!Objects.isNull(node)) {
            if (node.val == val) {
                return node;
            }
            if (node.val < val) {
                node = node.right;
                continue;
            }
            node = node.left;
        }
        return null;
    }
}

9 图

9.1 钥匙和房间

钥匙和房间

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入所有房间返回 true，否则返回 false。

输入：rooms = [[1],[2],[3],[]]

输出：true

解题思路：用一个数组记录房间是否被访问过，图的深度，广度遍历都可以
- 深度遍历：一条路走到底，没有在回溯上个房间，找下一条路
- 广度遍历：用队列存储所有可以访问的房间，一个个访问，有新的房间则加入队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[] visitedArr = new int[rooms.size()];
        visitedArr[0] = 1;
        Queue<Integer> keys = new ArrayDeque<>(rooms.get(0));
        while (!keys.isEmpty()) {
            Integer key = keys.poll();
            if (visitedArr[key] == 1) {
                continue;
            }
            keys.addAll(rooms.get(key));
            visitedArr[key] = 1;
        }
        for (int visited : visitedArr) {
            if (visited == 0) {
                return false;
            }
        }
        return true;
    }
}

10 动态规划

10.1 第 N 个泰波那契数

第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例：

输入：n = 4

输出：4

解题思路：可以按照动态规划，创建一个dp数组，按照规则维护数组；也可以选择准备4个变量进行维护

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int first = 0;
        int second = 1;
        int third = 1;
        int result;
        for (int i = 2; i < n; i ++) {
            result = first + second + third;
            first = second;
            second = third;
            third = result;
        }
        return result;
    }
}
// 时间复杂度：O(n)

10.2 使用最小花费爬楼梯

使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例：

输入：cost = [10,15,20]

输出：15

解释：你将从下标为 1 的台阶开始。支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。

解题思路： 维护一个dp数组，当前楼层最小值 = min((到达前1楼层的最小值 + 前1楼层的支付费用), (到达前2楼层的最小值 + 前2楼层的支付费用))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));
        }
        return dp[dp.length - 1];
    }
}
// 时间复杂度：O(n)

10.3 不同路径

不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例：

输入： m = 3, n = 7

输出： 28

解题思路： 维护一个二维的dp数组，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}
// 时间复杂度：O(mn)

10.4 最长公共子序列

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例：

输入： text1 = "abcde", text2 = "ace"

输出： 3

解释： 最长公共子序列是 "ace" ，它的长度为 3

解题思路：维护一个2元dp数组
- char1[i] == char2[j]时，dp[i][j] = dp[i-1][j-1] + 1
- char1[i] != char2[j]时，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()][text2.length()];
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {
                if (chars1[i] == chars2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length() - 1][text2.length() - 1];
    }
}
// 时间复杂度：O(mn)

10.5 买卖股票的最佳时机含手续费

买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例：

输入： prices = [1, 3, 2, 8, 4, 9], fee = 2

输出： 8

解释： 能够达到的最大利润:

在此处买入 prices[0] = 1

在此处卖出 prices[3] = 8

在此处买入 prices[4] = 4

在此处卖出 prices[5] = 9

总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

解题思路：维护一个二维dp数组，或者两个一维dp数组，其中一个记录无股票时的金额，另一个记录有股票的金额
- dp[0][0] = 0; dp[1][0] = -prices[i];
- dp[0][i] = max(dp[0][i - 1], prices[i] + dp[1][i - 1] - fee)，即手里无股票，有可能是前一天也没股票；或者前一天有股票，但在今天卖出
- dp[1][i] = max(dp[0][i - 1] - prices[i], dp[1][i - 1])，即手里有股票，有可能是前一天没股票，在今天进行购入；或者前一天就有股票了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[2][prices.length];
        dp[0][0] = 0;
        dp[1][0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], prices[i] + dp[1][i - 1] - fee);
            dp[1][i] = Math.max(dp[0][i - 1] - prices[i], dp[1][i - 1]);
        }
        return dp[0][prices.length - 1];
    }
}
// 时间复杂度：O(n)

10.6 编辑距离

编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例 1：

输入： word1 = "horse", word2 = "ros"

输出： 3

解释：

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

解题思路： 维护一个二维的dp数组，里面记录字符a到字符b的最小编辑距离
- dp[0][i] = i, dp[j][0] = j，初始化，空字符到字符a，或字符b的最小编辑距离是字符长度
- dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1])，字符的最短距离，是前一个字符的最短 + 1；如何字符i，字符j相同时，最短距离则为前一个字符，无需+1
- dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)，同理，只是字符i和字符j不相同时，需要+1编辑距离

 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


class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = i;
        }
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (char1[i - 1] == char2[j - 1]) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1]);
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
// 时间复杂度：O(mn)