从零开始的 leetcode 之旅

从零开始，此前没有任何算法竞赛经验，没有系统刷过题

加油！楼主要坚持啊，暑假一起刷（

基本没做过，启动！

完全没做过，启动！

数据结构与算法，启动！

暑假？

今晚蒜了。因为刚刚突然在群里聊嗨了一直聊到现在。

良好的开始🤣加油捏，寒假一起刷:rofl_kissing_heart:

时间挤不出来一点😭

太吊了。一个 easy 也不会

做了两道有意思的题
Linked List Cycle - LeetCode
Linked List Cycle II - LeetCode

做了。

141. Linked List Cycle

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

142. Linked List Cycle II

这个有点 tricky。要求空间复杂度 $O(1)$ ，又不让 modify linked list。于是看了下讨论区，发现真的是 tricky。

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

877. Stone Game

有点好笑，这个难度为 medium 的题目，答案就只有一行：

class Solution {
  public boolean stoneGame(int[] piles) {
    return true;
  }
}

主要看证明：因为 piles.length 为偶数，所以 Alice 每次都可以选择是拿奇数列还是偶数列，而 Bob 没有选择权利。如果所有奇数 pile 的值之和大于偶数的，那 Alice 每次都拿奇数 index 的，那么 Bob 每次都只能拿偶数 index 的，所以 Alice 永远会赢。and vice versa.

草，我 142 第一次做的太直接了，但是还好能 ac（

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode detected = head;// 要被判断是否是开始循环的结点
        while (detected != null) {    // 下同 141 题 判断是否有循环
            ListNode slow = detected;
            ListNode fast = detected;
            while (fast != null && fast.next != null ) {
                slow = slow.next;
                fast = fast.next.next;
                // 同时判断是否回到要被判断的结点
                if (slow == detected || fast == detected) {
                    return detected;
                }
                if (slow == fast) {
                    break;
                }
            }
            detected = detected.next;
        }
        return null;
    }
}

然后喜提速度最慢一档。后看了讨论区的方法，服了

trade off of time and space. 为了空间有点太舍弃时间了，还不如做标记位（

感觉你这个 worst case time complexity 有 $O(N^2)$

我每日一题呢 😉

12. Integer to Roman

怎么又是无脑题目

class Solution {

    public String intToRoman(int num) {
        StringBuilder roman = new StringBuilder();
        
        if (num / 1000 > 0) {
            roman.append("M".repeat(num / 1000));
            num %= 1000;
        }
        if (num >= 900) {
            roman.append("CM");
            num -= 900;
        }
        if (num >= 500) {
            roman.append("D");
            num -= 500;
        }
        if (num >= 400) {
            roman.append("CD");
            num -= 400;
        }
        if (num / 100 > 0) {
            roman.append("C".repeat(num / 100));
            num %= 100;
        }
        if (num >= 90) {
            roman.append("XC");
            num -= 90;
        }
        if (num >= 50) {
            roman.append("L");
            num -= 50;
        }
        if (num >= 40) {
            roman.append("XL");
            num -= 40;
        }
        if (num / 10 > 0) {
            roman.append("X".repeat(num / 10));
            num %= 10;
        }
        if (num >= 9) {
            roman.append("IX");
            num -= 9;
        }
        if (num >= 5) {
            roman.append("V");
            num -= 5;
        }
        if (num >= 4) {
            roman.append("IV");
            num -= 4;
        }
        if (num > 0) {
            roman.append("I".repeat(num));
        }
        return roman.toString();
    }
}

当然写法可以优化

debug 还要花钱，烂完了。

看 OI wiki 复习了一下 hash table，原来算法竞赛中常用的冲突处理方法是 separate chaining

1. Two Sum

我太成功了，真的。彻底成功。

class Solution {

    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();

        for (int i = 0; i < n; i++) {
            if (m.containsKey(target - nums[i])) return new int[] {i, m.get(target - nums[i])};
            m.put(nums[i], i);
        }
        return null;
    }
}

13. Roman to Integer

没学 Java 这些接口，然后 leet 也没有语法提示，有点讨厌。

class Solution {

    public int romanToInt(String s) {
        int result = 0;
        Map<Character, Integer> m = new HashMap<Character, Integer>();
        m.put('M', 1000);
        m.put('D', 500);
        m.put('C', 100);
        m.put('L', 50);
        m.put('X', 10);
        m.put('V', 5);
        m.put('I', 1);

        for (int i = 0; i < s.length(); i++) {
            int c = m.get(s.charAt(i));
            int next;
            if (i + 1 < s.length()) next = m.get(s.charAt(i + 1));
            else next = 0;
            if (c < next) {
                result += next - c;
                i++;
            } else {
                result += c;
            }
        }
        return result;
    }
}

来玩蓝桥杯罢。这学期把数据结构学完了，寒假突击学习一下 C++ 和算法，明年 4 月冲一下 🥺

（对立 flag 从不避讳

报个名先，15 号截止了

难绷，这么早就可以报名了吗

一起报 🥹

网站正在加载中...

好的喵，凑个热闹（）

算法题就是 Python 和 cpp 是吧，这两个有什么讲究吗（

有 C++，Java，Python 比赛，就选 C++ 呗，算法竞赛一般都用 C++。

不知道今年要不要去，去年坐了四个小时牢 😭

你去年没学过算法肯定坐牢了，一起突击一个寒假，这次就不坐牢了（

找一天弄点真题看看再做打算 🥲

记得下周截止报名了（

15. 3Sum

$O(N^2)$ ，只击败了 30 % 的选手捏 🥲

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        if (nums.length < 3 || nums[0] > 0) return new ArrayList<List<Integer>>() {};

        List<List<Integer>> results = new ArrayList<>();

        // construct hashmap
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            m.put(nums[i], i);
        }

        // main loop
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;

            for (int j = i + 1; j < nums.length - 1; j++) {
                Integer k = m.get(0 - nums[i] - nums[j]);
                if (k != null && k > j) {
                    results.add(Arrays.asList(new Integer[] { nums[i], nums[j], nums[k] }));
                }
                j = m.get(nums[j]);
            }
            i = m.get(nums[i]);
        }

        return results;
    }
}

使用了双指针！还是 $O(N^2)$ 但是省去了构建 Hashmap 的时间，这回打败了 83% 的选手

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> results = new ArrayList<>();
        if (nums.length < 3 || nums[0] > 0) return results;

        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum > 0) k--;
                else if (sum < 0) j++;
                else {
                    results.add(Arrays.asList(new Integer[] { nums[i], nums[j], nums[k] }));

                    int numJ = nums[j];
                    int numK = nums[k];
                    while (j + 1 < nums.length && nums[j] == numJ) j++;
                    while (k - 1 > j && nums[k] == numK) k--;
                }
            }
            while (i + 1 < nums.length && nums[i + 1] == nums[i]) i++;
        }

        return results;
    }
}

167. Two Sum II - Input Array Is Sorted

知道了双指针后，同样类型的就迎刃而解了

class Solution {

    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                return new int[] { i + 1, j + 1 };
            } else if (sum < target) i++;
            else j--;
        }
        return null;
    }
}

16. 3Sum Closest

双指针秒了 🤭

class Solution {

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];

                int dist = target - sum >= 0 ? target - sum : sum - target;
                int closestDist = target - closest >= 0 ? target - closest : closest - target;
                if (dist == 0) return sum;
                else if (dist < closestDist) closest = sum;
                
                if (sum < target) j++;
                else k--;
            }
        }
        return closest;
    }
}

18. 4Sum

竟然有数据溢出的 testcase，以后要多留心 data constraints 了

class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> results = new ArrayList<>();

        for (int i = 0; i < nums.length - 3; i++) {
            long targetI = target - nums[i];
            for (int j = i + 1; j < nums.length - 2; j++) {
                int k = j + 1;
                int l = nums.length - 1;
                long targetJ = targetI - nums[j];
                while (k < l) {
                    long sum = (long) nums[k] + nums[l];
                    if (sum == targetJ) {
                        results.add(Arrays.asList(new Integer[] { nums[i], nums[j], nums[k++], nums[l--] }));
                        
                        while (k < l && nums[k - 1] == nums[k]) k++;
                        while (l > k && nums[l + 1] == nums[l]) l--;
                    }
                    else if (sum < targetJ) k++;
                    else l--;
                }

                while (j + 1 < nums.length - 2 && nums[j + 1] == nums[j]) j++;
            }

            while (i + 1 < nums.length - 3 && nums[i + 1] == nums[i]) i++;
        }
        
        return results;
    }
}

今日摄入过量 two pointers，，，就到这吧

草你做了多少 N sum

应该这就是全部的了吧，我不信他还有 5-sum 6-sum

被简单题破防了，肯定是功力不够，大🔥刷 leetcode 都做了什么前置 😭

我就做了上面几道 🤔 感觉得多学点套路，然后多做

20. Valid Parentheses

考试也懒得复习，算法也懒得学，书也懒得读，觉也懒得睡，感觉人生报废了

class Solution {

    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') st.push(c);
            else if (c == ')') {
                if (!st.empty() && st.peek() == '(') st.pop();
                else return false;
            } else if (c == ']') {
                if (!st.empty() && st.peek() == '[') st.pop();
                else return false;
            } else if (c == '}') {
                if (!st.empty() && st.peek() == '{') st.pop();
                else return false;
            }
        }

        if (!st.empty()) return false;
        return true;
    }
}

22. Generate Parentheses

first try，只打败了 15% 的选手。应该是二叉树形式的递归，时间复杂度 $\sim 2^n$ 。

看了一下标签有动态规划，明天（如果有时间）看一下 oiwiki 的 dp 部分罢。今天就算了，感觉再学也是摸鱼，好讨厌。

class Solution {

    public List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList<>();
        generateParenthesis(results, "", n, n);
        return results;
    }

    private void generateParenthesis(List<String> r, String s, int op, int ed) {
        if (op == 0 && ed == 0 && isWellFormed(s)) r.add(s);
        if (op > 0 && isWellFormed(s + "(")) generateParenthesis(r, s + "(", op - 1, ed);
        if (ed > 0 && isWellFormed(s + ")")) generateParenthesis(r, s + ")", op, ed - 1);
    }

    private boolean isWellFormed(String s) {
        int opCount = 0;
        int edCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') opCount++;
            if (s.charAt(i) == ')') edCount++;
            if (edCount > opCount) return false;
        }
        return true;
    }
}

juicy 打算报 java 组吗？

C++ 组

草，我发现自己写的这个深度优先搜索，其实已经是动态规划了。那个 isWellFormed() 完全是冗余的，删掉之后就打败 88.76% 了。

class Solution {

    public List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList<>();
        generateParenthesis(results, "(", n - 1, n);
        return results;
    }

    private void generateParenthesis(List<String> r, String s, int op, int ed) {
        if (op == 0 && ed == 0) r.add(s);
        if (op > 0 && op <= ed) generateParenthesis(r, s + "(", op - 1, ed);
        if (ed > 0 && op <= ed) generateParenthesis(r, s + ")", op, ed - 1);
    }
}

32. Longest Valid Parentheses

这个 hard 难度的，看了评论区才会

class Solution {

    public int longestValidParentheses(String s) {
        boolean[] mark = new boolean[s.length() + 1];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (!stack.empty()) {
                    mark[stack.pop()] = true;
                    mark[i] = true;
                }
            }
        }

        int longest = 0;
        int current = 0;
        for (int i = 0; i < mark.length; i++) {
            if (mark[i] == true) current++;
            else {
                if (current > longest) longest = current;
                current = 0;
            }
        }

        return longest;
    }
}

优化了一下，now calculates longest on the fly

class Solution {

    public int longestValidParentheses(String s) {
        int longest = 0;
        int leftPos = -1;
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    // successfully close a pair
                    stack.pop();
                    if (!stack.isEmpty()) {
                        longest = (i - stack.peek()) > longest ? i - stack.peek() : longest;
                    } else {
                        longest = (i - leftPos) > longest ? i - leftPos : longest;
                    }
                } else {
                    // invalid closing
                    leftPos = i;
                }
            }
        }

        return longest;
    }
}

水了两道水题

144. Binary Tree Preorder Traversal

145. Binary Tree Postorder Traversal

94. Binary Tree Inorder Traversal

原来编号没在一块，就说怎么找不到，笑死。然而空间只打败了 16%，看了下，用空间低的都开了一个 stack，没用递归，但我觉得没必要卷这点空间。

867. Transpose Matrix

水每日一题

电脑堂堂复活，来做 N Sum

3Sum 第一次 AC 只打败了 34.30% 的人，尽管用了双指针。合理推测是因为用 HashSet 检测是否有重复的列表花费了太多时间。

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        Set<List<Integer>> dupMonitor = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int target = -nums[i];
            int leftPtr = i + 1;
            int rightPtr = nums.length - 1;
            while (leftPtr < rightPtr) {
                if (nums[leftPtr] + nums[rightPtr] > target) {
                    rightPtr--;
                } else if (nums[leftPtr] + nums[rightPtr] < target){
                    leftPtr++;
                } else {
                    List<Integer> newRes = new ArrayList<>();
                    newRes.add(nums[i]);
                    newRes.add(nums[leftPtr]);
                    newRes.add(nums[rightPtr]);
                    if (!dupMonitor.contains(newRes)) {
                        res.add(newRes);
                        dupMonitor.add(newRes);
                    }
                    leftPtr++;
                    rightPtr--;
                }
            }

        }
        return res;
    }
}

改进后就赢了

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int target = -nums[i];
            int leftPtr = i + 1;
            int rightPtr = nums.length - 1;
            while (leftPtr < rightPtr) {
                if (nums[leftPtr] + nums[rightPtr] > target) {
                    rightPtr--;
                } else if (nums[leftPtr] + nums[rightPtr] < target){
                    leftPtr++;
                } else {
                    List<Integer> newRes = new ArrayList<>();
                    newRes.add(nums[i]);
                    newRes.add(nums[leftPtr]);
                    newRes.add(nums[rightPtr]);
                    res.add(newRes);

                    int leftNum = nums[leftPtr];
                    int rightNum = nums[rightPtr];
                    while (leftPtr + 1 < nums.length && nums[leftPtr] == leftNum) leftPtr++;
                    while (rightPtr - 1 > leftPtr && nums[rightPtr] == rightNum) rightPtr--;
                }
            }
            int numI = nums[i];
            while (i + 1 < nums.length && nums[i + 1] == numI) i++;
        }
        return res;
    }
}

https://leetcode.cn/problems/candy/

看题解，伟大无需多言

https://leetcode.cn/problems/candy/solutions/17847/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/

https://leetcode.cn/problems/group-anagrams

输在了一个 java 语法上：

char[] 使用 toString 返回的是地址，不是这个字符数组拼接成的字符串。若要得到对应字符串，最好用：String.valueof()

这个 bug 看了半天怎么都看不出，最后打断点才知道问题出在这里了，气笑了

附上个人题解，貌似是最快的一档。

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            char[] temp = strs[i].toCharArray();
            Arrays.sort(temp);
            String tempString = String.valueOf(temp);

            if (map.containsKey(tempString)) {
                map.get(tempString).add(strs[i]);
            } else {
                List<String> tempList = new ArrayList<>();
                tempList.add(strs[i]);
                map.put(tempString, tempList);
                res.add(tempList);
            }
        }
        return res;
    }
}

https://leetcode.cn/problems/trapping-rain-water

接雨水，本来以为要一次性过 hard 了，结果：

附上最后 AC 的个人题解，动态规划

class Solution {
    public static int trap(int[] height) {
        int len = height.length;
        int waterSum = 0;
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];


        for (int i = 1; i <len - 1; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
        }
        for (int i = len - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
        }

        for (int i = 1; i < len - 1; i++) {
            int water = height[i] > Math.min(leftMax[i], rightMax[i]) ? 0 : Math.min(leftMax[i], rightMax[i]) - height[i];
            waterSum += water;
        }

        return waterSum;
    }
}

你的解答让我的解答显得过于暴力

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int total_rain = 0;
        std::deque<std::pair<int, int>> find_next_not_more;
        // find_next_not_more.first is index, find_next_not_more.second is height, 并且是目前已知的最高的严格小于自身的高度
        for (int i = 0; i < n; i++) {
            if (find_next_not_more.empty()) {
                if (!height[i])
                    continue;
                find_next_not_more.push_front({i, height[i]});
                continue;
            }
            if (height[i] < height[find_next_not_more.front().first]) {
                auto& front = find_next_not_more.front();
                front.second = height[i];
                find_next_not_more.push_front({i, height[i]});
                continue;
            }
            while (!find_next_not_more.empty() &&
                   height[find_next_not_more.front().first] <= height[i]) {
                int h =
                    std::min((height[i] - find_next_not_more.front().second),
                             (height[find_next_not_more.front().first] -
                              find_next_not_more.front().second));
                total_rain += h * (i - find_next_not_more.front().first - 1);
                find_next_not_more.pop_front();
            }
            if (!find_next_not_more.empty()) {
                total_rain +=
                    (std::abs(find_next_not_more.front().second - height[i])) *
                    (i - find_next_not_more.front().first - 1);
                auto& front = find_next_not_more.front();
                front.second = std::max(front.second, height[i]);
            }
            find_next_not_more.push_front({i, height[i]});
        }
        return total_rain;
    }
};

https://leetcode.cn/problems/minimum-window-substring/

这个题做的异常艰难，第一版代码改了半天后发现没法完全不出 bug 的解决最值问题，最后改了好多，才 AC。

感觉还是滑动窗口题做的太少，没有成框架的做题，导致丢三落四，一堆 bug。

最后是 AC 代码：

import java.util.*;

class Solution {
    public static String minWindow(String s, String t) {
        char[] goal = t.toCharArray();
        Map<Character, Integer> letterFreq = new HashMap<>();
        for (char c : goal) {
            letterFreq.put(c, letterFreq.getOrDefault(c, 0) + 1);
        }

        char[] source = s.toCharArray();
        int min = Integer.MAX_VALUE, pos = 0, left = 0, right = 0;

        while (right < source.length) {
            while (right < source.length && !e(letterFreq)) {
                if (letterFreq.containsKey(source[right])) {
                    letterFreq.put(source[right], letterFreq.get(source[right]) - 1);
                }
                right++;
            }

            if (left == 0 && !e(letterFreq)) {
                return "";
            }

            while (left <= right && e(letterFreq)) {
                if (letterFreq.containsKey(source[left])) {
                    letterFreq.put(source[left], letterFreq.get(source[left]) + 1);
                }
                left++;
            }

            if (min > right - left + 1) {
                min = right - left + 1;
                pos = left - 1;
            }
        }

        StringBuffer res = new StringBuffer("");
        for (int i = pos; i < pos + min; i++) {
            res.append(source[i]);
        }

        return res.toString();
    }

    public static boolean e(Map<Character, Integer> lettersFreq) {
        for (int count : lettersFreq.values()) {
            if (count > 0) {
                return false;
            }
        }
        return true;
    }
}

最近做的一些，选点我感觉有意思的。。。

https://leetcode.cn/problems/first-missing-positive/

https://leetcode.cn/problems/search-a-2d-matrix-ii/

https://leetcode.cn/problems/reverse-nodes-in-k-group/

https://leetcode.cn/problems/diameter-of-binary-tree/

你又卷赢我了

继续开刷啊 lz，我实习后每天要摸鱼刷几道
插个眼

:face_holding_back_tears::face_holding_back_tears:

咋还 deque 上了，完全看不懂啊！我也要追随大佬的脚步！

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> pos;
        pos.push_back(0);
        int lower = 0;
        int ans = 0;
        for (int i = 1; i < height.size(); i++) {
            bool flag = false;
            while (!pos.empty()) {
                int last = pos.back();
                if (height[last] > height[i]) flag = true;
                int fill_to = min(height[last], height[i]);
                ans += (fill_to - lower) * (i - last - 1);
                lower = fill_to;
                if (flag == true) break;
                pos.pop_back();
            }
            pos.push_back(i);
        }
        return ans;
    }
};

思路是考虑每一个新进来的柱子，它会一直贡献到左边比它高的第一个柱子，不难发现这堆柱子是单调的，用一个单调栈维护左边的柱子，每次暴力算出新柱子对答案的贡献，把不大于它的柱子都弹出去，然后把它加进去。还需要维护一个当前填到的高度，直接在每次计算答案的时候更新就行了。

你的做法简洁明了🥰
我的纯逆天做法，我的大脑是一坨浆糊