Leetcode算法解析1-50

<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只需要遍歷一遍數(shù)組楼吃，所以在時間復雜度上要優(yōu)于兩根指針始花，因為兩個指針的方法是基于排序數(shù)組。
Java中提供了HashMap的實現(xiàn)所刀。 Map以數(shù)組元素為Key衙荐，以索引為Value。
遍歷一遍數(shù)組浮创，先在map中尋找是否有元素能夠和當前值組成sum為target忧吟，這個查找是O(1)的復雜度，如果沒有斩披，就把當前值和索引作為一個鍵值對保存在Map中供后續(xù)查找溜族，保存也是O(1)的復雜度。Worst Case是遍歷整個數(shù)組垦沉，也就是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:
- 典型的同向型兩根指針問題的區(qū)間類問題况既。
- 維持一個符合條件的區(qū)間，每次更新最大值

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)時間復雜度的算法第一個想到的是二分组民，又是排序數(shù)組棒仍，更加確定是二分
- 求第k個數(shù)，每次把問題縮小到排除不可能的k / 2 個數(shù)
- 對兩個數(shù)組同時找到第k / 2 個數(shù)臭胜，如果第一個數(shù)組中的數(shù)小于第二個數(shù)組中的數(shù)莫其，那么第一個數(shù)組中必然不存在第k大的數(shù)，可以排除前k / 2 的數(shù)耸三，反之同理
- 遞歸執(zhí)行乱陡，注意遞歸的出口和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的解法是三重循環(huán)仪壮，一重確定起點憨颠，一重確定終點，一重驗證是否為回文串睛驳。復雜度為O(n^3)
- 這邊想到的優(yōu)化是如果我以一個點為中點烙心，來找以這個點為中點的最長回文串
- 這樣一重循環(huán)確定中點，一重循環(huán)找最長回文串乏沸，時間復雜度就降到O(n^2)
- 注意點是回文串要考慮到奇數(shù)長度和偶數(shù)長度兩種特殊情形

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:
- 借用網(wǎng)上摘來的圖表達題意
- [圖片上傳失敗...(image-eb60d7-1534568626309)]
- 這是一道模擬題淫茵，可以找到規(guī)律是以2 * numRows - 2 在循環(huán)
- 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負數(shù)取余為負數(shù)

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:
- 注意點：
  - 負數(shù)肯定不是
  - 注意溢出

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:
- 模擬題柄慰，要想知道羅馬數(shù)字的具體規(guī)則參考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:
- 模擬題鳍悠，要想知道羅馬數(shù)字的具體規(guī)則參考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。難點在于去重概行，去重即聯(lián)想到排序蠢挡！所以先把數(shù)組排序。if (i != 0 && nums[i] == nums[i - 1]) 就continue這種方法確保了每個數(shù)字只取第一個凳忙。在two sum中兩個while循環(huán)確保相同的組合只出現(xiàn)一次业踏。

Code:

# code block
public List<List<Integer>> threeSum(int[] nums) {
     /*
      * 2 Sum的變種， 可以簡化為確定一個數(shù)a消略， 在剩下的數(shù)中的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類，不用特意回溯
- 剪枝：當左邊括號和右邊括號數(shù)量相等時嘹承，可以省去加右邊括號的搜索

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中最小的那個值
- 聯(lián)想到heap叹卷， java中有heap的不完全實現(xiàn)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題撼港，注意哪些指針要改變，注意子函數(shù)該返回什么骤竹，注意空鏈表處理

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:
- 翻轉時注意判斷是否需要翻轉帝牡，哪些指針需要被改變，返回什么節(jié)點

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:
- 考的就是最基本的數(shù)組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:
- 有個更優(yōu)的算法叫KMP算法蒙揣，此處不做介紹靶溜，有興趣研究可以谷歌或百度
Solution:
- 簡單的兩重循環(huán)鸣奔，注意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的數(shù)量級到lg n
- 這題的難點在于對每一個細節(jié)的處理锨匆，正負崭别，溢出等等，包括考到正負數(shù)最大值的絕對值差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中比較難的題恐锣，這題先將排列的樹畫出來茅主，找規(guī)律
- A_NEXT一定與A有盡可能長的公共前綴。
- 如果元素從底向上一直處于遞增土榴，說明是對這些元素來說诀姚，是沒有下一個排列的
- 從后向前比較相鄰的兩個元素，直到前一個元素小于后一個元素玷禽，停止赫段，這樣確保A_NEXT 與A有最長的公共前綴
- 下一步是找交換的點，必然是找從底部開始第一個大于停止的那個元素進行交換矢赁，能確保最小
- 如果從低到根都是遞增糯笙，那么下一個元素就是reverse整個數(shù)組
- 文字解釋有些難以理解，實際情況用實例將全排列的樹畫出來就能理解

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)
- 看似是兩重循環(huán)嵌套一個reverse撩银，實際上第一個循環(huán)找到要交換的第一個點给涕，第二重循環(huán)找到要交換的第二個點，對兩點間進行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數(shù)組够庙，滿足二分條件
- 本題難點在于分情況討論

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第一次出現(xiàn)的索引和最后一次出現(xiàn)的索引恭应。
- 使用兩次二分是由于worst case 整個數(shù)組都是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:
- 搜索排序數(shù)組就要想到二分法暮屡。這題要找的是第一個>= target的索引。
- 注意點:
  - 使用start < end - 1 是防止棧溢出毅桃，如果start = end - 1的話mid就會是start，如果nums[mid] < target就會陷入死循環(huán)
  - 從循環(huán)跳出會有兩種情況准夷， 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:
- 組合的題，不包含重復數(shù)字楔绞，可以把組合當做一個隱式圖结闸，用DFS對隱式圖進行遍歷。首先排序酒朵，因為排完序之后方便去重桦锄，還方便對樹進行剪枝。假如第i個數(shù)已經(jīng)大于目標蔫耽，那后面的數(shù)一定也大于目標结耀，不在答案中。
- 注意點：
  - 每找到一個答案要進行deepcopy匙铡，因為dfs中用到了回溯图甜，state數(shù)組會一直變化。

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:
- 求組合的題鳖眼，可重復數(shù)字黑毅，并且數(shù)組中每個數(shù)字只能用一次，可以把組合當做一個隱式圖钦讳，用DFS對隱式圖進行遍歷矿瘦。首先排序，因為排完序之后方便去重蜂厅，還方便對樹進行剪枝匪凡。假如第i個數(shù)已經(jīng)大于目標，那后面的數(shù)一定也大于目標掘猿，不在答案中病游。
- 注意點：
  - 每找到一個答案要進行deepcopy，因為dfs中用到了回溯，state數(shù)組會一直變化衬衬。
    - 去重方法用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:
- 暴力方法是直接模擬乘法計算
- 比較優(yōu)雅的方法可以參考下圖
- [圖片上傳失敗...(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來記錄當前狀態(tài)的值的索引
- 回溯的時候注意不僅要回溯當前狀態(tài)，也需要回溯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玉控，經(jīng)典的去重題
- 與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:
- 這其實更像是找規(guī)律的題
- 解法一：沿對角線翻轉，按行reverse
- 解法二：通過尋找規(guī)律可以發(fā)現(xiàn)碾篡，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數(shù)組排序作為key，每一組anagram都有同一個key穆律，使用hashmap做收集
- 更優(yōu)的解法是自己寫不重復的hash function惠呼，可以參考網(wǎng)上的質(zhì)數(shù)解法

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)

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市峦耘，隨后出現(xiàn)的幾起案子剔蹋，更是在濱河造成了極大的恐慌，老刑警劉巖辅髓，帶你破解...
沈念sama閱讀 219,270評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件滩租，死亡現(xiàn)場離奇詭異，居然都是意外死亡利朵，警方通過查閱死者的電腦和手機律想，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,489評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來绍弟，“玉大人技即，你說我怎么就攤上這事≌燎玻” “怎么了而叼？”我有些...
開封第一講書人閱讀 165,630評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長豹悬。經(jīng)常有香客問我葵陵，道長，這世上最難降的妖魔是什么瞻佛？我笑而不...
開封第一講書人閱讀 58,906評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任脱篙，我火速辦了婚禮娇钱，結果婚禮上，老公的妹妹穿的比我還像新娘绊困。我一直安慰自己文搂，他們只是感情好，可當我...
茶點故事閱讀 67,928評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布秤朗。她就那樣靜靜地躺著煤蹭，像睡著了一般。火紅的嫁衣襯著肌膚如雪取视。梳的紋絲不亂的頭發(fā)上硝皂，一...
開封第一講書人閱讀 51,718評論 1贊 305
城市分裂傳說
那天，我揣著相機與錄音作谭，去河邊找鬼吧彪。笑死，一個胖子當著我的面吹牛丢早，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播秧倾，決...
沈念sama閱讀 40,442評論 3贊 420
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼怨酝，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了粉洼？” 一聲冷哼從身側響起批糟，我...
開封第一講書人閱讀 39,345評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤楞抡，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后斤葱，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,802評論 1贊 317
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡揖闸，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,984評論 3贊 337
?白月光啟示錄
正文我和宋清朗相戀三年揍堕，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片汤纸。...
茶點故事閱讀 40,117評論 1贊 351
活死人
序言：一個原本活蹦亂跳的男人離奇死亡衩茸，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出贮泞，到底是詐尸還是另有隱情楞慈，我是刑警寧澤，帶...
沈念sama閱讀 35,810評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布啃擦，位于F島的核電站囊蓝，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏令蛉。R本人自食惡果不足惜聚霜，卻給世界環(huán)境...
茶點故事閱讀 41,462評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧俯萎，春花似錦傲宜、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,011評論 0贊 22
一樁弒父案函卒，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至撇眯，卻和暖如春报嵌，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背熊榛。一陣腳步聲響...
開封第一講書人閱讀 33,139評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工锚国，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人玄坦。一個月前我還...
沈念sama閱讀 48,377評論 3贊 373
代替公主和親
正文我出身青樓血筑，卻偏偏與公主長得像，于是被迫代替她去往敵國和親煎楣。傳聞我的和親對象是個殘疾皇子豺总，可洞房花燭夜當晚...
茶點故事閱讀 45,060評論 2贊 355

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>

推薦閱讀更多精彩內(nèi)容