Leetcode算法解析51-100

作者: 铛铛铛clark | 来源:发表于2018-08-18 13:11 被阅读10次

<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寻找组合的问题，注意保存每一点的坐标信息
- 规则是不能在同一行或者同一列或者对角线上
- 可以通过二元组存坐标信息，也可以直接通过数组，数组索引做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，用一个全局的计数器计算组合就行

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 初始值设为最小int肯定会被更新， preMin设为0确保了最少包含一个值，刻意应付全部都是负数的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:
- 贪心法。每到达一个能到达的点，都去刷新所能到的最远距离，最后比较能到的最远距离和最后一个元素的索引。

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遍历并计数，时间复杂度过高
- 遇到permutation的题第一件事先把图画出来
- 可以找到规律，每一层节点为根的树有m！个叉，根据这个可以判断每层分别是哪个数

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的进位，比如999加一会答案位数会发生改变。

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:
- 注意边界条件判断
- 思路很简单，注意进位不要忽略

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:
- 动态规划的入门题
- 暴力解法使用搜索，会有大量重复计算
- 每一步只与前两步有关，所以初始化一二步，之后不断更新前两步的值

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题，最简单的思路是先对0 和大于 0 做一次partition，对1和2做一次partition。这样虽然时间复杂度依然是O(n)，但是还有一次遍历的更优方法。
- 以下方法(Rainbow sort)中，区间[0, l）都是0，区间（r, end]都是2. 根据该算法可以确定， [l, r)这个区间内全是1. 当跳出循环的时候i = r + 1, 可以确保[0, l) 是0, [l, i) 是1， [i, end]是2.
  因为只遍历了一次，所以时间复杂度还是O(n)，空间复杂度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的变形
- 因为长度限定，所以可以剪枝优化，优化的地方用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:
- 子集问题就是隐式图的深度优先搜索遍历。因为是distinct，所以不需要去重。

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:
- 典型的图上的搜索题，因为要搜索所有的组合，所以推荐使用DFS，利用回溯，只需要维持一个状态
- 注意点
  - 图上的遍历问题可以利用dx， dy数组来优化代码
  - 把判断是否在边界内写成一个私有函数来优化代码
  - 递归的出口的选择
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的时间复杂度是边的个数
Space Complexity: O(m ^ 2 * n ^ 2)
- 判断是否访问过的boolean数组，worst case 可能有 n ^ 2个

<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:
- 去重，但是每个元素可以保留两个，实现的方法不止一种，但是要考虑到改变了数组中的值是否会对后续判断产生影响。

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:
- 基础的链表去重题，注意指针的赋值

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:
* 简单链表题，注意使用dummynode和指针赋值的先后问题
* 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方法。不适用额外空间的方法就是从尾巴开始归并， 先把大的数填进去
* 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
* 对subsets的隐式图进行遍历，记录下每一个状态
* 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)

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法提高之LeetCode刷题

Leetcode 答案及解析