leetcode算法题总结2022.3-2022.5

发表于 更新于 分类于 阅读次数： Disqus：

最小路径和

基本思路：动态规划，每个格子依次计算，计算当前格子的最小路径和，因为每次移动必定是往下或者往右，因此每个格子的路径和必定来自于上边格子或者左边格子的数字加上当前格子的数字
时间复杂度分析：O(mn)，会遍历所有格子，因此复杂度是nm

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
/**
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 *
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 * 解释：因为路径 1→3→1→1→1 的总和最小。
 *
 * 提示：
 *
 *     m == grid.length
 *     n == grid[i].length
 *     1 <= m, n <= 200
 *     0 <= grid[i][j] <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class MinPathSum {
    static int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid.length ;
        int m = grid[0].length;
        // 动态规划
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j== 0) continue;
                if (i == 0) {
                    grid[0][j] += grid[0][j-1];
                    continue;
                }
                if (j == 0) {
                    grid[i][0] += grid[i-1][0];
                    continue;
                }
                if (grid[i-1][j] > grid[i][j-1]) {
                    grid[i][j] += grid[i][j-1];
                } else {
                    grid[i][j] += grid[i-1][j];
                }
            }
        }
        return grid[n-1][m-1];
    }

    public static void main(String[] args) {
        System.out.println(minPathSum(new int[][]{}));
    }
}

排序矩阵查找

基本思路：从右上角开始遍历，左边是比它小的，下边是比它大的，相当于是一个二叉树遍历
时间复杂度分析：O(mn)，会遍历所有格子，因此复杂度是nm

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
/**
 * 给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。
 *
 * 示例:
 *
 * 现有矩阵 matrix 如下：
 *
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 *
 * 给定 target = 5，返回 true。
 *
 * 给定 target = 20，返回 false。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sorted-matrix-search-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class SearchMatrix {
    // 基本思路，从右上角开始遍历，左边是比它小的，下边是比它大的，相当于是一个二叉树遍历
    static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int n = 0;
        int m = matrix[0].length - 1;
        while (true) {
            if (matrix[n][m] == target) return true;
            if (matrix[n][m] > target) m--;
            else n++;
            if (m < 0 || n >= matrix.length) return false;
        }
    }

    public static void main(String[] args) {
        System.out.println(searchMatrix(new int[][]{{}}, 18));
    }
}

合并若干三元组以形成目标三元组

基本思路：根据题设可知，每次合并都会取各个位置更大的那个数，因此如果一个数组中的任一位置存在比目标数更大的数，则这个数组一定不能进行合并；反之，如果一个数组的任一位置存在目标数，且其他各位置的数都比目标数小，则一定能进行合并

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
60
61
62
63
64
65
66
67
/**
 * 三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ，其中 triplets[i] = [ai, bi, ci] 表示第 i 个 三元组 。同时，给你一个整数数组 target = [x, y, z] ，表示你想要得到的 三元组 。
 *
 * 为了得到 target ，你需要对 triplets 执行下面的操作 任意次（可能 零 次）：
 *
 *     选出两个下标（下标 从 0 开始 计数）i 和 j（i != j），并 更新 triplets[j] 为 [max(ai, aj), max(bi, bj), max(ci, cj)] 。
 *         例如，triplets[i] = [2, 5, 3] 且 triplets[j] = [1, 7, 5]，triplets[j] 将会更新为 [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5] 。
 *
 * 如果通过以上操作我们可以使得目标 三元组 target 成为 triplets 的一个 元素 ，则返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
 * 输出：true
 * 解释：执行下述操作：
 * - 选择第一个和最后一个三元组 [[2,5,3],[1,8,4],[1,7,5]] 。更新最后一个三元组为 [max(2,1), max(5,7), max(3,5)] = [2,7,5] 。triplets = [[2,5,3],[1,8,4],[2,7,5]]
 * 目标三元组 [2,7,5] 现在是 triplets 的一个元素。
 *
 * 示例 2：
 *
 * 输入：triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
 * 输出：true
 * 解释：目标三元组 [2,5,8] 已经是 triplets 的一个元素。
 *
 * 示例 3：
 *
 * 输入：triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
 * 输出：true
 * 解释：执行下述操作：
 * - 选择第一个和第三个三元组 [[2,5,3],[2,3,4],[1,2,5],[5,2,3]] 。更新第三个三元组为 [max(2,1), max(5,2), max(3,5)] = [2,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
 * - 选择第三个和第四个三元组 [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。更新第四个三元组为 [max(2,5), max(5,2), max(5,3)] = [5,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]] 。
 * 目标三元组 [5,5,5] 现在是 triplets 的一个元素。
 *
 * 示例 4：
 *
 * 输入：triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
 * 输出：false
 * 解释：无法得到 [3,2,5] ，因为 triplets 不含 2 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-triplets-to-form-target-triplet
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MergeTriplets {
    static boolean mergeTriplets(int[][] triplets, int[] target) {
        if (triplets == null || target == null || triplets.length == 0 || triplets[0].length == 0 || target.length == 0) return false;
        int one = target[0];
        int two = target[1];
        int three = target[2];
        boolean oneJudge = false;
        boolean twoJudge = false;
        boolean threeJudge = false;
        for (int i = 0; i < triplets.length; i++) {
            if (!oneJudge && triplets[i][0] == one && triplets[i][1] <= two && triplets[i][2] <= three) oneJudge = true;
            if (!twoJudge && triplets[i][1] == two && triplets[i][0] <= one && triplets[i][2] <= three) twoJudge = true;
            if (!threeJudge && triplets[i][2] == three && triplets[i][0] <= one && triplets[i][1] <= two) threeJudge = true;
            if (oneJudge && twoJudge && threeJudge) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(mergeTriplets(new int[][]{{2,5,3},{1,8,4},{1,7,5}}, new int[]{2,5,3}));
    }
}

二叉搜索树与双向链表

基本思路：本质上是一个将二叉树按大小输出的问题，使用中序遍历可以实现。同时需要将头尾连接，因此存储头部结点，直到中序遍历结束，将最后的结点指向头部结点。

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
/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *
 * 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}

public class TreeToDoublyList {
    static Node head, pre;
    static Node treeToDoublyList(Node root) {
        if (root == null) return root;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    static void dfs(Node node) {
        // 中序遍历，按大小输出结点
        if (node == null) return;
        dfs(node.left);
        if (head == null) head = node;
        else {
            pre.right = node;
            node.left = pre;
        }
        pre = node;
        dfs(node.right);
    }

}

两个相同字符之间的最长子字符串

基本思路：
1.题设只有小写字母，因此可以用一个容量26的数组来进行存储。
2.按顺序遍历数组，将每个字母出现的位置索引存储在数组中，当找到重复的字母时，将其位置和数组中的索引进行相减，得到的结果和已存储的最大值比较，如果当前结果更大，将最大值替换
3.返回最大值

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * 给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。
 *
 * 子字符串 是字符串中的一个连续字符序列。

 * 示例 1：
 *
 * 输入：s = "aa"
 * 输出：0
 * 解释：最优的子字符串是两个 'a' 之间的空子字符串。
 *
 * 示例 2：
 *
 * 输入：s = "abca"
 * 输出：2
 * 解释：最优的子字符串是 "bc" 。
 *
 * 示例 3：
 *
 * 输入：s = "cbzxy"
 * 输出：-1
 * 解释：s 中不存在出现出现两次的字符，所以返回 -1 。
 *
 * 示例 4：
 *
 * 输入：s = "cabbac"
 * 输出：4
 * 解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。
 *

 * 提示：
 *
 *     1 <= s.length <= 300
 *     s 只含小写英文字母
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-substring-between-two-equal-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxLengthBetweenEqualCharacters {
    // 基本思路：遍历一遍，时间复杂度O(N)，通过map存储已经存在的字符，在遍历时再次发现该字符的话就把两个位置的值相减并和已存储的最大值进行比较
    /*static int maxLengthBetweenEqualCharacters(String s) {
        if (s == null || s.length() == 0) return -1;
        Map<Character, Integer> map = new HashMap<>();
        char[] characters = s.toCharArray();
        int result = 0;
        int temp;
        char ch;
        for (int i = 0; i < characters.length; i++) {
            ch = characters[i];
            if (map.containsKey(ch)) {
                temp = i - map.get(ch);
                if (temp > result) result = temp;
            } else {
                map.put(ch, i);
            }
        }
        return result - 1;
    }*/

    static int maxLengthBetweenEqualCharacters(String s) {
        // 不使用map的方案
        if (s == null || s.length() == 0) return -1;
        int[] alpha = new int[26];//ASCII字符长度
        char[] characters = s.toCharArray();
        int result = -1;
        int temp;
        int ch;
        for (int i = 0; i < characters.length; i++) {
            ch = characters[i] - 97; // a的ascII位置是97
            if (alpha[ch] > 0) {
                temp = i - alpha[ch];
                if (temp > result) result = temp;
            } else {
                alpha[ch] = i + 1; // int数组默认初始化为0，所以需要通过+1和初始0值进行区分
            }
        }
        return result;
    }

}

替换隐藏数字得到的最晚时间

基本思路：由于固定是XX:XX的格式字符串，因此需要处理的无非是四个位置的字符。后两位的字符如果出现’?’，那一定是可以替换为5和9。前两位出现’?’，需要考虑：
1.第一位是’?’，需要看第二位的值，如果大于3，那第一位只能是1，因为不存在24-29点这样的值；如果第二位是1，2，3，那第一位可以是2
2.第二位是’?’，需要看第一位的值，如果是2，那第二位最大是3；如果是第一位是1，那第二位最大可以是9

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
/**
 * 给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。
 *
 * 有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。
 *
 * 替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。
 *
 *
 *
 * 示例 1：
 *
 * 输入：time = "2?:?0"
 * 输出："23:50"
 * 解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。
 *
 * 示例 2：
 *
 * 输入：time = "0?:3?"
 * 输出："09:39"
 *
 * 示例 3：
 *
 * 输入：time = "1?:22"
 * 输出："19:22"
 *
 *
 *
 * 提示：
 *
 *     time 的格式为 hh:mm
 *     题目数据保证你可以由输入的字符串生成有效的时间
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/latest-time-by-replacing-hidden-digits
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaximumTime {
    static String maximumTime(String time) {
        char[] chars = time.toCharArray();
        if (chars[0] == '?') {
            // 直接比较字符大小时就是比较在ASCII码的大小
            if (chars[1] > '3' && chars[1] <= '9') chars[0] = '1';
            else chars[0] = '2';
        }
        if (chars[1] == '?') {
            if (chars[0] == '1' || chars[0] == '0') chars[1] = '9';
            else chars[1] = '3';
        }
        if (chars[3] == '?') chars[3] = '5';
        if (chars[4] == '?') chars[4] = '9';
        return String.valueOf(chars);
    }

    public static void main(String[] args) {
        System.out.println(maximumTime("?4:03"));
    }
}

拆分字符串使唯一子字符串的数目最大

基本思路：需要遍历所有的子字符串可能，用到递归+回溯

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
 * 给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
 *
 * 字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。
 *
 * 注意：子字符串 是字符串中的一个连续字符序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "ababccc"
 * 输出：5
 * 解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，因为其中的 'a' 和 'b' 都出现了不止一次。
 *
 * 示例 2：
 *
 * 输入：s = "aba"
 * 输出：2
 * 解释：一种最大拆分方法为 ['a', 'ba'] 。
 *
 * 示例 3：
 *
 * 输入：s = "aa"
 * 输出：1
 * 解释：无法进一步拆分字符串。
 *
 *
 *
 * 提示：
 *
 *     1 <= s.length <= 16
 *
 *     s 仅包含小写英文字母
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/split-a-string-into-the-max-number-of-unique-substrings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxUniqueSplit {
    int ct = 1;
    int length = 1;

    // aac a
    int maxUniqueSplit(String s) {
        Set<String> set = new HashSet<>(16);
        length = s.length();
        maxUniqueSplit(0, 0, s, set);
        return ct;
    }

    void maxUniqueSplit(int index, int split, String s, Set<String> set) {
        if (ct < split) ct = split;
        for (int i = index; i < length; i++) {
            if (length - i + split < ct) break;// 关键步骤，判断当前切分数加上剩余数组长度是否大于最大切分数，如果不大于，则没有必要进一步切分
            String substring = s.substring(index, i+1);
            if (set.add(substring)) {
                maxUniqueSplit(i + 1, split + 1, s, set);
                set.remove(substring);
            }
        }
    }

    int count=0;
    char[] arr;
    Set<String> lookUp;
    public int maxUniqueSplit_2(String s) {
        arr=s.toCharArray();
        lookUp=new HashSet<>();
        dfs(0,0,arr,s.length());
        return count;
    }

    private void dfs(int begin,int cur_depth,char[] arr,int remain_length){
        if(remain_length==0){
            count=Math.max(cur_depth,count);
            return;
        }
        for(int start=begin,end=begin;end<arr.length;end++){
            int left_length=arr.length-end-1;
            if(cur_depth+1+left_length<=count)
                break;
            String temp=new String(arr,start,end-start+1);
            if(lookUp.contains(temp))
                continue;

            lookUp.add(temp);
            dfs(end+1,cur_depth+1,arr,left_length);
            lookUp.remove(temp);
        }

    }

}

两个链表的第一个公共节点

基本思路：两个链表的长度可能不一，长度分别为m和n。必然有m+n=n+m。
情况一：两个链表相交

链表 headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c=m ，b+c=n。

如果 a=b，则两个指针会同时到达两个链表的第一个公共节点，此时返回两个链表的第一个公共节点；

如果 a≠b，则指针 pA 会遍历完链表 headA，指针 pB 会遍历完链表 headB，两个指针不会同时到达链表的尾节点，然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动，在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a 次之后，两个指针会同时到达两个链表的第一个公共节点，该节点也是两个指针第一次同时指向的节点，此时返回两个链表的第一个公共节点。

情况二：两个链表不相交

链表 headA\textit{headA}headA 和 headB\textit{headB}headB 的长度分别是 mmm 和 nnn。考虑当 m=nm=nm=n 和 m≠nm \ne nm​=n 时，两个指针分别会如何移动：

如果 m=n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 null，此时返回 null；

如果 m≠n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA 移动了 m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 null，此时返回 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
/**
 * 输入两个链表，找出它们的第一个公共节点。
 *
 * 如下面的两个链表：
 *
 * 在节点 c1 开始相交。
 *
 *
 *
 * 示例 1：
 *
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Reference of the node with value = 8
 * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 *
 *
 *
 * 示例 2：
 *
 * 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
 * 输出：Reference of the node with value = 2
 * 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
 *
 *
 *
 * 示例 3：
 *
 * 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
 * 输出：null
 * 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
 * 解释：这两个链表不相交，因此返回 null。
 *
 *
 *
 * 注意：
 *
 *     如果两个链表没有交点，返回 null.
 *     在返回结果后，两个链表仍须保持原有的结构。
 *     可假定整个链表结构中没有循环。
 *     程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 *     本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class GetIntersectionNode {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode head1 = headA;
        ListNode head2 = headB;
        while (head1 != head2) {
            head1 = head1 != null ? head1.next:headB;
            head2 = head2 != null ? head2.next:headA;
        }
        return head1;
    }
}

修改后的最大二进制字符串

基本思路：根据题设可知，最佳方案应当是将所有的0都移到一起，从而将00变成10，这样将是最大的可能，因此我们可以将第一个0右边的所有1都移到最右边，从而得到两边是1，中间是0的结构，然后再将中间的00依次转成10即可

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * 给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：
 *
 *     操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。
 *         比方说， "00010" -> "10010"
 *     操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。
 *         比方说， "00010" -> "00001"
 *
 * 请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：binary = "000110"
 * 输出："111011"
 * 解释：一个可行的转换为：
 * "000110" -> "000101"
 * "000101" -> "100101"
 * "100101" -> "110101"
 * "110101" -> "110011"
 * "110011" -> "111011"
 *
 * 示例 2：
 *
 * 输入：binary = "01"
 * 输出："01"
 * 解释："01" 没办法进行任何转换。
 *
 *
 *
 * 提示：
 *
 *     1 <= binary.length <= 105
 *     binary 仅包含 '0' 和 '1' 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-binary-string-after-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaximumBinaryString {
    /**
     * 第一步 从左往右，找到第一个0的位置，记录为zeroIndex
     * 第二步 从zeroIndex往右，找到1之后记录为oneIndex
     * 第三步 oneIndx>0的情况下，指针从右往左找0，找到之后记录为reverseZeroIndex
     * 第四步 将oneIndex和reverseZeroIndex所在的字符互换
     * 第五步 将oneIndex和reverseZeroIndex重置为-1
     * 第六步 指针重新从原来oneIndex的位置向右移动，重复二到五步
     * @param binary
     * @return
     */
    String maximumBinaryString(String binary) {
        if (binary == null || binary.length() <= 1) return binary;
        char[] chars = binary.toCharArray();
        int index;
        int len = chars.length;
        for (int i = 0; i < len;) {
            // 找到第一个0的位置
            if (chars[i++] == '0') {
                // 将第一个0下标+1的位置记录下来
                index = i;
                // i从第一个0的右边开始从左到右遍历，j从右到左遍历
                for (int j = len - 1; j >= i;) {
                    if (chars[i] == '1') {
                        // 将第一个0右边的1全部移到最右侧
                        if (chars[j] == '0') {
                            chars[i] = '0';
                            chars[j] = '1';
                        } else j--;
                    } else i++;
                    // 将左边的00变成10
                    if (chars[index] == '0') {
                        chars[index - 1] = '1';
                        index++;
                    }
                }
                break;
            }
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        MaximumBinaryString maximumBinaryString = new MaximumBinaryString();
        System.out.println(maximumBinaryString.maximumBinaryString("00010"));
    }
}

检查两个字符串是否几乎相等

基本思路：维护一个数组arr，随后对word1和word2两个字符串进行遍历，word1中出现的字符在arr中存储ascii值加1，word2种出现的字符在arr中存储ascii值减1，最后遍历arr，出现绝对值大于3的说明不符合要求。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * 如果两个字符串 word1 和 word2 中从 'a' 到 'z' 每一个字母出现频率之差都 不超过 3 ，那么我们称这两个字符串 word1 和 word2 几乎相等 。
 *
 * 给你两个长度都为 n 的字符串 word1 和 word2 ，如果 word1 和 word2 几乎相等 ，请你返回 true ，否则返回 false 。
 *
 * 一个字母 x 的出现 频率 指的是它在字符串中出现的次数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：word1 = "aaaa", word2 = "bccb"
 * 输出：false
 * 解释：字符串 "aaaa" 中有 4 个 'a' ，但是 "bccb" 中有 0 个 'a' 。
 * 两者之差为 4 ，大于上限 3 。
 *
 * 示例 2：
 *
 * 输入：word1 = "abcdeef", word2 = "abaaacc"
 * 输出：true
 * 解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
 * - 'a' 在 word1 中出现了 1 次，在 word2 中出现了 4 次，差为 3 。
 * - 'b' 在 word1 中出现了 1 次，在 word2 中出现了 1 次，差为 0 。
 * - 'c' 在 word1 中出现了 1 次，在 word2 中出现了 2 次，差为 1 。
 * - 'd' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
 * - 'e' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
 * - 'f' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
 *
 * 示例 3：
 *
 * 输入：word1 = "cccddabba", word2 = "babababab"
 * 输出：true
 * 解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
 * - 'a' 在 word1 中出现了 2 次，在 word2 中出现了 4 次，差为 2 。
 * - 'b' 在 word1 中出现了 2 次，在 word2 中出现了 5 次，差为 3 。
 * - 'c' 在 word1 中出现了 3 次，在 word2 中出现了 0 次，差为 3 。
 * - 'd' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
 *
 *
 *
 * 提示：
 *
 *     n == word1.length == word2.length
 *     1 <= n <= 100
 *     word1 和 word2 都只包含小写英文字母。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/check-whether-two-strings-are-almost-equivalent
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CheckAlmostEquivalent {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        int[] chArr1 = new int[26];
        int len = chars1.length;
        for (int i = 0; i < len; i++) {
            chArr1[chars1[i]-97]++;
            chArr1[chars2[i]-97]--;
        }
        for (int i = 0; i < 26; i++) {
            if (Math.abs(chArr1[i]) > 3) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        CheckAlmostEquivalent checkAlmostEquivalent = new CheckAlmostEquivalent();
        System.out.println(checkAlmostEquivalent.checkAlmostEquivalent("dfgcbehcifihghedhffbggdcebbbghigfhddhiigcgfeiih",
                "cdcgbeeceifbgchhfiffhifghiebfchbcbfhggchfbbhddb"
        ));
    }
}

转换字符串的最少操作次数

基本思路：贪心算法，每次遇到x时，选中包含X以及之后的三个字符，进行转换；换句话说，相当于每次碰到X，将计数器+1，同时遍历数组的索引+3

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
60
61
/**
 * 给你一个字符串 s ，由 n 个字符组成，每个字符不是 'X' 就是 'O' 。
 *
 * 一次 操作 定义为从 s 中选出 三个连续字符 并将选中的每个字符都转换为 'O' 。注意，如果字符已经是 'O' ，只需要保持 不变 。
 *
 * 返回将 s 中所有字符均转换为 'O' 需要执行的 最少 操作次数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "XXX"
 * 输出：1
 * 解释：XXX -> OOO
 * 一次操作，选中全部 3 个字符，并将它们转换为 'O' 。
 *
 * 示例 2：
 *
 * 输入：s = "XXOX"
 * 输出：2
 * 解释：XXOX -> OOOX -> OOOO
 * 第一次操作，选择前 3 个字符，并将这些字符转换为 'O' 。
 * 然后，选中后 3 个字符，并执行转换。最终得到的字符串全由字符 'O' 组成。
 *
 * 示例 3：
 *
 * 输入：s = "OOOO"
 * 输出：0
 * 解释：s 中不存在需要转换的 'X' 。
 *
 *
 *
 * 提示：
 *
 *     3 <= s.length <= 1000
 *     s[i] 为 'X' 或 'O'
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-moves-to-convert-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MinimumMoves {
    public int minimumMoves(String s) {
        char[] chars = s.toCharArray();
        int result = 0;
        for (int i = 0; i < chars.length;) {
            if (chars[i] == 'X') {
                result++;
                i = i + 3;
            }
            else i++;
        }
        
        return result;
    }

    public static void main(String[] args) {
        MinimumMoves minimumMoves = new MinimumMoves();
        System.out.println(minimumMoves.minimumMoves("XXXX"));
    }
}

有序矩阵中第 K 小的元素

基本思路：由于是有序矩阵，可以利用该特性进行二分查找，具体做法是，每次找到中间的位置时，比这个位置小的数字只可能是左上的方向，往左上方向查找比当前位置小的数字的个数，如果个数比k小，则需要往右下方向二分，如果个数比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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
 * 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
 *
 * 你必须找到一个内存复杂度优于 O(n2) 的解决方案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
 * 输出：13
 * 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
 *
 * 示例 2：
 *
 * 输入：matrix = [[-5]], k = 1
 * 输出：-5
 *
 *
 *
 * 提示：
 *
 *     n == matrix.length
 *     n == matrix[i].length
 *     1 <= n <= 300
 *     -10^9 <= matrix[i][j] <= 10^9
 *     题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
 *     1 <= k <= n^2
 *
 *
 *
 * 进阶：
 *
 *     你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题?
 *     你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class KthSmallest {
    public int kthSmallest(int[][] matrix, int k) {
        int len = matrix.length;
        int[] numArr = new int[len*len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                numArr[i*len + j] = matrix[i][j];
            }
        }
        Arrays.sort(numArr);
        return numArr[k-1];
    }

    // 二分法
    public int kthSmallest_v2(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(int[][] matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }


    public static void main(String[] args) {
        KthSmallest kthSmallest = new KthSmallest();
        System.out.println(kthSmallest.kthSmallest_v2(new int[][]{{1,2,2},{2,2,7},{3,4,8}},5));
    }
}