Leetcode算法解析51-100

<center>#51 N-Queens</center>

link
Description:
- The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
- avator
Input: 4
Output: [[".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."]]
Solution:
- dfs尋找組合的問(wèn)題，注意保存每一點(diǎn)的坐標(biāo)信息
- 規(guī)則是不能在同一行或者同一列或者對(duì)角線上
- 可以通過(guò)二元組存坐標(biāo)信息扎拣，也可以直接通過(guò)數(shù)組讥巡，數(shù)組索引做x粹胯，值做y

Code:

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

private void dfsHelper(int n, int x, List<Integer> state, List<List<String>> result) {
    if (n == x) {
        generateSolution(state, n, result);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (valid(x, i, state)) {
            state.add(i);
            dfsHelper(n, x + 1, state, result);
            state.remove(state.size() - 1);
        }
    }
}

private boolean valid(int x, int y, List<Integer> state) {
    for (int i = 0; i < state.size(); i++) {
        if (y == state.get(i)) {
            return false;
        }
        if (Math.abs(y - state.get(i)) == Math.abs(x - i)) {
            return false;
        }
    }
    return true;
}

private void generateSolution(List<Integer> state, int n, List<List<String>> result) {
    List<String> solution = new ArrayList<>();
    for (Integer x : state) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < x; i++) {
            sb.append(".");
        }
        sb.append("Q");
        for (int i = x + 1; i < n; i++) {
            sb.append(".");
        }
        solution.add(sb.toString());
    }
    result.add(solution);
}

<center>#52 N-Queens II</center>

link
Description:
- Follow up for N-Queens problem.
- Now, instead outputting board configurations, return the total number of distinct solutions.
Input: 5
Output: 10
Solution:
- N Queens 的follow up咐吼，用一個(gè)全局的計(jì)數(shù)器計(jì)算組合就行

Code:

# code block
class Solution {
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }
        dfsHelper(n, 0, new ArrayList<Integer>());
        return result;
    }

    private void dfsHelper(int n, int x, List<Integer> state) {
        if (n == x) {
            result++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (valid(x, i, state)) {
                state.add(i);
                dfsHelper(n, x + 1, state);
                state.remove(state.size() - 1);
            }
        }
    }

    private boolean valid(int x, int y, List<Integer> state) {
        for (int i = 0; i < state.size(); i++) {
            if (y == state.get(i)) {
                return false;
            }
            if (Math.abs(y - state.get(i)) == Math.abs(x - i)) {
                return false;
            }
        }
        return true;
    }

    private int result = 0;
}

<center>#53 Maximum Subarray</center>

link
Description:
- Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Assumptions:
- containing at least one number
Solution:
- 使用preSum的典型題蕾羊。Sum(i, j) = Sum(0, j) - Sum(0, i - 1);
- 邊界情況的處理， max 初始值設(shè)為最小int肯定會(huì)被更新， preMin設(shè)為0確保了最少包含一個(gè)值笤昨，刻意應(yīng)付全部都是負(fù)數(shù)的corner case。

Code:

# code block
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int max = Integer.MIN_VALUE;
    int preSum = 0;
    int preMin = 0;
    for (int i = 0; i < nums.length; i++) {
        preSum += nums[i];
        max = Math.max(max, preSum - preMin);
        preMin = Math.min(preMin, preSum);
    }
    return max;
}

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

<center>#55 Jump Game</center>

link
Description:
- Given an array of non-negative integers, you are initially positioned at the first index of the array.
- Each element in the array represents your maximum jump length at that position.
- Determine if you are able to reach the last index.
Input: [2,3,1,1,4]
Output: true
Assumptions:
- non-negative integers
Solution:
- 貪心法上真。每到達(dá)一個(gè)能到達(dá)的點(diǎn)咬腋，都去刷新所能到的最遠(yuǎn)距離，最后比較能到的最遠(yuǎn)距離和最后一個(gè)元素的索引睡互。

Code:

# code block
public boolean canJump(int[] nums) {
    if (nums == null || nums.length == 0) {
        return true;
    }
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i <= reach) {
            reach = Math.max(reach, i + nums[i]);
        }
    }
    return reach >= nums.length - 1 ? true : false;
}

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

<center>#58 Length of Last Word</center>

link
Description:
- Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
Input: s = "Hello World"
Output: 5
Assumptions:
- If the last word does not exist, return 0.
Solution:
- 模擬題，注意處理boundary case

Code:

# code block
public int lengthOfLastWord(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    String tmp = s.trim();
    int length = 0;
    char[] tc = tmp.toCharArray();
    for (int i = tc.length - 1; i >= 0; i--) {
        if (Character.isLetter(tc[i])) {
            length++;
        } else {
            break;
        }
    }
    return length;
}

Time Complexity: O(n)

<center>#60 Permutation Sequence</center>

link
Description:
- The set [1,2,3,…,n] contains a total of n! unique permutations.
- By listing and labeling all of the permutations in order,
- We get the following sequence (ie, for n = 3):
```
  "123"
  "132"
  "213"
  "231"
  "312"
  "321"
```
- Given n and k, return the kth permutation sequence.

Input: 3, 2
Output: 132
Assumptions:
- Given n will be between 1 and 9 inclusive.
Solution:
- 暴力的解法是使用DFS遍歷并計(jì)數(shù)陵像，時(shí)間復(fù)雜度過(guò)高
- 遇到permutation的題第一件事先把圖畫出來(lái)
- 可以找到規(guī)律就珠，每一層節(jié)點(diǎn)為根的樹有m！個(gè)叉醒颖，根據(jù)這個(gè)可以判斷每層分別是哪個(gè)數(shù)

Code:

# code block
public String getPermutation(int n, int k) {
    if (n == 1) {
        return "1";
    }
    int[] factor = new int[n + 1];
    factor[0] = 1;
    for (int i = 1; i <= n; i++) {
        factor[i] = factor[i - 1] * i;
    }
    k = (k - 1) % factor[n];
    StringBuilder sb = new StringBuilder();
    boolean[] flag = new boolean[n];
    for (int i = n - 1; i >= 0; i--) {
        int idx = k / factor[i];
        sb.append(getNth(idx, flag));
        k -= factor[i] * idx;
    }
    return sb.toString();
}

private int getNth(int idx, boolean[] flag) {
    int count = idx;
    int i = 0;
    while (i < flag.length) {
        if (flag[i]) {
            i++;
            continue;
        }
        if (count == 0) {
            flag[i] = true;
            return i + 1;
        }
        i++;
        count--;
    }
    return -1;
}

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

<center>#61 Rotate List</center>

link
Description:
- Given a list, rotate the list to the right by k places, where k is non-negative.

Input: 1->2->3->4->5->NULL k=2
Output: 4->5->1->2->3->NULL
Solution:
- 注意各種corner case 的處理

Code:

# code block
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = head;
    int length = 1;
    while (last.next != null) {
        length++;
        last = last.next;
    }
    k = k % length;
    if (k == 0) {
        return head;
    }
    int cut = length - k;
    ListNode prev = head;
    for (int i = 0; i < cut - 1; i++) {
        prev = prev.next;
    }
    ListNode next = prev.next;
    // n1->...->prev->next->...->nLast
    // next->...->nLast->n1->...->prev
    prev.next = null;
    last.next = head;
    return next;
}

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

<center>#66 Plus One</center>

link
Description:
- Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
Input: [9,9,9]
Output: [1,0,0,0]
Assumptions:
- assume the integer do not contain any leading zero, except the number 0 itself.
  - The digits are stored such that the most significant digit is at the head of the list.
Solution:
- 本題最重要的是考慮到各種corner case的處理妻怎。比如加完之后大于10的進(jìn)位，比如999加一會(huì)答案位數(shù)會(huì)發(fā)生改變泞歉。

Code:

# code block
public int[] plusOne(int[] digits) {
    if (digits == null || digits.length == 0) {
        return digits;
    }
    int carrier = 1;
    for (int i = digits.length - 1; i >= 0; i--) {
        int val = digits[i] + carrier;
        digits[i] = val % 10;
        carrier = val / 10;
    }
    if (carrier == 0) {
        return digits;
    }
    // one more digit than digits array
    int[] result = new int[digits.length + 1];
    result[0] = 1;
    for (int i = 0; i < digits.length; i++) {
        result[i + 1] = digits[i];
    }
    return result;
}

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

<center>#67 Add Binary</center>

link
Description:
- Given two binary strings, return their sum (also a binary string).
Input: a = "11" b = "1"
Output: "100"
Solution:
- 注意邊界條件判斷
- 思路很簡(jiǎn)單逼侦，注意進(jìn)位不要忽略

Code:

# code block
public String addBinary(String a, String b) {
    if (a == null || a.length() == 0) {
        return b;
    }
    if (b == null || b.length() == 0) {
        return a;
    }
    StringBuilder sb = new StringBuilder();
    int idx_a = a.length() - 1, idx_b = b.length() - 1;
    int carrier = 0;
    while (idx_a >= 0 && idx_b >= 0) {
        int val = a.charAt(idx_a) - '0' + b.charAt(idx_b) - '0' + carrier;
        sb.append(val % 2);
        carrier = val / 2;
        idx_a--;
        idx_b--;
    }
    while (idx_a >= 0) {
        int val = a.charAt(idx_a) - '0' + carrier;
        sb.append(val % 2);
        carrier = val / 2;
        idx_a--;
    }
    while (idx_b >= 0) {
        int val = b.charAt(idx_b) - '0' + carrier;
        sb.append(val % 2);
        carrier = val / 2;
        idx_b--;
    }
    if (carrier != 0) {
        sb.append(carrier);
    }
    return sb.reverse().toString();
}

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

<center>#69 Sqrt(x)</center>

link
Description:
- Implement int sqrt(int x).
Input: 2147483647
Output: 46340
Solution:
- 這是一道二分法求答案的題，二分的范圍不是很直接
- 這題最重要的是考慮了overflow的情況

Code:

# code block
public int mySqrt(int x) {
    if (x <= 0) {
        return 0;
    }
    long start = 1, end = x;
    while (start < end - 1) {
        long mid = start + (end - start) / 2;
        if (mid * mid == x) {
            return (int)mid;
        } else if (mid * mid > x) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (end * end <= x) {
        return (int)end;
    }
    return (int)start;
}

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

<center>#70 Climbing Stairs</center>

link
Description:
- You are climbing a stair case. It takes n steps to reach to the top.
- Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
- Given n will be a positive integer.
Input: 6
Output: 13
Solution:
- 動(dòng)態(tài)規(guī)劃的入門題
- 暴力解法使用搜索腰耙，會(huì)有大量重復(fù)計(jì)算
- 每一步只與前兩步有關(guān)榛丢，所以初始化一二步，之后不斷更新前兩步的值

Code:

# code block
public int climbStairs(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    int n_prev = 1;
    int n_curr = 1;
    for (int i = 2; i <= n; i++) {
        int n_next = n_prev + n_curr;
        n_prev = n_curr;
        n_curr = n_next;
    }
    return n_curr;
}

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

<center>#75 Sort Colors</center>

link
Description:
- Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
- Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively
Input: [1,2,2,1,1,0]
Output:[0,1,1,1,2,2]
Assumptions:
- You are not suppose to use the library's sort function for this problem.
Solution:
- 典型的Partition題挺庞，最簡(jiǎn)單的思路是先對(duì)0 和大于 0 做一次partition晰赞，對(duì)1和2做一次partition。這樣雖然時(shí)間復(fù)雜度依然是O(n)选侨，但是還有一次遍歷的更優(yōu)方法掖鱼。
- 以下方法(Rainbow sort)中，區(qū)間[0, l）都是0援制，區(qū)間（r, end]都是2. 根據(jù)該算法可以確定戏挡， [l, r)這個(gè)區(qū)間內(nèi)全是1. 當(dāng)跳出循環(huán)的時(shí)候i = r + 1, 可以確保[0, l) 是0, [l, i) 是1， [i, end]是2.
  因?yàn)橹槐闅v了一次晨仑，所以時(shí)間復(fù)雜度還是O(n)褐墅，空間復(fù)雜度O(1)。

Code:

# code block
public void sortColors(int[] nums) {
    if (nums == null || nums.length == 0) {
        return;
    }
    int l = 0, r = nums.length - 1;
    int i = 0;
    while (i <= r) {
        if (nums[i] == 0) {
            swap(nums, i, l);
            l++;
            i++;
        } else if (nums[i] == 1) {
            i++;
        } else {
            swap(nums, i, r);
            r--;
        }
    }
}

private void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}

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

<center>#77 Combinations</center>

link
Description:
- Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Input: n = 4 and k = 2
Output: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
Solution:
- 注意邊界條件判斷
- combination的變形
- 因?yàn)殚L(zhǎng)度限定寻歧，所以可以剪枝優(yōu)化掌栅，優(yōu)化的地方用pluning注釋了

Code:

# code block
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    if (n < 1 || k > n) {
        return result;
    }
    dfsHelper(n, k, 1, new ArrayList<Integer>(), result);
    return result;
}

private void dfsHelper(int n, int k, int start, List<Integer> state, List<List<Integer>> result) {
    if (k == 0) {
        result.add(new ArrayList<Integer>(state));
        return;
    }

    for (int i = start; i <= n - k + 1; i++) {
        state.add(i);
        dfsHelper(n, k - 1, i + 1, state, result);
        state.remove(state.size() - 1);
    }
}

<center>#78 Subsets</center>

link
Description:
- Given a set of distinct integers, nums, return all possible subsets.
Input: [1,2,3]
Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
Assumptions:
- The solution set must not contain duplicate subsets.
Solution:
- 子集問(wèn)題就是隱式圖的深度優(yōu)先搜索遍歷。因?yàn)槭莇istinct码泛，所以不需要去重猾封。

Code:

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

 private void dfsHelper(int[] nums, int start, List<Integer> state, List<List<Integer>> result) {
     result.add(new ArrayList<Integer>(state));
     for (int i = start; i < nums.length; i++) {
         state.add(nums[i]);
         dfsHelper(nums, i + 1, state, result);
         state.remove(state.size() - 1);
     }
 }

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

<center>#79 Word Search</center>

link
Description:
- Given a 2D board and a word, find if the word exists in the grid.
- The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Input: board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
] word = "ABCCED"
Output: true
Assumptions:
Solution:
- 典型的圖上的搜索題，因?yàn)橐阉魉械慕M合噪珊，所以推薦使用DFS晌缘，利用回溯齐莲，只需要維持一個(gè)狀態(tài)
- 注意點(diǎn)
  - 圖上的遍歷問(wèn)題可以利用dx， dy數(shù)組來(lái)優(yōu)化代碼
  - 把判斷是否在邊界內(nèi)寫成一個(gè)私有函數(shù)來(lái)優(yōu)化代碼
  - 遞歸的出口的選擇
Code:

# code block
class Solution {
    public static final int[] dx = {1, 0, 0, -1};
    public static final int[] dy = {0, 1, -1, 0};
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        int m = board.length, n = board[0].length;
        char[] wc = word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean[][] visited = new boolean[m][n];
                if (board[i][j] != wc[0]) {
                    continue;
                }
                if (dfsHelper(board, wc, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfsHelper(char[][] board, char[] wc, boolean[][] visited, int x, int y, int start) {
        if (visited[x][y]) {
            return false;
        }
        if (wc[start] != board[x][y]) {
            return false;
        }
        if (start == wc.length - 1) {
            // find the word
            return true;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            if (valid(x + dx[i], y + dy[i], board, visited) && dfsHelper(board, wc, visited, x + dx[i], y + dy[i], start + 1)) {
                return true;
            }
        }
        visited[x][y] = false;
        return false;
    }

    private boolean valid(int x, int y, char[][] board, boolean[][] visited) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length && !visited[x][y];
    }
}

Time Complexity: O(m * n)
- DFS的時(shí)間復(fù)雜度是邊的個(gè)數(shù)
Space Complexity: O(m ^ 2 * n ^ 2)
- 判斷是否訪問(wèn)過(guò)的boolean數(shù)組磷箕，worst case 可能有 n ^ 2個(gè)

<center>#80 Remove Duplicates from Sorted Array II</center>

link
Description:
- Follow up for "Remove Duplicates":
- What if duplicates are allowed at most twice?
Input: [1,1,2,2,2,3,3,3]
Output: [1,1,2,2,3,3]
Solution:
- 去重选酗，但是每個(gè)元素可以保留兩個(gè)，實(shí)現(xiàn)的方法不止一種岳枷，但是要考慮到改變了數(shù)組中的值是否會(huì)對(duì)后續(xù)判斷產(chǎn)生影響芒填。

Code:

# code block
public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int idx = 0;
    int i = 0;
    while (i < nums.length) {
        int val = nums[i];
        int count = 0;
        while (i < nums.length && nums[i] == val) {
            i++;
            count++;
        }
        for (int j = 0; j < 2 && j < count; j++) {
            nums[idx++] = val;
        }
    }
    return idx;
}

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

<center>#83 Remove Duplicates from Sorted List</center>

link
Description:
- Given a sorted linked list, delete all duplicates such that each element appear only once.
Input: 1->1->2
Output: 1->2
Solution:
- 基礎(chǔ)的鏈表去重題，注意指針的賦值

Code:

# code block
public ListNode deleteDuplicates(ListNode head) {
  if (head == null) {
      return head;
  }
  ListNode dummy = new ListNode(0);
  dummy.next = head;
  while (head.next != null) {
      if (head.next.val == head.val) {
          head.next = head.next.next;
      } else {
          head = head.next;
      }
  }
  return dummy.next;

}

* Time Complexity: O(n)
* Space Complexity: O(1)
### <center>#86 Partition List</center>
* [link](https://leetcode.com/problems/partition-list/description/)
* Description:
* Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
* You should preserve the original relative order of the nodes in each of the two partitions.
* Input: 1->4->3->2->5->2 and x = 3
* Output: 1->2->2->4->3->5
* Solution:
* 簡(jiǎn)單鏈表題空繁，注意使用dummynode和指針賦值的先后問(wèn)題
* Code:

code block

public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0);
ListNode dummy2 = new ListNode(0);
ListNode curr1 = dummy1;
ListNode curr2 = dummy2;
while (head != null) {
if (head.val < x) {
curr1.next = head;
head = head.next;
curr1 = curr1.next;
curr1.next = null;
} else {
curr2.next = head;
head = head.next;
curr2 = curr2.next;
curr2.next = null;
}
}
curr1.next = dummy2.next;
return dummy1.next;
}

* Time Complexity: O(n)
* Space Complexity: O(1)
### <center>#88 Merge Sorted Array</center>
* [link](https://leetcode.com/problems/merge-sorted-array/description/)
* Description:
* Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
* Input: [4,5,6,0,0,0] 3 [1,2,3] 3
* Output: [1,2,3,4,5,6]
* Assumptions:
* You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

* Solution:
*  用歸并排序的merge方法殿衰。不適用額外空間的方法就是從尾巴開始?xì)w并， 先把大的數(shù)填進(jìn)去
* Code:

code block

public void merge(int[] nums1, int m, int[] nums2, int n) {
int length = m + n;
int ptM = m - 1;
int ptN = n - 1;
int pt = length - 1;
while (pt >= 0) {
if (ptN < 0) {
//nums2 merge complete, nums1 can left as it is
break;
} else if (ptM < 0) {
nums1[pt] = nums2[ptN--];
} else if (nums1[ptM] > nums2[ptN]) {
nums1[pt] = nums1[ptM--];
} else {
nums1[pt] = nums2[ptN--];
}
pt--;
}
}

* Time Complexity: O(n)
* Space Complexity: O(1)
### <center>#90 Subsets II</center>
* [link](https://leetcode.com/problems/subsets-ii/description/)
* Description:
* Given a collection of integers that might contain duplicates, nums, return all possible subsets.
* The solution set must not contain duplicate subsets.
* Input: nums = [1,2,2]
* Output:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

* Solution:
* 先排序盛泡，去重, 去重的地方注釋了remove duplicate
* 對(duì)subsets的隱式圖進(jìn)行遍歷闷祥，記錄下每一個(gè)狀態(tài)
* Code:

code block

public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
if (nums == null || nums.length == 0) {
subsets.add(new ArrayList<Integer>());
return subsets;
}
Arrays.sort(nums);
dfsHelper(nums, 0, new ArrayList<Integer>(), subsets);
return subsets;
}

private void dfsHelper(int[] nums, int start, List<Integer> state, List<List<Integer>> subsets) {
subsets.add(new ArrayList<Integer>(state));
for (int i = start; i < nums.length; i++) {
// remove duplicate
if (i != start && nums[i] == nums[i - 1]) {
continue;
}
state.add(nums[i]);
dfsHelper(nums, i + 1, state, subsets);
state.remove(state.size() - 1);
}
}

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

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市傲诵，隨后出現(xiàn)的幾起案子凯砍，更是在濱河造成了極大的恐慌，老刑警劉巖拴竹，帶你破解...
沈念sama閱讀 206,723評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件悟衩，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡殖熟，警方通過(guò)查閱死者的電腦和手機(jī)局待，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,485評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)菱属，“玉大人钳榨，你說(shuō)我怎么就攤上這事∨γ牛” “怎么了薛耻？”我有些...
開封第一講書人閱讀 152,998評(píng)論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)赏陵。經(jīng)常有香客問(wèn)我饼齿，道長(zhǎng)，這世上最難降的妖魔是什么蝙搔？我笑而不...
開封第一講書人閱讀 55,323評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任缕溉，我火速辦了婚禮，結(jié)果婚禮上吃型，老公的妹妹穿的比我還像新娘证鸥。我一直安慰自己，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 64,355評(píng)論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布枉层。她就那樣靜靜地躺著泉褐，像睡著了一般。火紅的嫁衣襯著肌膚如雪鸟蜡。梳的紋絲不亂的頭發(fā)上膜赃，一...
開封第一講書人閱讀 49,079評(píng)論 1贊 285
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音揉忘，去河邊找鬼跳座。笑死，一個(gè)胖子當(dāng)著我的面吹牛癌淮，可吹牛的內(nèi)容都是我干的躺坟。我是一名探鬼主播，決...
沈念sama閱讀 38,389評(píng)論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼乳蓄，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了夕膀？” 一聲冷哼從身側(cè)響起虚倒，我...
開封第一講書人閱讀 37,019評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎产舞，沒(méi)想到半個(gè)月后魂奥，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,519評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡易猫，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,971評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年耻煤，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片准颓。...
茶點(diǎn)故事閱讀 38,100評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡哈蝇，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出攘已，到底是詐尸還是另有隱情炮赦，我是刑警寧澤，帶...
沈念sama閱讀 33,738評(píng)論 4贊 324
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布样勃，位于F島的核電站吠勘，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏峡眶。R本人自食惡果不足惜剧防，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,293評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望辫樱。院中可真熱鬧峭拘，春花似錦、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,289評(píng)論 0贊 19
一樁弒父案暇赤，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至宵凌，卻和暖如春鞋囊，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背瞎惫。一陣腳步聲響...
開封第一講書人閱讀 31,517評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工溜腐，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人瓜喇。一個(gè)月前我還...
沈念sama閱讀 45,547評(píng)論 2贊 354
代替公主和親
正文我出身青樓挺益，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親乘寒。傳聞我的和親對(duì)象是個(gè)殘疾皇子望众，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,834評(píng)論 2贊 345

Leetcode算法解析51-100

<center>#51 N-Queens</center>

<center>#52 N-Queens II</center>

<center>#53 Maximum Subarray</center>

<center>#55 Jump Game</center>

<center>#58 Length of Last Word</center>

<center>#60 Permutation Sequence</center>

<center>#61 Rotate List</center>

<center>#66 Plus One</center>

<center>#67 Add Binary</center>

<center>#69 Sqrt(x)</center>

<center>#70 Climbing Stairs</center>

<center>#75 Sort Colors</center>

<center>#77 Combinations</center>

<center>#78 Subsets</center>

<center>#79 Word Search</center>

<center>#80 Remove Duplicates from Sorted Array II</center>

<center>#83 Remove Duplicates from Sorted List</center>

code block

code block

code block

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