力扣HOT100解题记录

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            if (!map.containsKey(target - nums[i])){
                map.put(nums[i], i);
            } else {
                int[] res = {map.get(target - nums[i]), i};
                return res;
            }
        }
        return new int[0];
    }
}

记忆知识点与分析：
暴力法可以解，不过可以用hashmap来用空间换时间，降低计算复杂度

2. 两数相加

我硬写了啥，竟然也能过

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sumNum = l1.val + l2.val;
        ListNode start;
        int addNum;
        if (sumNum <= 9){
            start = new ListNode(sumNum);
            addNum = 0;
        } else {
            start = new ListNode(sumNum % 10);
            addNum = 1;
        }
        ListNode point0 = start;
        ListNode point1 = l1;;
        ListNode point2 = l2;

        while (point1.next != null && point2.next != null){
            sumNum = point1.next.val + point2.next.val + addNum;
            if (sumNum <= 9){
                point0.next = new ListNode(sumNum);
                addNum = 0;
            } else {
                point0.next = new ListNode(sumNum % 10);
                addNum = 1; 
            }
            point0 = point0.next;
            point1 = point1.next;
            point2 = point2.next;
        }

        if (point1.next == null && point2.next == null){
            if (addNum != 0){
                point0.next = new ListNode(1);
            }
            return start;
        }

        if (point1.next != null){
            while (point1.next != null && addNum != 0){
                sumNum = addNum + point1.next.val;
                if (sumNum <= 9){
                    point0.next = new ListNode(sumNum);
                    addNum = 0;
                    point1 = point1.next;
                    point0 = point0.next;
                } else {
                    point0.next = new ListNode(sumNum % 10);
                    addNum = 1;
                    point1 = point1.next;
                    point0 = point0.next;
                }
            }
            if (addNum == 0){
                point0.next = point1.next;
                return start;
            } 
            if (point1.next == null){
                point0.next = new ListNode(1);
                return start;
            }
        }

        if (point2.next != null){
            while (point2.next != null && addNum != 0){
                sumNum = addNum + point2.next.val;
                if (sumNum <= 9){
                    point0.next = new ListNode(sumNum);
                    addNum = 0;
                    point2 = point2.next;
                    point0 = point0.next;
                } else {
                    point0.next = new ListNode(sumNum % 10);
                    addNum = 1;
                    point2 = point2.next;
                    point0 = point0.next;
                }
            }
            if (addNum == 0){
                point0.next = point2.next;
                return start;
            } 
            if (point2.next == null){
                point0.next = new ListNode(1);
                return start;
            }
        }
        return start;
    }
}

官方解答看起来流程简单点

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode point = null;
        int addNum = 0;
        int num1 = l1 == null ? 0 : l1.val;
        int num2 = l2 == null ? 0 : l2.val;
        head = new ListNode((num1 + num2) % 10);
        point = head;
        addNum = (num1 + num2) / 10;
        l1 = l1.next;
        l2 = l2.next;

        while (l1 != null || l2 != null){
            num1 = l1 == null ? 0 : l1.val;
            num2 = l2 == null ? 0 : l2.val;
            point.next = new ListNode((num1 + num2 + addNum) % 10);
            addNum = (num1 + num2 + addNum) / 10;
            point = point.next;
            if (l1 != null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }
        }
        if (addNum != 0){
            point.next = new ListNode(1);
        }
        return head;
    }
}

记忆知识点与分析：
官方解答里，当有一个链表已经到尾巴的时候，需要做下null的判断，避免空指针

3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0){
            return 0;
        }
        int[] longestSubstring = new int[s.length()];
        char[] charArray = s.toCharArray();
        Map indexMap = new HashMap<>();
        longestSubstring[0] = 1;
        indexMap.put(charArray[0], 0);
        for (int i = 1; i < s.length(); i++){
            if (!indexMap.containsKey(charArray[i])){
                longestSubstring[i] = longestSubstring[i - 1] + 1;
                indexMap.put(charArray[i], i);
                continue;
            }
            if (i - indexMap.get(charArray[i]) > longestSubstring[i - 1]){
                longestSubstring[i] = longestSubstring[i - 1] + 1;
                indexMap.put(charArray[i], i);
            } else {
                longestSubstring[i] = i - indexMap.get(charArray[i]);
                indexMap.put(charArray[i], i);
            }   
        }
        int res = Integer.MIN_VALUE;
        for (int num : longestSubstring){
            res = Math.max(res, num);
        }
        return res;
    }
}

记忆知识点与分析：
题目好像在剑指Offer中做过，想了下就用了动态规划，不过当出现重复字符的判断没有判断正确，需要考虑重复字符之间的距离和上个最大字符串长度。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if ((nums1.length + nums2.length) % 2 == 1){
            return findXthNum((nums1.length + nums2.length) / 2 + 1, nums1, nums2);
        } else {
            return (findXthNum((nums1.length + nums2.length) / 2, nums1, nums2) + findXthNum((nums1.length + nums2.length) / 2 + 1, nums1, nums2)) / 2;
        }
    }
    public double findXthNum(int k, int[] nums1, int[] nums2){
        int length1 = nums1.length;
        int length2 = nums2.length;
        int index1 = 0;
        int index2 = 0;
        
        while (true){
            if (index1 == length1){
                return nums2[index2 + k - 1];
            }
            if (index2 == length2){
                return nums1[index1 + k - 1];
            }
            if (k == 1){
                return Math.min(nums1[index1], nums2[index2]);
            }

            int half = k / 2;
            if (nums1[Math.min(index1 + half, length1) - 1] <= nums2[Math.min(index2 + half, length2) - 1]){
                k = k - (Math.min(index1 + half, length1) - index1);
                index1 = Math.min(index1 + half, length1);
                continue;
            }
            if (nums1[Math.min(index1 + half, length1) - 1] > nums2[Math.min(index2 + half, length2) - 1]){
                k = k - (Math.min(index2 + half, length2) - index2);
                index2 = Math.min(index2 + half, length2);
                continue;
            }
        }
    }
}