算法盛宴：经典题解与实战策略

本文最后更新于：15 天前

生命的旅程就像一场冒险，每一步都充满了未知与惊喜。

破冰

  • 栏目介绍：

这是一个新的系列，该博文原名为 “冲刺蓝桥杯”，是 2023/04/14晚创建的，当时看了黑马阿玮老师的一个视频，有感而发新增的博文，也是我的博客中，最早的一批文章了

🥣 这篇博文长久以来并没有什么内容，原内容我已经保存在最下面的 “前世今生” 栏目中（好中二的栏目，哈哈哈）

🔥 我决定将该博文改造为全新的算法题目实战相关博文，开启一个全新的系列

🍖 我将在这篇博文下，给出常见的面试算法题 / 蓝桥杯赛题的题解，持续磨练自己的算法能力

今晚，命运的齿轮开始转动

🍖 推荐阅读：交换排序—冒泡排序 | 智能后端和架构 (yijiyong.com)

思维碰撞

废话少说，直接进入正题

力扣算法题打卡 Day 1

2023年11月10日

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 虚拟头节点
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode ans = new ListNode(-1);
        ListNode cur = head;
        
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        return ans.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 直接反转
class Solution {
    public ListNode reverseList(ListNode head) {
   	    ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

优雅的递归法：（2024/01/22晚）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
        return head;

           ListNode last =  reverseList(head.next);
           head.next.next = head;
           head.next = null;

           return last;
    }
}

合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 思路清晰的写法
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // write code here
        ListNode newHead = new ListNode(-1);
        ListNode res = newHead;
        // 1.两链表均不为空
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                newHead.next = list1;
                list1 = list1.next;
            } else if (list1.val > list2.val) {
                newHead.next = list2;
                list2 = list2.next;
            } else { //相等的情况，分别接两个链
                newHead.next = list2;
                list2 = list2.next;
                newHead = newHead.next;
                newHead.next = list1;
                list1 = list1.next;
            }
            newHead = newHead.next;
        }
        // 2.链表b为空
        while (list1 != null) {
            newHead.next = list1;
            list1 = list1.next;
            newHead = newHead.next;
        }
        // 3.链表a为空
        while (list2 != null) {
            newHead.next = list2;
            list2 = list2.next;
            newHead = newHead.next;
        }

        return res.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 简化后的写法
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        
        // 节点之间的比较，简化为两种情况
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }

        // 一条链表合并完成，直接拼接剩余链表的节点即可
        prev.next = list1 == null ? list2 : list1;
        return prehead.next;
    }
}

有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean isValid(String s) {
        if (s.length() <= 1) {
            return false;
        }
        // 1.构造HashMap
        Map<Character, Character> smap = new HashMap<>();
        smap.put('(', ')');
        smap.put('{', '}');
        smap.put('[', ']');
        // 2.构造栈
        Stack<Character> stack = new Stack<>();
        // 3.遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char item = s.charAt(i);
            // 入栈左括号
            if (smap.containsKey(item)) {
                stack.push(item);
                //检查右括号
            } else {
                if (stack.isEmpty()) {
                    return false;
                }

                Character left = stack.pop();
                char rightChar = smap.get(left);
                if (rightChar != item) {
                    return false;
                }
            }
        }
        //
        return stack.isEmpty();
    }
}

最小栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class MinStack {
    private Stack<Integer> stack;  
    private Stack<Integer> minStack;  

    public MinStack() {
    stack = new Stack<>();  
        minStack = new Stack<>();  
    }
    
    public void push(int val) {
 	stack.push(val);  
        if (minStack.isEmpty() || val <= minStack.peek()) {  
            minStack.push(val);  
        }  
    }
    
    public void pop() {
 	if (stack.peek().equals(minStack.peek())) {  
            minStack.pop();  
        }  
        stack.pop();  
    }
    
    public int top() {
 	return stack.peek();  
    }
    
    public int getMin() {
 	return minStack.peek();  
    }
}

力扣算法题打卡 Day 2

2023年11月11日

删除倒数第 K 个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 双指针法
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
   	    // 虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 快慢指针
        ListNode first = head;
        ListNode second = dummy;
        // 快指针先走n步
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        // 快慢指针同时走
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        // 删除节点
        assert second.next != null;
        second.next = second.next.next;
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 压栈法
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 栈
        Deque<ListNode> stack = new LinkedList<ListNode>();
        // 全部压入栈
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 依次出栈，删除第n个节点
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        assert prev != null;
        prev.next = prev.next.next;
        // 返回头节点
        return dummy.next;
    }
}

删除所有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
 
        //虚拟节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        // 找重复元素
        while (cur.next != null && cur.next.next != null) {
            // 找到重复元素
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                // 删除所有重复元素
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        
        // 返回头节点
        return dummy.next;
    }
}

二叉树层序遍历（分层）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点放入队列中，然后不断遍历队列
        queue.add(root);
        while (queue.size() > 0) {
            //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
            //如果节点的左/右子树不为空，也放入队列中
            for (int i = 0; i < size; ++i) {
                TreeNode t = queue.remove();
                tmp.add(t.val);
                if (t.left != null) {
                    queue.add(t.left);
                }
                if (t.right != null) {
                    queue.add(t.right);
                }
            }
            //将临时list加入最终返回结果中
            res.add(tmp);
        }
        return res;
    }
}

二叉树右视图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

力扣算法题打卡 Day 3

2023年11月12日

两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
              // 数组元素值 -> 对应下标
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
      .          return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

区间反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 头插法
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
  // 1.定义头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 2.pre来到left - 1个节点处，记录
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 3.pre来到right节点处，记录
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 4.截断链表
        ListNode leftNode = pre.next;
        ListNode succ = rightNode.next;

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

        // 5.反转链表
        reverseList(leftNode);

        // 6.拼接链表
        pre.next = rightNode;
        leftNode.next = succ;
        
        return dummyNode.next;
    }

     public static ListNode reverseList(ListNode head) {
        ListNode ans = new ListNode(-1);
        ListNode cur = head;
         
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        return ans.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 穿针引线法
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 1.定义虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        
        // 2.pre到达left前一节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 3.cur指向left
        ListNode cur = pre.next;
        ListNode next;
        // 4.反转链表
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        // 5.返回头节点
        return dummyNode.next;
    }
}

链表第一个公共节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 链表拼接法
public class Solution {
    public ListNode getIntersectionNode(ListNode pHead1, ListNode pHead2) {
 //        System.out.println("null == null" + (null == null));
        // 1.判断链表是否为空
        if (pHead1 == null || pHead2 == null) {
            return null;
        }

        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        // 2.依次遍历两条链表
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            if (p1 != p2) {// 这个判断不能少
                // 2.1.链表a遍历完, 切换遍历链表b
                if (p1 == null) {
                    p1 = pHead2;
                }
                // 2.2.链表b遍历完, 切换遍历链表a
                if (p2 == null) {
                    p2 = pHead1;
                }
            }
        }
        // 3.返回第一个公共节点
        return p1;
    }
}

更加清晰易懂的解法：（2023/01/22晚）

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 压栈法
public class Solution {
    public ListNode getIntersectionNode(ListNode pHead1, ListNode pHead2) {
          // 1.判断链表是否为空
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // 2.保存两链表头节点
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        // 3.通过Hash存储链表a的所有节点
        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        // 4.从头结点开始, 依次比较hash表中的节点与链表b的节点
        while (current2 != null) {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }
        // 5.未发现公共节点
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// hash 辅助
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 1.将两条链表从头节点开始, 分别压入栈中
        Stack<ListNode> stackA = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();
        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }
        // 2.两栈依次出栈, 当栈顶元素相同时, 保存该元素
        ListNode preNode = null;
        while (stackB.size() > 0 && stackA.size() > 0) {
            if (stackA.peek() == stackB.peek()) {
                preNode = stackA.pop();
                stackB.pop();
            } else {
                break;
            }
        }
        // 3.返回第一个公共节点
        return preNode;
    }
}

两两交换链表中的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 1.虚拟头节点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        
        while (cur.next != null && cur.next.next != null) {
            // 2.拿取反转两节点
            ListNode node1 = cur.next;
            ListNode node2 = cur.next.next;
            // 3.两两反转
            cur.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            cur = node1;
        }
        // 4.返回头节点
        return dummyHead.next;
    }
}

合并K个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for (ListNode list : lists) {
            res = mergeTwoListsMoreSimple(res, list);
        }
        return res;
    }

       public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
           
        // 节点之间的比较，简化为两种情况
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 一条链表合并完成，直接拼接剩余链表的节点即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}

二叉树锯齿型遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
         List<List<Integer>> result = new ArrayList<>();  
        if (root == null) {  
            return result;  
        }  
          
        Queue<TreeNode> queue = new LinkedList<>();  
        queue.add(root);  
        boolean isLeftToRight = true; // 标记是否从左到右遍历  
          
        while (!queue.isEmpty()) {  
            int levelSize = queue.size();  
            Deque<Integer> levelList = new LinkedList<>();  
              
            for (int i = 0; i < levelSize; i++) {  
                TreeNode node = queue.poll();  
                if (isLeftToRight) {  
                    levelList.addLast(node.val);  
                } else {  
                    levelList.addFirst(node.val);  
                }  
                  
                if (node.left != null) {  
                    queue.add(node.left);  
                }  
                if (node.right != null) {  
                    queue.add(node.right);  
                }  
            }  
            result.add(new ArrayList(levelList));  
            isLeftToRight = !isLeftToRight; // 切换遍历方向  
        }  
        return result;  
    }
}

二叉树的层平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
             List<Double> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);

        while (list.size() != 0) {
            int len = list.size();
            double max = Double.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                TreeNode node = list.poll();

                max = Double.max(max, node.val);
                if (node.left != null) list.add(node.left);
                if (node.right != null) list.add(node.right);
            }
            res.add(max);
        }
        return res;
    }
}

力扣算法题打卡 Day 4

2023年11月13日

合并两个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void merge(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
              int i = nums1_len + nums2_len - 1;
        int len1 = nums1_len - 1, len2 = nums2_len - 1;
        
        while (len1 >= 0 && len2 >= 0) {
            if (nums1[len1] <= nums2[len2])
                nums1[i--] = nums2[len2--];
            else if (nums1[len1] > nums2[len2])
                nums1[i--] = nums1[len1--];
        }
        
        //假如A或者B数组还有剩余
        while (len2 != -1) nums1[i--] = nums2[len2--];
        while (len1 != -1) nums1[i--] = nums1[len1--];
    }
}

反转字符串中的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String reverseWords(String s) {
                  if (s == null || s.length() == 0) {
            return s;
        }
        // 取出首尾空白字符串
        s = s.trim();
        // 分割单词
        String[] split = s.split("\\s+");
        List<String> wordList = Arrays.asList(split);
        // 反转
        Collections.reverse(wordList);
        // 转换为字符串
        return String.join(" ", wordList);
    }
}

验证回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        return sgood.toString().equals(sgood_rev.toString());
    }
}

删除指定元素

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
               int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        //最后剩余元素的数量
        return slow;
    }   
}

力扣算法题打卡 Day 5

2023年11月14日

删除数组中的重复元素

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

轮转数组

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

      public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }}
}

分发糖果

  • 力扣链接：
  • 代码示例：

二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxDepth(TreeNode root) {
      if (root == null) {
            return 0;
        }

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

力扣算法题打卡 Day 6

2023年11月15日

判断两个二叉树是否相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
         if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }

    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;  
        if (p == null || q == null) return false;  
        if (p.val != q.val) return false;  
        Queue<TreeNode> queue = new LinkedList<>();  
        queue.offer(p);  
        queue.offer(q);  
        while (!queue.isEmpty()) {  
            TreeNode node1 = queue.poll();  
            TreeNode node2 = queue.poll();  
            if (node1 != null && node2 != null) {  
                if (node1.val != node2.val) return false;  
                queue.offer(node1.left);  
                queue.offer(node2.left);  
                queue.offer(node1.right);  
                queue.offer(node2.right);  
            } else if (node1 != null || node2 != null) {  
                return false;  
            }  
        }  
        return true;  
    }  
}

存在重复元素Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
     Map<Integer, Integer> map = new HashMap<>();  
        for (int i = 0; i < nums.length; i++) {  
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {  
                return true;  
            }  
            map.put(nums[i], i);  
        }  
        return false;  
    }
}

汇总区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<String> summaryRanges(int[] nums) {
 List<String> res = new ArrayList<>();
        // slow 初始指向第 1 个区间的起始位置
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            // fast 向后遍历，直到不满足连续递增(即 nums[fast] + 1 != nums[fast + 1])
            // 或者 fast 达到数组边界，则当前连续递增区间 [slow, fast] 遍历完毕，将其写入结果列表。
            if (fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]) {
                // 将当前区间 [slow, fast] 写入结果列表
                StringBuilder sb = new StringBuilder();
                sb.append(nums[slow]);
                if (slow != fast) {
                    sb.append("->").append(nums[fast]);
                }
                res.add(sb.toString());
                // 将 slow 指向更新为 fast + 1，作为下一个区间的起始位置
                slow = fast + 1;
            }
        }
        return res;
                          
    }
}

环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Hash表
public class Solution {
    public boolean hasCycle(ListNode head) {
           HashSet<ListNode> set = new HashSet();

           while(head != null){
             if(!set.add(head)){
                return true;
              }
             head = head.next;
           }
            return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 快慢指针
public class Solution {
    public boolean hasCycle(ListNode head) {
               if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int searchInsert(int[] nums, int target) {
                    int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

力扣算法题打卡 Day 7

2023年11月16日

判断子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isSubsequence(String s, String t) {
          int sPointer = 0; // 指向字符串s的指针
        int tPointer = 0; // 指向字符串t的指针

        while (sPointer < s.length() && tPointer < t.length()) {
            if (s.charAt(sPointer) == t.charAt(tPointer)) {
                sPointer++; // 如果当前字符相同，则移动s的指针和t的指针
            }
            tPointer++; // 无论当前字符是否相同，都移动t的指针
        }

        return sPointer == s.length(); // 如果s的指针指向了末尾，说明s是t的子序列
    }
}

最长公共前缀

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

        String prefix = strs[0]; // 将第一个字符串作为初始前缀

        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                // 如果当前字符串不以当前前缀开头，则不断缩小前缀长度
                prefix = prefix.substring(0, prefix.length() - 1);
                
                if (prefix.isEmpty()) {
                    // 如果前缀为空，则说明没有公共前缀，可以直接返回空字符串
                    return "";
                }
            }
        }

        return prefix;
    }
}

多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int majorityElement(int[] nums) {
                   int candidate = nums[0];  // 初始候选元素
        int count = 1;  // 初始计数器为1

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == candidate) {
                count++;  // 相同则计数器加一
            } else {
                count--;  // 不同则计数器减一
            }

            if (count == 0) {
                candidate = nums[i];  // 当计数器变为0时，更换候选元素
                count = 1;  // 并将计数器重置为1
            }
        }

        return candidate;
    }
}

罗马数字转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int romanToInt(String s) {
                 int result = 0;
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);

        for (int i = 0; i < s.length(); i++) {
            if (i < s.length() - 1 && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                // 当前字符比下一个字符小，则减去当前字符对应的数值
                result -= map.get(s.charAt(i));
            } else {
                // 当前字符比下一个字符大或相等，则加上当前字符对应的数值
                result += map.get(s.charAt(i));
            }
        }

        return result;
    }
}

力扣算法题打卡 Day 8

2023年11月17日

快乐数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isHappy(int n) {
                    int slow = n;
        int fast = n;

        do {
            slow = digitSquareSum(slow);  // 慢指针计算平方和一次
            fast = digitSquareSum(fast);  // 快指针计算平方和两次
            fast = digitSquareSum(fast);
        } while (slow != fast);  // 直到两指针相遇

        return slow == 1;  // 最终平方和为1，该数为快乐数
    }

    public static int digitSquareSum(int n) {
        int sum = 0;

        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }

        return sum;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int strStr(String haystack, String needle) {
           int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}

最后一个单词的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLastWord(String s) {
           // 去除首尾空格
        String s_trim = s.trim();
        
        // 拆分成单词数组
        String[] words = s_trim.split(" ");
        
        // 判断是否存在单词
        if (words.length == 0) {
            return 0;
        }
        
        // 返回最后一个单词的长度
        return words[words.length - 1].length();
    }
}

买卖股票的最佳时机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else {
                int profit = price - minPrice;
                maxProfit = Math.max(maxProfit, profit);
            }
        }
    
        return maxProfit;
    }
}

力扣算法题打卡 Day 9

2023年11月18日

力扣算法题打卡 Day 10

2023年11月19日

赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
                    // 创建HashMap存储magazine中字符及其出现次数  
        Map<Character, Integer> charCount = new HashMap<>();  
        for (char c : magazine.toCharArray()) {  
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);  
        }  
  
        // 遍历ransomNote字符串，对每个字符，从HashMap中减去相应的数量  
        for (char c : ransomNote.toCharArray()) {  
            int count = charCount.getOrDefault(c, 0);  
            if (count == 0) {  
                // 如果HashMap中某个字符的数量小于0，说明ransomNote不能由magazine构成  
                return false;  
            } else {  
                charCount.put(c, count - 1);  
            }  
        }  
  
        // 如果遍历结束后都没有出现字符数量小于0的情况，说明ransomNote可以由magazine构成  
        return true;  
    }
}

同构字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean isIsomorphic(String s, String t) {
         if (s.length() != t.length()) {  
            return false;  
        }  
          
        Map<Character, Character> map = new HashMap<>();   
          
        for (int i = 0; i < s.length(); i++) {  
            char c1 = s.charAt(i);  
            char c2 = t.charAt(i);  
              
            // 检查map是否存在映射
            // 1.map存在映射
            if (map.containsKey(c1)) { 
                // 1.1.映射是否正确 
                if (map.get(c1) != c2) {  
                    return false;  
                }  
            // 2.map不存在映射
            } else { 
                // 2.2.映射是否正确 
                if (map.containsValue(c2)) {  
                    return false;  
                }  
                map.put(c1, c2);  
            }  
        }  
          
        return true;  
    }
}

单词规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean wordPattern(String pattern, String s) {
       String[] words = s.split(" ");
        if (words.length != pattern.length()) {
            return false;
        }
        
        HashMap<Character, String> map = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (map.containsKey(c)) {
                if (!map.get(c).equals(words[i])) {
                    return false;
                }
            } else {
                if (map.containsValue(words[i])) {
                    return false;
                }
                map.put(c, words[i]);
            }
        }
        
        return true;
    }
}

有效字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isAnagram(String s, String t) {
     if (s.length() != t.length()) {
            return false;
        }

        int[] counter = new int[26];  // 26个字母

        for (int i = 0; i < s.length(); i++) {
            counter[s.charAt(i) - 'a']++;
            counter[t.charAt(i) - 'a']--;
        }

        for (int count : counter) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

力扣算法题打卡 Day 11

2023年11月20日

二进制求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String addBinary(String a, String b) {
                    StringBuilder result = new StringBuilder();
        int ca = 0;
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0 || ca == 1; i--, j--) {
            int sum = ca;
            if (i >= 0) sum += a.charAt(i) - '0';
            if (j >= 0) sum += b.charAt(j) - '0';
            result.append(sum % 2);
            ca = sum / 2;
        }
        return result.reverse().toString();
    }
}

回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isPalindrome(int x) {
                   if (x < 0) {
            return false;
        }
        int reversed = 0;
        int original = x;
        while (x != 0) {
            int digit = x % 10;
            reversed = reversed * 10 + digit;
            x /= 10;
        }
        return original == reversed;
    }
}

爬楼梯

1
2
3
4
5
6
7
8
9
10
// 递归
class Solution {
    public int climbStairs(int n) {
    if (n <= 2) {  
            return n;  
        }  
  
        return climbStairs(n - 1) + climbStairs(n - 2);  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 动态规划
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {  
            return n;  
        }  
  
        int[] dp = new int[n + 1];  
        dp[1] = 1;  
        dp[2] = 2;  
  
        for (int i = 3; i <= n; i++) {  
            dp[i] = dp[i - 1] + dp[i - 2];  
        }  
  
        return dp[n];  
    }
}

路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        // 叶子节点，查看是否符合要求
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        // 非叶子节点，找左右孩子节点
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();

        queNode.offer(root);
        queVal.offer(root.val);

        while (!queNode.isEmpty()) {
            TreeNode now = queNode.poll();
            int temp = queVal.poll();

            if (now.left == null && now.right == null) {
                if (temp == targetSum) {
                    return true;
                }
                continue;
            }

            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }

            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }

        return false;
    }
}

完全二叉树的节点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int countNodes(TreeNode root) {
              if (root == null) {
        return 0;
    }
    // 拿到左右子树的深度
    int leftDepth = getDepth(root.left);
    int rightDepth = getDepth(root.right);
    // 左子树是满二叉树
    if (leftDepth == rightDepth) {
        return (int) Math.pow(2, leftDepth) + countNodes(root.right);
    // 右子树是满二叉树
    } else {
        return (int) Math.pow(2, rightDepth) + countNodes(root.left);
    }
    }

    public int getDepth(TreeNode node) {
    int depth = 0;
    while (node != null) {
        depth++;
        node = node.left;
    }
    return depth;
}
}

力扣算法题打卡 Day 12

2023年11月21日

数组加一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] plusOne(int[] digits) {
    // 从数组末尾开始遍历
    for (int i = digits.length - 1; i >= 0; i--) {
        // 如果当前数字小于9，则直接加一并返回结果
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        // 当前数字等于9，将其设为0，并继续遍历前一位
        digits[i] = 0;
    }
    // 如果遍历完数组仍然没有返回结果，则说明原数的最高位是9，需要在数组开头插入一个1
    int[] newDigits = new int[digits.length + 1];
    newDigits[0] = 1;
    return newDigits;
    }  
}

X 的平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }
    int left = 1;
    int right = x;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // mid 的平方等于 x
        if (mid == x / mid) {
            return mid;
        } else if (mid < x / mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
    }
}

只出现一次的数字

1
2
3
4
5
6
7
8
9
10
// 异或运算
class Solution {
    public int singleNumber(int[] nums) {
   int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 集合
class Solution {
    public int singleNumber(int[] nums) {
     Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (set.contains(num)) {
            set.remove(num);
        } else {
            set.add(num);
        }
    }
    // 最终集合中只剩下一个元素，即只出现一次的元素
    return set.iterator().next();
    }
}

位1的个数

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
                 int count = 0;
    while (n != 0) {
        count++;
        n &= (n - 1);
    }
    return count;
    }
}

颠倒二进制位

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
                  int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
    }
}

力扣算法题打卡 Day 13

2023年11月22日

未打卡

力扣算法题打卡 Day 14

2023年11月23日

买卖股票的最佳时机（可多次购买）

  • 力扣链接：
  • 代码示例：

跳跃游戏

  • 力扣链接：
  • 代码示例：

最长连续序列

  • 力扣链接：
  • 代码示例：

力扣算法题打卡 Day 15

2023年11月24日

未打卡

力扣算法题打卡 Day 16

2023年11月25日

两数之和（有序数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// map
class Solution {
    public int[] twoSum(int[] numbers, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int complement = target - numbers[i];

            if (map.containsKey(complement)) {
                return new int[]{map.get(complement) + 1, i + 1};
            }
            map.put(numbers[i], i);
        }
       return new int[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 快慢指针
class Solution {
    public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;

    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return new int[]{-1, -1}; // 如果没有找到满足条件的两个数，返回[-1, -1]
    }
}

盛水最多的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
        // 获取高度
        int minHeight = Math.min(height[left], height[right]);
        //计算容积
        int area = minHeight * (right - left);
        maxArea = Math.max(maxArea, area);
        // 左边高度小，左边界移动
        if (height[left] < height[right]) {
            left++;
            // 右边高度小，右边界移动
        } else {
            right--;
        }
    }

    return maxArea;
    }
}

三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
             List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            // 循环中发现了重复元素，直接跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 快慢指针
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                // 计算和
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                //  满足要求，直接添加至结果集
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 跳过相同元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    // 继续寻找
                    left++;
                    right--;

                    // 结果过小，继续寻找
                } else if (sum < 0) {
                    left++;
                    // 结果过大，继续寻找
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

分隔链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public ListNode partition(ListNode head, int x) {
                   if (head == null || head.next == null) {
            return head;
        }

        ListNode lessHead = new ListNode(0);
        ListNode moreHead = new ListNode(0);
        // 虚拟头节点，分别维护大 / 小元素
        ListNode less = lessHead;
        ListNode more = moreHead;

        while (head != null) {
            if (head.val < x) {
                less.next = head;
                less = less.next;
            } else {
                more.next = head;
                more = more.next;
            }
            head = head.next;
        }
        
        // 首尾相连
        more.next = null;
        less.next = moreHead.next;

        return lessHead.next;
    }
}

力扣算法题打卡 Day 17

2023年11月26日

合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，说明不重叠。
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之说明重叠，则将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        
        return Arrays.copyOf(res, idx + 1);
    }
}

字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) 
             return new ArrayList<>();

        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            // 排序字符串
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String keyStr = String.valueOf(ca);
            
            if (!map.containsKey(keyStr)) 
                map.put(keyStr, new ArrayList<>());

            map.get(keyStr).add(s);
        }

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

长度最小的子数组

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

    int sum = 0;
    int start = 0;

    for (int end = 0; end < n; end++) {
        sum += nums[end];
        // 满足条件，尝试压缩长度
        while (sum >= target) {
            ans = Math.min(ans, end - start + 1);
            sum -= nums[start];
            start++;
        }
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

力扣算法题打卡 Day 18

2023年11月27日

力扣算法题打卡 Day 19

2023年11月28日

力扣算法题打卡 Day 20

2023年11月29日

插入区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][2];
        int idx = 0;
        
        // 遍历区间列表：
        // 首先将新区间左边且相离的区间加入结果集
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res[idx++] = intervals[i++];
        }
        
        // 判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，
        // 将最终合并后的新区间加入结果集
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        res[idx++] = newInterval;
        
        // 最后将新区间右边且相离的区间加入结果集
        while (i < intervals.length) {
            res[idx++] = intervals[i++];
        }

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

🍖 注意：

  • 不确保新插入的区间是否能与原区间合并，所以新的区间容量保守加一：
1
int[][] res = new int[intervals.length + 1][2];
  • 区间插入成功后，如果未发生合并，直接返回 res 数组是没问题的。
  • 但如果发生了合并，则新数组的容量是多一位的，直接返回 res 就会出问题：

image-20240112105943078

  • 而新数组的真实容量大小是由 idx 决定的，直接限制返回数组的容量：（2023/01/12早）
1
return Arrays.copyOf(res, idx);

用最少的箭引爆气球

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

        Arrays.sort(points, (a, b) -> a[0] - b[0]);

        int arrows = 1;
        int end = points[0][1];

        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                arrows++;
                end = points[i][1];
            }
        }

        return arrows;
    }
}

简化路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String simplifyPath(String path) {
            Stack<String> stack = new Stack<>();
        String[] parts = path.split("/");

        for (String part : parts) {
            if (part.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!part.isEmpty() && !part.equals(".")) {
                stack.push(part);
            }
        }

        StringBuilder result = new StringBuilder();
        for (String dir : stack) {
            result.append("/").append(dir);
        }

        return result.length() > 0 ? result.toString() : "/";
    }
}

LRU 缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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; 
    }
}

力扣算法打卡 Day 21

2023年12月6日

无重复字符的最长字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;

        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        // 记录无重复字符最长长度
        int max = 0;
        // 维护左边界
        int left = 0;

        // 重复字符
        for(int i = 0; i < s.length(); i ++){
            char c = s.charAt(i);
            // 左边界前移一位
            if(map.containsKey(c)){
              left = Math.max(left,map.get(c) + 1);
            }
            // 记录元素位置
            map.put(c,i);
            // 记录长度
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}

逆波兰表达式求值

2023年12月5号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;

        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            // 是数字，直接压栈
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
                // 是符号，依次出栈俩数字
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                // 计算之后将结果入栈
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
 
    }

     public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

力扣算法打卡 Day 22

2023年12月8日

除自身以外数组的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public int[] productExceptSelf(int[] nums) {
    int n = nums.length;  
    int[] answer = new int[n];  
    int[] left = new int[n];  
    int[] right = new int[n];  
      
    // 计算每个元素左边所有元素的乘积  
    left[0] = 1;  
    for (int i = 1; i < n; i++) {  
        left[i] = left[i-1] * nums[i-1];  
    }  
      
    // 计算每个元素右边所有元素的乘积  
    right[n-1] = 1;  
    for (int i = n-2; i >= 0; i--) {  
        right[i] = right[i+1] * nums[i+1];  
    }  
      
    // 计算答案  
    for (int i = 0; i < n; i++) {  
        answer[i] = left[i] * right[i];  
    }  
      
    return answer;  
    }
}

加油站

2023年12月5号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalGas = 0;  // 总汽油量  
    int currentGas = 0;  // 当前汽油量  
    int startStation = 0;  // 起始加油站编号  
  
    for (int i = 0; i < gas.length; i++) {  
        totalGas += gas[i] - cost[i];  
        currentGas += gas[i] - cost[i];  
  
        // 如果当前汽油量小于0，表示无法从起始加油站到达当前加油站  
        // 需要将起始加油站设为下一个加油站，并将当前汽油量重置为0  
        if (currentGas < 0) {  
            startStation = i + 1;  
            currentGas = 0;  
        }  
    }  
  
    // 如果总汽油量小于0，表示无法绕环路行驶一周  
    // 返回-1表示无解  
    if (totalGas < 0) {  
        return -1;  
    }  
  
    // 返回起始加油站的编号  
    return startStation;  
    }
}

力扣算法打卡 Day 23

2024年1月6日

冒泡排序

  • 代码示例
1
2
3
4
5
6
7
8
public static void main(String[] args) {
      int[] arr = {64, 34, 25, 12, 22, 11, 90};
      bubbleSort3(arr);
      System.out.println("排序后的数组：");
      for (int i : arr) {
          System.out.print(i + " ");
      }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bubbleSort2(int[] arr) {
        int length = arr.length;
        // 比较轮数
        for (int i = 0; i < length - 1; i++) {
            // 每轮比较几次
            for (int j = 0; j < length - 1 - i; j++) {
                if (arr[j] > arr[j + 1])
                    swap(arr, j, (j + 1));
            }
        }
    }

  public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
  }
  • 优化后：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static void bubbleSort3(int[] arr) {
      int length = arr.length;
      // 比较轮数
      for (int i = 0; i < length - 1; i++) {
          boolean swap = false;
          // 每轮比较几次
          for (int j = 0; j < length - 1 - i; j++) {
              if (arr[j] > arr[j + 1]) {
                  // 发生交换
                  swap(arr, j, (j + 1));
                  swap = true;
              }
          }

          // 打印每轮排序后的数组状态
          System.out.println("Round " + (i + 1) + ": " + Arrays.toString(arr));

          // 未发生交换，已经有序，直接结束
          if (!swap) {
              System.out.println("数组已经有序，直接结束");
              break;
          }
      }
  }

  public static void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
  • 深入理解冒泡排序：比较次数、交换次数、是否发生比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void bubbleSort4(int[] arr) {
       int length = arr.length;
       
       // 比较轮数
       for (int i = 0; i < length - 1; i++) {
           int compareNum = 0;
           int swapNum = 0;
           boolean isSwap = false;
           
           // 每轮比较几次
           for (int j = 0; j < length - 1 - i; j++) {
               // 记录比较次数
               compareNum++;
               if (arr[j] > arr[j + 1]) {
                   // 发生交换
                   swap(arr, j, (j + 1));
                   // 记录是否发生交换
                   isSwap = true;
                   // 记录交换次数
                   swapNum++;
               }
           }

           // 打印每轮排序后的数组状态
           System.out.println("Round " + (i + 1) + ": " + Arrays.toString(arr));
           System.out.println("本轮共比较" + compareNum + "次");
           System.out.println("本轮共交换" + swapNum + "次");

           // 未发生交换，已经有序，直接结束
           if (!isSwap) {
               System.out.println("数组已经有序，直接结束");
               break;
           }
       }
   }

选择排序

  • 代码示例：
1
2
3
4
5
6
7
8
public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectionSort2(arr);
        System.out.println("排序后的数组：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void selectionSort2(int[] arr) {
        int length = arr.length;

        // 选举轮数
        for (int i = 0; i < length; i++) {
            // 选举下标
            int index = i;
            // 遍历选举
            for (int j = i + 1; j < length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }

            swap(arr, i, index);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
  • 优化点：发生选举后作交换、使用位运算交换、不使用临时变量作交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void selectionSort2(int[] arr) {
       int length = arr.length;

       // 选举轮数
       for (int i = 0; i < length; i++) {
           // 选举下标
           int index = i;
           // 遍历选举
           for (int j = i + 1; j < length; j++) {
               if (arr[j] < arr[index]) {
                   index = j;
               }
           }

           // 发生过选举
           if (i != index) {
               swap3(arr, i, index);
           }
       }
   }
1
2
3
4
5
6
7
8
9
10
11
public static void swap2(int[] arr, int i, int j) {
       arr[i] ^= arr[j];
       arr[j] ^= arr[i];
       arr[i] ^= arr[j];
 }

   public static void swap3(int[] arr, int i, int j) {
       arr[i] = arr[i] + arr[j];
       arr[j] = arr[i] - arr[j];
       arr[i] = arr[i] - arr[j];
   }
  • 踩了个大坑，未发生过选举就作交换，即元素与本身作交换，使用后两种交换方法会出问题：

image-20240106092330528

  • 想一想这是为什么，跟引用有关系（2024/01/06早）

插入排序

  • 代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void insertionSort2(int[] arr) {
       int length = arr.length;

       // 从第二个元素开始，选举
       for (int i = 1; i < length; i++) {
           int key = arr[i];
           int j = i - 1;
           // 比 key 大的，后移
           while (j >= 0 && arr[j] > key) {
               arr[j + 1] = arr[j];
               j--;
           }
           // 插入
           arr[j + 1] = key;
       }
   }
  • 优化点：把查找过程改造为二分查找，减少比较次数，这里按下不表

快速排序

一般方法

  • 代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void quickSort2(int[] arr, int low, int high) {
      if (low < high) {
          // 基准值
          int key = arr[high];
          // 分界点
          int i = low - 1;
          
          for (int j = low; j < high; j++) {
              if (arr[j] < key) {
                  i++;
                  swap(arr, i, j);
              }
          }
          
          // 固定基准值，分界
          int index = i + 1;
          swap(arr, index, high);
          
          // 分治法，递归
          quickSort2(arr, low, index - 1);
          quickSort2(arr, index + 1, high);
      }
  }
  • 在语雀画板上画个图就能明白，理解：使用 i 维护分界点；每轮快排之后基准值位置的确定

快慢指针法

  • 代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void quickSort4(int[] arr, int low, int high) {
        // 判断递归结束的条件
        if (low >= high) {
            return;
        }
        // 定义快慢指针、基准值
        int point = arr[low];

        int slow = low;
        int fast = low + 1;

        // 快指针检索大数
        while (fast <= high) {
            // 慢指针维护小数
            if (arr[fast] < point) {
                // todo 0
                slow++;
                int temp = arr[slow];
                arr[slow] = arr[fast];
                arr[fast] = temp;
            }
            fast++;
        }

        // 返回基准值
        // todo 1
        int temp = arr[slow];
        arr[slow] = arr[low];
        arr[low] = temp;

        quickSort4(arr, low, slow - 1);
        quickSort4(arr, slow + 1, high);
    }
  • 重点在于理解：选取基准值为靠左，快指针检索，慢指针维护分界

堆排序

力扣算法打卡 Day 23

2024年1月15日

打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {  
    public int rob(int[] nums) {  
        if (nums == null || nums.length == 0) {  
            return 0;  
        }

        if (nums.length == 1) {  
            return nums[0];  
        }  

        if (nums.length == 2) {  
            return Math.max(nums[0], nums[1]);  
        }  

        int[] dp = new int[nums.length];  
        
        dp[0] = nums[0];  
        dp[1] = Math.max(nums[0], nums[1]);

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

        return dp[nums.length - 1];  
    }  
}

力扣算法打卡 Day 24

2024年1月16日

划分字母区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static List<Integer> partitionLabels(String s) {
       int[] last = new int[26];
       int length = s.length();
       // 记录每个字母出现的最后位置
       for (int i = 0; i < length; i++) {
           last[s.charAt(i) - 'a'] = i;
       }

       List<Integer> partition = new ArrayList<>();
       int start = 0, end = 0;
       
       for (int i = 0; i < length; i++) {
           end = Math.max(end, last[s.charAt(i) - 'a']);

           if (i == end) {
               partition.add(end - start + 1);
               start = end + 1;
           }
       }
       return partition;
   }

子数组最大平均数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static double findMaxAverage(int[] nums, int k) {
      int len = nums.length;
      int windowSum = 0;
      if (k > len || len < 1 || k < 1) {
          return 0;
      }
      // 求第一个窗口的值
      for (int i = 0; i < k; i++) {
          windowSum += nums[i];
      }

      int res = windowSum;
      // 遍历，左边减去一个，右边增加一个
      for (int right = k; right < len; right++) {
          windowSum += nums[right] - nums[right - k];
          res = Math.max(res, windowSum);
      }

      return (double) res / k;
  }

最长连续递增序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findLengthOfLCIS(int[] nums) {
     int left = 0;
     int right = 0;
     int res = 0;
     
     while (right < nums.length) {
         if (right > 0 && nums[right - 1] >= nums[right]) {
             left = right;
         }
         right++;
         res = Math.max(res, right - left);
     }
     return res;
 }

最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longestStreak = 0;

        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

力扣算法打卡 Day 25

2024年1月17日

长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;

        while(right < nums.length){
            sum += nums[right];
            while(sum>= target){
                min = Math.min(min,right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

其中，核心代码可以改写为：

1
2
3
4
5
6
7
while(right < nums.length){
           sum += nums[right++];
           while(sum>= target){
               min = Math.min(min,right - left);
               sum -= nums[left++];
           }
       }

算法佛脚 120 题

链表

栈、队列和 Hash

1、栈实现

实现一个简单的栈，支持入栈、出栈、弹出栈顶元素、判空操作
  • 数组实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Mystack<T> {    
    // 内部数组
    Object[] stack = null;

    // 栈顶
    int top;

    public Mystack() {
        this.stack = new Object[10];
        this.top = 0;
    }

    // 入栈
    public void push(T t) {
        expandCapacity(top + 1);

        this.stack[top] = t;
        top++;
    }

    // 弹出栈顶元素
    public T peek() {
        T t = null;

        if (!isEmpty()) {
            t = (T) this.stack[top - 1];
        }

        return t;
    }

    // 出栈
    public T pop() {
        T t = this.peek();

        if (!isEmpty()) {
            this.stack[top - 1] = null;
            top--;
        }

        return t;
    }

    // 判空
    public Boolean isEmpty() {
        return top == 0;
    }

    // 栈容量
    public int getSize() {
        return stack.length;
    }

    // 扩容
    public void expandCapacity(int size) {
        if (size > getSize()) {
            size = size + size >> 1;
            Arrays.copyOf(this.stack, size);
        }
    }

    public static void main(String[] args) {
        Mystack<String> stack = new Mystack<>();
        System.out.println(stack.peek());
        System.out.println(stack.isEmpty());
        stack.push("java");
        stack.push("is");
        stack.push("beautiful");
        stack.push("language");
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.peek());
    }
}
  • 测试结果如下：

image-20231106191028733

  • 链表实现（2023/11/06晚）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class ListStack<T> {
    public int size;

    static class Node<T> {
        public T t;
        public Node next;

        public Node(T t) {
            this.t = t;
            this.next = null;
        }
    }

    // 内部链表
    public Node head;

    public ListStack() {
        head = null;
    }

    // 入栈
    public void push(T t) {
        if (!isEmpty()) {
            Node<T> newNode = new Node<>(t);
            newNode.next = head;
            head = newNode;
        } else {
            head = new Node(t);
        }
        this.size++;
    }

    // 弹出栈顶元素
    public T peek() {
        T t = null;
        if (!isEmpty()) {
            t = (T) head.t;
        }

        return t;
    }

    // 出栈
    public T pop() {
        T t = null;

        if (!isEmpty()) {
            t = peek();
            head = head.next;
            this.size--;
        }

        return t;
    }

    // 判空
    public Boolean isEmpty() {
        return head == null;
    }

    // 栈容量
    public int getSize() {
        return this.size;
    }

    public static void main(String[] args) {
        ListStack<String> stack = new ListStack<>();
        System.out.println(stack.peek());
        System.out.println(stack.isEmpty());
        System.out.println(stack.getSize());
        stack.push("java");
        stack.push("is");
        stack.push("beautiful");
        stack.push("language");
        System.out.println(stack.getSize());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.getSize());
        System.out.println(stack.peek());
    }
}
  • 测试结果如下：

image-20231106194059778

2、队列实现

实现一个简单的队列，支持入队、出队、遍历队列、判空操作

  • 链表实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class LinkQueue {
    private Node front;
    private Node rear;
    private int size;

    public LinkQueue() {
        this.front = new Node(0);
        this.rear = new Node(0);
    }

    /**
     * 入队
     */
    public void push(int value) {
        // 尾插法
        Node newNode = new Node(value);
        Node temp = front;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        rear = newNode;
        size++;
    }

    /**
     * 出队
     */
    public int pull() {
        // 头删法
        if (front.next == null) {
            System.out.println("队列已空");
        }
        Node firstNode = front.next;
        front.next = firstNode.next;
        size--;
        return firstNode.data;
    }

    /**
     * 遍历队列
     */
    public void traverse() {
        Node temp = front.next;
        while (temp != null) {
            System.out.print(temp.data + "\t");
            temp = temp.next;
        }
    }

    static class Node {
        public int data;
        public Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    //测试main方法
    public static void main(String[] args) {
        LinkQueue linkQueue = new LinkQueue();
        linkQueue.push(1);
        linkQueue.push(2);
        linkQueue.push(3);
        System.out.println("第一个出队的元素为:" + linkQueue.pull());
        System.out.println("队列中的元素为:");
        linkQueue.traverse();
    }
}
  • 测试结果如下：

image-20231106193809524

3、括号匹配问题

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
    * 括号匹配问题
    *
    * @param s
    * @return
    */
   static boolean isValid(String s) {
       if (s.length() <= 1) {
           return false;
       }
       // 1.构造HashMap
       Map<Character, Character> smap = new HashMap<>();
       smap.put('(', ')');
       smap.put('{', '}');
       smap.put('[', ']');
       // 2.构造栈
       Stack<Character> stack = new Stack<>();
       // 3.遍历字符串
       for (int i = 0; i < s.length(); i++) {
           char item = s.charAt(i);
           // 入栈左括号
           if (smap.containsKey(item)) {
               stack.push(item);
               //检查右括号
           } else {
               if (stack.isEmpty()) {
                   return false;
               }

               Character left = stack.pop();
               char rightChar = smap.get(left);
               if (rightChar != item) {
                   return false;
               }
           }
       }
       //
       return stack.isEmpty();
   }

2.LeetCode 155，设计⼀个⽀持 push ，pop ，top 操作，并能在常数时间内检索到最⼩元素的栈。

3.LeetCode 716.设计⼀个最⼤栈数据结构，既⽀持栈操作，⼜⽀持查找栈中最⼤元素。

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

5.LeetCode150.根据 逆波兰表示法，求表达式的值

6.LeetCode232 请你仅使⽤两个栈实现先⼊先出队列。队列应当⽀持⼀般队列⽀持的所有操作（push、pop、

peek、empty）

7.leetcode225 请你仅使⽤两个队列实现⼀个后⼊先出（LIFO）的栈，并⽀持普通栈的全部四种操作（push、

top、pop 和 empty）。

8.LeetCode1.给定⼀个整数数组 nums 和⼀个整数⽬标值 target，请你在该数组中找出 和为⽬标值 target 的那两

个整数，并返回它们的数组下标。

9.LeetCode146：运⽤你所掌握的数据结构，设计和实现⼀个LRU (最近最少使⽤) 缓存机制

10.LeetCode460：运⽤你所掌握的数据结构，设计和实现⼀个LFU 缓存机制

蓝桥杯热门赛题

终极算法笔记

手把手刷链表算法

  • 双指针：合并链表、分割链表、合并K个有序链表、单链表中点、单链表倒数第K个节点、判断链表是否包含环、判断链表相交
  • 链表反转：反转链表、反转前n个节点、反转区间、K个一组反转链表
  • 判断回文链表：压栈，反转，双指针

简单的链表算法

合并链表

解法思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    
    ListNode p1 = l1, p2 = l2;
    ListNode p = dummy;
    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }
    
    // 一条链表合并完成，直接拼接剩余链表的节点即可
    p.next = p1 == null ? p2 : p1;
    
    return dummy.next;
}

分割链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
ListNode partition(ListNode head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode p1 = dummy1, p2 = dummy2;
     
    // 这里是将一个链表分解成两个链表
    ListNode p = head;
    while (p != null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // 不能直接让 p 指针前进，
        // p = p.next
        // 断开原链表中的每个节点的 next 指针
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // 连接两个链表
    p1.next = dummy2.next;

    return dummy1.next;
}

image-20240130164612234

合并K个有序链表

简单实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for (ListNode list : lists) {
            res = mergeTwoListsMoreSimple(res, list);
        }
        return res;
    }

       public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
           
        // 节点之间的比较，简化为两种情况
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 一条链表合并完成，直接拼接剩余链表的节点即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}

基于优先级队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列，最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

寻找倒数第 K 个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead == null || k <= 0) {
            return null;
        }

        ListNode fast = pHead;
        ListNode slow = pHead;

        // 先让 fast 指针向前移动 k 步
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                // 如果链表的长度小于 k，返回空链表
                return null;
            }
            fast = fast.next;
        }

        // 然后 fast 和 slow 同时向前移动，直到 fast 到达链表尾部
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

删除倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 删除倒数第K个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}
    
private ListNode findFromEnd(ListNode head, int k) {
    // 代码见上文
}

// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

单链表中点

1
2
3
4
5
6
7
8
9
10
11
12
ListNode middleNode(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}

判断链表是否包含环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

链表寻找环起点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        // 上面的代码类似 hasCycle 函数
        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }

        // 重新指向头结点
        slow = head;
        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

img

判断链表相交

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

image-20240130165806976

链表反转

链表反转

递归反转整个链表：

1
2
3
4
5
6
7
8
9
10
// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

迭代反转整个链表：

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
    ListNode ans = new ListNode(-1);
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = ans.next;
        ans.next = cur;
        cur = next;
    }
    return ans.next;
}
1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

反转前 N 个节点

递归反转前 N 个节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

区间反转

递归反转一个区间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

迭代反转一个区间，穿针引线法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 穿针引线法
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 1.定义虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        
        // 2.pre到达left前一节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 3.cur指向left
        ListNode cur = pre.next;
        ListNode next;
        // 4.反转链表
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        // 5.返回头节点
        return dummyNode.next;
    }
}

迭代反转一个区间，头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 头插法
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
  // 1.定义头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 2.pre来到left - 1个节点处，记录
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 3.pre来到right节点处，记录
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 4.截断链表
        ListNode leftNode = pre.next;
        pre.next = null;
        
        ListNode post = rightNode.next;
        rightNode.next = null;

        // 5.反转链表
        reverseList(leftNode);

        // 6.拼接链表
        pre.next = rightNode;
        leftNode.next = post;
        
        return dummyNode.next;
    }

     public static ListNode reverseList(ListNode head) {
        ListNode ans = new ListNode(-1);
        ListNode cur = head;
         
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        return ans.next;
    }
}

K 个一组反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public ListNode reverse(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(-1);
        dummy.next = a;

        while(a != b){
            ListNode next = a.next;
            a.next = dummy.next;
            dummy.next = a;
            a = next;
        }

        return dummy.next;
    }


    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;

        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++){
            if (b == null) return head;
            b = b.next;
        }    

        ListNode newHead = reverse(a, b);

        a.next = reverseKGroup(b, k);
        return newHead;
    }
}

判断回文链表

判断回文链表：压栈，反转，双指针

压栈

压栈法判断回文链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
     * 方法1：全部压栈遍历 全部出栈遍历
     *
     * @param head
     * @return
     */
    public static boolean isPalindromeByAllStack(ListNode head) {
        ListNode temp = head;
        Stack<Integer> stack = new Stack<>();
        // 1.压栈 遍历
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        // 2.出栈 遍历
        while (head != null) {
            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
     * 方法2：全部压栈遍历 一半出栈遍历
     *
     * @param head
     * @return
     */
    public static boolean isPalindromeByHalfStack(ListNode head) {
        if (head == null)
            return true;
        ListNode temp = head;
        Stack<Integer> stack = new Stack<>();
        //链表的长度
        int len = 0;
        //把链表节点的值存放到栈中
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
            len++;
        }
        //len长度除以2
        len >>= 1;
        //然后再出栈
        while (len-- >= 0) {
            if (head.val != stack.pop())
                return false;
            head = head.next;
        }
        return true;
    }

反转

反转链表思路很简单，使用任意一种方法反转链表，同时遍历反转后的链表和原链表，即可判断原链表是否为回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {  
   /**
     * 构造反转链表
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        // 1.构造反转链表

        ListNode ans = new ListNode(-1);
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }

        ListNode newHead = ans.next;
        
        // 2.同时遍历两链表
        while (newHead != null && head != null) {
            if (head.val != newHead.val)
                return false;

            head = head.next;
            newHead = newHead.next;
        }

        return true;
    }
}

正常思路一定是像上面这样，但结果是错误的，因为这样会将原链表反转，而我们需要构造新的反转链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {  
   /**
     * 构造反转链表
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        // 1.构造反转链表

        ListNode ans = new ListNode(-1);
        ListNode temp = head;
        while (temp != null) {
            ListNode cur = new ListNode(temp.val); 

            cur.next = ans.next;
            ans.next = cur;
           
            temp = temp.next;
        }

        ListNode newHead = ans.next;
        
        // 2.同时遍历两链表
        while (newHead != null && head != null) {
            if (head.val != newHead.val)
                return false;

            head = head.next;
            newHead = newHead.next;
        }

        return true;
    }
}

双指针

双指针判断回文字符串：

1
2
3
4
5
6
7
8
9
10
11
12
boolean isPalindrome(String s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

双指针寻找回文字符串：

1
2
3
4
5
6
7
8
9
10
11
String palindrome(String s, int left, int right) {
    // 防止索引越界
    while (left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        // 双指针，向两边展开
        left--;
        right++;
    }
    // 返回以 s[left] 和 s[right] 为中心的最长回文串
    return s.substring(left + 1, right);
}

递归 + 反转实现类双指针判断回文链表：（2024/01/30晚）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
boolean isPalindrome(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if (fast != null)
        slow = slow.next;
    
    ListNode left = head;
    ListNode right = reverse(slow);
    while (right != null) {
        if (left.val != right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    
    return true;
}

ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

牛客 TOP 100

2024年2月27日

链表反转：

  • 迭代：定义虚拟节点；从节点1开始，根据虚拟节点后继，设置每个节点后继；更新虚拟节点后继；节点向后移动，提前更新节点后继。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
      // 定义虚拟节点
      ListNode ans = new ListNode(0);
      // 根据虚拟节点后继，设置每个节点后继
      ListNode cur = head;
      while(cur != null){
        ListNode next = cur.next;
	    // 设置每个节点后继
        cur.next = ans.next;
        // 更新虚拟节点后继
        ans.next = cur;
	    // 节点向后移动
        cur = next;
      }

      return ans.next;
    }
  • 递归：校验节点是否为空；设置终止条件，递归到最后一个节点停止；开始回溯，设置节点后继；断掉新后继节点的原先后继；向外抛回新的头节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param head ListNode类 
   * @return ListNode类
   */
  public ListNode ReverseList (ListNode head) {
      // write code here
      if(head == null){
          return head;
      }

      if(head.next == null){
          return head;
      }

      ListNode last = ReverseList(head.next);
      head.next.next = head;
      head.next = null;

      return last;
  }

区间反转：

  • 迭代（头插法）：定义虚拟节点；迭代，单独拿到左右区间节点，断开与整体联系；链表反转，反转区间；反转完成，拼接链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
      ListNode dummy = new ListNode(0);
      dummy.next = head;

      ListNode pre = dummy;
      for(int i = 0; i < m - 1; i++){
        pre = pre.next;
      }
     
      ListNode rightNode = pre;
      for(int i = 0; i < n - m + 1; i++){
        rightNode = rightNode.next;
      }

      ListNode leftNode = pre.next;
      pre.next = null;

      ListNode post = rightNode.next;
      rightNode.next = null;

      reverseList(leftNode);

      pre.next = rightNode;
      leftNode.next = post;

      return dummy.next;
    }

     public static ListNode reverseList(ListNode head) {
        ListNode ans = new ListNode(-1);
        ListNode cur = head;
         
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        return ans.next;
    }
}
  • 递归：不搞

合并链表：定义虚拟头节点；两链表均不为空，着手合并；两链表从头比较，优先合并小节点，否则合并大节点；节点向后移动；一条链表合并完毕，直接拼接剩下的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
    * @param pHead1 ListNode类 
    * @param pHead2 ListNode类 
    * @return ListNode类
    */
   public ListNode Merge (ListNode pHead1, ListNode pHead2) {
       // write code here
       ListNode dummy = new ListNode(-1);

       ListNode p1 = pHead1, p2 = pHead2;
       ListNode p = dummy;
       while(p1 != null && p2 != null) {
           if (p1.val > p2.val) {
               p.next = p2;
               p2 = p2.next;
           } else {
               p.next = p1;
               p1 = p1.next;
           } 

           p = p.next;
       }

       p.next = p1 == null ? p2 : p1; 

       return dummy.next;
   }

合并 K 个已排序的链表：从头开始，遍历所有链表头节点，做到两两合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        ListNode res = null;
        for (ListNode list : lists) {
            res = mergeTwoListsMoreSimple(res, list);
        }
        return res;
    }

       public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
           
        // 节点之间的比较，简化为两种情况
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 一条链表合并完成，直接拼接剩余链表的节点即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }

判断链表中是否有环：定义快慢指针，从头开始；只有快指针不为空，且快指针后继不为空（即允许快指针走两步），允许前进；慢指针前进一步，快指针前进两步；快慢指针相遇，说明存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean hasCycle(ListNode head) {
       ListNode slow = head, fast = head;

       while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
               return true;
            }
       }

       return false;
   }

链表中环的入口节点：找到环之后，慢节点从头开始；两节点每次都向前一步，直到相遇；相遇的节点就是环的入口节点。（解释：看图，设定首次相遇位置 P，快慢指针在到达 P 点之前，唯一一次相遇就是在链表的环的入口节点处）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast, slow;
        fast = slow = pHead;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }

        if (fast == null || fast.next == null) {
            return null;
        }

        slow = pHead;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

寻找倒数第 K 个节点：

  • 快慢指针：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param pHead ListNode类
   * @param k int整型
   * @return ListNode类
   */
  public ListNode FindKthToTail (ListNode pHead, int k) {
      if (pHead == null || k <= 0) {
          return null;
      }

      ListNode fast = pHead;
      ListNode slow = pHead;

      // 先让 fast 指针向前移动 k 步
      for (int i = 0; i < k; i++) {
          if (fast == null) {
              // 如果链表的长度小于 k，返回空链表
              return null;
          }
          fast = fast.next;
      }

      // 然后 fast 和 slow 同时向前移动，直到 fast 到达链表尾部
      while (fast != null) {
          fast = fast.next;
          slow = slow.next;
      }

      return slow;
  }
  • 栈

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

  • 集合/哈希辅助：遍历存储第一条链表所有节点，再遍历第二条链表，挨个从集合中查找判断是否有相同节点
  • 链表拼接：两链表同时向后遍历，如果遍历结束，就分别换另一条链表继续遍历。如果两链表相交，则遍历过程中必然会相遇，直接返回即可；如果不相交，则必不会相遇，且一定会同时遍历结束，直接返回了null
  • 压栈：两链表分别压栈，依次出栈，如果节点相同，保存节点，不相同就直接返回最近保存的节点，就是答案

链表相加：

  • 链表反转：
  • 压栈：

判断回文链表：

删除有序链表中的重复元素Ⅰ：

删除有序链表中的重复元素Ⅱ：

蓝桥杯

2024年4月11日

蓝桥杯，五天冲刺计划

第十四届蓝桥杯大赛软件赛省赛Java 大学 B 组

第十三届蓝桥杯大赛软件赛省赛Java 大学 B 组

第十二届蓝桥杯大赛软件赛省赛Java 大学 B 组

第十一届蓝桥杯大赛软件赛省赛Java 大学 B 组

第十届蓝桥杯大赛软件赛省赛Java 大学 B 组

点睛之笔

认识数据结构和算法

  • 数据结构：数据存储的方式 数组，字符串，树，堆，栈，队列，哈希表
  • 算法：数据计算的方式枚举遍历，排序，二分查找，递归，回溯

算法题类型

  • 数学
  • 数组
  • 链表
  • 字符串
  • 哈希表
  • 双指针
  • 递归
  • 栈
  • 队列
  • 树
  • 图与回溯算法
  • 贪心
  • 动态规划

刷题顺序

  • 第一轮：数学 -> 数组 -> 链表 -> 字符串 -> 哈希表 -> 双指针 -> 递归 -> 栈 -> 队列 难度简单 50%
  • 第二轮：数学 -> 数组 -> 链表 -> 字符串 -> 哈希表 -> 双指针 -> 递归 -> 栈 -> 队列 难度中等 50%
  • 第三轮：分治 贪心 动态规划 二叉搜索树 图 50%
  • 第四轮：难
Java > 算法
#经验 #Java
算法盛宴：经典题解与实战策略
http://example.com/2023/04/14/算法盛宴：经典题解与实战策略/
作者
Memory
发布于
2023年4月14日
更新于
2024年4月24日
许可协议