从零开始的 leetcode 之旅

学术专区
21

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;
    }
}
22

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

23

（对立 flag 从不避讳

24

报个名先，15 号截止了

25

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

26

一起报 :face_holding_back_tears:

http://pec.xjtu.edu.cn/info/1191/3901.htm

27

好的喵，凑个热闹（）

28

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

29

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

1 Like
30

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

31

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

32

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

33

记得下周截止报名了（

34

15. 3Sum

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

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;
    }
}
35

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

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;
    }
}
1 Like
36

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;
    }
}
1 Like
37

16. 3Sum Closest

双指针秒了 :face_with_hand_over_mouth:

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;
    }
}
1 Like
39

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;
    }
}
1 Like
40

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

1 Like
41

草你做了多少 N sum

1 Like