刷题skill+编程cultivation+记录

AChris

AChris 发表于 2019-2-22 01:05
02/21/2019 Day16

Leetcode 443. String Compression

Integer.toString(count).toCharArray()
这个函数挺有用的，要记住

AChris

02/22/2019 Day17

LeetCode 79. Word Search
【非常好的一题👍】

解题思路：本题算事backtracking / DFS 中比较复杂的一题。还是有一些技巧值得学习。

首先，我们并不清楚word的第一个字母会在board中哪里找到，所以说，第一次branch的话，要从rootbranch到board当中所有的element。
之后的branch，我们就在之前的node的基础上，往上下左右四个方向branch。

其次，往四个方向branch，可能出现一个问题，就是会重复使用之前使用过的字母。那么这里有一个【技巧】，就是利用【‘#’】来替换已经用过的字母，之后recover的时候再复原就好。

第三，base case的就是，我们一直branch，当搜索的depth大于等于word.lenght的时候，也就是我们找到word的时候。

最后，注意不要 index out of bound

以上

class Solution {
public boolean exist(char[][] board, String word) {
// board: m*m, word: k
// time: O(m * n * 4 ^ k) 99.56%
// space: O(k) 96.62%
// ABCCED
// root
// / / / / \ \ \ \ \ \ (first branch to all elements)
// A(0,0) A(2, 0) (rest branch to 4 direction)
// / | | \ / | | \
// B(0,1)
// / | | \
if(board == null || board.length == 0 || board[0] == null || board[0].length == 0 || word == null) return false;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (exist(board, word, 0, i, j)) {
return true;
}
}
}
return false;
}
private boolean exist(char[][] board, String word, int start, int i, int j) {
if (start >= word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
// use '#' to replace the used character to avoid reusing
if (board[i][j] == word.charAt(start)) {
char c = board[i][j];
board[i][j] = '#';
boolean res = exist(board, word, start + 1, i + 1, j) ||
exist(board, word, start + 1, i - 1, j) ||
exist(board, word, start + 1, i, j + 1) ||
exist(board, word, start + 1, i, j - 1);
board[i][j] = c;
return res;
}
return false;
}
}

复制代码

AChris

02/22/2019 Day17

LeetCode 20. Valid Parentheses
Importance【4】

这题再次应证了，easy题目中还是有很多值得一刷的类星体。感觉这题如果之前没见过，还是很难想到用stack来解的。

解题思路：本题主要利用了stack push的数据和pop的数据有一种类似回文的性质。依次根据见到的 ( [ { 并push进他们的另一面。遇到另一面时候，再pop出来看和现在遇到的一不一样。

class Solution {
public boolean isValid(String s) {
// time: O(n) 98.12%
// space: O(n) 30.42%
/*
Parenthese is some specific kind of problem.
when we come across this kind of problem, always try to solve it with Stack.
since:
123456
stack:123456
pop: 654321
*/
/*
case 1: "()[]{}"
true
case 2: "(]"
fasle
case 3: "([)]"
fasle
*/
if (s == null || s.length() == 0) return true;
Stack<Character> stack = new Stack<> ();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
// we get )/]/} at first or mess the order
if (stack.isEmpty() || stack.pop() != c) return false;
}
}
// if stack is empty then every things fine
return stack.isEmpty();
}
}

复制代码

AChris

02/22/2019 Day18

LeetCode 70. Climbing Stairs
Importance【4】

解题思路：这题还是很重要的，主要是自己第一次见到将问题往dynamic programming中的fibonacci number转化
另外注意，用backtracking也可以，但是因为没有像DP中利用之前计算出来的结果，所以会做很多重复计算，本题中用这个会导致time limit exceed

class Solution {
// method1:
public int climbStairs(int n) {
// time: O(n)
// space: O(1)
/* ==== Fibonacci number ====
define f(n): n -> how many distinct ways to n
base case: f(0) = f(1) = 1
induction f(n) = f(n - 1) + f(n - 2)
*/
// oneStep denotes f(n-1) since from n-1 to n only need one step
if (n <= 1) return 1;
int oneStep = 1, twoStep = 1, res = 0;
for (int i = 2; i <= n; i++) {
res = oneStep + twoStep;
twoStep = oneStep;
oneStep = res;
}
return res;
}
// // method2: works but time limit exceeded e.g. n = 45
// public int climbStairs(int n) {
// /*
// Some drawback of recursive:
// In this recursive tree, we didn't use some common feature. for example, we calculate how many ways there are when n = 3 twice.
// n = 5
// / \
// 4 3
// / \ / \
// 3 2 2 1
// / \
// 2 1
// */
// if (n == 0) return 1;
// if (n <= 2) return n;
// return climbStairs(n - 1) + climbStairs(n - 2);
// }
}

复制代码

补充内容 (2019-2-24 00:16):
02/23/2019 Day18
为什么日期总是写错。。。

AChris

02/23/2019 Day18

Leetcode 102. Binary Tree Level Order Traversal
Importance【4】

解题思路：这题如题所讲，是树结构的按层遍历。
主要分为两种方法，一种是BFS的方法，利用一个queue实现，每次循环的时候，把每一层的数从queue拿出来，存到result 里，并将该层的下一层再offer到queue里去。
另一种是DFS，正常递归写法。

解题技巧：
1.利用queue实现BFS

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// method 1: Using BFS by Queue
public List<List<Integer>> levelOrder(TreeNode root) {
// time: O(n) 85.87%
// space: O(n) 32.65%
List<List<Integer>> res = new ArrayList<> ();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<> ();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> curLevel = new ArrayList<> ();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.remove();
curLevel.add(cur.val);
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
res.add(curLevel);
}
return res;
}
// // method 2: Using DFS
// public List<List<Integer>> levelOrder(TreeNode root) {
// // time: O(n) 100%
// // space: O(n) 5.51%
// List<List<Integer>> res = new ArrayList<> ();
// if (root == null) return res;
// helper(res, root, 0);
// return res;
// }
// private void helper(List<List<Integer>> res, TreeNode cur, int level) {
// if (cur == null) return;
// if (level >= res.size()) {
// res.add(new ArrayList<> ());
// }
// res.get(level).add(cur.val);
// helper(res, cur.left, level + 1);
// helper(res, cur.right, level + 1);
// return;
// }
}

复制代码

AChris

02/24/2019 Day19

Leetcode 114. Flatten Binary Tree to Linked List
Importance【4】

解题思路：
本题是一道类似于traversal的题目，解法使用的递归。
将一个tree flatten分三步：
1.把右面的sub tree flatten
2.把右子树放到最左节点的最右子树上
3.把左子树放到右子树上
   1                      1                1
   / \    ->       /       ->       \
2.    3                2                      2
                              \                      \
                              3                      3

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
// time: O(n) 100%
// space: O(1) 5.09%
// similar to the some tree traversal (right -> left -> root)
if (root == null) return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
}

复制代码

AChris

02/25/2019 Day20

Leetcode 104. Maximum Depth of Binary Tree
Importance【3】

解题思路：
非常简单的一道题。主要是利用函数自己本身的递归思路求解。别忘了+1。

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
// time: O(n) 100%
// space: O(n) 9.61%
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}

复制代码

AChris

02/25/2019 Day20

Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal
Importance【5】

解题思路：
一道有些难度的题目。
主要是要理解inorder与preorder。
inorder的话是 left -> root -> right，在array中，每一个root的左边是他的左子树，右边是右子树
preorder的话是root -> left -> right，在array中，可以根据size找到root的值

然后，主要利用递归，不断给root的左右子树赋值

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// time: O(n^2)
// space: O(n)
/*
3
/ \
9 20
/ \
15 7
preorder = [3, 9, 20, 15, 7]
root, left, right
inorder = [9, 3, 15, 20, 7]
left, root, right
for each node, left=side is left children & parents, right-side is right children
*/
return helper(0, 0, preorder.length - 1, preorder, inorder);
}
private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = -1;
for (int i = inStart; i < inorder.length; i++) {
if (root.val == inorder[i]) inIndex = i;
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
// size of left subtree: inIndex - inStart
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}

复制代码

AChris

02/25/2019 Day21

Leetcode 101. Symmetric Tree
Importance【4】

解题思路：
挺有意思的一道题，属于那种见过秒做，没见过还挺难想的那种。
关键是利用递归，把值应该相同的两个node一对一对送进helper函数里面，去检验他们的值是否相同。

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
// time: O(n) 100%
// space: O(logn) 5.12%
if (root == null) return true;
return helper(root.left, root.right);
}
private boolean helper(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
if (left.val == right.val && helper(left.left, right.right) && helper(left.right, right.left)) return true;
return false;
}
}

复制代码

补充内容 (2019-2-28 03:36):

日期更正：02/26/2019 Day21

	29垅无效楼层，该帖已经被删除

刷题skill+编程cultivation+记录

浏览过的版块