61. 旋转链表

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

思路：求长度,取模最终移动多少位,重新拼接

/**
 * 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 rotateRight(ListNode head, int k) {
        if(k == 0) return head;
        if(head == null) return head;
        if(head.next == null) return head;
        int c = getCount(head);
        k = k%c;
        if(k == 0)return head;
        Deque<ListNode> stack = new LinkedList();
        ListNode cur = head;
        while(cur.next != null){
            stack.push(cur);
            cur = cur.next;
        }
        //最后一个也放进去
        stack.push(cur);

        int count =0;
        ListNode l = null;
        while(count <= k){
            l = stack.pop();
            count++;
        }
        
        ListNode rst = l.next;
        l.next = null;
        cur.next = head;

        return rst;
    }

    public int getCount(ListNode head){
        int count = 0;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
}

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

思路：做两个链表,然后拼接起来即可

/**
 * 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 partition(ListNode head, int x) {
        ListNode small = new ListNode();
        ListNode samllCur = small;
        ListNode big = new ListNode();
        ListNode bigCur = big;
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                samllCur.next = cur;
                samllCur = samllCur.next;
            }else{
                bigCur.next = cur;
                bigCur = bigCur.next;
            }
            cur = cur.next;
        }
        samllCur.next = big.next;
        bigCur.next = null;
        return small.next;
    }
}

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ；如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

思路：
栈+map

class LRUCache {
    Deque<Integer> stack;
    Map<Integer,Integer> map;
    int length;

    public LRUCache(int capacity) {
         stack = new LinkedList();
         map = new HashMap(capacity);
         this.length = capacity;
    }

    public int get(int key) {
        Integer value =  map.get(key);
        if(value == null) return -1;
        stack.remove(key);
        stack.push(key);
        return value;
    }

    public void put(int key, int value) {
       Integer val = map.get(key);
       if(val !=null){
        map.put(key,value);
        stack.remove(key);
        stack.push(key);
        return;
       }
       stack.push(key);
       map.put(key,value);
       if(map.size() > this.length){
        int tmp = stack.pollLast();
        map.remove(tmp);
       }
    }


}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

104. 二叉树的最大深度

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：

输入：root = [1,null,2]
输出：2

思路：
树比递归

/**
 * 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;
        int leftDep = maxDepth(root.left);
        int rightDep = maxDepth(root.right);
        return Math.max(leftDep,rightDep) +1;
    }
}

100. 相同的树

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

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

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

思路：
树必递归

/**
 * 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;
        if(p!=null && q!= null && p.val == q.val){
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right) && p.val == q.val;
        }else{
            return false;
        }
    }
}

226. 翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：

输入：root = [2,1,3]
输出：[2,3,1]
示例 3：

输入：root = []
输出：[]

思路：
递归

/**
 * 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){
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
            invertTree (root.left);
            invertTree(root.right);
        }

        return root;
    }
}

101. 对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

思路：
树必递归

/**
 * 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) {
       return isSame(root.left,root.right); 
    }

    public boolean isSame(TreeNode left,TreeNode right){
        if(left != null&& right!=null && left.val == right.val && isSame(left.left,right.right) && isSame(left.right,right.left)) return true;
        if(left == null && right == null) return true;
        return false;
    }
}

792. 匹配子序列的单词数

给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数。

字符串的子序列是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是none),而不改变其余字符的相对顺序。

例如, “ace” 是 “abcde” 的子序列。

示例 1:

输入: s = “abcde”, words = [“a”,”bb”,”acd”,”ace”]
输出: 3
解释: 有三个是 s 的子序列的单词: “a”, “acd”, “ace”。
Example 2:

输入: s = “dsahjpjauf”, words = [“ahjpjau”,”ja”,”ahbwzgqnuk”,”tnmlanowax”]
输出: 2

思路：

如果暴力,为了判断是不是子串,大量重复
另外,给的带判断数组,也有大量重复,重复相乘,笛卡尔积得复杂度
思路,每个带判断字符串做一个对象,自己维护指针,减少重复。

注意点, 集合循环删除,要用迭代器。

package h.xd.algo;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Main72 {
    public static void main(String[] args) {
        new Solution72().numMatchingSubseq("abcde",new String[]{"a","bb","acd","ace"});
    }
}

class Solution72 {
    public int numMatchingSubseq(String s, String[] words) {
        char[] scs = s.toCharArray();
        Map<String,SubStr> dic = new HashMap();
        for(int i=0;i<words.length;i++){
            if(dic.get(words[i]) != null){
                dic.get(words[i]).count++;
                continue;
            }
            SubStr ss = new SubStr(words[i]);
            dic.put(words[i], ss);
        }
        int rst = 0;
        for(int i=0;i<scs.length;i++){
            Iterator<Map.Entry<String, SubStr>> iterator = dic.entrySet().iterator();
            while(iterator.hasNext()){
                SubStr tmp = iterator.next().getValue();
                if(tmp.isSub) {
                    rst+=tmp.count;
                    iterator.remove();
                    continue;
                }
                tmp.comeChar(scs[i]);
            }
        }
        for(SubStr tmp:dic.values()){
            if(tmp.isSub) rst+=tmp.count;
        }
        return rst;
    }
}

class SubStr{
    char[] wc;
    int begin;
    int length;
    int count;
    boolean isSub;

    public SubStr(String word){
        this.wc = word.toCharArray();
        this.begin=0;
        this.length =this.wc.length;
        this.isSub = false;
        this.count = 1;
    }

    public void comeChar(char c){
        if(c == this.wc[this.begin]){
            this.begin++;
            if(this.begin == this.length){
                this.isSub= true;
            }
            return;
        }
        return;
    }
}

System.gc() 到底会不会触发 GC？

面试官如果这么问,可以这么回答：

System.gc() 和 Runtime.gc() 只是”建议”JVM 进行垃圾回收,是否执行由 JVM 自己决定。现代 JVM 的 GC 策略通常会忽略这个调用,以优化性能。可以通过 -XX:+DisableExplicitGC 禁用 System.gc(),或者用 -XX:+ExplicitGCInvokesConcurrent 让其触发并发 GC。

听完如果点头,那就稳了！如果他继续追问”那你觉得 System.gc() 什么时候应该用？”

你可以再补充：一般情况下,我们不会手动调用 System.gc(),除非是在一些特定的环境下,比如：

进行性能测试时,确保 GC
影响最小处理大对象,手动释放内存
游戏或者图形渲染应用,控制 GC 运行时机

但大部分情况下,让 JVM 自己决定 GC 时机才是最好的选择。

总结System.gc() 和 Runtime.gc()： ✅ 只是一个“请求”，JVM 可能会忽略
✅ 不保证立刻触发 GC
✅ 在现代 JVM 中通常不需要手动调用
✅ 可以用 -XX:+DisableExplicitGC 禁用