刷题skill+编程cultivation+记录

AChris

02/12/2019 Day7
LeetCode 40. Combination Sum II

解题思路：和combination I相似，要注意的就是，在递归的时候，在每一次branch的时候，同一个数只需要 branch 一次

class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// time: O(2^n)
// space: O(n)
// [2,5,2,1,2] -> [1, 2, 2, 2, 5]
// 5
// root
// /. |. \
// 1 2 5
// /. \ / \
// 2 5 2 5
// / \ / \
// 2 5 2 5
// / \ /
// 2 5 5
List<List<Integer>> res = new ArrayList<> ();
if (candidates == null || candidates.length == 0 || target == 0) return res;
Arrays.sort(candidates);
dfsHelper(res, candidates, target, new ArrayList<> (), 0);
return res;
}
// // method 1
// private void dfsHelper(List<List<Integer>> res, int[] candidates, int target, List<Integer> cur, int start) {
// if (target == 0 && !res.contains(cur)) {
// // in case there is same number like two 1
// res.add(new ArrayList<> (cur));
// return;
// }
// if (target < 0 || start >= candidates.length) return;
// for (int i = start; i < candidates.length; i++) {
// cur.add(candidates[i]);
// dfsHelper(res, candidates, target - candidates[i], cur, i+1);
// cur.remove(cur.size() - 1);
// }
// return;
// method 2
private void dfsHelper(List<List<Integer>> res, int[] candidates, int target, List<Integer> cur, int start) {
if (target == 0) {
// in case there is same number like two 1
res.add(new ArrayList<> (cur));
return;
}
if (target < 0 || start >= candidates.length) return;
for (int i = start; i < candidates.length; i++) {
// when branch, same numbe only get one branch at a time
if (i != start && candidates[i] == candidates[i-1]) continue;
cur.add(candidates[i]);
dfsHelper(res, candidates, target - candidates[i], cur, i+1);
cur.remove(cur.size() - 1);
}
return;
}
}

复制代码

补充内容 (2019-2-14 23:51):
【日期更正】02/13/2019 Day8

AChris

02/14/2019 Day9
LeetCode 60. Permutation Sequence

解题思路：这题主要是利用等价拆分排序的思想。
1. 首先想到，n个数，总共有n！种情况，第一位有n种情况，每种情况对应一个set，set相互之间有序，每个set有（n-1）！种情况。
2. 那么我们可以根据 k_index / (n-1) ！得到我们想要的数在第几个set里面
3. k_index % （n-1）！可以得到在那个set里面，我们要找第几个数

class Solution {
// method 1: 96.03% 100%
public String getPermutation(int n, int k) {
// time: O(n)
// space: O(n)
// {1,2,3,4}
// 1 -> {2,3,4}
// 2 -> {1,3,4}
// 3 -> {1,2,4}
// 4 -> {1,2,3}
//
// k = 18 -> k = 17
// index = k / fact[3] = 2; k = k % fact[3] = 5
// res = {1,2,4}
// k = 5
// index = k / fact[2] = 2; k = k % fact[2] = 1
//. res = {1,2}
// k = 1
// index = k / fact[1] = 1; k = k % fact[1] = 0
// res = {1}
// k = 0
// index = k / fact[0] = 0; k = k % fact[0] = 0
// res = {}
List<Integer> res = new ArrayList<Integer> ();
if (n == 0) new String ();
for (int i = 1; i <= n; i++) {
res.add(i);
}
//fact[i] to store i!
int[] fact = new int[n];
fact[0] = 1;
for (int i = 1; i < n; i++) {
fact[i] = fact[i-1] * i;
}
k = k - 1;
StringBuilder sb = new StringBuilder ();
for (int i = n - 1; i >= 0; i--) {
int index = k / fact[i];
k = k % fact[i];
sb.append(res.get(index));
res.remove(index);
}
return sb.toString();
}
// // method 2: 15.53% 100%
// // time: O(n*k)
// // space: O(n)
// public String getPermutation(int n, int k) {
// StringBuilder sb = new StringBuilder ();
// if (n == 0) return sb.toString();
// for (int i = 1; i <= n; i++) {
// sb.append((char)('0' + i));
// }
// for (int i = 1; i < k; i++) {
// increasePer(sb);
// }
// return sb.toString();
// }
// private void increasePer(StringBuilder sb) {
// int firstSmall = -1;
// for (int i = sb.length() - 2; i >= 0; i--) {
// if (sb.charAt(i) < sb.charAt(i+1)) {
// firstSmall = i;
// break;
// }
// }
// // System.out.println("*firstSmall*" + firstSmall);
// if (firstSmall == -1) {
// reverse(sb, 0, sb.length() - 1);
// }
// // firstLarge must exists since sb.charAt(firstSmall) < sb.charAt(firstSmall + 1)
// int firstLarge = -1;
// for (int i = sb.length() - 1; i >= firstSmall + 1; i--) {
// if (sb.charAt(i) > sb.charAt(firstSmall)) {
// firstLarge = i;
// break;
// }
// }
// // System.out.println("*firstLarge*" + firstLarge);
// swap(sb, firstSmall, firstLarge);
// reverse(sb, firstSmall + 1, sb.length() - 1);
// }
// private void reverse(StringBuilder sb, int i, int j) {
// while( i < j) {
// swap(sb, i++, j--);
// }
// }
// private void swap(StringBuilder sb, int i, int j) {
// char temp = sb.charAt(i);
// sb.setCharAt(i, sb.charAt(j));
// sb.setCharAt(j, temp);
// }
}

复制代码

AChris

02/15/2019 Day10

63. Unique Paths II

解题思路：
利用Dynammic Programming，创造dist 矩阵，记录到每一个点的路线总数

class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// obstacleGrid contains n elements
// time: O(n)
// space: O(n)
// [[0, 0]]
// rowNum = 1, colNum = 2
//
// [[1, 0]]
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return 0;
}
int rowNum = obstacleGrid.length;
int colNum = obstacleGrid[0].length;
// the default value in dist[i][j] is 0 for all i, j
int[][] dist = new int[rowNum][colNum];
for (int j = 0; j < colNum; j++) {
if (obstacleGrid[0][j] != 1) {
dist[0][j] = 1;
} else {
break;
}
}
for (int i = 0; i < rowNum; i++) {
if (obstacleGrid[i][0] != 1) {
dist[i][0] = 1;
} else {
break;
}
}
for (int i = 1; i < rowNum; i++) {
for (int j = 1; j < colNum; j++) {
if (obstacleGrid[i][j] != 1) {
dist[i][j] = dist[i-1][j] + dist[i][j-1];
}
}
}
return dist[rowNum - 1][colNum - 1];
}
private void printMap(int[][] map) {
int rowNum = map.length;
int colNum = map[0].length;
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
}

复制代码

AChris

02/16/2019 Day11

Leetcode 64. Minimum Path Sum

解题思路：dynammic programming
技巧：1.可以在原矩阵上面赋值，减小空间复杂度
2. 可以将多个for loop 合为一个for loop，具体怎么合并，要好好思考，为了减小代码行数

class Solution {
// method 1: 70.79%, 100%
public int minPathSum(int[][] grid) {
// time: O(m * n)
// space: O(1)
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++){
if (i == 0 && j != 0) grid[i][j] += grid[i][j-1];
if (i != 0 && j == 0) grid[i][j] += grid[i-1][j];
if (i != 0 && j != 0) grid[i][j] += Math.min(grid[i][j-1], grid[i-1][j]);
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
// // method 2: 29.47% 100%
// public int minPathSum(int[][] grid) {
// // grid = m * n
// // time: O(m*n)
// // space: O(n)
// if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
// int rowNum = grid.length;
// int colNum = grid[0].length;
// if (rowNum == 1) return IntStream.of(grid[0]).sum();
// if (colNum == 1) {
// int sum = 0;
// for (int i = 0; i < rowNum; i++) sum += grid[i][0];
// return sum;
// }
// int[] dist = new int[colNum];
// dist[0] = grid[0][0];
// for (int j = 1; j < colNum; j++) {
// dist[j] = dist[j-1] + grid[0][j];
// }
// for (int i = 1; i < rowNum; i++) {
// dist[0] += grid[i][0];
// for (int j = 1; j < colNum; j++) {
// // can use Math.min
// dist[j] = Math.min(dist[j-1], dist[j]) + grid[i][j];
// }
// }
// return dist[colNum - 1];
// }
}

复制代码

AChris

02/17/2019 Day12

Leetcode 73. Set Matrix Zeroes

解题思路：
这道题主要类似暴力解法。但是，空间复杂度为O（1）的方法，如果不是事先做，还是有些难想到的。

首先，对矩阵进行每个元素进行遍历，然后将每一个row和每一个col是否为0记录在第一行和第一列上。但是呢，因为第一行，第一列本身是用来记录每一行每一列的，所以，第一行第一列是不是全是0，我们需要用另外两个boolean来记录。
然后，根据所记录的first row，first col 对 matrix[1:][1:]赋值。根据row，col对第一行第一列赋值

class Solution {
public void setZeroes(int[][] matrix) {
// time: O(m*n) 99.98%
// space: O(1) 100%
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
int m = matrix.length;
int n = matrix[0].length;
boolean row = false;
boolean col = false;
// construct indicator using first row and first column
// row and col indicates whether first row and first column are all 0
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
if (i == 0) row = true;
if (j == 0) col = true;
}
}
}
// Use the indicator to set 0 to matrix[1:][1:]
for (int i = 1; i < m; i++) {
if (matrix[i][0] == 0) {
for (int j = 1; j < n; j++) {
matrix[i][j] = 0;
}
}
}
for (int j = 1; j < n; j++) {
if (matrix[0][j] == 0) {
for (int i = 1; i < m; i++) {
matrix[i][j] = 0;
}
}
}
// Set the first row and first column
if (row) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (col) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
return;
}
}

复制代码

AChris

02/17/2019 Day13

Leetcode 94. Binary Tree Inorder Traversal

解题思路：
本题非常基础。主要就是中序遍历。有两种写法。
第一种，利用函数递归。
第二种，利用stack遍历。在Binary Search Tree （BST）中，进行中序遍历的结果是一组sorted的上升序列。

都要掌握。

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// // method1: recursive
// public List<Integer> inorderTraversal(TreeNode root) {
// // n elements in total
// // time: O(n) 100%
// // space: O(n) 100%
// List<Integer> res = new ArrayList<Integer> ();
// if (root == null) return res;
// helper(res, root);
// return res;
// }
// public void helper(List<Integer> res, TreeNode root) {
// if (root == null) return;
// helper(res, root.left);
// res.add(root.val);
// helper(res, root.right);
// }
// method2: Stack Traversal
// in Binary Search Tree(BST), the in oder traversal going through tree with numbers increasing
// So, in order traversal is very important
public List<Integer> inorderTraversal(TreeNode root) {
// n elements in total
// time: O(n) 55.50%
// space: O(n) 100.00%
List<Integer> res = new ArrayList<> ();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<> ();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
return res;
}
}

复制代码

补充内容 (2019-2-20 02:35):
02/18/2019 Day13 日期打错了

AChris

02/19/2019 Day14

Leetcode 96. Unique Binary Search Trees

解题思路：这题事一到典型的dynammic programming
注意BST的特点，左子树的所有元素一定小于root，右子树的所有元素一定大于root

class Solution {
public int numTrees(int n) {
// time: O(n^2) 100%
// space: O(n) 100%
// dynammic programming
//example: [1, 2, 3]
// root: 1; left: 0; right: 2;
// root: 2; left: 1; right: 1;
// root: 3; left: 2; right: 0;
// f(n) denotes how many unique BSTs exists given n numbers
// f(n) = f(0) * f(n-1) + f(1) * f(n-2) + ...... + f(n-1) * f(0)
int[] res = new int[n+1];
res[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
res[i] += res[j] * res[i - 1 - j];
}
}
return res[n];
}
}

复制代码

AChris

02/20/2019 Day15

Leetcode 98. Validate Binary Search Tree

解题思路：
本题利用recursive的递归方法。
利用helper函数作为辅助。每个helper函数有三个输入，root，min表示root能有的最小值，max表示root能有的最大值。

解题技巧：
root的最大值最小值不知道该取什么的时候（比如最开始的时候），可以输入一个null指针，对应的min、max可以用Integer的类型的参数。Integer 是一个object，接受null的输入。
null不可输入给int型。int 型是primitive typ。

总共有8个primitive type:
1. Integer: byte, char, short, int, long
2. floating point: float, double
3. other: boolean
(void)

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
// in total, there are n elements in the tree
// time: O(n) 100%
// space: O(n) 93.13%
//
// 10
// / \
// 8 12
// / \
// 7 15(invalid)
// so we need to store min and max
//
if (root == null) return true;
return helper(root, null, null);
}
// use Integer here!! int cannot be null
private static boolean helper(TreeNode root, Integer max, Integer min) {
if (root == null) return true;
if (min != null && root.val <= min) return false;
if (max != null && root.val >= max) return false;
return helper(root.left, root.val, min) && helper(root.right, max, root.val);
}
}

复制代码

AChris

02/21/2019 Day16

Leetcode 78. Subsets

解题思路：backtracking/recursive暴力解决，
注意嵌套递归的时候用的是i+1， helper(res, nums, ls, i + 1);

class Solution {
public List<List<Integer>> subsets(int[] nums) {
// time: O(2^n) 100%
// space: O(2^n) 32.34%
//
// []
// [1], [1,2], [1,2,3], [1, 3]
// [2], [2,3]
// [3]
//
// 1 --------- 2 ------ 3
// | |
// 2 -- 3 3
// |
// 3
//
// root
// / | \
// 1 2 3
// / \ |
// 2 3 3
// /
// 3
List<List<Integer>> res = new ArrayList<> ();
if (nums == null || nums.length == 0) return res;
Arrays.sort(nums);
List<Integer> ls = new ArrayList<> ();
res.add(new ArrayList<> (ls));
helper(res, nums, ls, 0);
return res;
}
private void helper(List<List<Integer>> res, int[] nums, List<Integer> ls, int start) {
for (int i = start; i < nums.length; i++) {
ls.add(nums[i]);
res.add(new ArrayList<> (ls));
helper(res, nums, ls, i + 1);
// recover
ls.remove(ls.size() - 1);
}
return;
}
}

复制代码

AChris

02/21/2019 Day16

Leetcode 443. String Compression

解题思路：主要是确定要用的三个指标，
cur，记录哪里需要赋值
count，当前的字母有几个
c，当前的字母

今天发现这道easy的题目也没有想象中那么简单。自己的easy题目也还是要刷啊，多多熟悉各种操作。

class Solution {
// method 1
public int compress(char[] chars) {
// time: O(n) 100%
// space: O(1) 90.56%
if (chars == null) return 0;
if (chars.length == 1) return 1;
int cur = 0;
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
int count = 1;
while ((i+1) < chars.length && chars[i] == chars[i+1]) {
count++;
i++;
}
chars[cur++] = c;
if (count != 1){
for (char digit: Integer.toString(count).toCharArray()) {
chars[cur++] = digit;
}
}
}
return cur;
}
// // method 2
// public int compress(char[] chars) {
// // time: O(n) 100%
// // space: O(1) 30.04%
// if (chars == null) return 0;
// if (chars.length == 1) return 1;
// int cur = 0;
// for (int i = 0; i < chars.length; i++) {
// char c = chars[i];
// int count = 1;
// if ((i+1) >= chars.length || chars[i] != chars[i+1]) {
// chars[cur++] = c;
// continue;
// }
// while ((i+1) < chars.length && chars[i] == chars[i+1]) {
// count++;
// i++;
// }
// chars[cur++] = c;
// if (count < 10) {
// chars[cur++] = (char) (count + '0');
// }
// else {
// chars[cur++] = (char) (count / 10 + '0');
// chars[cur++] = (char) (count % 10 + '0');
// }
// }
// return cur;
// }
}

复制代码

刷题skill+编程cultivation+记录

浏览过的版块