Leetcode算法解析1-50

2018-08-18 本文已影响27人铛铛铛clark

<center>#1 Two Sum</center>

link
Description:
- Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Input: [2, 7, 11, 15]
Output: [0, 1]
Assumptions:
- each input would have exactly one solution
- you may not use the same element twice

Solution:

Two Sum 的题一般有两种解法，一种是用hash，一种是用两根指针。对于本题来说，用hash只需要遍历一遍数组，所以在时间复杂度上要优于两根指针，因为两个指针的方法是基于排序数组。
Java中提供了HashMap的实现。 Map以数组元素为Key，以索引为Value。
遍历一遍数组，先在map中寻找是否有元素能够和当前值组成sum为target，这个查找是O(1)的复杂度，如果没有，就把当前值和索引作为一个键值对保存在Map中供后续查找，保存也是O(1)的复杂度。Worst Case是遍历整个数组，也就是O(n)。
Code:

# code block
class Solution {
    public int[] twoSum(int[] nums, int target) {
        /*
         * Two Sum的题变种很多，所以第一个要关注的就是Assumption，本题是
         * 最原始的two sum， 只有一个答案， 并且同一个元素不能用两次
         *
         */
        // 校验：本题的assumption确保有至少一个解，所以该步可以省略
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        // intialize the result
        int[] result = new int[0];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result = new int[2];
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                return result;
            }
            map.put(nums[i], i);
        }

        return result;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

<center>#2 Add Two Numbers</center>

link
Description:
- 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:
Output:
Assumptions:
- two numbers do not contain any leading zero, except the number 0 itself.
Solution:
- 注意点：
  - 使用dummy node
  - 处理到所有case：
    - l1 或 l2 位 null
    - l1 l2长度相等
    - l1 长于 l2
    - l2 长于 l1
    - 答案需要进位

Code:

# code block
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    int carrier = 0;
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        int val = l1.val + l2.val + carrier;
        curr.next = new ListNode(val % 10);
        curr = curr.next;
        carrier = val / 10;
        l1 = l1.next;
        l2 = l2.next;
    }
    while (l1 != null) {
        int val = l1.val + carrier;
        curr.next = new ListNode(val % 10);
        curr = curr.next;
        carrier = val / 10;
        l1 = l1.next;
    }
    while (l2 != null) {
        int val = l2.val + carrier;
        curr.next = new ListNode(val % 10);
        curr = curr.next;
        carrier = val / 10;
        l2 = l2.next;
    }
    if (carrier != 0) {
        curr.next = new ListNode(carrier);
    }
    return dummy.next;
}

Time Complexity: O(max(m, n))
Space Complexity: O(1)

<center>#3 Longest Substring Without Repeating Characters</center>

link
Description:
- Given a string, find the length of the longest substring without repeating characters.
Input: "abcabcbb"
Output: 3
Solution:
- 典型的同向型两根指针问题的区间类问题。
- 维持一个符合条件的区间，每次更新最大值

Code:

# code block
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    boolean[] hash = new boolean[256];
    char[] sc = s.toCharArray();
    int result = 0;
    int left = 0, right = 0;
    while (right < sc.length) {
        while (right < sc.length && hash[sc[right]] == false) {
            hash[sc[right]] = true;
            right++;
        }
        result = Math.max(result, right - left);
        hash[sc[left]] = false;
        left++;
    }
    return result;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#4 Median of Two Sorted Arrays</center>

link
Description:
- 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)).
Input: nums1 = [1, 2] nums2 = [3, 4]
Output:2.5
Assumptions:
- At least one of this two arrays has more than 0 element.
Solution:
- 要求时间复杂度为O(log (m+n)), 这题可以由时间复杂度倒推方法
- 满足O(log n)时间复杂度的算法第一个想到的是二分，又是排序数组，更加确定是二分
- 求第k个数，每次把问题缩小到排除不可能的k / 2 个数
- 对两个数组同时找到第k / 2 个数，如果第一个数组中的数小于第二个数组中的数，那么第一个数组中必然不存在第k大的数，可以排除前k / 2 的数，反之同理
- 递归执行，注意递归的出口和corner case

Code:

# code block
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1 == null) {
        // prevent null exception
        nums1 = new int[0];
    }
    if (nums2 == null) {
        nums2 = new int[0];
    }
    int m = nums1.length;
    int n = nums2.length;
    // 1-based index
    int k = (m + n + 1) / 2;
    int median1 = findK(nums1, nums2, 0, 0, k);
    if ((m + n) % 2 == 1) {
        // total number is odd
        return (double)median1;
    }
    int median2 = findK(nums1, nums2, 0, 0, k + 1);
    // Remind of the conversion from int to double
    return (median1 + median2) / 2.0;
}

private int findK(int[] nums1, int[] nums2, int start1, int start2, int k) {
    int m = nums1.length, n = nums2.length;
    if (start1 >= m) {
        return nums2[start2 + k - 1];
    }
    if (start2 >= n) {
        return nums1[start1 + k - 1];
    }
    if (k == 1) {
        return Math.min(nums1[start1], nums2[start2]);
    }
    int mid = k / 2;
     // make sure never drop the val1 when start1 + mid - 1 >= m
    int val1 = (start1 + mid - 1 < m) ? nums1[start1 + mid - 1] : Integer.MAX_VALUE;
    int val2 = (start2 + mid - 1 < n) ? nums2[start2 + mid - 1] : Integer.MAX_VALUE;
    if (val1 < val2) {
        // drop amount of mid number in nums1
        return findK(nums1, nums2, start1 + mid, start2, k - mid);
    } else {
        return findK(nums1, nums2, start1, start2 + mid, k - mid);
    }
}

Time Complexity: O(log (m+n))
Space Complexity: O(1)

<center>#5 Longest Palindromic Substring</center>

link
Description:
- Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Input: "babad"
Output: "bab" or "aba"
Solution:
- 求最长子回文串，brute force的解法是三重循环，一重确定起点，一重确定终点，一重验证是否为回文串。复杂度为O(n^3)
- 这边想到的优化是如果我以一个点为中点，来找以这个点为中点的最长回文串
- 这样一重循环确定中点，一重循环找最长回文串，时间复杂度就降到O(n^2)
- 注意点是回文串要考虑到奇数长度和偶数长度两种特殊情形

Code:

# code block
public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
        return s;
    }
    for (int i = 0; i < s.length(); i++) {
        updateLongest(s, i, i);
        if (i != s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
            updateLongest(s, i, i + 1);
        }
    }
    return s.substring(start, end + 1);
}

private void updateLongest(String s, int l, int r) {
    while (l >= 0 && r < s.length()) {
        if (s.charAt(l) != s.charAt(r)) {
            break;
        }
        if (r - l > end - start) {
            start = l;
            end = r;
        }
        l--;
        r++;
    }
}

private int start = 0;
private int end = 0;

Time Complexity: O(n ^ 2)
Space Complexity: O(1)

<center>#6 ZigZag Conversion</center>

link
Description:
- The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
Input: "PAYPALISHIRING", 3
Output: "PAHNAPLSIIGYIR"
Solution:
- 借用网上摘来的图表达题意
- [图片上传失败...(image-eb60d7-1534568626309)]
- 这是一道模拟题，可以找到规律是以2 * numRows - 2 在循环
- corner case： numRos = 1 时就是原字符串

Code:

# code block
public String convert(String s, int numRows) {
    if (s == null || s.length() <= numRows || numRows <= 1) {
        return s;
    }
    int sep = numRows * 2 - 2;
    char[] sc = s.toCharArray();
    StringBuilder[] sb = new StringBuilder[numRows];
    for (int i = 0; i < sb.length; i++) {
        sb[i] = new StringBuilder();
    }
    for (int i = 0; i < sc.length; i++) {
        int idx = i % sep;
        if (idx < numRows) {
            sb[idx].append(sc[i]);
        } else {
            sb[sep - idx].append(sc[i]);
        }
    }
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < sb.length; i++) {
        result.append(sb[i]);
    }
    return result.toString();
}

Time Complexity: O(n)
Space Complexity: O(n)

<center>#7 Reverse Integer</center>

link
Description: Reverse Integer
- Reverse digits of an integer.
Input: 123
Output: 321
Assumptions:
- return 0 when the reversed integer overflows.
Solution:
- 注意点：
  - 检查overflow，注释位置为详细解法
  - 注意java负数取余为负数

Code:

# code block
public int reverse(int x) {
    boolean isPos = (x >= 0) ? true : false;
    int result = 0;
    while (x / 10 != 0 || x % 10 != 0) {
        int val = result * 10 + Math.abs(x % 10);
        // check overflow
        if (val / 10 != result) {
            return 0;
        }
        result = val;
        x /= 10;
    }
    return isPos? result : -result;
}

Time Complexity: O(number of digits)
Space Complexity: O()

<center>#8 String to Integer (atoi)</center>

link
Description:
- Implement atoi to convert a string to an integer.
- Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
- Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Input: " -0012a42"
Output: -12
Solution:
- 注意考虑所有Corner Case：
  - null
  - empty string
  - positive or negative
  - start with space
  - overflow (max and min are different)
- 方法二：转换成long型来判断

Code:

# code block
public int myAtoi(String str) {
    if (str == null) {
        // prevent null exception
        return 0;
    }
    str = str.trim();
    if (str.length() == 0) {
        // emtpy string
        return 0;
    }
    int result = 0;
    boolean isPos = true;
    char[] sc = str.toCharArray();
    int i = 0;
    // postive or negative
    if (Character.isDigit(sc[0])) {
        isPos = true;
    } else if (sc[0] == '+') {
        isPos = true;
        i = 1;
    } else if (sc[0] == '-') {
        isPos = false;
        i = 1;
    } else {
        return 0;
    }
    for (; i < sc.length; i++) {
        if (!Character.isDigit(sc[i])) {
            // invalid string
            return result;
        }
        if (isPos) {
            int val = result * 10 + sc[i] - '0';
            if (val / 10 != result) {
                // check overflow
                return Integer.MAX_VALUE;
            }
            result = val;
        } else {
            int val = result * 10 + '0' - sc[i];
            if (val / 10 != result) {
                return Integer.MIN_VALUE;
            }
            result = val;
        }
    }
    return result;
}

Time Complexity: O(n)
Space Complexity: O(n)

<center>#9 Palindrome Number</center>

link
Description:
- Determine whether an integer is a palindrome. Do this without extra space.
Input: 121
Output: true
Solution:
- 注意点：
  - 负数肯定不是
  - 注意溢出

Code:

# code block
public boolean isPalindrome(int x) {
    if (x < 0) {
        return false;
    }
    long org = x;
    long reverse = 0;
    while (x / 10 != 0 || x % 10 != 0) {
        reverse = reverse * 10 + x % 10;
        x /= 10;
    }
    return reverse == org;
}

Time Complexity: O(lg n)
Space Complexity: O(1)

<center>#11 Container With Most Water</center>

link
Description:
- Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Input: [1,2,1]
Output: 2
Assumptions:
- You may not slant the container and n is at least 2.
Solution:
- 典型的相向型两根指针问题。面积等于底乘高。当两根指针相向，底只会越来越小，所以只需要找到更高的高与当前最大值比较即可。
- 两根线和x轴组成容器，选取短板做高，所以每次更新短板，就能更新高度。

Code:

# code block
public int maxArea(int[] height) {
    if (height == null || height.length <= 1) {
        return 0;
    }
    int max = 0;
    int left = 0, right = height.length - 1;
    while (left < right) {
        max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#12 Integer to Roman</center>

link
Description:
- Given an integer, convert it to a roman numeral.
Input: 456
Output: "CDLVI"
Assumptions:
- Input is guaranteed to be within the range from 1 to 3999.
Solution:
- 模拟题，要想知道罗马数字的具体规则参考wikipedia

Code:

# code block
class Solution {
    public static final int[] number = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    public static final String[] symbol = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (num != 0) {
            int times = num / number[i];
            if (times != 0) {
                for (int j = 0; j < times; j++) {
                    sb.append(symbol[i]);
                }
                num = num % number[i];
            }
            i++;
        }
        return sb.toString();
    }
}

<center>#13 Roman to Integer</center>

link
Description:
- Given a roman numeral, convert it to an integer.
Input: "CDLVI"
Output: 456
Assumptions:
- Input is guaranteed to be within the range from 1 to 3999.
Solution:
- 模拟题，要想知道罗马数字的具体规则参考wikipedia

Code:

# code block
class Solution {
    public static final int[] number = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    public static final String[] symbol = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    public int romanToInt(String s) {
        int result = 0;
        if (s == null || s.length() == 0) {
            return result;
        }
        StringBuilder sb = new StringBuilder(s);
        int i = 0;
        while (sb.length() > 0 && i < number.length) {
            String curr = symbol[i];
            while (sb.length() >= curr.length() && sb.substring(0, curr.length()).equals(curr)) {
                result += number[i];
                sb.delete(0, curr.length());
            }
            i++;
        }
        return result;
    }
}

<center>#14 Longest Common Prefix</center>

link
Description:
- Write a function to find the longest common prefix string amongst an array of strings.
Input:["aasdfgas", "aaasafda"]
Output:"aa"
Solution:
- 多种解法
- 最巧妙地是排序之后比较首尾
- 二分也可以通过测试

Code:

# code block
public String longestCommonPrefix(String[] strs) {
    StringBuilder result = new StringBuilder();

    if (strs!= null && strs.length > 0){

        Arrays.sort(strs);

        char [] a = strs[0].toCharArray();
        char [] b = strs[strs.length-1].toCharArray();

        for (int i = 0; i < a.length; i ++){
            if (b.length > i && b[i] == a[i]){
                result.append(b[i]);
            }
            else {
                return result.toString();
            }
        }
    return result.toString();
}

Time Complexity: O(n lg n)

Code:

# code block
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int start = 0;
        int end = Integer.MAX_VALUE;
        for (String str : strs) {
            end = Math.min(end, str.length());
        }
        end--;
        while (start < end - 1) {
            int mid = start + (end - start) / 2;
            if (checkValid(mid, strs)) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (checkValid(end, strs)) {
            return strs[0].substring(0, end + 1);
        }
        if (checkValid(start, strs)) {
            return strs[0].substring(0, start + 1);
        }
        return "";
    }

    private boolean checkValid(int n, String[] strs) {
        String tmp = strs[0].substring(0, n + 1);
        for(int i = 1; i < strs.length; i++) {
            if (!strs[i].substring(0, n + 1).equals(tmp)) {
                return false;
            }
        }
        return true;
    }
}

<center>#15 3Sum</center>

link
Description:
- Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1, 0, 1], [-1, -1, 2]]
Assumptions:
- The solution set must not contain duplicate triplets
Solution:
- Two sum 变种。可以简化为固定一个值，在剩下的值中寻找two sum。难点在于去重，去重即联想到排序！所以先把数组排序。if (i != 0 && nums[i] == nums[i - 1]) 就continue这种方法确保了每个数字只取第一个。在two sum中两个while循环确保相同的组合只出现一次。

Code:

# code block
public List<List<Integer>> threeSum(int[] nums) {
     /*
      * 2 Sum的变种， 可以简化为确定一个数a， 在剩下的数中的2 Sum为target - a
      * 难点，去重
      */
     // Initialize the result
     List<List<Integer>> result = new ArrayList<>();
     // Boundary case
     if (nums == null || nums.length < 3) {
         return result;
     }
     // The two pointer solution for two sum is based on sorted array
     Arrays.sort(nums);
     for (int i = 0; i < nums.length - 2; i++) {
         // remove duplicates
         if (i != 0 && nums[i] == nums[i - 1]) {
             continue;
         }
         int left = i + 1, right = nums.length - 1;
         while (left < right) {
             int val = nums[i] + nums[left] + nums[right];
             if (val == 0) {
                 // find one solution
                 List<Integer> solution = new ArrayList<>();
                 solution.add(nums[i]);
                 solution.add(nums[left]);
                 solution.add(nums[right]);
                 result.add(solution);
                 left++;
                 right--;
                 // remove duplicates
                 while (left < right && nums[left] == nums[left - 1]) {
                     left++;
                 }
                 while (left < right && nums[right] == nums[right + 1]) {
                     right--;
                 }
             } else if (val > 0) {
                 // drop the right
                 right--;
             } else {
                 // drop the left
                 left++;
             }
         }
     }
     return result;
 }

Time Complexity: O(n ^ 2)
Space Complexity: O(1)

<center>#16 3Sum Closest</center>

link
Description:
- Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Input: [2, 7, 11, 15]
Output: [0, 1]
Assumptions:
- assume that each input would have exactly one solution.
Solution:
- 3Sum的变种，保存一个与target的差值，每次作比较，小于这个差值即更新答案。
  - 注意点：
  - 三个int相加使用long防止溢出

Code:

# code block
public int threeSumClosest(int[] nums, int target) {
     Arrays.sort(nums);
     long diff = (long)Integer.MAX_VALUE * 2;
     int result = 0;
    // 3 Sum template
     for (int i = 0; i < nums.length - 2; i++) {
         int left = i + 1, right = nums.length - 1;
         while (left < right) {
             long val = nums[i] + nums[left] + nums[right];
             if (Math.abs(val - target) < Math.abs(diff)) {
                 diff = val - target;
                 result = (int)val;
             }
       // when val == target, it must be the answer
             if (val == target) {
                 return target;
             } else if (val > target) {
                 right--;
             } else {
                 left++;
             }
         }
     }
     return result;
 }

Time Complexity: O(n ^ 2)
Space Complexity: O(n)

<center>#17 Letter Combinations of a Phone Number</center>

link
Description:
- Given a digit string, return all possible letter combinations that the number could represent.
- A mapping of digit to letters (just like on the telephone buttons) is given below.
- avator
Input: Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Assumptions:
- The digits are between 2 and 9
Solution:
- 求组合的题，在隐式图上做DFS
- 注意点：
  - 没有明显的回溯痕迹是因为String是immutable的类，每次修改都会形成一个新的对象

Code:

# code block
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        char[] dc = digits.toCharArray();
        dfsHelper(dc, 0, "", result);
        return result;
    }

    private void dfsHelper(char[] dc, int start, String curr, List<String> result) {
        if (start == dc.length) {
            result.add(curr);
            return;
        }
        char[] letters = pad[dc[start] - '0'].toCharArray();
        for (char letter : letters) {
            dfsHelper(dc, start + 1, curr + letter, result);
        }
    }

    public static final String[] pad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
}

<center>#18 4Sum</center>

link
Description:
- Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Input: [1, 0, -1, 0, -2, 2]
Output: [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]
Assumptions:
- solution set must not contain duplicate quadruplets.
Solution:
- Two sum 变种。固定两个值，在剩下的值中做two sum，注意点和3Sum一样还是排序和去重。

Code:

# code block
public List<List<Integer>> fourSum(int[] nums, int target) {
      List<List<Integer>> result = new ArrayList<>();
      if (nums == null || nums.length < 4) {
          return result;
      }
      Arrays.sort(nums);
      for (int i = 0; i < nums.length - 3; i++) {
          if (i != 0 && nums[i] == nums[i - 1]) {
              continue;
          }
          for (int j = i + 1; j < nums.length - 2; j++) {
              if (j != i + 1 && nums[j] == nums[j - 1]) {
                  continue;
              }
              twoSum(nums, j + 1, target, nums[i], nums[j], result);
          }
      }
      return result;
  }

  private void twoSum(int[] nums, int left, int target, int v1, int v2, List<List<Integer>> result) {
      int right = nums.length - 1;
      while (left < right) {
          long val = v1 + v2 + nums[left] + nums[right];
          if (val == target) {
              List<Integer> solution = new ArrayList<>();
              solution.add(v1);
              solution.add(v2);
              solution.add(nums[left]);
              solution.add(nums[right]);
              result.add(solution);
              left++;
              right--;
              while (left < right && nums[left] == nums[left - 1]) {
                  left++;
              }
              while (left < right && nums[right] == nums[right + 1]) {
                  right--;
              }
          } else if (val > target) {
              right--;
          } else {
              left++;
          }
      }
  }

Time Complexity: O(n ^ 3)
Space Complexity: O(1)

<center>#19 Remove Nth Node From End of List</center>

link
Description:
- Given a linked list, remove the nth node from the end of list and return its head.
Input: 1->2->3->4->5 n = 2
Output: 1->2->3->5
Assumptions:
- Given n will always be valid.
- Try to do this in one pass.
Solution:
- 使用dummynode因为可能要删除第一个元素
- 使用两根指针保持距离即可

Code:

# code block
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    ListNode slow = dummy;
    ListNode fast = dummy;
    dummy.next = head;
    for (int i = 0; i < n; i++) {
        if (fast == null) {
            return head;
        }
        fast = fast.next;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#20 Valid Parentheses</center>

link
Description:
- Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
- The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
Input: "()[]{}"
Output: true
Solution:
- 模拟题，用栈来做最适合，注意corner case

Code:

# code block
public boolean isValid(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }
    char[] sc = s.toCharArray();
    Stack<Character> stack = new Stack<>();
    for (char c : sc) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            if (c == ')' && stack.peek() != '(') {
                return false;
            }
            if (c == ']' && stack.peek() != '[') {
                return false;
            }
            if (c == '}' && stack.peek() != '{') {
                return false;
            }
            stack.pop();
        }
    }
    return stack.isEmpty();
}

Time Complexity: O(n)
Space Complexity: O(n)

<center>#21 Merge Two Sorted Lists</center>

link
Description:
- Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Input: 1->3->5->null 2->4->6->7->null
Output:1->2->3->4->5->6->7->null
Solution:
- 归并排序
- 注意所有corner case

Code:

# code block
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        ListNode tmp = null;
        if (l1.val < l2.val) {
            tmp = l1;
            l1 = l1.next;
            tmp.next = null;
        } else {
            tmp = l2;
            l2 = l2.next;
            tmp.next = null;
        }
        curr.next = tmp;
        curr = curr.next;
    }
    if (l1 != null) {
        curr.next = l1;
    }
    if (l2 != null) {
        curr.next = l2;
    }
    return dummy.next;
}

Time Complexity: O(m + n)
Space Complexity: O(1)

<center>#22 Generate Parentheses</center>

link
Description:
- Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Input: 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Solution:
- 排列题，用隐式图DFS遍历
- String 是immutable类，不用特意回溯
- 剪枝：当左边括号和右边括号数量相等时，可以省去加右边括号的搜索

Code:

# code block
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    if (n < 0) {
        return result;
    }
    dfsHelper(0, 0, n, "", result);
    return result;
}

private void dfsHelper(int left, int right, int n, String state, List<String> result) {
    if (left == n && right == n) {
        result.add(state);
    }
    if (left < n) {
        dfsHelper(left + 1, right, n, state + "(", result);
    }
    // 剪枝
    if (right < left) {
        dfsHelper(left, right + 1, n, state + ")", result);
    }
}

<center>#23 Merge k Sorted Lists</center>

link
Description:
- Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Input: [[1,2],[3,6],[4,5]];
Output:[1,2,3,4,5,6]
Solution:
- 归并k个list，往归并排序的方向去想
- 归并排序两个list中去小的那一个的值，k个list就是取k个list中最小的那个值
- 联想到heap， java中有heap的不完全实现priorityqueue
- 要学会写java中的comparator

Code:

# code block
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    Queue<ListNode> pq = new PriorityQueue<>(lists.length + 1, new Comparator<ListNode>() {
        @Override
        public int compare(ListNode a, ListNode b) {
            return a.val - b.val;
        }
    });
    for (ListNode node : lists) {
        if (node != null) {
            pq.offer(node);
        }
    }
    while (!pq.isEmpty()) {
        ListNode min = pq.poll();
        if (min.next != null) {
            pq.offer(min.next);
        }
        curr.next = min;
        curr = curr.next;
    }
    return dummy.next;
}

Time Complexity: O(n lg k)
Space Complexity: O(1)

<center>#24 Swap Nodes in Pairs</center>

link
Description:
- Given a linked list, swap every two adjacent nodes and return its head.
Input: 1->2->3->4
Output: 2->1->4->3
Assumptions:
- Your algorithm should use only constant space.
- You may not modify the values in the list, only nodes itself can be changed.
Solution:
- 链表reverse题，注意哪些指针要改变，注意子函数该返回什么，注意空链表处理

Code:

# code block
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    while ((prev = swap(prev)) != null);
    return dummy.next;
}

// prev->n1->n2->next
// prev->n2->n1->next;
// return n1 if swap, else return null
private ListNode swap(ListNode prev) {
    if (prev.next == null || prev.next.next == null) {
        // No swap needed
        return null;
    }
    ListNode n1 = prev.next;
    ListNode n2 = n1.next;
    ListNode next = n2.next;
    prev.next = n2;
    n2.next = n1;
    n1.next = next;
    return n1;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#25 Reverse Nodes in k-Group</center>

link
Description:
- Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
- k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
- You may not alter the values in the nodes, only nodes itself may be changed.
- Only constant memory is allowed.
Input: 1->2->3->4->5 k = 2
Output: 2->1->4->3->5
Solution:
- 翻转时注意判断是否需要翻转，哪些指针需要被改变，返回什么节点

Code:

# code block
public ListNode reverseKGroup(ListNode head, int k) {
    if (k == 1) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    while ((prev = reverseK(prev, k)) != null);
    return dummy.next;
}

// prev->n1->n2->n3...->nk->next
// prev->nk->nk-1->...->n1->next;
// return n1
private ListNode reverseK(ListNode prev, int k) {
    ListNode nk = prev;
    for (int i = 0; i < k; i++) {
        nk = nk.next;
        if (nk == null) {
            return null;
        }
    }
    ListNode n1 = prev.next;
    ListNode nkPlus = nk.next;
    ListNode left = prev;
    ListNode right = prev.next;
    while (right != nkPlus) {
        ListNode tmp = right.next;
        right.next = left;
        left = right;
        right = tmp;
    }
    prev.next = nk;
    n1.next = nkPlus;
    return n1;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#26 Remove Duplicate</center>

link
Description:
- Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length
- Do not allocate extra space for another array, you must do this in place with constant memory.
Input: [1,1,2]
Output: 2
Assumptions:
- Do not allocate extra space for another array, you must do this in place with constant memory.
Solution:
- 考的就是最基本的去重, 关键在于注释了remove the duplicate的那个if判断

Code:

# code block
public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int idx = 0;
    for (int i = 0; i < nums.length; i++) {
// remove the duplicate
        if (i != 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        nums[idx] = nums[i];
        idx++;
    }
    return idx;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#27 Remove Element</center>

link
Description:
- Given an array and a value, remove all instances of that value in place and return the new length.
- Do not allocate extra space for another array, you must do this in place with constant memory.
- The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Input: [3,2,2,3]
Output: 2
Assumptions:
- Do not allocate extra space for another array, you must do this in place with constant memory.
Solution:
- 考的就是最基本的数组in-place去除元素, 关键在于注释了remove the duplicate的那个if判断

Code:

# code block
public int removeElement(int[] nums, int val) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int idx = 0;
    for (int i = 0; i < nums.length; i++) {
// remove duplicates
        if (nums[i] == val) {
            continue;
        }
        nums[idx++] = nums[i];
    }
    return idx;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#28 Implement strStr()</center>

link
Description:
- Implement strStr().
- Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Input: "asdf" "sd"
Output: 1
Assumptions:
- 有个更优的算法叫KMP算法，此处不做介绍，有兴趣研究可以谷歌或百度
Solution:
- 简单的两重循环，注意corner case

Code:

# code block
public int strStr(String haystack, String needle) {
    if (haystack == null || needle == null) {
        return -1;
    }
    if (needle.length() == 0) {
        return 0;
    }
    if (haystack.length() == 0) {
        return -1;
    }
    for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
        boolean flag = true;
        for (int j = 0; j < needle.length() && j + i < haystack.length(); j++) {
            if (needle.charAt(j) != haystack.charAt(j + i)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return i;
        }
    }
    return -1;
}

Time Complexity: O(n ^ 2)
Space Complexity: O(1)

<center>#29 Divide Two Integers</center>

link
Description:
- Divide two integers without using multiplication, division and mod operator.
- If it is overflow, return MAX_INT.
Input: 123121 67
Output: 1837
Solution:
- 求商不能使用除，余还有乘操作，那么思路一般就是使用位运算
- brute force的方法是累加divisor绝对值直到大于dividend
- 但是使用位运算，左移一位就是两倍，这题可以用对divisor移位来简化复杂度，从n的数量级到lg n
- 这题的难点在于对每一个细节的处理，正负，溢出等等，包括考到正负数最大值的绝对值差1

Code:

# code block
public int divide(int dividend, int divisor) {
    if (divisor == 0) {
        return Integer.MAX_VALUE;
    }
    boolean isPos = true;
    if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
        isPos = false;
    }
    long dividendL = Math.abs((long)dividend);
    long divisorL = Math.abs((long)divisor);
    if (dividendL < divisorL) {
        return 0;
    }
    long factor = 1;
    long cmp = divisorL;
    long result = 0;
    while ((cmp << 1) <= dividendL) {
        cmp <<= 1;
        factor <<= 1;
    }
    while (factor > 0 && dividendL > 0) {
        if (dividendL >= cmp) {
            result += factor;
            dividendL -= cmp;
        }
        factor >>= 1;
        cmp >>= 1;
    }
    if (isPos) {
        return (result < Integer.MAX_VALUE) ? (int)result : Integer.MAX_VALUE;
    } else {
        return (-result > Integer.MIN_VALUE) ? (int)-result : Integer.MIN_VALUE;
    }
}

Time Complexity: O(lg n)
Space Complexity: O(1)

<center>#31 Next Permutation</center>

link
Description:
- Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
- If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
- The replacement must be in-place, do not allocate extra memory.
Input: 1,2,3
Output: 1,3,2
Solution:
- permutation中比较难的题，这题先将排列的树画出来，找规律
- A_NEXT一定与A有尽可能长的公共前缀。
- 如果元素从底向上一直处于递增，说明是对这些元素来说，是没有下一个排列的
- 从后向前比较相邻的两个元素，直到前一个元素小于后一个元素，停止，这样确保A_NEXT 与A有最长的公共前缀
- 下一步是找交换的点，必然是找从底部开始第一个大于停止的那个元素进行交换，能确保最小
- 如果从低到根都是递增，那么下一个元素就是reverse整个数组
- 文字解释有些难以理解，实际情况用实例将全排列的树画出来就能理解

Code:

# code block
public void nextPermutation(int[] nums) {
    if (nums == null || nums.length == 0) {
        return;
    }
    for (int i = nums.length - 2; i >= 0; i--) {
        if (nums[i] >= nums[i + 1]) {
            continue;
        }
        for (int j = nums.length - 1; j > i; j--) {
            if (nums[j] > nums[i]) {
                swap(nums, i, j);
                reverse(nums, i + 1, nums.length - 1);
                return;
            }
        }
    }
    reverse(nums, 0, nums.length - 1);
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        swap(nums, start, end);
        start++;
        end--;
    }
}

Time Complexity: O(n)
- 看似是两重循环嵌套一个reverse，实际上第一个循环找到要交换的第一个点，第二重循环找到要交换的第二个点，对两点间进行reverse，实际是三个O(n)的操作
Space Complexity: O(1)

<center>#33 Search in Rotated Sorted Array</center>

link
Description:
- Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
- (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
- You are given a target value to search. If found in the array return its index, otherwise return -1.
Input: 4 5 6 7 0 1 2, 5
Output: 2
Assumptions:
- You may assume no duplicate exists in the array.
Solution:
- 排序非重复rotated数组，满足二分条件
- 本题难点在于分情况讨论

Code:

# code block
public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int start = 0, end = nums.length - 1;
    while (start < end - 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[start] < nums[end]) {
            // mono increasing
            if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        } else if (nums[mid] <= nums[end]) {
            if (nums[mid] < target && nums[end] >= target) {
                start = mid;
            } else {
                end = mid;
            }
        } else {
            if (nums[mid] > target && nums[start] <= target) {
                end = mid;
            } else {
                start = mid;
            }
        }
    }
    if (nums[start] == target) {
        return start;
    }
    if (nums[end] == target) {
        return end;
    }
    return -1;
}

Time Complexity: O(lg n)
Space Complexity: O(1)

<center>#34 Search for a Range</center>

link
Description:
- Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
- Your algorithm's runtime complexity must be in the order of O(log n).
Input: [5, 7, 7, 8, 8, 10] and target value 8
Output: [3, 4]
Assumptions:
- If the target is not found in the array, return [-1, -1]
Solution:
- 使用两次二分分别找target第一次出现的索引和最后一次出现的索引。
- 使用两次二分是由于worst case 整个数组都是target，两次二分能保证O(lg n)的复杂度。

Code:

# code block
public int[] searchRange(int[] nums, int target) {
    int[] result = new int[2];
    if (nums == null || nums.length == 0) {
        result[0] = -1;
        result[1] = -1;
        return result;
    }
    int start = 0, end = nums.length - 1;
    // find the first occurence of target
    while (start < end - 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] >= target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (nums[start] == target) {
        result[0] = start;
    } else if (nums[end] == target) {
        result[0] = end;
    } else {
        result[0] = -1;
        result[1] = -1;
        return result;
    }

    start = 0;
    end = nums.length - 1;
    // find the last occurence of target
    while (start < end - 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] <= target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    if (nums[end] == target) {
        result[1] = end;
    } else {
        result[1] = start;
    }
    return result;
}

Time Complexity: O(lg n)
Space Complexity: O(1)

<center>#35 Search Insert Position</center>

link
Description:
- Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
Input: [1,3,5,6], 5
Output: 2
Assumptions:
- assume no duplicates in the array.
Solution:
- 搜索排序数组就要想到二分法。这题要找的是第一个>= target的索引。
- 注意点:
  - 使用start < end - 1 是防止栈溢出，如果start = end - 1的话mid就会是start，如果nums[mid] < target就会陷入死循环
  - 从循环跳出会有两种情况， start == end 或 start == end - 1。所以对start和end进行分别处理。

Code:

# code block
public int searchInsert(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int start = 0, end = nums.length - 1;
    while (start < end - 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] >= target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (nums[start] >= target) {
        return start;
    } else if (nums[end] >= target) {
        return end;
    } else {
      // the target is greater than all the numbers in the array
        return end + 1;
    }
}

Time Complexity: O(lg n)
Space Complexity: O(1)

<center>#36 Valid Sudoku</center>

link
Description:
- Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
- The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Input:
Output:
Assumptions:
- A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Solution:
- 注意逻辑要分离

Code:

# code block
public boolean isValidSudoku(char[][] board) {
    return checkRow(board) && checkColumn(board) && checkGrids(board);
}

private boolean checkRow(char[][] board) {
    for (int i = 0; i < 9; i++) {
        boolean[] visit = new boolean[10];
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (visit[board[i][j] - '0']) {
                return false;
            }
            visit[board[i][j] - '0'] = true;
        }
    }
    return true;
}

private boolean checkColumn(char[][] board) {
    for (int j = 0; j < 9; j++) {
        boolean[] visit = new boolean[10];
        for (int i = 0; i < 9; i++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (visit[board[i][j] - '0']) {
                return false;
            }
            visit[board[i][j] - '0'] = true;
        }
    }
    return true;
}

private boolean checkGrids(char[][] board) {
    for (int i = 0; i < 9; i += 3) {
        for (int j = 0; j < 9; j += 3) {
            if (!checkGrid(board, i, j)) {
                return false;
            }
        }
    }
    return true;
}

private boolean checkGrid(char[][] board, int x, int y) {
    boolean[] visit = new boolean[10];
    for (int i = x; i < x + 3; i++) {
        for (int j = y; j < y + 3; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (visit[board[i][j] - '0']) {
                return false;
            }
            visit[board[i][j] - '0'] = true;
        }
    }
    return true;
}

Time Complexity: O(n ^ 2)
Space Complexity: O(n ^ 2)

<center>#38 Count and Say</center>

link
Description:
- The count-and-say sequence is the sequence of integers with the first five terms as following:
- 1 is read off as "one 1" or 11.
- 11 is read off as "two 1s" or 21.
- 21 is read off as "one 2, then one 1" or 1211.
- Given an integer n, generate the nth term of the count-and-say sequence.
- Note: Each term of the sequence of integers will be represented as a string.
Input: 4
Output: "1211"
Solution:
- 模拟题，按照题目的原意模拟过程
- 注意corner case，比如1的时候

Code:

# code block
public String countAndSay(int n) {
    String result = "1";
    for (int i = 2; i <= n; i++) {
        result = countAndSay(result);
    }
    return result;
}

private String countAndSay(String str) {
    int count = 1;
    char say = str.charAt(0);
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) == say) {
            count++;
            continue;
        } else {
            sb.append(count);
            sb.append(say);
            count = 1;
            say = str.charAt(i);
        }
    }
    sb.append(count);
    sb.append(say);
    return sb.toString();
}

<center>#39 Combination Sum</center>

link
Description:
- Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
- The same repeated number may be chosen from C unlimited number of times.
Input: [2, 3, 6, 7]
Output: [[7], [2, 2, 3]]
Assumptions:
- without duplicates
  - All numbers (including target) will be positive integers.
Solution:
- 组合的题，不包含重复数字，可以把组合当做一个隐式图，用DFS对隐式图进行遍历。首先排序，因为排完序之后方便去重，还方便对树进行剪枝。假如第i个数已经大于目标，那后面的数一定也大于目标，不在答案中。
- 注意点：
  - 每找到一个答案要进行deepcopy，因为dfs中用到了回溯，state数组会一直变化。

Code:

# code block
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (candidates == null || candidates.length == 0) {
        return result;
    }
    Arrays.sort(candidates);
    dfsHelper(candidates, target, 0, new ArrayList<Integer>(), result);
    return result;
}

private void dfsHelper(int[] nums, int target, int start, List<Integer> state, List<List<Integer>> result) {
    if (target == 0) {
        result.add(new ArrayList<Integer>(state));
        return;
    }
    for (int i = start; i < nums.length; i++) {
      // 剪枝
        if (nums[i] > target) {
            break;
        }
        state.add(nums[i]);
        // start from i because every number can be used for multiple times.
        dfsHelper(nums, target - nums[i], i, state, result);
        // backtracking
        state.remove(state.size() - 1);
    }
}

<center>#40 Combination Sum II</center>

link
Description:
- Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Input: [10, 1, 2, 7, 6, 1, 5] and target 8
Output: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]
Assumptions:
- All numbers (including target) will be positive integers.
  - The solution set must not contain duplicate combinations
Solution:
- 求组合的题，可重复数字，并且数组中每个数字只能用一次，可以把组合当做一个隐式图，用DFS对隐式图进行遍历。首先排序，因为排完序之后方便去重，还方便对树进行剪枝。假如第i个数已经大于目标，那后面的数一定也大于目标，不在答案中。
- 注意点：
  - 每找到一个答案要进行deepcopy，因为dfs中用到了回溯，state数组会一直变化。
    - 去重方法用remove duplicate注释了

Code:

# code block
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
     List<List<Integer>> result = new ArrayList<>();
     if (candidates == null || candidates.length == 0) {
         return result;
     }
     Arrays.sort(candidates);
     dfsHelper(candidates, target, 0, new ArrayList<Integer>(), result);
     return result;
 }

 private void dfsHelper(int[] candidates, int target, int start, List<Integer> state, List<List<Integer>> result) {
     if (target == 0) {
         result.add(new ArrayList<Integer>(state));
         return;
     }
     for (int i = start; i < candidates.length; i++) {
         if (candidates[i] > target) {
             break;
         }
         // remove duplicates
         if (i != start && candidates[i] == candidates[i - 1]) {
             continue;
         }
         state.add(candidates[i]);
         dfsHelper(candidates, target - candidates[i], i + 1, state, result);
         state.remove(state.size() - 1);
     }

 }

<center>#43 Multiply Strings</center>

link
Description:
- Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
- The length of both num1 and num2 is < 110.
- Both num1 and num2 contains only digits 0-9.
- Both num1 and num2 does not contain any leading zero.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
Input: "123", "456"
Output: "56088"
Solution:
- 暴力方法是直接模拟乘法计算
- 比较优雅的方法可以参考下图
- [图片上传失败...(image-4f2751-1534568626309)]
- 注意点：主要处理trailing zeroes

Code:

# code block
public String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0")) {
        return "0";
    }
    int l1 = num1.length();
    int l2 = num2.length();
    int[] result = new int[l1 + l2];
    for (int i = l1 - 1; i >= 0; i--) {
        for (int j = l2 - 1; j >= 0; j--) {
            int val = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            int sum = result[i + j + 1] + val;
            result[i + j] += sum / 10;
            result[i + j + 1] = sum % 10;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < result.length; i++) {
        if (sb.length() == 0 && result[i] == 0) {
            continue;
        }
        sb.append(result[i]);
    }
    return sb.length() == 0 ? "0" : sb.toString();
}

Time Complexity: O(m * n)
Space Complexity: O(m * n)

<center>#46 Permutations</center>

link
Description:
- Given a collection of distinct numbers, return all possible permutations.
Input:[1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Solution:
- 与排列相比较，需要多一个Set来记录当前状态的值的索引
- 回溯的时候注意不仅要回溯当前状态，也需要回溯Set的值
- 因为是distinct numbers，所以不需要去重

Code:

# code block
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }
    dfsHelper(nums, new HashSet<Integer>(), new ArrayList<Integer>(), result);
    return result;
}

private void dfsHelper(int[] nums, Set<Integer> set, List<Integer> state, List<List<Integer>> result) {
    if (nums.length == set.size()) {
        result.add(new ArrayList<Integer>(state));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (!set.contains(i)) {
            set.add(i);
            state.add(nums[i]);
            dfsHelper(nums, set, state, result);
            // backtracking
            state.remove(state.size() - 1);
            set.remove(i);
        }
    }
}

<center>#47 Permutations II</center>

link
Description:
- Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Input: [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
Solution:
- Permutation 的 follow up，经典的去重题
- 与combination一样，要选代表，不同的就是combination是通过start记录历史，而permutation是使用set
- 去重第一个要想到排序
- 去重的部分使用注释标识了

Code:

# code block
public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }
    Arrays.sort(nums);
    dfsHelper(nums, new HashSet<Integer>(), new ArrayList<Integer>(), result);
    return result;
}

private void dfsHelper(int[] nums, Set<Integer> set, List<Integer> state, List<List<Integer>> result) {
    if (nums.length == set.size()) {
        result.add(new ArrayList<Integer>(state));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // remove duplicate
        if (set.contains(i)) {
            continue;
        }
        // if nums[i] equals to nums[i - 1], then nums[i - 1] must be in the permutation
        // this is the strategy for removing duplicates
        if (i != 0 && nums[i] == nums[i - 1] && !set.contains(i - 1)) {
            continue;
        }

        state.add(nums[i]);
        set.add(i);
        dfsHelper(nums, set, state, result);
        // backtracking
        set.remove(i);
        state.remove(state.size() - 1);
    }
}

<center>#48 Rotate Image</center>

link
Description:
- You are given an n x n 2D matrix representing an image.
- Rotate the image by 90 degrees (clockwise).
- You have to rotate the image in-place, which means you have to modify the input 2D matrix directly.
- DO NOT allocate another 2D matrix and do the rotation.
Input:
```
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
```
Output:
```
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
```
Solution:
- 这其实更像是找规律的题
- 解法一：沿对角线翻转，按行reverse
- 解法二：通过寻找规律可以发现，swap三次可以使沿中心对称的四个点到达最终位置，所以可以一圈一圈的转换。One Pass。

Code:

# code block
解法一：
public void rotate(int[][] matrix) {
    if (matrix == null || matrix.length <= 1) {
        return;
    }
    int n = matrix.length;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            swap(matrix, i, j, j, i);
        }
    }
    for (int i = 0; i < n; i++) {
        reverse(matrix, i);
    }
}

private void reverse(int[][] matrix, int x) {
    int start = 0, end = matrix[x].length - 1;
    while (start < end) {
        int tmp = matrix[x][start];
        matrix[x][start] = matrix[x][end];
        matrix[x][end] = tmp;
        start++;
        end--;
    }
}

private void swap(int[][] matrix, int x1, int y1, int x2, int y2) {
    int tmp = matrix[x1][y1];
    matrix[x1][y1] = matrix[x2][y2];
    matrix[x2][y2] = tmp;
}
解法二：
public void rotate(int[][] matrix) {
    if (matrix == null || matrix.length <= 1) {
        return;
    }
    int n = matrix.length;
    int start = 0, end = n - 1;
    while (start < end) {
        for (int i = start; i < end; i++) {
            swap(matrix, start, i, i, end);
            swap(matrix, start, i, end, end - i);
            swap(matrix, start, i, end - i, start);
        }
        start++;
        end--;
    }
}

private void swap(int[][] matrix, int x1, int y1, int x2, int y2) {
    int tmp = matrix[x1][y1];
    matrix[x1][y1] = matrix[x2][y2];
    matrix[x2][y2] = tmp;
}

Time Complexity: O(n ^ 2)
Space Complexity: O(1)

<center>#49 Group Anagrams</center>

link
Description:
- Given an array of strings, group anagrams together.
Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["ate","eat","tea"],["nat","tan"]]
Solution:
- 这题考察的是哈希表的应用，以及对anagram的理解
- 通过对每一个string的char数组排序作为key，每一组anagram都有同一个key，使用hashmap做收集
- 更优的解法是自己写不重复的hash function，可以参考网上的质数解法

Code:

# code block
public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> result = new ArrayList<>();
    if (strs == null || strs.length == 0) {
        return result;
    }
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] sc = s.toCharArray();
        Arrays.sort(sc);
        String key = new String(sc);
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<String>());
        }
        map.get(key).add(s);
    }
    for (String key : map.keySet()) {
        result.add(map.get(key));
    }
    return result;
}

Time Complexity: O(n * lg(length))
Space Complexity: O(n * length)

Leetcode算法解析1-50

<center>#1 Two Sum</center>

<center>#2 Add Two Numbers</center>

<center>#3 Longest Substring Without Repeating Characters</center>

<center>#4 Median of Two Sorted Arrays</center>

<center>#5 Longest Palindromic Substring</center>

<center>#6 ZigZag Conversion</center>

<center>#7 Reverse Integer</center>

<center>#8 String to Integer (atoi)</center>

<center>#9 Palindrome Number</center>

<center>#11 Container With Most Water</center>

<center>#12 Integer to Roman</center>

<center>#13 Roman to Integer</center>

<center>#14 Longest Common Prefix</center>

<center>#15 3Sum</center>

<center>#16 3Sum Closest</center>

<center>#17 Letter Combinations of a Phone Number</center>

<center>#18 4Sum</center>

<center>#19 Remove Nth Node From End of List</center>

<center>#20 Valid Parentheses</center>

<center>#21 Merge Two Sorted Lists</center>

<center>#22 Generate Parentheses</center>

<center>#23 Merge k Sorted Lists</center>

<center>#24 Swap Nodes in Pairs</center>

<center>#25 Reverse Nodes in k-Group</center>

<center>#26 Remove Duplicate</center>

<center>#27 Remove Element</center>

<center>#28 Implement strStr()</center>

<center>#29 Divide Two Integers</center>

<center>#31 Next Permutation</center>

<center>#33 Search in Rotated Sorted Array</center>

<center>#34 Search for a Range</center>

<center>#35 Search Insert Position</center>

<center>#36 Valid Sudoku</center>

<center>#38 Count and Say</center>

<center>#39 Combination Sum</center>

<center>#40 Combination Sum II</center>

<center>#43 Multiply Strings</center>

<center>#46 Permutations</center>

<center>#47 Permutations II</center>

<center>#48 Rotate Image</center>

<center>#49 Group Anagrams</center>

猜你喜欢

热点阅读