150题
#算法 2024-01-17

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 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
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m+n];
        int cur = 0;
        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++];
            }

            sorted[p1+p2-1]=cur;
        }

        for(int i=0; i< nums1.length; i++){
            nums1[i] = sorted[i];
        }
    }
}

时间复杂度 $O(m+n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while(len1 >= 0 && len2 >= 0) {
            // 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }
}

移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int idx = 0;
        for(int num : nums){
            if(num!=val){
                nums[idx++] = num;
            }
        }

        return idx;
    }
}

删除有序数组的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int removeDuplicates(int[] nums) {
        int idx = 0;
        for (int i=0;i<nums.length - 1;i++){
            if(nums[i]!=nums[i+1])
                nums[idx++] = nums[i];
        }
        nums[idx++] = nums[nums.length - 1];
        return idx;
    }
}

改进: 数组中没有重复元素，按照上面的方法，每次比较时 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。

因此我们可以添加一个小判断，当 q - p > 1 时，才进行复制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
        if(nums[p] != nums[q]){
            if(q - p > 1){
                nums[p + 1] = nums[q];
            }
            p++;
        }
        q++;
    }
    return p + 1;
}

删除有序数组的重复项2

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeDuplicates(int[] nums) {
        int idx = 0;

        for(int i=idx+2; i<nums.length;i++){
            if(nums[idx] != nums[i]){
                nums[idx+2] = nums[i];
                idx++;
            }
        }

        return idx+2;
    }
}

计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int removeDuplicates(int[] nums) {
        int left=0,right=0,n=nums.length;
        int preNum = nums[0],cnt=0;
        while(right<n){
            if(nums[right]==preNum){
                cnt++;
                if(cnt>2){
                    right++;
                    continue;
                }
            }else{
                preNum = nums[right];
                cnt=1;
            }
            nums[left++]=nums[right++];
        }
        return left;
    }
}

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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 majorityElement(int[] nums) {
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();

        for(int i = 0; i<nums.length;i++){
            if(mp.get(nums[i])==null){
                mp.put(nums[i], 1);
            }else{
                int temp = mp.get(nums[i]) + 1;
                mp.put(nums[i], temp);
            }
        }

        for(Map.Entry<Integer, Integer> entry: mp.entrySet()){
            if(entry.getValue()>(nums.length/2)){
                return entry.getKey();
            }
        }

        return 0;
    }
}

排序

1
2
3
4
5
6
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public void rotate(int[] nums, int k) {
        int[] temp = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            temp[(i+k)%nums.length] = nums[i];
        }

        System.arraycopy(temp, 0, nums, 0, nums.length);

    }
}

环状替换

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 void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}

翻转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void rotate(int[] nums, int k) {
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums,k,nums.length-1);

    }

    public void reverse(int[] nums, int start, int end){
        while(start<end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            start++;
            end--;
        }


    }
}

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int count = 0;
        int min = 10000;
        for(int i=0; i<prices.length; i++){
            if(prices[i]<min)
                min = prices[i];
            if(count<(prices[i]-min))
                count = prices[i]-min;

        }

        return count;
    }
}

买卖股票的最佳时机2

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

贪心

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int count = 0;
        for(int i=0; i<prices.length-1;i++){
            if(prices[i+1]>prices[i]){
                count += prices[i+1] - prices[i];
            }
        }

        return count;
    }

动态规划

第 1 步：定义状态

状态 dp[i][j] 定义如下：

dp[i][j] 表示到下标为 i 的这一天，持股状态为 j 时，我们手上拥有的最大现金数。

注意：限定持股状态为 j 是为了方便推导状态转移方程，这样的做法满足 无后效性。

其中：

第一维 i 表示下标为 i 的那一天（ 具有前缀性质，即考虑了之前天数的交易 ）；
第二维 j 表示下标为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。
第 2 步：思考状态转移方程

状态从持有现金（cash）开始，到最后一天我们关心的状态依然是持有现金（cash）；
每一天状态可以转移，也可以不动。

说明：

由于不限制交易次数，除了最后一天，每一天的状态可能不变化，也可能转移；
写代码的时候，可以不用对最后一天单独处理，输出最后一天，状态为 0 的时候的值即可。
第 3 步：确定初始值

起始的时候：

如果什么都不做，dp[0][0] = 0；
如果持有股票，当前拥有的现金数是当天股价的相反数，即 dp[0][1] = -prices[i]；
第 4 步：确定输出值

终止的时候，上面也分析了，输出 dp[len - 1][0]，因为一定有 dp[len - 1][0] > dp[len - 1][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
public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 0：持有现金
        // 1：持有股票
        // 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }
}

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
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, i+nums[i]);
        }

        return true;
    }
}

跳跃游戏2

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。返回到达 nums[n - 1] 的最小跳跃次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int end = 1;
        int k = 0;

        for(int i=0;i<nums.length;i++){
            k = Math.max(k, i+nums[i]);
            if(i == end){
                end = k;
                ans++;
            }
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int end = 0;
        int begin = 0;

        while(end<nums.length-1){
            int temp = 0;

            for(int i = begin; i<=end; i++){
                temp = Math.max(i+nums[i], temp);
            }

            begin = end + 1;
            end = temp;
            ans++;
        }

        return ans;
    }
}

H指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1;
        while(i>= 0 && citations[i]>h){
            h++;
            i--;
        }

        return h;
    }
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length, tot = 0;
        int[] counter = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {
                counter[n]++;
            } else {
                counter[citations[i]]++;
            }
        }
        for (int i = n; i >= 0; i--) {
            tot += counter[i];
            if (tot >= i) {
                return i;
            }
        }
        return 0;
    }
}

二分查找

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 {
    public int hIndex(int[] citations) {
        int left = 0,right = citations.length;
        int count = 0, mid = 0;

        while(left<right){
            mid = (left+right+1)>>1;

            count = 0;
            for(int i =0; i< citations.length;i++){
                if(citations[i]>=mid)
                    count++;
            }

            if(count>=mid)
                left = mid;
            else
                right = mid -1;
            
        }
        return left;
    }
}

O(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
class RandomizedSet {
    Random rd;
    Map<Integer, Integer> mp;
    int idx;
    static int[] nums = new int[200010];

    public RandomizedSet() {
        rd = new Random();
        mp = new HashMap();
        idx = -1;
    }
    
    public boolean insert(int val) {
        if(!mp.containsKey(val)){
            nums[++idx] = val;
            mp.put(val, idx);
            return true;
        }else{
            return false;
        }
            
    }
    
    public boolean remove(int val) {
        if(mp.containsKey(val)){
            int loc = mp.remove(val);
            if(loc != idx) mp.put(nums[idx], loc);
            nums[loc] = nums[idx--];
            return true;
        }else{
            return false;
        }
    }
    
    public int getRandom() {
        return nums[rd.nextInt(idx + 1)];
    }
}

出自身以外元素的乘积

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

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

请 不要使用除法，且在 O(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
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];

        int[] left = new int[nums.length];
        int[] right = new int[nums.length];

        left[0] = 1;
        for(int i=1; i<nums.length; i++){
            left[i] = left[i - 1] * nums[i -1];
        }

        right[nums.length - 1] = 1;

        for(int i=nums.length -2;i>=0;i--){
            right[i] = right[i+1]*nums[i+1];
        }

        for(int i = 0;i<nums.length;i++){
            answer[i] = left[i] * right[i];
        }

        return answer;
    }
}

改进

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 int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i];
        }
        return answer;
    }
}

加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -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
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;

        while(i<n){
            int sum_g = 0,sum_c = 0;
            int count = 0;

            while(count < n){
                int j = (i+count)%n;
                sum_g += gas[j];
                sum_c += cost[j];

                if(sum_g<sum_c)
                    break;

                count++;
            }

            if(count == n){
                return i;
            }else{
                i = i + count + 1;
            }


        }

        return -1;



    }
}

分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 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

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];

        for(int i=0;i<n;i++){
            if(i>0 && ratings[i]>ratings[i-1]){
                left[i] = left[i-1]+1;
            }else{
                left[i] = 1;
            }
        }

        int right = 0, count = 0;

        for(int i = n-1; i>=0; i--){
            if(i<n-1 && ratings[i]>ratings[i+1]){
                right++;
            }else{
                right = 1;
            }

            count += Math.max(left[i], right);
        }

        return count;
    }

    
}

接雨水

给定 n 个非负整数表示每个宽度为 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
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int m = getMax(height);
        int sum = 0;
        for(int i=1;i<=m;i++){
            boolean isStart = false;
            int temp = 0;
            for(int j = 0; j<n; j++){
                if(isStart && height[j]<i){
                    temp++;
                }
                if(height[j]>=i){
                    sum = sum + temp;
                    temp = 0;

                    isStart = true;
                }
            }
        }

        return sum;
    }

    public int getMax(int[] height){
        int max = 0;
        for(int i=0; i<height.length;i++){
            if(max<height[i])
                max = height[i];
        }
        
        return max;
    }
}

按列算

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
class Solution {
    public int trap(int[] height) {
        int sum = 0;
        for(int i= 1;i<height.length-1;i++){
            int max_left = 0;
            for(int j = i - 1;j>=0;j--){
                if(height[j]>max_left)
                    max_left = height[j];
            }

            int max_right = 0;

            for(int j=i+1;j<height.length;j++){
                if(height[j]>max_right)
                    max_right = height[j];
            }

            int min = Math.min(max_left, max_right);

            if(min>height[i]){
                sum += (min - height[i]);
            }
        }

        return sum;
    }
}

动态规划

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
class Solution {
    public int trap(int[] height) {
        int sum = 0;

        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];

        for(int i =1;i<height.length-1;i++){
            max_left[i]= Math.max(max_left[i-1], height[i-1]);
        }

        for(int i = height.length - 2; i>=0;i--){
            max_right[i] = Math.max(max_right[i+1], height[i+1]);
        }

        for(int i=1;i<height.length-1;i++){
            int min = Math.min(max_left[i], max_right[i]);
            if(min>height[i]){
                sum += (min - height[i]);
            }
        }

        return sum;
    }
}

双指针

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) {
        int sum = 0;
        int max_left = 0;
        int[] max_right = new int[height.length];
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            max_left = Math.max(max_left, height[i - 1]);
            int min = Math.min(max_left, max_right[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }
}

罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

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
class Solution {
    public int romanToInt(String s) {
        char[] chars = s.toCharArray();
        int[] ints = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            ints[i] = getValue(chars[i]);
        }
        int sum = 0;
        for (int i = 0; i < ints.length; i++) {
            if (i < ints.length - 1 && ints[i] < ints[i + 1]) {
                ints[i] *= -1;
            }
            sum += ints[i];
        }
        return sum;
    }

    private int getValue(char romanChar) {
        switch (romanChar) {
            case 'I' -> {
                return 1;
            }
            case 'V' -> {
                return 5;
            }
            case 'X' -> {
                return 10;
            }
            case 'L' -> {
                return 50;
            }
            case 'C' -> {
                return 100;
            }
            case 'D' -> {
                return 500;
            }
            case 'M' -> {
                return 1000;
            }
            default -> {
                return 0;
            }
        }
    }
}

整数转罗马数字

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。

模拟

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[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();

        for(int i=0;i<values.length;i++){
            int value = values[i];
            String symbol = symbols[i];

            while(num>=value){
                num -= value;
                roman.append(symbol);
            }
            if(num == 0){
                break;
            }
        }

        return roman.toString();
    }
}

硬编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    String[] thousands = {"", "M", "MM", "MMM"};
    String[] hundreds  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    String[] tens      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    String[] ones      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        roman.append(thousands[num / 1000]);
        roman.append(hundreds[num % 1000 / 100]);
        roman.append(tens[num % 100 / 10]);
        roman.append(ones[num % 10]);
        return roman.toString();
    }
}

最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int lengthOfLastWord(String s) {
        int end = s.length() - 1;
        while(end>=0&& s.charAt(end) == ' ') end--;
        if(end<0) return 0;
        int start = end;
        while(start>=0 && s.charAt(start)!= ' ') start--;
        return end-start;
    }
}

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

横向扫描

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
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0)
            return "";

        String pre = strs[0];
        for(int i=1;i<strs.length;i++){
            pre = common(pre, strs[i]);
            if(pre.length()==0)
                break;
        }

        return pre;
    }

    public String common(String str1, String str2){
        int length = Math.min(str1.length(), str2.length());

        int index = 0;
        while(index<length&&str1.charAt(index) == str2.charAt(index))
            index++;
        
        return str1.substring(0, index);
    }
}

纵向扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        int length = strs[0].length();
        int count = strs.length;

        for(int i=0; i<length;i++){
            char c = strs[0].charAt(i);
            for(int j = 1;j<count;j++){
                if(i == strs[j].length()||strs[j].charAt(i)!=c)
                    return strs[0].substring(0, i);
            }
        }

        return strs[0];
    }
}

反转字符串中的单词

给你一个字符串 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
24
25
class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        int length = s.length() ;
        StringBuilder ans = new StringBuilder();

        for(int i = length -1;i>=0;i--){
             while(i>=0 && s.charAt(i) ==' '){
                --i;
            }
            int end = i;
            if(i<0){
                break;
            }

            while(i>=0 && s.charAt(i)!=' '){
                i--;
            }

            ans.append(" ").append(s.substring(i+1, end+1));
        }

        return ans.toString().trim();
    }
}

Z字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

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
class Solution {
    public String convert(String s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r*2 - 2;
        int c = (n+t-1)/t * (r-1);


        char[][] mat = new char[r][c];

        for(int i=0, x=0, y=0;i<s.length();i++){
            mat[x][y] = s.charAt(i);
            if(i%t<r-1){
                ++x;
            }else{
                --x;
                ++y;
            }
        }

        StringBuffer ans = new StringBuffer();
        for(char[] row: mat){
            for(char ch: row){
                if(ch!=0){
                    ans.append(ch);
                }
            }
        }

        return ans.toString();
    }
}

flag 

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 String convert(String s, int numRows) {
        if(numRows<2) return s;
        List<StringBuffer> rows = new ArrayList<StringBuffer>();

        for(int i=0;i<numRows;i++) rows.add(new StringBuffer());

        int i=0, flag = -1;

        for(char c:s.toCharArray()){
            rows.get(i).append(c);

            if(i == 0 || i == numRows - 1) flag = -flag;

            i+= flag;
        }
        StringBuffer res = new StringBuffer();
        for(StringBuffer row : rows) res.append(row);

        return res.toString();
    }
}

找出字符串中第一个匹配的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -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
class Solution {
    public int strStr(String haystack, String needle) {
        int n = needle.length();
        int length  = haystack.length();
        int ans = -1;
        for(int i=0;i<=length - n;i++){
            String temp = haystack.substring(i, i+n);

            if(equals(temp, needle)){
                ans = i;
                break;
            }
        }

        return ans;
    }

    public boolean equals(String s_1, String s_2){
        char[] s1 = s_1.toCharArray(), s2 = s_2.toCharArray();
        int n = s_1.length(), m = s_2.length();
        if(n!=m)
            return false;
        for(int i=0;i<n;i++){
            if(s1[i]!=s2[i])
                return false;
        }

        return true;

        
    }
}

KMP

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
class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }
}

文本左右对齐

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

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
52
53
54
55
56
57
58
59
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<String>();

        int right = 0, n = words.length;
        while(true){
            int left = right;
            int sumlen = 0;
            while(right<n && sumlen + words[right].length() + right - left <= maxWidth){
                sumlen += words[right++].length();
            }

            if(right == n){
                StringBuffer sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                ans.add(sb.toString());
                return ans;
            }

            int numWords = right - left;
            int numSpaces = maxWidth - sumlen;

            if(numWords==1){
                StringBuffer sb = new StringBuffer(words[left]);
                sb.append(blank(numSpaces));
                ans.add(sb.toString());
                continue;
            }

            // 当前行不只一个单词
            int avgSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuffer sb = new StringBuffer();
            sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接额外加一个空格的单词
            sb.append(blank(avgSpaces));
            sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其余单词
            ans.add(sb.toString());
        }
    }

    // blank 返回长度为 n 的由空格组成的字符串
    public String blank(int n) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; ++i) {
            sb.append(' ');
        }
        return sb.toString();
    }

    // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
    public StringBuffer join(String[] words, int left, int right, String sep) {
        StringBuffer sb = new StringBuffer(words[left]);
        for (int i = left + 1; i < right; ++i) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }
}

验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isPalindrome(String s) {
      StringBuffer temp = new StringBuffer();

      int n = s.length();  
      for(int i=0;i<n;i++){
          char c = s.charAt(i);

          if(Character.isLetterOrDigit(c)){
              temp.append(Character.toLowerCase(c));
          }
      }

      StringBuffer rev = new StringBuffer(temp).reverse();

      return temp.toString().equals(rev.toString());
    }
}

双指针

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 boolean isPalindrome(String s) {
      StringBuffer temp = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                temp.append(Character.toLowerCase(ch));
            }
        }
      int n = temp.length();  
      int i = 0, j = n - 1;

      while(i<j){
          char ch1 = temp.charAt(i);
          char ch2 = temp.charAt(j);
          if(ch1!=ch2)
            return false;
          i++;
          j--;
      }

      return true;
    }
}

判断子序列

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

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

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = t.length();
        int n = s.length();

        int i=0, j = 0;

        while(i<n && j < m){
            if(s.charAt(i) == t.charAt(j)){
                i++;
            }
            j++;
        }

        return i == 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
28
class Solution {
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();

        int[][] f = new int[m + 1][26];
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s.charAt(i) - 'a'] == m) {
                return false;
            }
            add = f[add][s.charAt(i) - 'a'] + 1;
        }
        return true;
    }
}

两数之和||

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

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[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length -1;
        int length = numbers.length;
        int[] ans = new int[2];
        while(i<j){
            int temp = numbers[i] + numbers[j];

            if(temp == target){
                ans[0] = i+1;
                ans[1] = j+1;
                return ans;
            }else if(temp < target){
                i++;
            }else{
                j--;
            }
        }

        return ans;
    }
}

盛最多水的容器

给定一个长度为 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
class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int max = 0;
        while(i<j){
            int temp = (j - i) * Math.min(height[j], height[i]);

            if(temp>max)
                max = temp;
            if(height[j]>=height[i]){
                i++;
            }else if(height[j]<=height[i]){
                j--;
            }
        }

        return max;
    }
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        int len = nums.length;
        if(nums == null||len<3){
            return res;
        }

        Arrays.sort(nums);

        for(int i=0;i<len;i++){
            if(nums[i]>0){
                break;
            }

            if(i>0 && nums[i] == nums[i-1])
                continue;
            
            int l = i + 1;
            int r = len - 1;

            while(l<r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));

                    while(l < r && nums[l] == nums[l+1]) {
                        l++;
                    }
                    
                    while(l< r && nums[r] == nums[r-1]){
                        r--;
                    } 

                    l++;
                    r--;
                }else if(sum < 0){
                    l++;
                }else{
                    r--;
                }
            }
        }

        return res;
    }
}

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int len = nums.length;

        for(int i=0;i<len;i++){
            int temp = 0;
            for(int j = i;j<len;j++){
                temp += nums[j];
                if(temp>=target){
                    ans = Math.min(ans, j-i+1);
                    break;
                }
                
            }
        }

        return ans == Integer.MAX_VALUE?0:ans;

    }
}

前缀和+二分查找

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
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int len = nums.length;

        if(len == 0)
            return 0;
        
        int[] sum = new int[len+1];
        for(int i = 1;i<=len;i++){
            sum[i] =sum[i-1] + nums[i-1];
        }

        for(int i=1;i<=len;i++){
            int temp = target + sum[i-1];
            int bound = Arrays.binarySearch(sum, temp);
            if(bound<0){
                bound = -bound - 1;
            }
            if(bound<=len){
                ans = Math.min(ans, bound-(i-1));
            }
        }

        return ans == Integer.MAX_VALUE?0:ans;

        
    }
}

滑动窗口

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 int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;

        while(end<n){
            sum += nums[end];
            while(sum>=target){
                sum -= nums[start];
                ans = Math.min(ans, end-start+1);
                start++;
            }

            end++;
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> mp = new HashMap();

        int n = s.length();
        int ans = 0;
        int pre = 0;
        for(int i =0; i<n; i++){
            if(mp.containsKey(s.charAt(i))){
                pre = Math.max(pre,mp.get(s.charAt(i)) + 1);
            }
            mp.put(s.charAt(i), i);
            ans = Math.max(ans, i-pre+1);
        }

        return ans;
    }
}

串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,”cd”,”ef”]， 那么 “abcdef”， “abefcd”，”cdabef”， “cdefab”，”efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

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
52
53
54
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        //所有单词的个数
        int num = words.length;

        int wordLen = words[0].length();
        int stringLen = s.length();

        for(int i=0;i<wordLen;i++){
            if(i+num*wordLen>stringLen){
                break;
            }

            Map<String, Integer> differ = new HashMap<>();
            for(int j = 0;j<num;j++){
                String word = s.substring(i+j*wordLen, i+(j+1)*wordLen);
                differ.put(word, differ.getOrDefault(word, 0)+1);
            }

            for(String word: words){
                differ.put(word, differ.getOrDefault(word, 0) -1);

                if(differ.get(word) == 0){
                    differ.remove(word);
                }
            }

            for(int start = i;start<stringLen - num * wordLen+1; start += wordLen){
                if(start != i){
                    String word = s.substring(start + (num - 1) * wordLen, start + num * wordLen);
                    differ.put(word, differ.getOrDefault(word, 0)+1);
                    if(differ.get(word)==0){
                        differ.remove(word);
                    }

                    word = s.substring(start - wordLen, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);

                    if(differ.get(word) == 0){
                        differ.remove(word);
                    }
                    word = s.substring(start-wordLen, start);
                }

                if(differ.isEmpty()){
                    res.add(start);
                }
            }

        }
        return res;
    }
}

##最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

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
class Solution {
    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for(int i = 0;i<tLen;i++){
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0)+1);
        }

        int l = 0, r=-1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while(r<sLen){
            ++r;

            if(r<sLen && ori.containsKey(s.charAt(r))){
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while(check() && l<= r){
                if(r-l+1<len){
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if(ori.containsKey(s.charAt(l))){
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }

        return ansL == -1 ? "" : s.substring(ansL, ansR);

    }

    public boolean check() {
        Iterator iter = ori.entrySet().iterator(); 
        while (iter.hasNext()) { 
            Map.Entry entry = (Map.Entry) iter.next(); 
            Character key = (Character) entry.getKey(); 
            Integer val = (Integer) entry.getValue(); 
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        } 
        return true;
    }

}

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

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
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int size = 9;
        int[] rows = new int[size];
        int[] columns = new int[size];
        int[] boxs = new int[size];

        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                char val = board[i][j];

                if(val!='.'){
                    int index = 1<<(val-'0');
                    int boxNum = (i/3)*3+j/3;
                    if((rows[i] & index) != 0 || (columns[j] & index) != 0 || (boxs[boxNum] & index) != 0){
                        return false;
                    }
                    rows[i] |= index;
                    columns[j] |= index;
                    boxs[boxNum] |= index;
                }
            }
        }

        return true;
    }
}

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法一：（顺序合并）

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
/**
 * 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 mergeKLists(ListNode[] lists) {
        int n = lists.length;
        ListNode ans = null;
        for(int i=0;i<n;i++){
            ans = mergeTwoLists(ans, lists[i]);
        }

        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b){
        if(a==null||b==null){
            return a!=null?a:b;
        }

        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;

        while(aPtr!=null&&bPtr!=null){
            if(aPtr.val<bPtr.val){
                tail.next = aPtr;
                aPtr = aPtr.next;
            }else{
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }

        tail.next = (aPtr!=null?aPtr:bPtr);

        return head.next;
    }
}

解法二（分治合并）

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
52
53
54
55
56
57
/**
 * 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 mergeKLists(ListNode[] lists) {
        int n = lists.length;
        ListNode ans = null;
        for(int i=0;i<n;i++){
            ans = mergeTwoLists(ans, lists[i]);
        }

        return ans;
    }

    public ListNode merge(ListNode[] lists, int l,int r){
        if(l==r){
            return lists[l];
        }
        if(l>r){
            return null;
        }
        int mid = (l+r)>>1;

        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid+1,r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b){
        if(a==null||b==null){
            return a!=null?a:b;
        }

        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;

        while(aPtr!=null&&bPtr!=null){
            if(aPtr.val<bPtr.val){
                tail.next = aPtr;
                aPtr = aPtr.next;
            }else{
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }

        tail.next = (aPtr!=null?aPtr:bPtr);

        return head.next;
    }
}

503. 下一个更大的元素 ||

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for(int i=0;i<n*2-1;i++){
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i%n]){
                ret[stack.pop()]=nums[i%n];
            }
            stack.push(i%n);
        }

        return ret;
    }
}

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isValid(String s) {
        int n = s.length();

        Stack<Character> stack = new Stack<>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c==']')
                stack.push(']');

            else if(stack.empty()||c!=stack.pop())
                return false;
        }
        
        return stack.empty();
    }
}
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 isValid(String s) {
        Deque<Character> stack = new LinkedList<>();

        for(char c:s.toCharArray()){
            if(c == '(')
                stack.addFirst(')');
            else if(c == '{')
                stack.addFirst('}');
            else if(c=='[')
                stack.addFirst(']');

            else if(stack.isEmpty()||c!=stack.pollFirst())
                return false;
        }
        if(stack.isEmpty())
            return true;
        
        return false;
    }
}

71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//‘）都被视为单个斜杠 ‘/‘ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 ‘/‘ 开头。
两个目录名之间必须只有一个斜杠 ‘/‘ 。
最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
返回简化后得到的 规范路径 。

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
class Solution {
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<String>();
        for(String name:names){
            if("..".equals(name)){
                if(!stack.isEmpty()){
                    stack.pollLast();
                }
            }else if(name.length()>0&&!".".equals(name)){
                stack.offerLast(name);
            }
        }
        StringBuilder ans = new StringBuilder();
        if(stack.isEmpty()){
            ans.append('/');
        }else{
            while(!stack.isEmpty()){
                ans.append('/');
                ans.append(stack.pollFirst());
            }  
        }
        return ans.toString();
    }
}

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        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;
    }
}

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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
/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;

        int carry = 0;
        while(l1!=null||l2!=null){
            int x = l1 ==null ? 0 :l1.val;
            int y = l2 == null ? 0: l2.val;
            int sum = x+y+carry;

            carry = sum/10;
            sum = sum %10;
            cur.next = new ListNode(sum);

            cur = cur.next;

            if(l1!=null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;

        }

        if(carry == 1){
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }
}

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
}

BFS

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
/**
 * 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 int maxDepth(TreeNode root) {
       if(root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        queue.offer(root);
        int ans = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size>0){
                TreeNode node = queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }

        return ans;
    }
}

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

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
/**
 * 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 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);
        }

    }
}

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

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 List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();

        for(int num:nums){
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first){
        if(first==n){
            res.add(new ArrayList<Integer>(output));
        }
        for(int i = first; i<n;i++){
            Collections.swap(output, first, i);
            backtrack(n, output, res, first+1);
            Collections.swap(output, first, i);
        }
    }
}

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

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
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(k<=0||n<k){
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);

        return res;
    }

    private void dfs(int n, int k, int begin, 
    Deque<Integer> path, List<List<Integer>> res){
        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i=begin;i<=n;i++){
            path.addLast(i);
            dfs(n, k, i+1, path, res);
            path.removeLast();
        }
    }
}

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();

        int len = candidates.length;
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);

        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, 
    Deque<Integer> path, List<List<Integer>> res) {
        if(target<0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i=begin;i<len;i++){
            path.addLast(candidates[i]);
            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
        }
    }

}

##198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=nums[0];

        for(int i=2;i<=n;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }

        return dp[n];
    }
}

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> word = new HashSet(wordDict);

        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        
        for(int i =1; i<=s.length();i++){
            for(int j = 0;j<i;j++){
                if(dp[j]&&word.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

322. 零钱互换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int max= amount+1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, max);
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j = 0;j<n;j++){
                if(coins[j]<=i)
                    dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
            }
        }

        return dp[amount]>amount?-1:dp[amount];
    }
}

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxans = 1;
        dp[0] = 1;
        for(int i=1;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
            
        }

        return maxans;
    }
}

226. 翻转二叉树

给你一棵二叉树的根节点 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
/**
 * 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 invertTree(TreeNode root) {
        if(root==null)
            return null;

        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

BFS

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
/**
 * 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 invertTree(TreeNode root) {
        if(root==null)
            return null;
        
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();

        queue.add(root);

        while(!queue.isEmpty()){
            TreeNode tmp = queue.poll();
            TreeNode left = tmp.left;
            tmp.left = tmp.right;
            tmp.right = left;

            if(tmp.left!=null){
                queue.add(tmp.left);
            }

            if(tmp.right!=null){
                queue.add(tmp.right);
            }

        }

        return root;
    }
}

199. 二叉树的右视图

给定一个二叉树的 根节点 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
48
49
/**
 * 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) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;


        Queue<TreeNode> nodequeue = new LinkedList<TreeNode>();
        Queue<Integer> depthqueue = new LinkedList<Integer>();
        List<Integer> ans = new ArrayList<Integer>();
        nodequeue.add(root);
        depthqueue.add(0);

        while(!nodequeue.isEmpty()){
            TreeNode node = nodequeue.remove();
            int depth = depthqueue.remove();
            
            if(node!=null){
                max_depth = Math.max(max_depth, depth);
                rightmostValueAtDepth.put(depth, node.val);

                nodequeue.add(node.left);
                nodequeue.add(node.right);
                depthqueue.add(depth + 1);
                depthqueue.add(depth + 1);
            }
        }

        for(int depth=0;depth<=max_depth;depth++){
            ans.add(rightmostValueAtDepth.get(depth));
        }
        return ans;

    }
}

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (v1, v2)->v1[0]-v2[0]);

        int[][] res = new int[intervals.length][2];

        int idx = -1;

        for(int[] interval:intervals){
            if(idx==-1||interval[0]>res[idx][1]){
                res[++idx] = interval;
            }else{
                res[idx][1] = Math.max(interval[1], res[idx][1]);
            }
        }

        return Arrays.copyOf(res, idx+1);
    }
}

228. 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

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 List<String> summaryRanges(int[] nums) {
        LinkedList<String> ans = new LinkedList<>();

        int n = nums.length;
        int i = 0;
        while(i<n){
            int low = i;
            i++;

            while(i<n&&nums[i]-nums[i-1]==1){
                i++;
            }

            int high = i -1;
            StringBuffer tmp = new StringBuffer(Integer.toString(nums[low]));
            if(low<high){
                tmp.append("->");
                tmp.append(Integer.toString(nums[high]));
            }
            ans.add(tmp.toString());
        }

        return ans;
    }
}

101. 对称二叉树

给你一个二叉树的根节点 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
/**
 * 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 isSymmetric(TreeNode root) {
        if(root==null)
            return true;

        return dfs(root.left, root.right);
    }

    private boolean dfs(TreeNode left, TreeNode right){
        if(left==null && right == null)
            return true;
        if(left==null||right==null)
            return false;
        if(left.val!=right.val)
            return false;
        
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }
}
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
/**
 * 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 isSymmetric(TreeNode root) {
        if(root == null || (root.left==null&&root.right==null)){
            return true;
        }

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();

        queue.add(root.left);
        queue.add(root.right);

        while(!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            if(left==null && right == null){
                continue;
            }
            if(left==null||right==null){
                return false;
            }
            if(left.val!=right.val){
                return false;
            }

            queue.add(left.left);
            queue.add(right.right);

            queue.add(left.right);
            queue.add(right.left);
        }

        return true;
    }
}

逆波兰表达式

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、’-‘、’*’ 和 ‘/‘ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

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
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> queue = new LinkedList<>();

        for(String s: tokens){
            if(s.equals("+")){
                Integer val1 = queue.pollFirst();
                Integer val2 = queue.pollFirst();
                Integer val = val2 + val1;
                queue.addFirst(val);
            }else if (s.equals("-")){
                Integer val1 = queue.pollFirst();
                Integer val2 = queue.pollFirst();
                Integer val = val2 - val1;
                queue.addFirst(val);
            }else if (s.equals("/")){
                Integer val1 = queue.pollFirst();
                Integer val2 = queue.pollFirst();
                Integer val = val2 / val1;
                queue.addFirst(val);
            }else if(s.equals("*")){
                Integer val1 = queue.pollFirst();
                Integer val2 = queue.pollFirst();
                Integer val = val2 * val1;
                queue.addFirst(val);
            }else{
                queue.addFirst(Integer.parseInt(s));
            }
        }

        return queue.pollFirst();
    }
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for(String str:strs){
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }

        return new ArrayList<List<String>>(map.values());
    }
}

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(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
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<>();
        for(int num:nums){
            num_set.add(num);
        }

        int max_len = 0;
        for(int num:num_set){
            if(!num_set.contains(num-1)){
                int currentNum = num;
                int cur_len = 1;

                while(num_set.contains(currentNum+1)){
                    currentNum += 1;
                    cur_len += 1;
                }

                max_len = Math.max(cur_len, max_len);
            }
        }

        return max_len;
    }
}

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null)
            return null;
        
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();

        while(cur!=null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;

        while(cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

92. 反转链表||

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

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
52
/**
 * 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 reverseBetween(ListNode head, int left, int right) {
        int count = 0;
        ListNode reverse = new ListNode(-1);
        reverse.next = head;
        ListNode pre = reverse;

        for(int i = 0;i<left-1;i++){
            pre = pre.next;
        }

        ListNode rightNode = pre;
        for(int i = 0;i<right-left+1;i++){
            rightNode = rightNode.next;
        }

        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        pre.next = null;
        rightNode.next = null;

        reverseLinkedList(leftNode);

        pre.next = rightNode;
        leftNode.next = curr;

        return reverse.next;
    }

    private void reverseLinkedList(ListNode head){
        ListNode pre =null;
        ListNode cur = head;

        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}