月度归档： 2022年6月

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

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

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

Example 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

• 数中节点数在 [1, 5000] 范围内
• 1 <= Node.val <= 107
• root 是二叉搜索树
• 1 <= val <= 107

根据二叉搜索树的左小右大的特性【递归&遍历树】

递归

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
    }
}

应该没啥特殊的，二叉搜索树的特性

左子节点  <   根节点   <  右子节点

所以照着这个写就行了

也可以改递归为遍历的写法，毕竟 递归和遍历循环是可以相互转化的

遍历

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root !=null){
            if (root.val == val) return root;
            root = root.val > val? root.left : root.right;
        }
        return root;
    }
}

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：

输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：

• 0 <= len(big) <= 1000
• 0 <= len(smalls[i]) <= 1000
• smalls的总字符数不会超过 100000。
• 你可以认为smalls中没有重复字符串。
• 所有出现的字符均为英文小写字母。

smalls数组构建字典树

1. 把smalls数组构建字典树
2. 把big数组从第i位开始到结尾的子序列拿到字典树上匹配，i从0开始分别求解，直到结束
3. 因为匹配的时候需要知道当前字典树上字符串结束节点是哪个字符的，所以字典树的节点需要额外记录下各自归属与smalls数组中对应字符串的下标
4. 在树上匹配的过程中，但凡匹配到了一个结束字符，就在结果数组的对应这个字符串下标的子数组中插入一个当前匹配的big字符串子序列的开始下标

代码

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie();
        trie.smallsCount = smalls.length;
        trie.insert(smalls);
        return trie.search(big);
    }


    public class Trie{

        Node tree;
        int smallsCount = 0;

        public Trie(){
            tree = new Node();
        }

        void insert(String[] strArr){
            for (int idx = 0; idx < strArr.length; idx++) {
                Node cur = tree;
                String str = strArr[idx];
                int i = -1;
                while (++i < str.length()){
                    int child = str.charAt(i)-'a';
                    if (cur.children[child] == null){
                        cur.children[child] = new Node();
                    }
                    cur = cur.children[child];
                }
                cur.flag = true;
                cur.smallIndex = idx;
            }
        }

        int[][] search(String str){
            int[][] res = new int[smallsCount][];
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < smallsCount; i++) {
                list.add(new ArrayList<>());
            }

            for (int i = 0; i < str.length(); i++) {
                String subStr = str.substring(i);
                Node cur = tree;
                int idx = -1;
                while (cur != null && ++idx < subStr.length()){
                    char c = subStr.charAt(idx);
                    if (cur.children[c-'a'] != null){
                        cur = cur.children[c-'a'];
                        if (cur.flag){
                            list.get(cur.smallIndex).add(i);
                        }
                    }else{
                        break;
                    }
                }
            }
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i).stream().mapToInt(Integer::intValue).toArray();
            }
            return res;
        }




        class Node{
            boolean flag = false;
            Node[] children;
            int smallIndex = -1;
            public Node(){
                children = new Node[26];
            }
        }
    }
}

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

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

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 升序 排列

简单题简单做，双指针，后值往前覆盖

拿示例数据比划比划，其实这题还是比较有意思的

1. A、B两个指针，A在前B在后
2. 由于数组本身的有序递增性，所以B指针的指向必然是大于等于A的此时，所以需要移动B指针往后，找到比A指针指向的值大的数值，不能等于
3. 接下来把找到的大于A指针指向的值赋值到A指针的下一个位置，A指针移动到这个新的位置，即往后移动一位
4. 接下来继续这个循环比较A、B指针所指向的值
5. 终止条件：B指针已经走到了数组结尾
6. 返回结果：此时A指针所指向的值为所需结果的结尾指针，那么长度就是A指针的数值+1
7. 特殊情况: 当数组长度小于2的时候，可能是0，也可能是1，数组不用修改，直接返回数组长度即可（0或者1）

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 2){
            return nums.length;
        }
        int cur1 = 0;
        int cur2 = 1;
        while (cur2 < nums.length){
            if (nums[cur1] >= nums[cur2]){
                cur2++;
                continue;
            }
            cur1++;
            nums[cur1] = nums[cur2];
        }
        return cur1 + 1;
    }
}

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

遍历修改指针

修改指针

操作简单

1. 把当前节点的next指向之前遍历的节点pre，这是核心
2. 因为进行了上一步操作之后下一个节点就找不到了，所以需要一个变量暂存一下修改之前的next指向
3. 同时pre指向跟随遍历窗口移动到当前节点
4. 同时需要把当前移动到原链表的下一个节点，也就是步骤(2)中记下的那个
5. 到结束时遍历到原链表的结尾null节点，此时pre指向为原链表的结尾非空那个节点，也就是翻转后的头结点

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (null == head || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：

数组长度为 5 

数组的数取值为 [0, 13] .

简单统计遍历替代处理

简单、思路比较清晰

1. 建一个int[] arr = new int[14];统计次数
2. 遍历arr数组，从下标arr[1]开始，arr[0]作为特殊情况暂时留着后面有用
3. 先遍历找到统计次数不是1的下标，表示顺子可能开始的地方，当然也可能不是从这开始的，后面会说，并开始记录连续区间的长度count
4. 遇到的最基本的情况当前数字统计出现了1次，连续区间长度count加1
5. 如果某个数字出现了超过1次，必然不能组成长度为5的顺子，发牌员总共就给了5张牌
6. 如果遇到了某个数字出现次数为0，表示顺子断开了，从原来的arr[0]位置，拿一张通配牌王来顶一下
7. 如果王不够了,已经无计可施了，则直接判断此时的连续区间长度是否达到了5
8. 如果已经遍历结束了，看下已经统计到的连续区间的长度count是否为5，如果不为5的话再看看有没有多余的通配牌王，可以拿来放在当前连续区间的前面，也就是上面的第3条说的，连续区间的开始位置可能不是匹配到的位置，可能在这个位置之前拿王来抵用
9. 当然你也可能摸了5张王，而连续区间长度count为0，而arr[0] = 5,那你就是天选之人 （邱森旺） 了
10. 综上最终判断其实是(count + arr[0]) == 5

代码

class Solution {
    public boolean isStraight(int[] nums) {
        int[] arr = new int[14];
        for (int num : nums) {
            arr[num]++;
        }
        int idx = 0;
        //从1开始 可匹配任意的 0 先不管
        while (++idx < arr.length && arr[idx]==0){}
        idx--;
        int count = 0;
        while (++idx < arr.length){
            if (arr[idx]>1){
                //如果有一个数字出现的次数大于1了，则必然不能
                return false;
            }
            if (arr[idx]==0){
                if (arr[0]>0){
                    //拿 通配牌  `王` 来顶一个
                    count++;
                    arr[0]--;
                }else{
                    // `王` 也不够顶了
                    return count==5;
                }
            }else{
                //这里是等于1的情况
                count++;
            }
        }
        //可能有剩余的`王` + 已知的连续个数合起来看看能不能凑齐五个
        return (count+arr[0]) == 5;
    }
}

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

双指针合并，不如找两串珠子自己比划比划

这个问题之前给人家形象的比喻讲解过。

1. 你拿两串珠子，分别按照题意标上有序递增的数字
2. 另外你再拿一根线，把这两串珠子合并成一串，这时候你会怎么做呢？
3. 当然是两个原串头上挑小的串起来呀！哪个小串哪个，另外一串没有了就整个串上就完了

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}

如果本题能够很好理解了不妨再去试试23. 合并K个升序链表
题解JAVA 分治归并 其实挺简单的

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

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

JAVA 分治归并 其实挺简单的

1. 对于K个链表，可以两两合并（有点归并排序的意思）
2. 一次合并完了之后此时变成K/2个链表了，对剩下的链表继续两两合并
3. 最终全都合并到了一个链表里
4. 至于两个链表的合并过程，直接参考剑指Offer25题，比较简单算链表基本题了吧，我之前写的题解双指针合并，不如找两串珠子自己比划比划
5. 至于如何选择两两的过程可以简单设计下

//对应为k个链表在入参数组中的下标
1 [0,1],[2,3],[4,5],[6,7],[8]
2 [0,2],[4,6],[8]
4 [0,4],[8]
8 [0,8]

- 第一次 `[0,1],[2,3],[4,5],[6,7]`互相合并，结果留在第一个链表位置， `[8]`单独拉下了没关系先留着
- 第二次 `[0,2],[4,6]` 互相合并，结果存在0 , 4 位置，8继续留着，`[8]`没关系
- 第三次 再次合并`[0,4]`，`[8]`继续留着
- 最后一次合并`[0,8]`结束收工

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 1){
            return lists[0];
        }
        if (lists.length == 0){
            return null;
        }
        int dis = 1;
        while (dis < lists.length){
            //1 [0,1],[2,3],[4,5],[6,7],[8]
            //2 [0,2],[4,6],[8]
            //4 [0,4],[8]
            //8 [0,8]
            for (int i = 0; i + dis < lists.length; i += dis*2) {
                //合并两个有序链表  剑指Offer25题
                lists[i] = mergeTwoLists(lists[i],lists[i+dis]);
                lists[i+dis] = null;
            }
            dis *=2;
        }
        return lists[0];
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}