Leetcode HOT面试题目

mengnankkzhou2025-05-282025-07-15

面试一轮

146. LRU 缓存

linkedHashMap

请你设计并实现一个满足 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) 的平均时间复杂度运行。

一看到是存储键值对数据，那我们可以使用map集合来做，然后返现需要插入xud

LinkedHashMap而其内部是靠建立一个双向链表 来维护这个顺序的，在每次插入、删除后，都会调用一个函数来进行双向链表的维护，准确的来说，是有三个函数来做这件事，这三个函数都统称为 回调函数 ，这三个函数分别是：

void afterNodeAccess(Node p) { }
其作用就是在访问元素之后，将该元素放到双向链表的尾巴处(所以这个函数只有在按照读取的顺序的时候才会执行)，之所以提这个，是建议大家去看看，如何优美的实现在双向链表中将指定元素放入链尾！
void afterNodeRemoval(Node p) { }
其作用就是在删除元素之后，将元素从双向链表中删除，还是非常建议大家去看看这个函数的，很优美的方式在双向链表中删除节点！
void afterNodeInsertion(boolean evict) { }
这个才是我们题目中会用到的，在插入新元素之后，需要回调函数判断是否需要移除一直不用的某些元素！

所以我们直接继承linkedhashmap来解决这个问题

class LRUCache extends LinkedHashMap<Integer,Integer>{
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity,0.75F,true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key,-1);
    }

    public void put(int key, int value) {
        super.put(key,value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
        return size()>capacity;
    }
}

直接返回即可了

206. 反转链表

单链表的头节点 head ，请你反转链表，并返回反转后的链表。

那我们就一直交换他们的指针应该就可以了，从尾部交换到头

class Solution206A {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

A.pre->cur

A.cur->cur.next

A.cur.next = pre

然后用头插法依次把节点 1,2,3 插到这个新链表的头部

1->2->3

2.next->1

2.pre->2

2.cur->3

3->2->1

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution{
    public int findKthLargest(int[] nums,int k){
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

直接排序，返回倒数第k个就完事

15. 三数之和

双指针

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

class Solution15A{
    public List<List<Integer>> threeSum(int[] nums){
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n  = nums.length;
        for (int i =0;i<n-2;i++){
            int x = nums[i];
            if (i>0&&x==nums[i-1]) continue;//跳过重复数组
            if (x+nums[i+1]+nums[i+2]>0) break;//没负数就别看了
            if (x+nums[n-2]+nums[n-1]<0) continue;//每个正数也不看了
            int j = i+1;
            int k  = n-1;
            while (j<k){
                int s= x+nums[j]+nums[k];
                if (s>0){
                    k--;
                }else if (s<0){
                    j++;
                }else {
                    ans.add(List.of(x, nums[j], nums[k]));
                    for (j++;j<k&&nums[j]==nums[j-1];j++);//去重
                    for (k--;k>j&&nums[k]==nums[k+1];k--);//去重


                }
            }
        }
        return ans;
    }
}

一个进行优化和提前去观察的双指针方法，提前看最大的能不能实现，还有最小的情况能不能符合.

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

class Solution25A{
    public ListNode reverseKGroup(ListNode head, int k){
        int n =0;
        for (ListNode cur = head;cur!=null;cur =cur.next){
            n++;//计数器
        }
        ListNode dummy = new ListNode(0,head),preHead = dummy;
        ListNode pre = null,cur = head;
        for (;n>=k;n-=k){//重复n-k次
            for (int i = 0;i<k;++i){
                ListNode  next = cur.next;
                cur.next = pre;
                pre =cur;
                cur  = next;
            }
            ListNode tail = preHead.next;//反转区间的结尾
            tail.next = cur;//下个区间
            preHead.next = pre;//区间的新head
            preHead = tail;//到达结尾进行下一个
        }
        return dummy.next;
    }
}

53. 最大子数组和

分组循环

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

class Solution53A{
    public int maxSubArray(int[] nums){
        int ans = nums[0];
        int sum = 0;
        for (int x:nums){
            if (sum>0){
                sum +=x;
            }else {
                sum = x;
            }
            ans = Math.max(sum,ans);
        }
        return ans;
    }
}

很简单的去解决，如果和为正数的话，就继续去加数。不是的话，就从当前这个数开始重新计算

也有点分组循环的意思了哈哈

手撕快速排序

快速排序每一次都排定一个元素（这个元素呆在了它最终应该呆的位置），然后递归地去排它左边的部分和右边的部分，依次进行下去，直到数组有序；

class Solution912{
    private static final int INSERTION_SORT_THRESHOLD = 7;
    private static final Random RANDOM  = new Random();

    public int[] sortArray(int[] nums){
        int len  = nums.length;
        quickSort(nums,0,len-1);
        return nums;
    }
    private void quickSort(int[] nums,int left,int right){
        if (right-left<=INSERTION_SORT_THRESHOLD){
            insertSort(nums,left,right);
            return;
        }
        int pIndex = partition(nums,left,right);
        quickSort(nums,left,pIndex-1);
        quickSort(nums,pIndex+1,right);
    }
    private void insertSort(int[] nums,int left,int right){
        for (int i = left+1;i<=right;i++){
            int tmp = nums[i];
            int j = i;
            while (j>left&&nums[j-1]>tmp){
                nums[j] = nums[j-1];
                j--;
            }
            nums[j] = tmp;

        }
    }
    private int partition(int[] nums, int left, int right){
        int randomIndex = left+RANDOM.nextInt(right-left+1);
        swap(nums,randomIndex,left);

        int pivot = nums[left];
        int lt = left+1;
        int gt = right;
        while (true) {
            while (lt <= right && nums[lt] < pivot) {
                lt++;
            }

            while (gt > left && nums[gt] > pivot) {
                gt--;
            }

            if (lt >= gt) {
                break;
            }

            // 细节：相等的元素通过交换，等概率分到数组的两边
            swap(nums, lt, gt);
            lt++;
            gt--;
        }
        swap(nums, left, gt);
        return gt;

    }
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
    
}

有点难了😓

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2; // 注：如果都为空则返回空
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

空的话就返回另一个的链表

如果l1的值小于l2的话，递归调用的链表接l1之后。反之一样

然后返回当前节点

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution5A{
    public String longestPalindrome(String s){
        String res = "";
        for (int i =0;i<s.length();i++){
            String s1 = expend(s,i,i+1);
            String s2 = expend(s,i,i);
            res = res.length()>s1.length()?res:s1;
            res = res.length()>s2.length()?res:s2;
        }
        return res;
    }
    private String expend(String s,int l,int r){
        while (l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l+1,r);
    }
}

expend返回的是上一次合法回文的范围。然后慢慢扩大范围，s1为偶数回文

s2为奇数回文

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

class Solution102A{
    public List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue   = new ArrayDeque<>();
        if (root!=null){
            queue.add(root);
        }
        while (!queue.isEmpty()){
            int n = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i=0;i<n;i++){
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left!=null){
                    queue.add(node.left);
                }
                if (node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

level为当前的层数，n为当前层数的所有节点数

然后使用bfs进步遍历，不为空，就加入队列遍历

1. 两数之和

hashmap

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

class Solution1A{
    public int[] twoSum(int[] nums,int target){
        Map<Integer,Integer> map  = new HashMap<>();
        for (int i=0;i<nums.length;i++){
            if (map.containsKey(target-nums[i])){
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

使用hash表解决，在map里有target-nums[i]的数，就新建数组

然后放入nums[i]，没有就扔出异常

33. 搜索旋转排序数组

二分查找

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution33A{
    private boolean check(int[] nums, int target, int i){
        int x = nums[i];
        int end = nums[nums.length-1];
        if (x>end){
            return target>end&&x>=target;
        }
        return target>end||x>=target;
    }
    public int search(int[] nums, int target){
        int left = -1;
        int right = nums.length-1;
        while (left+1<right){
            int mid = (left+right)>>>1;
            if (check(nums,target,mid)){
                right = mid;
            }else{
                left = mid;
            }
        }
        return nums[right]==target?right:-1;
    }
}

使用二分查找

把某个数 x 与最后一个数 nums[n−1] 比大小

如果x>nums[n-1]的话

nums一定被旋转分为左右两个递增的，就是前面的一段移动到后面来了

然后前面的大于后面的

x还在第一段

反之，x<=nums[n-1]就说明x在第二段

或者他就是递增数组

根据这个写我们的check函数，来确定x的范围，好让我们进行二分查找

private boolean check(int[] nums, int target, int i){
        int x = nums[i];
        int end = nums[nums.length-1];
        if (x>end){
            return target>end&&x>=target;
        }
        return target>end||x>=target;
    }

200. 岛屿数量

bfs

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

class Solution200{
    public int numIslands(char[][] grid){
        int ans = 0;
        for (int i =0;i<grid.length;i++){
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j]=='1'){
                    dfs(grid,i,j);
                    ans++;
                }
            }
        }
        return ans;
    }
    private void dfs(char[][] grid,int i,int j){
        if (i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]!='1'){
            return;
        }
        grid[i][j]='2';
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
    }
}

就是遍历这整个矩阵，然后如果是1就count++;

然后把通过的改为2，防止重复遍历

46. 全排列

回溯法

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

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] onPath = new boolean[nums.length];
        dfs(nums, path, onPath, ans);
        return ans;
    }

    private void dfs(int[] nums, List<Integer> path, boolean[] onPath, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (onPath[i]) continue;
            path.add(nums[i]);
            onPath[i] = true;
            dfs(nums, path, onPath, ans);
            path.remove(path.size() - 1); // 回溯
            onPath[i] = false;
        }
    }
}

onPath用来放这个j有没有使用

path为路径，就是数组，长度全了的话，就给他加入到答案中

然后遍历，进入路径，设为匹配，dfs后，再恢复

88. 合并两个有序数组

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

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

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

class Solution{
    public void merge(int[] nums1, int m, int[] nums2, int n){
        int p1 = m-1;
        int p2 = n-1;
        int p = m+n-1;
        while (p2>=0){
            if (p1>=0&&nums1[p1]>nums2[p2]){
                nums1[p--] = nums1[p1--];
            }
            else {
                nums1[p--] = nums2[p2--];
            }
        }
    }
}

简单的交换，谁大谁在后面

20. 有效的括号

栈

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

有效字符串需满足：

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

class Solution20{
    public boolean isValid(String s){
        if (s.isEmpty()){
            return true;
        }
        Stack<Character> stack = new Stack<Character>();
        for (char c :s.toCharArray()){
            if (c=='(') stack.push(')');
            else if (c=='{') stack.push('}');
            else if (c=='[') stack.push(']');
            else if (stack.isEmpty()||c!=stack.pop()){
                return false;
            }

        }
        return stack.isEmpty();
    }

}

使用栈的思想，有左的话，就把右边的入栈

或者空了，或者是所不对应的时候，返回fasle

然后最后看是不是空

121. 买卖股票的最佳时机

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

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

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

class Solution121{
    public int maxProfit(int[] prices){
        int cost = Integer.MAX_VALUE,profit = 0;
        for (int p:prices){
            cost = Math.min(cost,p);
            profit = Math.max(profit,p-cost);
        }
        return profit;
    }
}

easy题目

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

class Solution103A{
    public List<List<Integer>> zigzagLevelOrder(TreeNode root){
        if (root==null) return List.of();
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()){
            int n = q.size();
            List<Integer> vals = new ArrayList<>(n);
            while (n-->0){
                TreeNode node = q.poll();
                vals.add(node.val);
                if (node.left!=null) q.add(node.left);
                if (node.right!=null) q.add(node.right);
            }
            if (ans.size()%2>0) Collections.reverse(vals);
            ans.add(vals);
        }
        return ans;

    }
}

一看到这种层序遍历，我们首先想到使用bfs，然后层序遍历，先遍历left,然后遍历right

之前的代码跟层序遍历差不多，只不过，他要形成锯齿状，奇数层就要反转。即就是下面的代码

刚刚前面判断写的有点麻烦了

class Solution103A{
    public List<List<Integer>> zigzagLevelOrder(TreeNode root){
        
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        
        if(root!=null) q.add(root);
        while (!q.isEmpty()){
            int n = q.size();
            List<Integer> vals = new ArrayList<>(n);
            while (n-->0){
                TreeNode node = q.poll();
                vals.add(node.val);
                if (node.left!=null) q.add(node.left);
                if (node.right!=null) q.add(node.right);
            }
            if (ans.size()%2>0) Collections.reverse(vals);
            ans.add(vals);
        }
        return ans;

    }
}

更正一下

联系102二叉树的层序遍历

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

class Solution236{
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root==null||root==q||root==p) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left==null) return right;
        if (right==null) return left;
        return root;
    }
}

就是有啥就返回啥，没有就返回另一半，都没有就返回root

141. 环形链表

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

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

如果链表中存在环 ，则返回 true 。否则，返回 false 。

class Solution141{
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

这个环形，也就是说是快慢指针碰到一块了就是一个环

92. 反转链表 II

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

class Solution92{
    public ListNode reverseBetween(ListNode head, int left, int right){
        ListNode dummy = new ListNode(0,head);
        ListNode p0 = dummy;
        for (int i=0;i<left-1;i++){
            p0= p0.next;
        }
        ListNode pre = null;
        ListNode cur = p0.next;
        for (int i = 0;i<right-left+1;i++){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur= next;
        }
        p0.next.next = cur;
        p0.next = pre;
        return dummy.next;
    }
}

类似 leetcode25,206

反转需要注意的

ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur= next;

反转后在原来的链表上看，pre指向反转一段的末尾，

cur指向反转一段后续的下一个节点

然后修改

1
2
3

p0.next.next = cur;
        p0.next = pre;
        return dummy.next;

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

class Solution54A{
    public List<Integer> spiralOrder(int[][] matrix){
        List<Integer> res = new ArrayList<>();
        if (matrix.length==0) return res;
        int l =0,r = matrix[0].length-1;
        int t = 0,b = matrix.length-1;

        while (l<=r&&t<=b){
            for (int i = l;i<=r;i++) res.add(matrix[t][i]);
            t++;
            if (t>b) break;

            for (int i =t;i<=b;i++) res.add(matrix[i][r]);
            r--;
            if (l>r) break;

            for (int i=r;i>=l;i--) res.add(matrix[b][i]);
            b--;
            if (t>b) break;

            for (int i =b;i>=t;i--) res.add(matrix[i][l]);
            l++;
            if (l>r) break;
        }
        return res;
    }
}

就是一个遍历的问题，从左到右，从上到下，然后从右到左，再从下到上

然后循环，主要是边界也要跟着移动

300. 最长递增子序列

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

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

class Solution300{
    public int lengthOfLIS(int[] nums){
        int[] res = new int[nums.length];
        int k = 0;
        res[0] = nums[0];
        for (int i  =1;i<nums.length;i++){
            if (nums[i]>res[k]){
                res[++k] = nums[i];
                continue;
            }
            for (int j = 0;j<=k;j++){
                if (res[j]>=nums[i]){
                    res[j] =nums[i];
                    break;
                }
            }
        }
        return k+1;
    }
}

先遍历出来个递增的数组

如果不是的话，从0-k中找一个别的数，来贪心替换

最后k+1就是有效的长度

23. 合并 K 个升序链表

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

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

class Solution23{
    public ListNode mergeKLists(ListNode[] lists){
        int m =  lists.length;
        if (m==0){
            return null;
        }
        for (int step = 1;step<m;step*=2){
            for (int i =0;i<m-step;i+=step*2){
                lists[i] =  meryTwoLists(lists[i],lists[i+step]);
            }
        }
        return lists[0];
    }
    private ListNode meryTwoLists(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (list1!=null&&list2!=null){
            if (list1.val<list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1!=null?list1:list2;
        return dummy.next;
    }
}

下面的函数时按大小来合并链表的

每次将间隔为 step 的链表合并成一个新链表

然后要满足所有，可以合并一道二，二到四，四道八这样一点一点的递归下去

143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

1	L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

1	L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution143{
    public ListNode middleNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null&&fast.next.next!=null){
            slow =slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    public void mergeList(ListNode l1, ListNode l2){
        ListNode l1_temp;
        ListNode l2_temp;
        while (l1!=null&&l2!=null){
            l1_temp = l1.next;
            l2_temp = l2.next;

            l1.next = l2;
            l1 = l1_temp;

            l2.next = l1;
            l2 = l2_temp;
        }
    }
    public void reorderList(ListNode head){
        if (head==null){
            return;
        }
        ListNode mid = middleNode(head);
        ListNode l1 =head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverseList(l2);
        mergeList(l1,l2);
    }
}

我们发现这个题目可以进行拆分，主要是分为三步

先是找到中间点，然后按照中间点分开，然后后面的链表反转，然后跟前面的链表合并

所以我们需要写三个函数，和一个主函数

找到中间点的方法就是

一个快指针，一个慢指针。然后快指针到尾部了。慢指针的位置就是中间点

反转链表不必多说：

next = cur.next

cur.next = pre;

pre = cur;

cur =next;

然后合并链表，就是先加l1的头，然后再加l2的头这样

l1tmp = l1.next;

l2tmp = l2.next;

l1.next = l2;

l1 = l1tmp

l2.next = l1;

l2 = l2tmp

然后完成。

我自己想的思路是，我用双指针解决，找一个新的链表，然后先是左指针的节点加入，然后再加入右指针，然后左右指针都移动，一次类推，然后到左右指针相遇的时候，加入最后的节点。这个思路。但是这样的时间复杂度是o(n)不太符合哭。

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式

既然他不让直接进行计算器算的话，那我们去模拟计算器

从每个数的结尾去计算，如果进位的话，就加入

class Solution415{
    public String addStrings(String num1, String num2){
        StringBuilder res = new StringBuilder("");
        int i =  num1.length()-1, j = num2.length()-1,carry = 0;
        while (i>=0||j>=0){
            int n1 = i>=0?num1.charAt(i)-'0':0;
            int n2 = j>=0?num2.charAt(i)-'0':0;
            int tmp = n1+n2+carry;
            carry = tmp/10;
            res.append(tmp%10);
            i--;j--;
        }
        if (carry==1) res.append(1);
        return res.reverse().toString();
    }
}

然后这里使用的stringBuilder用来操作字符串是非常好的，因为字符串String是final不能修改值

但是stringbuilder和stringbuffer是可以的。其中stringbuilder是单线程的

stringbuffer是多线程，是线程安全的。

56. 合并区间

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

class Solution56A{
    public int[][] merge(int[][] intervals){
        Arrays.sort(intervals,(p,q)->p[0]-q[0]);
        List<int[]> ans = new ArrayList<>();
        for(int[] p:intervals){
            int m = ans.size();
            if (m>0&&p[0]<=ans.get(m-1)[1]){
                ans.get(m-1)[1] = Math.max(ans.get(m-1)[1],p[1]);
            }else {
                ans.add(p);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

就是先按左端点排序，然后这样就可以清楚合并的顺序

如果ans的大小大于0，然后p的左端点要小于ans最后一个的右端点的话

那就可以合并

然后更新右端点，更新为p的右端点ans最后一个的右端点

如果不是的话，就把这个数组加进入来

然后最后将ans转为ans.size大小的数组

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

class Solution160{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB){
        if (headA==null||headB==null) return null;
        ListNode A = headA,B=headB;
        while (A!=B){
            A=(A!=null)?A.next:headB;
            B=(B!=null)?B.next:headA;
        }
        return A;
    }
}

有两种情况

一个是B走的快吧，B走到null了，然后A处在的位置就是首个公共节点

为空了就给他赋值为headA,然后让他从A走

A为空了就赋值为headB让他从B走，然后他们相遇的地方就是公共节点

实际上就是A遍历完headA再遍历headB；B反之；这样就相当于走了同样的距离，也就是两次循环找到交点

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

就是使用双指针，记录中间夹的地方能记录多少雨水

class Solution42A{
    public int trap(int[] height){
        int left = 0,right = height.length-1;
        int preMax= 0,SubMax = 0;
        int ans = 0;
        while (left<right){
            preMax = Math.max(height[left],preMax);
            SubMax = Math.max(height[right],SubMax);
            ans +=preMax<SubMax?preMax-height[left++]:SubMax-height[right--];

        }
        return ans;
    }
}

一个记录左边，一个记录右边

先记录左边这个小的，就是哪个小先记录哪个

然后指针移动

更新最大值

class Solution42A{
    public int trap(int[] height){
        int left = 0,right = height.length-1;
        int preMax= 0,SubMax = 0;
        int ans = 0;
        while (left<right){
            preMax = Math.max(height[left],preMax);
            SubMax = Math.max(height[right],SubMax);
            ans +=preMax<SubMax?preMax-height[left++]:SubMax-height[right--];

        }
        return ans;
    }
    public int trapA(int[] height){
        int index = 0,peak = 0;
        for (int i=0;i<height.length;i++){
            if (height[i]>peak){
                peak = height[i];
                index = i;
            }
        }
        int ans = 0;
        int peakInterL =0;
        for (int i=0;i<index;i++){
            if (height[i]>peakInterL){
                peakInterL = height[i];
            }
            ans +=(peakInterL-height[i]);
        }
        int peakInterR = 0;
        for (int i = height.length-1;i>index;i--){
            if (height[i]>peakInterR){
                peakInterR = height[i];
            }
            ans +=(peakInterR-height[i]);
        }
        return ans;
    }
}

再来一个二次遍历

72. 编辑距离(x)

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

124. 二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和

class Solution124{
    private int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node){
        if (node==null) return 0;
        int LVal = dfs(node.left);
        int RVal = dfs(node.right);
        ans  = Math.max(ans,LVal+RVal+node.val);
        return Math.max(Math.max(LVal,RVal)+node.val,0);
    }
}

就是选择使用左或者右大的哪个，然后最后返回走过的路径，然后记录ans；

最后返回。

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

class Solution142{
    public ListNode detectCycle(ListNode head){
        ListNode fast= head,slow  =head;
        while (fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow  = slow.next;
            if (fast==slow){
                fast = head;
                while (slow!=fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}

如果快慢指针相遇的话，说明有环，然后快指针再从头开始，快慢指针第二次相遇的地方，就是开始入环的第一个节点

93. 复原 IP 地址（回溯）

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和"192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

class Solution93{
    private List<String> ans = new ArrayList<>();
    private List<String> segments = new ArrayList<>();

    public List<String> restoreIpAddresses(String s){
        if (s.length()<4||s.length()>12){
            return ans;
        }
        dfs(s,0,segments);
        return ans;
    }
    private void dfs(String s,int index,List<String> segments){
        if (segments.size()==4){
            if (index==s.length()){
                ans.add(String.join(".",segments));
            }
            return;
        }
        for (int len = 1;len<=3;len++){
            if (index+len>s.length()){
                break;
            }
            String segment = s.substring(index,index+len);
            if (isValid(segment)) {
                segments.add(segment);
                dfs(s, index + len, segments);
                segments.remove(segments.size() - 1);  //恢复现场
            }
        }
    }
    private boolean isValid(String segment){
        if (segment.length() > 1 && segment.startsWith("0")){
            return false;
        }
        int num = Integer.parseInt(segment);
        return num >= 0 && num <= 255;
    }
}

使用回溯算法，主要是要符合ip地址的规则

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

看到这个就想到了这应该是动态规划问题

嗯按照灵神的思路慢慢推演

先是记忆搜索，最初级的阶段

class Solution1143{
    private char[] s,t;
    private int[][] memo;
    public int longestCommonSubsequence(String text1, String text2){
        s =text1.toCharArray();
        t = text2.toCharArray();
        int n  =s.length;
        int m = t.length;
        memo = new int[n][m];
        for (int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(n-1,m-1);
    }
    private int dfs(int i ,int j){
        if (i<0||j<0) return 0;
        if (memo[i][j]!=-1) return memo[i][j];
        if (s[i]==t[j]) return memo[i][j] = dfs(i-1,j-1)+1;
        return memo[i][j] = Math.max(dfs(i-1,j),dfs(i,j-1));
        
    }
}

就是简单的dfs，然后遇到搜索过的直接调用，减少了时间。

遇到符合条件的，把这个位置设置为1

然后返回的时候，去找搜索的时候更好的

但是这个太慢了，要优化一下

1:1 翻译成递推：

class Solution1143{
 public int longestCommonSubsequenceA(String text1, String text2){
        s =text1.toCharArray();
        t = text2.toCharArray();
        int n  =s.length;
        int m = t.length;
        int[][] f = new int[n+1][m+1];
        for (int i =0;i<n;i++){
            for (int j=0;j<m;j++){
                f[i+1][j+1] = s[i] == t[j]?f[i][j]+1:Math.max(f[i][j+1],f[i+1][j]);
            }
        }
        return f[n][m];
    }
}

这个主要是递推，就是遍历然后

下面的i+1,j+1就为

1	s[i] == t[j]?f[i][j]+1:Math.max(f[i][j+1],f[i+1][j])

s[i]和t[j]是不是想到，然后相等的话，

f[i][j]

就+1说明走过了，然后不想的话，就去找下一个路径

最后公共的就是

f[n][m]

然后再进行一波优化

class Solution1143{
    public int longestCommonSubsequenceB(String text1, String text2){
        char[] t = text2.toCharArray();
        int m = t.length;
        int[] f = new int[m + 1];
        for (char x:text1.toCharArray()){
            int pre=  0;
            for (int j=0;j<m;j++){
                int tmp = f[j+1];
                f[j+1] = x==t[j]?pre+1:Math.max(f[j+1],f[j]);
                pre = tmp;
            }
        }
        return f[m];
    }
}

把上面的递推，换成一个数组来操作，这样的话，因为他们的类似方法都是相同的，这样的话，我们直接使用一个数组就可以完成了。

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

想象有一把长度固定的尺子，左端点在链表头部，右端点在正数第 n 个节点。向右移动尺子，当尺子右端点到达链表末尾时，左端点就在倒数第 n 个节点。

我们需要找到倒数第n+1个节点

左端点在链表头部，右端点在正数第 n+1 个节点。向右移动尺子，当尺子右端点到达链表末尾时，左端点就在倒数第 n+1 个节点。

我们可以在头节点的前面插入一个哨兵节点（dummy node），把它当作链表的头节点，这样就有正数第 n+1 个节点了。换句话说，如果遇到需要删除头节点的题目，添加哨兵节点可以简化代码逻辑，请记住这个技巧。

class  Solution19A{
    public ListNode removeNthFromEnd(ListNode head, int n){
        ListNode dummy = new ListNode(0,head);
        ListNode left = dummy;
        ListNode right = dummy;
        while (n-->0){
            right = right.next;
        }
        while (right.next!=null){
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }
}

找到这个节点，然后直接跳过这个节点就行了

就相当于删除了这个节点

82. 删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head); // 新头节点，指向原链表头
        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int duplicateVal = cur.next.val;
                // 跳过所有重复节点
                while (cur.next != null && cur.next.val == duplicateVal) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}

4. 寻找两个正序数组的中位数（困难啊）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

如果不限制时间复杂度的话，这个题目还是挺简单的。直接从后面开始遍历数组，合并数组。然后找中间的数即可

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

这个题目肯定是先从跟节点开始，类似于去找他最右边的那个元素。

所以我们要先递归这个右子树。就是他的这一层第一次出现的时候，也就是深度第一次出现的时候

class Solution199{
    public List<Integer> rightSideView(TreeNode root){
        List<Integer> ans = new ArrayList<>();
        dfs(root,0,ans);
        return ans;
    }
    private void dfs(TreeNode root,int depth,List<Integer> ans){
        if (root==null) return ;
        if (depth==ans.size()){
            ans.add(root.val);
        }
        dfs(root.right,depth+1,ans);
        dfs(root.left,depth+1,ans);
    }
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

中序遍历吗。就是根节点在中间

left root right

class Solution94{
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> ans = new ArrayList<>();
        dfs(root,ans);
        return ans;
    }
    private void dfs(TreeNode root,List<Integer> ans){
        if (root==null) return;
        dfs(root.left,ans);
        ans.add(root.val);
        dfs(root.right,ans);
    }
}

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution704{
    public int search(int[] nums, int target){
        int left = 0,right = nums.length-1;
        while (left<right){
            int mid = (left+right)>>>1;
            if (nums[mid]<target){
                left = mid+1;
            }else if (nums[mid]==target){
                return mid;
            }else {
                right = mid-1;
            }
        }
        return -1;
    }
}

简单的二分查找，记得这个是

可以取到值得

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

class MyQueue {
    private Stack<Integer> A;
    private Stack<Integer> B;

    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        A.push(x);
    }

    public int pop() {
        int peek =peek();
        B.pop();
        return peek;
    }

    public int peek() {
        if (!B.isEmpty()) return B.peek();
        if (A.isEmpty()) return -1;
        while (!A.isEmpty()){
            B.push(A.pop());
        }
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty()&&B.isEmpty();
    }
}

使用两个栈，入队得时候就是进A栈，然后出栈得时候，就是A出栈得元素，压入B栈，然后B出栈

实现先进先出FIFO

165. 比较版本号

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

如果 *version1* < *version2* 返回 -1，
如果 *version1* > *version2* 返回 1，
除此之外返回 0。

class Solution165{
    public int compareVersion(String v1, String v2){
        int i=0,j=0;
        int n = v1.length(),m= v2.length();
        while (i<n||j<m){
            int num1 = 0,num2=0;
            while (i<n&&v1.charAt(i)!='.') num1 = num1*10+v1.charAt(i++)-'0';
            while (j<m&&v2.charAt(j)!='.') num2 = num2*10+v2.charAt(j++)-'0';
            if (num1>num2) return 1;
            else if (num1<num2) return -1;
            i++;j++;

        }
        return 0;
    }
}

就是把小数的哪个分开，然后使用双指针开始遍历

然后比较

148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

class Solution148A{
    public ListNode sortList(ListNode head){
        if (head==null||head.next==null) return head;

        ListNode s = head,f =head,ps = head;
        while (f!=null&&f.next!=null){
            f = f.next.next;
            ps= s;
            s=  s.next;
        }

        ps.next = null;

        ListNode l  =sortList(head);
        ListNode r = sortList(s);

        return merge(l,r);
    }

    ListNode merge(ListNode l,ListNode r){
        ListNode dummy = new ListNode();
        ListNode cur = dummy;

        while (l!=null&&r!=null){
            if (l.val<=r.val){
                cur.next = l;
                l = l.next;
            }
            else {
                cur.next = r;
                r = r.next;
            }
            cur = cur.next;

        }
        if (l==null){
            cur.next =r;
        }else {
            cur.next = l;
        }
        return dummy.next;
    }
}

使用了归并排序，跟之前的反转链表类似，找到中点，然后分割，然后进行大小的比较排序

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

class Solution22{

    private int n;
    private final List<String> ans = new ArrayList<>();
    private char[] path;
    public List<String> generateParenthesis(int n){
        this.n = n;
        path = new char[2*n];
        dfs(0,0);
        return ans;

    }
    private void dfs(int i ,int open){
        if (i==2*n){//填补完成
            ans.add(new String(path));
            return;
        }
        if (open<n){//填补左括号
            path[i] = '(';
            dfs(i+1,open+1);
        }
        if (i-open<open){//填补右括号
            path[i] = ')';
            dfs(i+1,open);
        }
    }
}

31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

从右向左，找第一个小于右侧相邻数字的数 x

找 x 右边最小的大于 x 的数 y，交换 x 和 y

反转 y 右边的数，把右边的数变成最小的排列

class Solution31{
    public void nextPermutation(int[] nums){
        int n = nums.length;
        int i = n-2;
        while (i>=0&&nums[i]>=nums[i+1]){
            i--;
        }
        if (i>=0){
            int j = n-1;
            while (nums[j]<=nums[i]){
                j--;
            }
            swap(nums,i,j);
        }
        reverse(nums,i+1,n-1);
    }
    private void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        
    }
    private void reverse(int[] nums,int left,int right){
        while (left<right){
            swap(nums,left++,right--);
        }
    }
}

分为先找数，然后交交换，然后反转这三步骤。

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

class Solution69{
    public int mySqrt(int x){
        int left = 0, right = Math.min(x, 46340) + 1;
        while (left+1<right){
            int mid = (left+right)>>>1;
            if (mid*mid<=x){
                left = mid;
            }else {
                right = mid;
            }
        }
        return left;
    }
}

使用二分查找来解决，注意这里是mid*mid<=x,也就是小于target

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

虽然看着说是滑动窗口，其实用队列做是更好的

class Solution239AA{
    public int[] maxSlidingWindowA(int[] nums, int k ){
        if (nums.length==0||k==0) return new  int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length-k+1];
        for (int j = 0,i=1-k;j<nums.length;i++,j++){
            if (i>0&&deque.peekFirst()==nums[i-1]){
                deque.removeFirst();
            }
            while (!deque.isEmpty()&&deque.peekLast()<nums[j]){
                deque.removeLast();
                deque.addLast(nums[j]);
            }
            if (i>=0)
                res[i] =deque.peekFirst();
        }
        return res;
    }
    public int[] maxSlidingWindow(int[] nums, int k){
        int n = nums.length;
        int[] ans= new int[n-k+1];
        Deque<Integer> deque= new ArrayDeque<>();
        for (int i =0;i<n;i++){
            while (!deque.isEmpty()&&nums[deque.getLast()]<=nums[i]){//入队，维护单调性
                deque.removeLast();
            }
            deque.addLast(i);
            
            if (deque.getFirst()<=i-k){//出队队首已经离开窗口了
                deque.removeFirst();
            }
            if (i>=k-1){队满
                ans[i-k+1] = nums[deque.getFirst()];
            }
        }
        return ans;
    }
}

2. 两数相加

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

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

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

class Solution2{
    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;
    }
}

就是实现两个链表数的加法，使用进位的问题

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

函数 myAtoi(string s) 的算法如下：

空格：读入字符串并丢弃无用的前导空格（" "）
符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
舍入：如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1 。

返回整数作为最终结果。

class Solution {
    public int myAtoi(String s) {
        List<Character> ans = new ArrayList<>();
        int sign = 1;
        boolean started = false;

        for (char e : s.toCharArray()) {
            if (!started) {
                if (e == ' ') continue;
                if (e == '+') {
                    started = true;
                    continue;
                }
                if (e == '-') {
                    sign = -1;
                    started = true;
                    continue;
                }
                if (Character.isDigit(e)) {
                    ans.add(e);
                    started = true;
                } else {
                    break;
                }
            } else {
                if (Character.isDigit(e)) {
                    ans.add(e);
                } else {
                    break;
                }
            }
        }

        if (ans.size() == 0) return 0;

        long num = 0;
        for (char c : ans) {
            num = num * 10 + (c - '0');
            if (sign == 1 && num > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (sign == -1 && -num < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }

        return (int)(sign * num);
    }
}

直接按要求暴力破解，最后的时候进行一波转换

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution70AA{
    public int climbStairs(int n ){
        int[] memo = new int[n+1];
         return dfs(n,memo);
    }
    private int dfs(int i,int[] memo){
        if (i<=1) return 1;
        if (memo[i]!=0) return memo[i];
        return memo[i] = dfs(i-1,memo)+dfs(i-2,memo);
    }
}

记忆搜推，直接进行

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

class Solution32A{
    public int longestValidParentheses(String s){
        Deque<Integer> stack = new LinkedList<Integer>();
        int[] dp = new int[s.length()];
        int maxlen = 0;
        for (int i =0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else if (!stack.isEmpty()&&s.charAt(i)==')'){
                int leftIndex = stack.pop();
                int length = i-leftIndex+1;
                if (leftIndex-1>=0){
                    length+=dp[leftIndex-1];
                }
                dp[i] = length;
                maxlen = Math.max(maxlen,length);
            }
        }
        return maxlen;
    }
}

一想到了这个有效的括号，我们就想到了用栈来实现

遇到 '(' 左括号就入栈，记录它的下标。

遇到 ')' 右括号：

如果栈不为空，说明有匹配的左括号。
从栈中弹出匹配的左括号的下标 leftIndex。
当前这一对括号的基本长度就是 i - leftIndex + 1。
注意：\如果 leftIndex > 0，而 dp[leftIndex - 1] > 0，说明前面有一段*连续的有效括号*，可以加上！
1
2

length = i - leftIndex + 1 + dp[leftIndex - 1];
把这段长度记录到 dp[i] 中，表示以 i 为结尾的最长有效括号长度。
更新全局最大值 res = Math.max(res, dp[i])。

322. 零钱兑换

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

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

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

这是背包问题，

问：关于完全背包，有两种写法，一种是外层循环枚举物品，内层循环枚举体积；另一种是外层循环枚举体积，内层循环枚举物品。如何评价这两种写法的优劣？

答：两种写法都可以，但更推荐前者。外层循环枚举物品的写法，只会遍历物品数组一次；而内层循环枚举物品的写法，会遍历物品数组多次。从 cache 的角度分析，多次遍历数组会导致额外的 cache miss，带来额外的开销。所以虽然这两种写法的时间空间复杂度是一样的，但外层循环枚举物品的写法常数更小。

class Solution322{
    public int coinChange(int[] coins,int amount){
        int[] f = new int[amount+1];
        Arrays.fill(f,Integer.MAX_VALUE/2);
        f[0]= 0;
        for (int x:coins){
            for (int c=x;c<=amount;c++){
                f[c] = Math.min(f[c],f[c-x]+1);
            }
        }
        int ans = f[amount];
        return ans<Integer.MAX_VALUE/2?ans:-1;
    }
}

完全背包，先物品再容量.内层遍历背包容量（从小到大）：,如果当前容量 c 用当前硬币 x，可以转移为 f[c - x] + 1（多用了1个 x 面额硬币）。

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

class Solution43{
    public String multiply(String num1, String num2){
        if(num1.equals("0")||num2.equals("0")) return "0";
        int[] res = new int[num1.length()+num2.length()];
        for (int i = num1.length()-1;i>=0;i--){
            int n1 = num1.charAt(i)-'0';
            for (int j = num2.length()-1;j>=0;j--){
                int n2 = num2.charAt(j)-'0';
                int sum = (res[i+j+1]+n1*n2);
                res[i+j+1] =sum%10;
                res[i+j] +=sum/10;
            }
        }
        StringBuilder result =new StringBuilder();
        for (int i =0;i<res.length;i++){
            if (i==0&&res[i]==0) continue;
            result.append(res[i]);
        }
        return result.toString();
    }
}

就是讲乘法拆开，然后根据

乘数 num1 位数为 M，被乘数 num2 位数为 N， num1 x num2 结果 res 最大总位数为 M+N

num1[i] x num2[j] 的结果为 tmp(位数为两位，”0x”, “xy” 的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

class Solution105AA{
    public TreeNode buildTree(int[] preorder, int[] inorder){
        int n = preorder.length;
        if (n==0) return null;
        int leftSize = indexOf(inorder,preorder[0]);//左子树大小
        int[] pre1 = Arrays.copyOfRange(preorder,1,1+leftSize);//左子树序列
        int[] pre2 = Arrays.copyOfRange(preorder,1+leftSize,n);//右子树序列
        int[] in1 =Arrays.copyOfRange(inorder,0,leftSize);//左子树
        int[] in2 = Arrays.copyOfRange(inorder,1+leftSize,n);//右子树

        TreeNode left = buildTree(pre1,in1);
        TreeNode right = buildTree(pre2,in2);
        return new TreeNode(preorder[0],left,right);


    }
    private int indexOf(int[] a,int x){//查找位置
        for (int i=0;;i++){
            if (a[i]==x){
                return i;
            }
        }
    }
}

就是根据两个遍历，一层一层的递归，然后完成查找。速度有些慢就是了

LCR 140. 训练计划 II

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

class SolutionLCR140 {
    public ListNode trainingPlan(ListNode head, int cnt) {
        List<Integer> vals = new ArrayList<>();
        ListNode cur = head;

        // Step1: 将链表的 val 存入数组
        while (cur != null) {
            vals.add(cur.val);
            cur = cur.next;
        }

        // Step2: 从 vals 的最后 cnt 位构造新链表
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (int i = vals.size() - cnt; i < vals.size(); i++) {
            p.next = new ListNode(vals.get(i));
            p = p.next;
        }

        return dummy.next;
    }
}

我就是把这个链表的数据提取出来，然后放入新的链表

时间复杂度太高了

然后使用了快慢指针来看

class SolutionLCR140 {
    public ListNode trainingPlanA(ListNode head, int cnt) {
        List<Integer> vals = new ArrayList<>();
        ListNode cur = head;

        // Step1: 将链表的 val 存入数组
        while (cur != null) {
            vals.add(cur.val);
            cur = cur.next;
        }

        // Step2: 从 vals 的最后 cnt 位构造新链表
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (int i = vals.size() - cnt; i < vals.size(); i++) {
            p.next = new ListNode(vals.get(i));
            p = p.next;
        }

        return dummy.next;
    }
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode node1 = null;
        ListNode node2 = null;
        node1 = head;
        node2 = head;
        
        if (head.next==null){
            return head;
        }
        for (int i =1;i<cnt;i++){
            node2 = node2.next;
        }
        while (node2.next!=null){
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }
}

确实这个方法好啊

类似的可以找出从中点开始的链表

151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

class Solution151{
    public String reverseWords(String s){
        String[] str = s.trim().split(" ");
        StringBuilder res = new StringBuilder();
        for (int i =str.length-1;i>=0;i--){
            if (str[i].equals(""))continue;
            res.append(str[i]+" ");
        }
        return res.toString().trim();
    }
}

那么我们直接倒着遍历不得了

遇到空格就跳过继续，然后把当前拿到的全都放入结果

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

看到这种题目就知识这应该是使用回溯算法了

class Solution78A{
    private final List<List<Integer>> ans = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();
    private int[] nums;
    
    public List<List<Integer>> subsets(int[] nums){
        this.nums = nums;
        dfs(0);
        return ans;
    }
    private void dfs(int i ){
        if (i== nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }
        dfs(i+1);
        path.add(nums[i]);
        dfs(i+1);
        path.remove(path.size()-1);
    }

}

使用回溯法，就是选不选第i个

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

class  Solution129{
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node,int x){
        if (node==null){
            return 0;
        }
        x  =x*10+node.val;
        if (node.left==node.right){
            return x;
        }
        return dfs(node.left,x)+dfs(node.right,x);
    }
}

就是遍历，然后到下一层的时候，*10+node.val就ok

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

class MinStack{
    private Stack<Integer> stack;
    private Stack<Integer> min_stack;
    public MinStack(){
        stack = new Stack<>();
        min_stack = new Stack<>();
    }
    public     void push(int x){
        stack.push(x);
        if (min_stack.isEmpty()||x<=min_stack.peek()){
            min_stack.push(x);
        }
    }
    public     void pop(){
        if (stack.pop().equals(min_stack.peek())){
            min_stack.pop();
        }
    }
    public     int top(){
        return stack.peek();
    }
       public int getMin(){
        return min_stack.peek();
    }
}

就是使用两个栈，然后最小的栈存储最小的元素，然后维护这个最小栈

101. 对称二叉树

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

class Solution101A{
    public boolean isSymmetric(TreeNode root){
        return root==null||recur(root.left,root.right);
    }
    private boolean recur(TreeNode L,TreeNode R){
        if (L==null&&R==null) return true;
        if (L==null||R==null||L.val!=R.val) return false;
        return recur(L.left,R.right)&&recur(R.left,L.right);
    }
}

就是遍历，左的左要等于右的右这样的

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution34AA {
    public int[] searchRange(int[] nums, int target) {
        int start = lowBound(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        int end = lowBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    private int lowBound(int[] nums, int target) {
        int left = 0, right = nums.length; // 注意 right = nums.length，开区间写法
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid; // nums[mid] >= target
            }
        }
        return left;
    }
}

二分查找，，，

104. 二叉树的最大深度

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

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

class Solution104AA{
    public int maxDepth(TreeNode root){
        if (root==null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

简单的递归

39. 组合总和

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

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

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

class Solution93AA{
    void backtrack(List<Integer> state,int target,int[] choices,int start,List<List<Integer>> res){
        if (target==0){
            res.add(new ArrayList<>(state));
            return;
        }
        for (int i=start;i<choices.length;i++){
            if (target-choices[i]<0){
                break;
            }
            state.add(choices[i]);
            backtrack(state,target-choices[i],choices,i,res);
            state.remove(state.size()-1);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates,int target){
        List<Integer> state = new ArrayList<>();
        Arrays.sort(candidates);
        int start = 0;
        List<List<Integer>> res = new ArrayList<>();
        backtrack(state,target,candidates,start,res);
        return res;
    }
}

还是回溯法+递归，一个一个去遍历找，然后最后恢复

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

class Solution394{
    public String decodeString(String s) {
        Stack<Integer> countstack = new Stack<>();
        Stack<StringBuilder> stringstack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int k = 0;

        for (char c:s.toCharArray()){
            if (Character.isDigit(c)){
                k = k*10+(c-'0');
            }
            else if (c=='['){
                countstack.push(k);
                k=0;
                stringstack.push(currentString);
                currentString = new StringBuilder();
            }
            else if (c==']'){
                int repeat = countstack.pop();
                StringBuilder sb = stringstack.pop();
                for (int i =0;i<repeat;i++){
                    sb.append(currentString);
                }
                currentString = sb;
            }else {
                currentString.append(c);
            }
        }
        return currentString.toString();
    }
}

左括号的话，就往字符栈里加字符，然后把重复的次数加进数字栈

然后右括号的时候

就把数字取出来，作为重复次数，字符栈取出来作为重复的字符

然后重复就好，单纯的字符就直接加入

最后返回字符串

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

class Solution{
    List<Integer> ans = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root){
        if (root==null){
            return new ArrayList<>();
        }
        ans.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return ans;
    }
}

非常easy的题目

110. 平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树

class Solution110A{
    public boolean isBalanced(TreeNode root){
        return getHeight(root) !=-1;
    }
    private int getHeight(TreeNode node){
        if (node==null){
            return 0;
        }
        int leftH = getHeight(node.left);
        if (leftH==-1){
            return -1;
        }
        int rightH = getHeight(node.right);
        if (rightH==-1||Math.abs(leftH-rightH)>1){
            return -1;
        }
        return Math.max(leftH,rightH)+1;
    }
}

平衡二叉树的定义就是高度差不能s超过1

然后左边右边都不能超过1，左边右边比较也是

470. 用 Rand7() 实现 Rand10()

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

(randX() - 1)Y + randY() 可以等概率的生成[1, X Y]范围的随机数

64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

class Solution{
    public int minPathSum(int[][] grid){
        for(int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (i==0&&j==0) continue;
                else if (i==0) grid[i][j] = grid[i][j-1]+grid[i][j];
                else if (j==0) grid[i][j]=grid[i-1][j]+grid[i][j];
                else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

就是如果当前的为空的话，就转到另一个地方去尝试，然后把前面的最小的路径加到和上

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1	matrix[i][j]→matrix[j][n−1−i]

class Solution48A{
    public void rotate(int[][] matrix){
        int n  = matrix.length;
        int[][] tmp  = new int[n][];
        for (int i =0;i<n;i++){
            tmp[i] = matrix[i].clone();
        }
        for (int i =0;i<n;i++){
            for (int j = 0;j<n;j++){
                matrix[j][n-1-i] = tmp[i][j];
            }
        }
    }
}

借助一个辅助矩阵，进行顺时针转换

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

class Solution{
    private int ans;
    
    public int diameterOfBinaryTree(TreeNode root){
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node){
        if (node ==null){
            return -1;
        }
        int llen = dfs(node.left)+1;
        int rlen = dfs(node.right)+1;
        ans = Math.max(ans,llen+rlen);
        return Math.max(llen,rlen);
    }
}

就一致遍历，算左边和右边高度的和

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

class Solution221{
    int maximalSquare(char[][] matrix){
        int n  = matrix[0].length;
        int[] heights = new int[n+1];
        int ans = 0;
        for (char[] row :matrix){
            for (int j =0;j<n;j++){
                if (row[j]=='0'){
                    heights[j]=0;//柱子高度为0
                }else {
                    heights[j]++;
                }
            }
            ans = Math.max(ans,largesSize(heights));
        }
        return ans * ans;
    }
    private int largesSize(int[] heights){
        int n = heights.length;
        int[] st = new int[n];
        int top = -1;
        st[++top]  = -1;//在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        int ans = 0;
        for (int right = 0;right<n;right++){
            int h = heights[right];
            while (top>0&&h<=heights[st[top]]){
                int i = st[top--];
                int left = st[top];
                ans =Math.max(ans,Math.min(heights[i],right-left-1));
            }
            st[++top] =right;
        }
        return ans;
    }
}

将每一行视为“底”，构建柱状图；每一列记录高度，形成一个直方图（heights）；
在这个直方图中，用单调栈找以某个位置为底的最大 正方形（不是矩形）边长，最后平方得到面积。

122. 买卖股票的最佳时机 II

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

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

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

class Solution122A{
    public int maxProfit(int[] prices){
        int profit = 0;
        for (int i =1;i<prices.length;i++){
            int tmp = prices[i]-prices[i-1];
            if (tmp>0) profit+=tmp;
        }
        return profit;
    }
}

简单的遍历贪心

128. 最长连续序列

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

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

最简单的就是直接遍历，然后比较i和i-1

但是这样效率太低，所以我们使用hashset来遍历，这样的时间复杂度低

class Solution128A{
    public int longestConsecutive(int[] nums){
        int ans = 0;
        Set<Integer> st = new HashSet<>();
        for (int num:nums){
            st.add(num);
        }
        for (int x:st){
            if (st.contains(x-1)){
                continue;
            }
            int y = x+1;
            while (st.contains(y)){
                y++;
            }
            ans = Math.max(ans,y-x);
        }
        return ans;
    }
}

去找如果有前面的数字的话，就不对。

有后面数字的话，就y++

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

class Solution240{
    public boolean searchMatrix(int[][] matrix, int target){
        int i = 0;
        int j  = matrix[0].length-1;
        while (i<matrix.length&&j>=0){
            if (matrix[i][j]==target){
                return true;
            }
            if(matrix[i][j]<target){
                i++;
            }else {
                j--;
            }
        }
        return false;
    }
}

这个题目类似二分查找

小于就往右去找，大于就往上去找

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

一看到这种的立马想到递归+dfs

class Solution98AA {
    public boolean isValidBST(TreeNode root) {
        return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);

    }
    private boolean dfs(TreeNode node,long left,long right){
        if (node==null){
            return true;
        }
        long x = node.val;
        return x<right&&x>left&&dfs(node.left,left,x)&&dfs(node.right,x,right);
    }
}

就是简单的遍历

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

我们可以找到这个链表的中点（快慢指针），然后分为两个链表，反转后面的链表，然后判断是不是想等，两个链表

class Solution234{
    public boolean isPalindrome(ListNode head) {
        if (head==null||head.next==null) return true;
        ListNode slow = head,fast = head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode secondList = reverseList(slow);
        ListNode p1 = head;
        ListNode p2 = secondList;
        while (p2!=null){
            if (p1.val!= p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
    private ListNode reverseList(ListNode node){
        ListNode pre = null,cur = node;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

14. 最长公共前缀

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

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

class Solution14AAA{
    public String longestCommonPrefix(String[] strs){
        if(strs.length==0) return "";
        String ans = strs[0];
        for (int i =1;i<strs.length;i++){
            int j =0;
            for (;j<ans.length()&&j<strs[i].length();j++){
                if(ans.charAt(j)!=strs[i].charAt(j)) break;
            }
            ans = ans.substring(0,j);
            if (ans.equals("")) return ans;
        }
        return ans;
    }
}

就是简单的双重遍历

面试笔试1

因为这个表，他需要自己呈现出多层结构，所以要使用自关联

CREATE TABLE department (
    id INT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(100) NOT NULL,
    parent_id INT,  
    leader VARCHAR(100),
    FOREIGN KEY (parent_id) REFERENCES department(id)
);

然后是一个树形的结构，需要使用递归来解决

递归地解析每一条记录的上级部门，先插入父再插入子

部门表的实体类的设计：

public class Department {
    private Integer id;
    private String name;
    private String leader;
    private Integer parentId;
    private List<Department> children = new ArrayList<>();

    public Department(Integer id, String name, String leader, Integer parentId) {
        this.id = id;
        this.name = name;
        this.leader = leader;
        this.parentId = parentId;
    }

    public Integer getId() { return id; }
    public String getName() { return name; }
    public Integer getParentId() { return parentId; }
    public List<Department> getChildren() { return children; }
}

构建树的设计：

public class DepartmentTreeBuilder {
    public Department buildDepartmentTree(List<Department> allDepartments, Integer rootId) {
        Map<Integer, Department> deptMap = new HashMap<>();
        for (Department dept : allDepartments) {
            deptMap.put(dept.getId(), dept);
        }

        Department root = null;
        for (Department dept : allDepartments) {
            if (dept.getParentId() == null) {
                continue;
            }

            Department parent = deptMap.get(dept.getParentId());
            if (parent != null) {
                parent.getChildren().add(dept);
            }

            if (dept.getId().equals(rootId)) {
                root = dept;
            }
        }
        if (root == null && deptMap.containsKey(rootId)) {
            root = deptMap.get(rootId);
        }

        return root;
    }
}

需求：体检项目不固定，字段名与字段类型可自定义

表的设计：

CREATE TABLE exam_record (
    id INT PRIMARY KEY,
    user_id INT,
    exam_date DATE
);
CREATE TABLE exam_field (
    id INT PRIMARY KEY,
    name VARCHAR(100), 
    type VARCHAR(20)
);
CREATE TABLE exam_value (
    record_id INT,
    field_id INT,
    value_text TEXT,
    PRIMARY KEY(record_id, field_id),
    FOREIGN KEY (record_id) REFERENCES exam_record(id),
    FOREIGN KEY (field_id) REFERENCES exam_field(id)
);

使用 value_text 存储所有类型的值，在读取时再根据字段定义做类型转换；

新字段可以动态添加到 exam_field 表，不需要改动表结构；

数据插入/查询时，通过 field_id 关联字段定义表。

java代码：

实体类：

@Data
public class ExamField {
    private Integer id;
    private String name;
    private String type;
}

插入逻辑:

public class ExamService {

    private Map<String, ExamField> fieldMap = new HashMap<>();

    public void insertExamRecord(int recordId, Map<String, Object> values) {
        for (Map.Entry<String, Object> entry : values.entrySet()) {
            String fieldName = entry.getKey();
            Object value = entry.getValue();
            ExamField field = fieldMap.get(fieldName);
            if (field == null) {
                throw new RuntimeException("字段未定义：" + fieldName);
            }
            String valueText = String.valueOf(value);

            insertExamValue(recordId, field.getId(), valueText);
        }
    }
    private void insertExamValue(int recordId, int fieldId, String valueText) {
        System.out.println("插入：recordId=" + recordId + ", fieldId=" + fieldId + ", value=" + valueText);
    }
}

查询逻辑：

public class ExamService {

    private Map<String, ExamField> fieldMap = new HashMap<>();
    private Map<Integer, ExamField> fieldIdMap = new HashMap<>();

    public Map<String, Object> getExamRecord(int recordId) {
        Map<Integer, String> rawValues = queryValuesFromDB(recordId);
        Map<String, Object> result = new HashMap<>();

        for (Map.Entry<Integer, String> entry : rawValues.entrySet()) {
            Integer fieldId = entry.getKey();
            String rawText = entry.getValue();

            ExamField field = fieldIdMap.get(fieldId);
            if (field == null) continue;

            Object realValue = parseValue(field.getType(), rawText);
            result.put(field.getName(), realValue);
        }

        return result;
    }

    private Object parseValue(String type, String raw) {
        switch (type) {
            case "int":
                return Integer.parseInt(raw);
            case "decimal":
                return Double.parseDouble(raw);
            case "date":
                return LocalDate.parse(raw);
            default:
                return raw;
        }
    }
    private Map<Integer, String> queryValuesFromDB(int recordId) {
        Map<Integer, String> dummy = new HashMap<>();
        dummy.put(1, "4.8");
        dummy.put(2, "90"); 
        dummy.put(3, "2025-06-26"); 
        return dummy;
    }
}

差不多就是这样。

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

我们可以直接暴力破解，遍历然后直接看是不是中间的最大的元素，但是这样的时间复杂度为O(logn)

不行，所以我们考虑是不是可以使用二分查找

class Solution162{
    public int findPeakElement(int[] nums){
        int left = -1,right = nums.length-1;
        while (left+1<right){
            int mid = (left+right)>>>1;
            if (nums[mid]>nums[mid+1]){
                right = mid;
            }else {
                left = mid;
            }
        }
        return right;
    }
}

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

一看除了递归dfs也没啥好的方法了，直接递归吧

class Solution695{
    public int dfs(int[][] grid,int i,int j){
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0) return 0;
        int sum = 1;
        grid[i][j] = 0;
        sum +=dfs(grid,i+1,j);
        sum +=dfs(grid,i,j+1);
        sum +=dfs(grid,i-1,j);
        sum +=dfs(grid,i,j-1);
        return sum;
    }
    public int maxAreaOfIsland(int[][] grid){
        int max = 0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]==1){
                    max = Math.max(max,dfs(grid,i,j));
                }
            }
        }
        return max;
    }
}

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

class Solution113AA {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(root,targetSum,path,ans);
        return ans;
    }
    private void dfs(TreeNode node, int left, List<Integer> path, List<List<Integer>> ans){
        if (node==null){
            return;
        }
        path.add(node.val);
        left -=node.val;
        if (node.left==node.right&&left==0){
            ans.add(new ArrayList<>(path));
        }else {
            dfs(node.left,left,path,ans);
            dfs(node.right,left,path,ans);
        }
        path.remove(path.size()-1);
    }
}

就是到了叶子节点我们就把他加入，没到叶子节点的话，就去递归左右节点

然后操作完之后如果超过了的话，那我我们回溯，把这次的删除。

662. 二叉树最大宽度

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的宽度。

每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

class Solution662{
    Map<Integer,Integer> map = new HashMap<>();
    int ans;
    public int widthOfBinaryTree(TreeNode root) {
       dfs(root,1,0);
       return ans;
    }
    void dfs(TreeNode root,int u,int depth){
        if (root==null) return;
        if (!map.containsKey(depth)) map.put(depth,u);//第一次访问的话，记录最左的节点
        ans = Math.max(ans,u-map.get(depth)+1);
        u = u-map.get(depth)+1;
        dfs(root.left,u<<1,depth+1);
        dfs(root.right,u<<1|1,depth+1);
    }
}

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution62A{
    public int uniquePaths(int m, int n){
        int[] f = new int[n+1];
        f[1]= 1;
        for (int i=0;i<m;i++){
            for (int j =0;j<n;j++){
                f[j+1] +=f[j];
            }
        }
        return f[n];
    }
}

简单的动态规划直接完事

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

看到这个应该就是使用回溯法了，或者是直接遍历，当前数字大于等于1就加入子数组，小于就不加入

但是这个是不对的，因为可能是两个负数，然后导致更大，所以应该是动态规划，记录当前的最大值和最小值

class Solution152A{
    public int maxProduct(int[] nums) {
        int maxF = nums[0];
        int minF = nums[0];
        int ans = nums[0];

        for (int i=1;i<nums.length;i++){
            int cur = nums[i];
            int tmpMax = maxF,tmpMin = minF;
            maxF = Math.max(cur, Math.max(cur * tmpMax, cur * tmpMin));
            minF = Math.min(cur, Math.min(cur * tmpMax, cur * tmpMin));
            ans = Math.max(ans,maxF);
        }
        return ans;
    }
}

198. 打家劫舍

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

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

class Solution198{
    public int rob(int[] nums){
        int pre = 0,cur = 0,tmp;
        for(int num:nums){
            tmp = cur;
            cur = Math.max(pre+num,cur);
            pre = tmp;
        }
        return cur;
    }
}

快速方法，就是遍历，然后更新值。

选最大的那个，是选这个还是不选这个。

然后更新pre节点

179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

}
class Solution179{
    public String largestNumber(int[] nums){
        String[] strs = new String[nums.length];
        for (int i=0;i<nums.length;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs,(x,y)->(y+x).compareTo(x+y));
        if (strs[0].equals("0")) return "0";
        StringBuilder res = new StringBuilder();
        for (String s:strs){
            res.append(s);
        }
        return res.toString();
    }
}

就是规定一个排序的问题

如果x+y>y+x那么就说明x更大，应该排在前面。使用这个方式进行排序

然后转为StringBuilder，然后toString

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

一看这种题目就要使用dfs

然后递归，targer-node.val，然后继续递归

class Solution112A{
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        targetSum -=root.val;
        if (root.left==root.right&&root.left==null) return targetSum==0;
        return hasPathSum(root.left,targetSum)||hasPathSum(root.right,targetSum);
    }
    
}

简洁写法

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

class Solution560{
    public int subarraySum(int[] nums, int k) {
        int ans = 0;
        int s = 0;
        Map<Integer,Integer> cnt = new HashMap<>(nums.length);
        for(int x:nums){
            cnt.merge(s,1,Integer::sum);
            s +=x;
            ans +=cnt.getOrDefault(s-k,0);
        }
        return ans;
    }
}

使用hashmap进行查找操作。

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

解决计算器的通用方法：

对于「任何表达式」而言，我们都使用两个栈 nums 和 ops：

nums ：存放所有的数字
ops ：存放所有的数字以外的操作

 class Solution227A {
    public int calculate(String s) {
        int num = 0;
        char sign = '+'; // 初始默认是加法
        Stack<Integer> stack = new Stack<>();
        int n = s.length();

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

            // 如果是数字，累加
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }

            // 如果是运算符，或者是最后一个字符，就处理当前数字
            if ((!Character.isDigit(c) && c != ' ') || i == n - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num); // 题目要求整数除法
                }
                sign = c;
                num = 0;
            }
        }

        // 把栈里所有数字加起来
        int result = 0;
        for (int val : stack) {
            result += val;
        }
        return result;
    }
}

这是双栈不好用，改为单栈了

169. 多数元素

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution169 {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> cnt = new HashMap<>();
        for (int x:nums){
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            if (cnt.get(x)>nums.length/2){
              return x;
            }
        }
        return -1;
    }
}

使用hash表非常简单，但是不够快。

这里引入摩尔投票

设输入数组 nums 的众数为 x ，数组长度为 n 。

若记众数的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。

若数组的前 a 个数字的 票数和 =0 ，则数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的众数仍为x

class Solution169A{
    public int majorityElement(int[] nums){
        int x = 0,votes = 0;
        for (int num:nums){
            if (votes==0) x = num;
            votes +=num ==x?1:-1;
        }
        return x;
    }
}

226. 翻转二叉树

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

class Solution226{
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        TreeNode tmp =root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }
}

就是递归交换

718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

class Solution718{
    public int findLength(int[] nums1, int[] nums2){
        int n  = nums1.length;
        int m = nums2.length;
        int ans = 0;
        int [][] f= new int[n+1][m+1];
        for(int i =0;i<n;i++){
            for (int j=0;j<m;j++){
                if(nums1[i]==nums2[j]){
                    f[i+1][j+1] = f[i][j]+1;
                    ans = Math.max(ans,f[i+1][j+1]);
                }
            }
        }
        return ans;
    }
}

使用动态规划

如果相等的话

1	f[i+1][j+1] = f[i][j]+1;

然后求出最大值，就是公共子数组的长度

209. 长度最小的子数组

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

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

class Solution209{
    public int minSubArrayLen(int target, int[] nums){
        int n =  nums.length;
        int left =0,ans = Integer.MAX_VALUE;
        int sum = 0;
        for (int right  = 0;right<n;right++){
            sum +=nums[right];
            while (sum>=target){
                ans = Math.min(ans,right-left+1);
                sum -=nums[left++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

使用滑动窗口

139. 单词拆分

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

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

class Solution139{
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp =new boolean[n+1];
        dp[0] = true;
        for (int i=1;i<=n;i++){
            for (int j=0;j<i;j++){
                if (dp[j]&&set.contains(s.substring(j,i))){
                    dp[i] =true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

使用动态dp

i是s中的，j是字典中的

然后使用Hashset来快速查找

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

我的思路是这个val和前面的相等的时候，就跳过当前的元素

class Solution83A{
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null) return null;
        ListNode cur = head;
        while (cur!=null&&cur.next!=null){
            if (cur.val==cur.next.val){
                cur.next = cur.next.next;
            }else {
                cur =cur.next;
            }
        }
        return head;
    }
}

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

封装一个交换方法，用tmp值的方式

class Solution24A{
    public ListNode swapPairs(ListNode head) {
        if (head==null||head.next==null) return head;
        ListNode tmp = head.next;
        head.next = swapPairs(tmp.next);
        tmp.next = head;
        return tmp;
    }
}

就跟平常的交换一样

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

就遇到零就交换位置呗，然后遍历

class Solution283A{
    public void moveZeroes(int[] nums){
        int slow = 0;
        for (int fast = 0;fast<nums.length;fast++){
            if (nums[fast]!=0){
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow++] = temp;
            }
        }
    }
}

468. 验证IP地址

给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4" ；如果是有效的 IPv6 地址，返回 "IPv6" ；如果不是上述类型的 IP 地址，返回 "Neither" 。

有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。

一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址，其中:

1 <= xi.length <= 4
xi 是一个 十六进制字符串 ，可以包含数字、小写英文字母( 'a' 到 'f' )和大写英文字母( 'A' 到 'F' )。
在 xi 中允许前导零。

例如 "2001:0db8:85a3:0000:0000:8a2e:0370:7334" 和 "2001:db8:85a3:0:0:8A2E:0370:7334" 是有效的 IPv6 地址，而 "2001:0db8:85a3::8A2E:037j:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。

就两种ip地址，ipv4和ipv6

就看分隔符是.还是：来分治即可

class Solution{
    public String validIPAddress(String queryIP){
        boolean flag = false;
        for (int i=0;i<queryIP.length();i++){
            if (queryIP.charAt(i)=='.'){
                flag = true;
                break;
            }else if (queryIP.charAt(i)==':'){
                flag  = false;
                break;
            }
        }
        if (!flag){
            String [] split = queryIP.split(":",-1);
            if (split.length!=8){
                return "Neither";
            }
            for (String s:split){
                if (s.length()>4||s.isEmpty()) return "Neither";
                for (char c:s.toCharArray()){
                    if (!String.valueOf(c).matches("[0-9a-fA-F]")){
                        return "Neither";
                    }
                }
            }
            return "IPv6";
        }else {
            String[] split = queryIP.split("\\.",-1);
            if (split.length!=4) return "Neither";
            for (String s:split){
                if (s.isEmpty()) return "Neither";
                try {
                    int num = Integer.parseInt(s);
                    if (num>255||!String.valueOf(num).equals(s)){
                        return "Neither";
                    }
                }catch (NumberFormatException e){
                    return "Neither";
                }
            }
            return "IPv4";
        }
    }
}

这里用了正则表达式来验证，能通过就说明是xxx

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n =temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i=0;i<n;i++){
            while (!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                int pre = stack.pop();
                res[pre]  =i-pre;
            }
            stack.push(i);
        }
        return res;
    }
}

使用单调栈来比较大小，

138. 随机链表的复制

给你一个长度为 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 作为传入参数。

class Solution138A{
    public Node copyRandomList(Node head){
        if (head==null) return null;
        for(Node cur = head;cur!=null;cur = cur.next.next){
            cur.next = new Node(cur.val,cur.next);
        }
        for (Node cur =head;cur!=null;cur = cur.next.next){
            if (cur.random!=null){
                cur.next.random = cur.random.next;
            }
        }
        Node newHead = head.next;
        Node cur = head;
        for (;cur.next.next!=null;cur=cur.next){
            Node copy = cur.next;
            cur.next = copy.next;
            copy.next =copy.next.next;
        }
        cur.next = null;
        return newHead;
        
    }
}

我们这里采用灵神的方法，交叉

拷贝节点的时候，将他放在原节点的后面，比如：

1->2->3

1->1’->2->2’->3->3’

然后这样的话，我们1节点的random.next就是next节点的random

然后最后的时候我们在挑出复制的节点

就完成了拷贝

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

还是那句话，遇到这种基本计算器，我们就使用栈来解决

我们的栈用来存放先前的结果和符号，然后数字采用累加的方法。这里没有乘除，不需要优先级

class Solution224A{
    public int calculate(String s){
            int res = 0;
            int num = 0;
            int sign = 1; // 当前符号，1 表示正，-1 表示负
            Deque<Integer> stack = new LinkedList<>();
            for(int i=0;i<s.length();i++){
                char ch = s.charAt(i);
                if (Character.isDigit(ch)){
                    num = num*10+(ch-'0');
                }else if (ch=='+'){
                    res  +=sign*num;
                    num = 0;
                    sign = 1;
                }else if (ch=='-'){
                    res +=sign*num;
                    num = 0;
                    sign=-1;
                } else if (ch=='('){
                    stack.push(res);
                    stack.push(sign);
                    res= 0;
                    sign =1;
                }else if (ch==')'){
                    res +=sign*num;
                    num = 0;
                    int preSign = stack.pop();
                    int preRes = stack.pop();
                    res = preRes+preSign*res;
                }
            }
            res +=sign*num;
            return res;
    }
}

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

我想的是找到最大值，他的下一个数就是最小值，如果在最后的话，就是第一个元素。

直接遍历的话肯定不行

我这个思路out

class Solution153{
    public int findMin(int[] nums){
        int left = 0,right = nums.length-1;
        if (nums[left]<nums[right]) return nums[0];
        while (left<right){
            int mid = (left+right)>>>1;
            if (nums[mid]>nums[right]){
                left = mid+1;
            }else {
                right = mid;
            }
        }
        return nums[left];
    }
}

我们还是使用二分查找把

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

这个本质上是有向环问题

构建邻接表

List<Integer>[] g = new ArrayList[numCourses];
Arrays.setAll(g, i -> new ArrayList<>());
for (int[] p : prerequisites) {
    g[p[1]].add(p[0]); // b -> a（学 a 前要学 b）
}

构建颜色数组，

颜色值	状态	含义
`0`	未访问	初始状态
`1`	正在访问中	在 DFS 栈上（路径上）
`2`	已访问完成	DFS 已经遍历完

遍历，每个课程看是不是有环

private boolean dfs(int x, List<Integer>[] g, int[] colors) {
    colors[x] = 1; // 标记为正在访问

    for (int y : g[x]) {
        // 如果邻接节点 y 也正在访问（回到路径中前面的点了），说明有环
        if (colors[y] == 1 || (colors[y] == 0 && dfs(y, g, colors))) {
            return true; // 有环
        }
    }

    colors[x] = 2; // 所有子节点访问完，标记为已完成
    return false; // 无环
}

class Solution207{
    public boolean canFinish(int numCourses, int[][] prerequisites){
        List<Integer>[] g  = new ArrayList[numCourses];
        Arrays.setAll(g,i->new ArrayList<>());;
        for (int[] p : prerequisites) {
            g[p[1]].add(p[0]);
        }

        int[] colors =new int[numCourses];
        for (int i=0;i<numCourses;i++){
            if (colors[i]==0&&dfs(i,g,colors)){
                return false;
            }

        }
        return true;
    }
    private boolean dfs(int x, List<Integer>[] g, int[] colors){
        colors[x]=1;
        for (int y:g[x]){
            if (colors[y]==1||colors[y]==0&&dfs(y,g,colors)){
                return true;
            }
        }
        colors[x]=2;
        return false;
    }
}

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution79A{
    public boolean exist(char[][] board, String word) {
        int r = board.length;
        int t = board[0].length;
        boolean[][] visited = new boolean[r][t];
        for (int i=0;i<r;i++) {
            for (int j = 0; j < t; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, word, i, j, 0, visited)) {
                        return true;
                    }

                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int row, int col, int index, boolean[][] visited){
        if (index==word.length()){
            return true;
        }
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
                board[row][col] != word.charAt(index) || visited[row][col]) {
            return false;
        }
        visited[row][col]=true;
        boolean found = dfs(board, word, row + 1, col, index + 1, visited) ||
                dfs(board, word, row - 1, col, index + 1, visited) ||
                dfs(board, word, row, col + 1, index + 1, visited) ||
                dfs(board, word, row, col - 1, index + 1, visited);
        visited[row][col]= false;
        return found;
    }
}

使用搜推的方法来完成，主要就是dfs去寻找

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

使用回溯法，

先将数组排序，交换从0开始遍历，交换下一个数字数字，然后回溯。进行递归

class Solution47AA {
    List<Integer> nums;
    List<List<Integer>> res;

    void swap(int a, int b) {
        int tmp = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, tmp);
    }

    void dfs(int x) {
        if (x == nums.size() - 1) {
            res.add(new ArrayList<>(nums));
            return;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i = x; i < nums.size(); i++) {//固定x
            if (set.contains(nums.get(i))) {
                continue;
            }
            set.add(nums.get(i));
            swap(i, x);
            dfs(x + 1);
            swap(x, i);
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.res = new ArrayList<>();
        this.nums = new ArrayList<>();
        for (int num : nums) {
            this.nums.add(num);
        }
        dfs(0);
        return res;
    }
}

402. 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

class Solution402A {
    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder();
        for(char ch:num.toCharArray()){
            while (!sb.isEmpty()&&ch<sb.charAt(sb.length()-1)&&k>0){
                sb.deleteCharAt(sb.length()-1);
                k--;
            }
            sb.append(ch);
        }
        while (!sb.isEmpty()&&k>0){
            sb.deleteCharAt(sb.length()-1);
            k--;
        }
        while (!sb.isEmpty()&&sb.charAt(0)=='0'){
            sb.deleteCharAt(0);
        }
        return sb.isEmpty()?"0":sb.toString();

    }
}