IT小白

这个屌丝很懒，什么也没留下！

热门标签

Leetcode面试经典150题_leecode

作者：IT小白 | 2024-08-22 18:35:02

踩

leecode

数组字符串

合并两个有序数组

思路

类似于归并排序，对两个有序数组进行合并即可，但是空间复杂度是O(n+m);

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] ans = new int[n + m];
        int i = 0, j = 0;
        int cnt = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                ans[cnt++] = nums1[i++];
            } else {
                ans[cnt++] = nums2[j++];
            }
        }
        while(i < m) ans[cnt++] = nums1[i++];
        while(j < n) ans[cnt++] = nums2[j++];
        for (int k = 0; k < cnt; ++k) {
            nums1[k] = ans[k];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

优化：有一点小优化吧，可以从后往前合并装入nums1的后面，这样不会影响nums1的元素，同样也节省了n+m的空间（本题的数据量小，所以看不出）。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int cnt = n + m - 1;
        while(i >= 0 && j >= 0) {
            if (nums1[i] < nums2[j]) {
                nums1[cnt--] = nums2[j--];
            } else {
                nums1[cnt--] = nums1[i--];
            }
        }
        while(i >= 0) nums1[cnt--] = nums1[i--];
        while(j >= 0) nums1[cnt--] = nums2[j--];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

移除元素

思路

原地移除，用一个类似于指针的变量ind，从0开始遍历，如果与val相同则一直往后走，如果不同则压入到ind这个位置

代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int ind = 0;
        int i = 0;
        while (i < nums.length) {
            int j = i;
            while (j < nums.length && nums[j] == val) j++;
            if (j < nums.length) nums[ind++] = nums[j];
            i = j + 1;
        }
        return ind;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

删除有序数组中的重复项

思路

与上一个题相似，过滤掉相同的数字即可。

代码

class Solution {
    public int removeDuplicates(int[] nums) {
         int cnt = 1;
         int n = nums.length;
         for (int i = 0; i < n;) {
            int j = i + 1;
            while(j < n && nums[j] == nums[i]) ++j;
            if (j >= n) break;
            nums[cnt++] = nums[j];
            i = j;
         }
         return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

删除有序数组中的重复项 II

思路

与上一题类似，只是需要加一个判断，j和i的距离相差是否大于等于2。

代码

class Solution {
    public int removeDuplicates(int[] nums) {
         int cnt = 1, i = 0, j = 0;
         int n = nums.length;
         for (i = 0; i < n;) {
            j = i + 1;
            while(j < n && nums[j] == nums[i]) ++j;
            if (j >= n) break;
            if (j - i >= 2) { // 判断重复数字是否超过1个，如果超过就保留一个
                nums[cnt++] = nums[i];
            }
            nums[cnt++] = nums[j];
            i = j;
         }
         if (j - i >= 2) {
            nums[cnt++] = nums[i];
        }
         return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

多数元素

思路

选择一个候选人，将其作为答案，遇到跟候选人相同的元素，候选人就得一票，如果不同，就是自己失去一票（对方得一票）。如果票数为0，就重新选候选人。

代码

class Solution {
    public int majorityElement(int[] nums) {
        // 由于多数的个数大于其他数的个数，当遇到和候选人相同的数，票数＋1，否则票数－1
        int cand_num = nums[0], cand_cnt = 0; 
        for (int num : nums) {
            if (cand_num == num) {
                cand_cnt += 1;
            } else {
                cand_cnt -= 1;
            }
            if (cand_cnt == 0) {
                cand_num = num;
                cand_cnt = 1;
            }
        }
        return cand_num;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

轮转数组

思路

将数组元素右移k个位置，看例1：nums = [1,2,3,4,5,6,7], k = 3 ，向右移3个位置，就变为[5,6,7,1,2,3,4]
我们可以将其看为翻转：
先将1234翻转得到4321567,再将567翻转，得到4321765，再将整体进行饭庄就等到了最终结果5671234。
三次翻转的顺序可以不一致。

代码

class Solution {
    public void rotate(int[] nums, int k) {
        // 3次翻转， 整体一次， (0,k), (k, n)
        int n = nums.length;
        k %= n;
        reversal(nums, 0, n);
        reversal(nums, 0, k);
        reversal(nums, k, n);
    }
    public void reversal(int[] nums, int st, int end) {
        while(st < end) {
            int t = nums[st];
            nums[st] = nums[end - 1];
            nums[end - 1] = t;
            st++;
            end--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

买卖股票的最佳时机

思路

题意的意思是找两个数，前一个数减后一个数的结果最大。从后枚举找最大值即可。

代码

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        int mx = prices[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            ans = Math.max(ans, mx - prices[i]);
            mx = Math.max(mx, prices[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

买卖股票的最佳时机 II

思路

上一题是只求一次购买股票，现在改成可以练习购买彩票，要求获得最大的利润。可以思考一个规律
1.如果今天持有股票，那么可能是两种情况，一种是一直在入股没有卖，第二个是今天才买入的股票。
2.如果今天不持有股票，也有两种情况，一种是一直不持有股票，第二个是今天才卖出的股票。

代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 1][2];
        f[0][1] = Integer.MIN_VALUE; // 第0天持有股票的利润不存在。
        for (int i = 0; i < n; ++i) {
            f[i + 1][0] = Math.max(f[i][1] + prices[i], f[i][0]); // 第i天不持有的，等于第i-1天持有加第i天卖出。
            f[i + 1][1] = Math.max(f[i][0] - prices[i], f[i][1]); // 第i天持有的，等于第i-1天不持有加第i天买入。
        }
        return f[n][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

跳跃游戏

思路

试着跳，可以将每一个能跳到的位置作为起点，然后更新能跳到的最远距离。

代码

class Solution {
    public boolean canJump(int[] nums) {
        // 试着跳
        int k = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (i > k) return false;
            k = Math.max(k, nums[i] + i);
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11

跳跃游戏 II

思路

上一题的题意是，是否能够跳到最后，而这个题是能够到达最终位置，求最短跳跃次数。每次尝试能够跳到最远的距离，然后更新区间。

代码

class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int st = 0;
        int en = 1;
        int mxPos = 0;
        while (en < nums.length) {
            for (int i = st; i < en; ++i) {
                mxPos = Math.max(mxPos, nums[i] + i);// 每次尝试能跳到多远
            }
            st = en;
            en = mxPos + 1;
            ans++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

H指数

思路

统计引用次数相同的文章有多少篇，然后从后往前遍历论文引用次数，引用次数多的文章，满足引用次数少的文章。

代码

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] cnt = new int[n + 1];
        for (int c : citations) {
            cnt[Math.min(c, n)]++;
        }
        int s = 0;
        for (int i = n; ; --i) {
            s += cnt[i];
            if (s >= i) {
                return i;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

380. O(1) 时间插入、删除和获取随机元素

思路

本题要实现O(1)时间的插入，删除和随机获取元素，一个数据结构是不能同时满足三种情况的，O(1)时间的插入，删除可以用Map实现，而O(1)随机获取元素，要用数组或者是ArrayList实现（底层也是数组实现的），因为数组中的元素在内存中是连续的。
插入元素，按照元素插入顺序存放到数组里面，而要将其值存到map中作为用O（1）时间来判断是否存在结构中，就需要用插入的值作为键，而下标作为值。这样做的目的，是在删除元素时，容易通过删除map中的key，得到ind，将其作为下标，然后将最后的元素放到这个位置。要更新map中的值。

代码

class RandomizedSet {
    static final int N = (int) 2e5 + 10;
    int[] a;
    int idx = -1;
    Map<Integer, Integer> mp;
    Random random = new Random();
    public RandomizedSet() {
        a = new int[N];
        mp = new HashMap<>();
    }
    
    public boolean insert(int val) {
        if (mp.containsKey(val)) return false;
        a[++idx] = val;
        mp.put(val, idx);
        return true;
    }
    
    public boolean remove(int val) {
        if (!mp.containsKey(val)) return false;
        int cnt = mp.remove(val);
        if (cnt != idx) mp.put(a[idx], cnt);
        a[cnt] = a[idx--];
        return true;
    }
    
    public int getRandom() {
        return a[random.nextInt(idx + 1)];
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */
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

238. 除自身以外数组的乘积

思路1

最简单的做法就是统计前后串

代码1

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 前后缀乘积
        int n = nums.length;
        int[] last = new int[n];
        int[] fast = new int[n];
        fast[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            fast[i] = fast[i - 1] * nums[i];
        }
        last[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            last[i] = last[i + 1] * nums[i];
        }
        int[] ans = new int[n];
        ans[0] = last[1];
        ans[n - 1] = fast[n - 2];
        for (int i = 1; i < n - 1; ++i) {
            ans[i] = last[i + 1] * fast[i - 1];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

小优化，可以直接用一个前缀数组，后缀数组可以通过整体的乘积除以当前位置的元素和他的前缀数组。

思路2

将前后缀数组改为用一个变量k作为前后缀数组。

代码2

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 前后缀乘积
        int n = nums.length;
        int[] ans = new int[n];
        int k = 1;
        for (int i = 0; i < n; ++i) {
            ans[i] = k;
            k *= nums[i];
        }
        k = 1;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] *= k;
            k *= nums[i];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

加油站

思路

我们将加汽油记为收入，将花费记为支出，如果总的净收入值小于0，那么不能环形一周。如果大于0，则需要找到开始出发的位置，可以这么想，当累加的净收入值达到最小时，从最小的位置的下一个位置出发，就能环形一周。

代码

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int spare = 0;
        int minSpare = Integer.MAX_VALUE;
        int minI = 0;
        for (int i = 0; i < n; ++i) {
            spare += gas[i] - cost[i];
            if (spare < minSpare) {
                minSpare = spare;
                minI = i;
            }
        }
        if (minSpare > 0) return 0;
        return spare < 0 ? -1 : (minI + 1) % n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

分发糖果

思路

可以用两个数组，左数组要满足如果当前的分数大于左边的分数，那么左数组就要比右边数组多一个，而右数组要满足如果当前的分数大于右边的分数，那么右数组就要比左数组多一个。然后取同一个位置的左右数组中最大那个值。

代码

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        }
        int ans = left[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            ans += Math.max(left[i], right[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

接雨水

思路

单调栈，怎么才能接到雨水，找子区间的三个值，最高值，次高值和最低值，该区间能够接到的雨水量，等于最高值的位置-次高值的位置的绝对值，乘以次高值-最低值算出高度。

代码

class Solution {
    public int trap(int[] height) {
       // 只需要记录三个点， 当前的高，次高，和低
        Stack<Integer> st = new Stack<>();
        int ans = 0;
        for (int i = 0; i < height.length; ++i) {
            int h = height[i];
            while (!st.isEmpty() && h >= height[st.peek()]) {
                int bot = height[st.pop()]; // 底
                if (st.isEmpty()) break;
                int left = st.peek();
                int dh = Math.min(h, height[left]) - bot; // 高
                ans += dh * (i - left - 1);
            }
            st.add(i);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

罗马数字转整数

思路

模拟，将特殊情况，例如IV，也是直接计算I + V，然后减去2* I。

代码

class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> mp = new HashMap<>();
        mp.put('I', 1); mp.put('V', 5); mp.put('X', 10); mp.put('L', 50); mp.put('C', 100); mp.put('D', 500); mp.put('M', 1000);
        int ans = mp.get(s.charAt(0));
        char[] ch = s.toCharArray();
        for (int i = 1; i < ch.length; ++i) {
            ans += mp.get(ch[i]);
            boolean flag = ch[i - 1] == 'I' && (ch[i] == 'V' || ch[i] == 'X') ||
                            ch[i - 1] == 'X' && (ch[i] == 'L' || ch[i] == 'C') ||
                            ch[i - 1] == 'C' && (ch[i] == 'D' || ch[i] == 'M');
            if (flag) ans -= 2 * mp.get(ch[i - 1]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

整数转罗马数字

思路

贪心，从最大值开始找满足的条件。

代码

class Solution {
    public String intToRoman(int num) {
        StringBuilder ans = new StringBuilder();
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int ind = 0;
        while (ind < 13) {
            while (num >= nums[ind]) {
                num -= nums[ind];
                ans.append(romans[ind]);
            }
            ind++;
        }
        return ans.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最后一个单词的长度

思路

模拟。

代码

class Solution {
    public int lengthOfLastWord(String s) {
        int cnt = 0;
        int i = s.length() - 1;
        while (s.charAt(i) == ' ') {
            --i;
        }
        while (i >= 0 && check(s.charAt(i))) {
            ++cnt;
            --i;
        }
        return cnt;
    }
    private boolean check(char s) {
        return s >= 'a' && s <= 'z' || s >= 'A' && s <= 'Z';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

双指针

验证回文串

思路

用头指针和尾指针，每次比较的时候必须满足两个指针指向的是数字或字符，其他的符号都跳过。

代码

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        int len = s.length();
        int i = 0, j = len - 1;
        char[] ch = s.toCharArray();
        while(i < j) {
            while(i < len && !check(ch[i])) ++i;
            while(j >= 0 && !check(ch[j])) --j;//前面两句是过滤非字符或数字
            if (i > j) {
                break;
            }
            if (ch[i] >= 'a') {
                ch[i] -= 32;
            }
            if (ch[j] >= 'a') {
                ch[j] -= 32;
            }// 如果是字符，则统一转为小写
            if (ch[i] != ch[j]) {
                return false;
            }
            ++i;
            --j;
        }
        return true;
    }
    private boolean check(char ch) {
        if (ch <= 'z' && ch >= 'a') {
            return true;
        }
        if (ch <= 'Z' && ch >= 'z') {
            return true;
        }
        if (ch <= '9' && ch >= '0') {
            return true;
        }
        return 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
37
38
39

滑动窗口

长度最小的子数组

思路

由滑动窗口思想：设两个指针，尾指针一直走，当满足某个条件时，头指针也跟着走。
条件：当子数组和大于target时，不断缩小窗口，找到最小的窗口。

代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = nums.length;
        int ind = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            while (sum >= target) {
                sum -= nums[ind];
                ans = Math.min(ans, i - ind + 1);
                ind++;
            }
        }
        if (ind == 0) { // sum>=target没有执行，不存在子数组
            return 0;
        } 
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

矩阵

有效的数独

思路

创建三个set数组，分别是对存“行”，“列”，“区域”的数字，如果对应的set中有值，那么就不是有效的。否则就添加
这里最主要的是怎样判断是否为同一个区域。
可以先对9x9的表格通过i/3,j/3划分为9个3x3区域然后每个区域的值都是
(0, 0), (0, 1), (0, 2)
(1, 0), (1, 1)…
再通过将二维数组变为一维数组的计算公式i * row + j。就是9个区域。

代码

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<Character>[] rows = new HashSet[9];
        Set<Character>[] cols = new HashSet[9];
        Set<Character>[] area = new HashSet[9];
        for (int i = 0; i < 9; ++i) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            area[i] = new HashSet<>();
        }
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] > '9' || board[i][j] < '0') continue;
                if (rows[i].contains(board[i][j])) {
                    return false;
                } else {
                    rows[i].add(board[i][j]);
                }

                if (cols[j].contains(board[i][j])) {
                    return false;
                } else {
                    cols[j].add(board[i][j]);
                }
                int t= i / 3 * 3 + j / 3;
                //System.out.println(i + " " + j + " " + t);
                if (area[t].contains(board[i][j])) {
                    return false;
                } else {
                    area[t].add(board[i][j]);
                }
            }
        }
        return true;
    }
}
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

哈希表

赎金信

思路

比较r和m的26个字符个数，如果r的某个字符个数大于m的某个字符个数，则r不能由m的字符组成。

代码

class Solution {
    public boolean canConstruct(String r, String m) {
        int[] rCnt = new int[26];
        int[] mCnt = new int[26];
        for (int i = 0; i < r.length(); ++i) {
            rCnt[r.charAt(i) - 'a']++;
        }
        for (int i = 0; i < m.length(); ++i) {
            mCnt[m.charAt(i) - 'a']++;
        }
        for (int i = 0; i < 26; ++i) {
            if (rCnt[i] > mCnt[i]) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

区间

汇总区间

思路

简单模拟

代码

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n;) {
            int j = i;
            while(j < n -1 && nums[j] + 1 == nums[j + 1]) j++;
            if (j == i) {
                ans.add("" + nums[i]);
                ++i;
            } else {
                ans.add(nums[i] + "->" + nums[j]);
                i = j + 1;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

栈

有效括号

思路

如果能够匹配则删除栈顶元素，如果不能匹配就进栈，最后判断是否为空。

代码

class Solution {
    static final Map<Character, Character> map = new HashMap<>() {{
        put('(',')');
        put('{','}');
        put('[',']');
    }};
    public boolean isValid(String s) {
        char[] ch = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        
        for (char c : ch) {
            if (stack.isEmpty()) {
                stack.push(c);
                continue;
            }
            Character peek = stack.peek();
            if (map.containsKey(peek) && map.get(peek) == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
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

链表

环形链表

思路

链表长度最长1e4，头结点一直往后走，如果次数超过链表长度，必定有环（投机取巧了）

代码

public class Solution {
    public boolean hasCycle(ListNode head) {
        int cnt = 0;
        while(head != null) {
            head = head.next;
            cnt++;
            if (cnt > 10005) {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

正解：快慢指针，根据Floyd判圈法，又称为龟兔赛跑算法，乌龟每次走一格，兔子每次走两格，如果有环，兔子提前进入环并且一直在环内运动，而当乌龟进入环时，兔子一定会追到乌龟。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next ==null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二叉树

二叉树的最大深度

思路

模拟走一遍二叉树同时记录层数。

代码

class Solution {
    int ans = 0;
    public int maxDepth(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
    public void dfs(TreeNode root, int level) {
        if (root == null) {
            ans = Math.max(ans, level);
            return;
        }
        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉树的遍历

二叉树的右视图

思路

二叉树的层序遍历，取每层的最后一个节点即可。

代码

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        int cnt = 0, lastVal = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            cnt = queue.size();// 每层有多少个节点
            while(cnt-- > 0) {
                TreeNode curNode = queue.poll();
                if (curNode.left != null) queue.add(curNode.left);
                if (curNode.right != null) queue.add(curNode.right);
                lastVal = curNode.val;
            }
            ans.add(lastVal);//每层的最后一个节点
        }
        return ans;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二叉搜索树

二叉搜索树的最小绝对差

思路

二叉搜索树的中序遍历是升序，而升序的相邻节点可以得到一个最小值，即答案所求。

代码

class Solution {
    int ans = Integer.MAX_VALUE;
    int pre = -1; // 记录中序遍历的前一个节点,初始化为-1，是还没找到中序遍历的第一个节点
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return ans;
    }
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre == -1) {
            pre = root.val;
        } else {
            ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

图

岛屿数量

思路

dfs没走过的为1的格子

代码

class Solution {
    int N = 305;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    boolean[][] vis = new boolean[N][N];
    int n, m, ans;
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (vis[i][j] || grid[i][j] == '0') continue;
                dfs(grid, i, j);
                //System.out.println(i + "<->" + j);
                ans++;
            }
        }
        return ans;
    }
    private void dfs(char[][] g, int x, int y) {
        vis[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            int curX = x + dir[i][0];
            int curY = y + dir[i][1];
            if (curX < 0 || curY < 0 || curX >= m || curY >= n || g[curX][curY] == '0' || vis[curX][curY]) continue;
            dfs(g, curX, curY);
        }
    }
}
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

图广度优先搜索

蛇梯棋

思路

题实在没读懂，参考解析。
利用广度优先搜索，先走格子，如果遇到梯子或蛇就直接传送（传送不花时间）。

代码

class Solution {
    int n;
    int[] g;
    public int snakesAndLadders(int[][] board) {
        n = board.length;
        boolean isR = true;
        g = new int[n * n + 1];
        int ind = 0;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = (isR ? 0 : n - 1); isR ? j < n : j >= 0; j += isR ? 1 : -1) { // 经典的神龙摆尾
                g[++ind] = board[i][j];
            }
            isR = !isR;
        }
        int ans = bfs();
        return ans;
    }
    private int bfs()  {
        Queue<Integer> queue = new LinkedList<>(); // 当前到的点
        Map<Integer, Integer> m = new HashMap<>(); // 用于存当前点和步数
        m.put(1, 0);
        queue.add(1);
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            int step = m.get(cur);
            if (cur == n * n) return step;
            for (int i = 1; i <= 6; ++i) {
                int nxt = cur + i;
                if (nxt > n * n) continue;
                if (g[nxt] != -1) nxt = g[nxt]; //直接传送
                if (m.containsKey(nxt)) continue; // 已经走过
                m.put(nxt, step + 1);
                queue.add(nxt);
            }
        }
        return -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
29
30
31
32
33
34
35
36
37
38
39

字典树

实现 Trie (前缀树)

思路

字典树模版题

代码

class Trie {
    static final int N = (int) 1e5 + 9;
    static int[] cnt = new int[N];
    static int[][] tree = new int[N][26];
    static int ind = 0;
    public Trie() {
        for (int i = ind; i >= 0; --i) {
            Arrays.fill(tree[i], 0);
        }
        Arrays.fill(cnt, 0);
        ind = 0;
    }
    
    public void insert(String word) {
        int p = 0;
        for (int i = 0; i < word.length(); ++i) {
            int u = word.charAt(i) - 'a';
            if (tree[p][u] == 0) tree[p][u] = ++ind;
            p = tree[p][u];
        }
        cnt[p]++;
    }
    
    public boolean search(String word) {
        int p = 0;
        for (int i = 0; i < word.length(); ++i) {
            int u = word.charAt(i) - 'a';
            if (tree[p][u] == 0) return false;
            p = tree[p][u];
        }
        return cnt[p] != 0;
    }
    
    public boolean startsWith(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); ++i) {
            int u = prefix.charAt(i) - 'a';
            if (tree[p][u] == 0) return false;
            p = tree[p][u];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
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
48
49
50
51

回溯

电话号码的字母组合

思路

将每个键对应的字母存到String里，然后dfs变量每一个键，遍历到的键存到一个数组里，指导存了digits.size()个。

代码

class Solution {
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    private final List<String> ans = new ArrayList<>();
    private char[] digits, path;
    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if (n == 0) return List.of();
        this.digits = digits.toCharArray();
        path = new char[n];
        dfs(0);
        return ans;
    }
    private void dfs(int i) {
        if (i ==digits.length) { // 如果已经按完
            ans.add(new String(path));
            return;
        }
        for (char c : MAPPING[digits[i] - '0'].toCharArray()) { // 枚举按每一个键
            path[i] = c; // 考虑先后顺序，先出现的和后出现的做匹配
            dfs(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
24

分治

将有序数组转换为二叉搜索树

思路

以每个区间的中点作为根节点进行建树，这是一个分治的过程。

代码

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }
    private TreeNode dfs(int[] nums, int L, int R) {
        if (L > R) {
            return null;
        }
        int mid = (L + R) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, L, mid - 1);
        root.right = dfs(nums, mid + 1, R);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Kadane 算法

最大子数组和

思路

思维题，用一个sum变量记录当前子数组和的最大值，如果小于0，则不要这段数组，因为任何数加一个小于0的数都会变小。边加边取最大值即可。

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int sum =0;
        for (int num : nums) {
            if (sum < 0) {
                sum = 0;
            }
            sum += num;
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二分查找

搜索插入位置

思路

二分查找模版题

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l +r) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

堆

数组中的第K个最大元素

思路

用优先队列来做，因为优先队列底层就是堆实现的（默认小根堆），然后开一个k+1大小的小根堆，每次维持堆里的元素只有k个，最后输出堆顶，也就是队首即可。

代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k + 1);
        for (int num : nums) {
            queue.offer(num);
            if (queue.size() == k + 1) {
                queue.poll();
            }
        }
        return queue.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】