首页 > 代码库 > LeetCode 全解

LeetCode 全解

2024-09-09 03:40:56   218人阅读

1.Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

使用hash

技术分享 
public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length < 2) {
            return res;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(target - nums[i])) {
                res[0] = map.get(target - nums[i]);
                res[1] = i;
                return res;
            }
            map.put(nums[i], i);
        }
        return res;
    }
View Code

 

2.Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

dummyHead cur控制。carry携带进位

技术分享 
def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummyHead = ListNode(0)
        cur = dummyHead
        carry = 0
        while (l1 or l2):
            sum = 0
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
            sum += carry
            carry = sum / 10
            cur.next = ListNode(sum % 10)
            cur = cur.next
        if carry != 0:
            cur.next = ListNode(carry)
        return dummyHead.next
View Code

 

3.Longest Substring Without Repeating Characters --- not bug free

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

使用数组充当map

注意：left的更新规则，可能有些出现过的点上次出现的位置还在left的左边。最后也需要一个max的操作

技术分享 
 1 public int lengthOfLongestSubstring(String s) {
 2         if (s == null || s.length() == 0) {
 3             return 0;
 4         }
 5         int[] map = new int[128];
 6         Arrays.fill(map, -1);
 7         char[] chars = s.toCharArray();
 8         int n = s.length();
 9         int left = 0;
10         int right = 0;
11         int res = 0;
12         while (right < n) {
13             if (map[chars[right]] == -1) {
14                 map[chars[right]] = right;
15                 right++;
16             } else {
17                 res = Math.max(res, right - left); 
18                 left = Math.max(left, map[chars[right]] + 1); // Attention!
19                 map[chars[right]] = right;
20                 right++;
21             }
22         }
23         res = Math.max(res, right - left);
24         return res; // Attention!
25     }
View Code

 

4.Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

findTopK。检测四个条件：是否一个为空了，是否找第一个，是否其中一个不够 k / 2 了，谁大谁小。

技术分享 
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return 0.0;
        }
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        if (total % 2 == 0) {
            return (findTopK(nums1, 0, m - 1, nums2, 0, n - 1, total / 2) 
                + findTopK(nums1, 0, m - 1, nums2, 0, n - 1, total / 2 + 1)) / 2.0;
        } else {
            return (double)findTopK(nums1, 0, m -1, nums2, 0, n - 1, total / 2 + 1);
        }
    }
    public int findTopK(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        if (start1 > end1) {
            return nums2[start2 + k - 1];
        }
        if (start2 > end2) {
            return nums1[start1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        if (start1 + k / 2 - 1 > end1) {
            return findTopK(nums1, start1, end1, nums2, start2 + k / 2, end2, k - k / 2);
        }
        if (start2 + k / 2 - 1 > end2) {
            return findTopK(nums1, start1 + k / 2, end1, nums2, start2, end2, k - k / 2);
        }
        if (nums1[start1 + k / 2 - 1] > nums2[start2 + k / 2 - 1]) {
             return findTopK(nums1, start1, end1, nums2, start2 + k / 2, end2, k - k / 2);
        } else {
            return findTopK(nums1, start1 + k / 2, end1, nums2, start2, end2, k - k / 2);
        }
    }
View Code

 

LeetCode 全解


联系
我们