刷题skill+编程cultivation+记录

AChris

03/06/2019 Day29

Leetcode 160. Intersection of Two Linked Lists
Importance【4】

解题思路：
本题主要有两种解法。
a ----> |
------->c
b ----> |
第一种：
两个指针，分别从headA 和headB开始，路线分别是 a ->c -> b 和 b- > c - > a。这样可以保证两个指针在c开头的地方相遇。

第二种：
首先求出两个list长度，然后通过截取 list A 和 list B 的头部让他们成为长度相同的 list。然后再从他们头部移动两个指针直到他们相等位置，他们相遇的位置便是 c 的头部。

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
// method1:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// time: O(n) 99.64%
// space: O(1) 58.37%
if (headA == null || headB == null) return null;
ListNode a = headA, b = headB;
while (a != b) {
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
// // method2:
// public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// // time: O(n) 99.64%
// // space: O(1) 6.99%
// if (headA == null || headB == null) return null;
// int lenA = len(headA), lenB = len(headB);
// if (lenA > lenB) {
// while (lenA != lenB) {
// headA = headA.next;
// lenA--;
// }
// } else {
// while (lenA != lenB) {
// headB = headB.next;
// lenB--;
// }
// }
// while (headA != headB) {
// headA = headA.next;
// headB = headB.next;
// }
// return headA;
// }
// private int len(ListNode head) {
// int length = 0;
// while (head.next != null) {
// head = head.next;
// length++;
// }
// return length;
// }
}

复制代码

AChris

03/07/2019 Day30

Leetcode 169. Majority Element
Importance【4】

解题思路：
本题有三种解法
1. 摩尔投票法。非常巧妙的一个算法。
首先，如果真存在一个元素是majority element的话，他数量一定要比其他元素的数量至少多1或2个。所以，我们就设置一个count，一个candidate。count负责抵消，是candidate的话+1，不是的话-1，如果count为0以后，下一次就选用新的candidate。因为反正majority element数量要多，所以，一定可以最后找到的。
顺便说一下，本题有一个假设，是majority element 一定存在。如果没有这个假设的话，需要在判断一下candidate是不是majority candidate，如果是的话，就返回。不是的话，说明不存在。

2. 先sort，然后第 length / 2 + 1个元素，也就是index为length / 2的元素就是要找的元素。

4.利用map一个一个数。

class Solution {
// method 1: (Moore Voting Algorithm)
// [url]https://www.youtube.com/watch?v=zOyOwDEF1Rc[/url]
public int majorityElement(int[] nums) {
// time: O(n) 99.43%
// space: O(1) 63.46%
int count = 0;
int candidate = -1;
for (int num : nums) {
if (count == 0) {
candidate = num;
count++;
} else {
if (num == candidate) count++;
else count--;
}
}
// // step 2:
// // if we do not have the assumption that the majority element always exist, we need this step to make sure the candidate is the majority element
// // e.g. 2,7,2,1,9 gives us 9 as candidate which is not he majority element
// count = 0;
// for (int num : nums) {
// if (num == candidate) count++;
// }
// if (count <= nums.length / 2) candidate = -1;
return candidate;
}
// // method 2:
// public int majorityElement(int[] nums) {
// // time: O(nlogn) 99.43%
// // space: O(1) 50.47%
// // 10 -> 6th element -> nums[5]
// // 9 -> 5th element -> nums[4]
// Arrays.sort(nums);
// return nums[nums.length / 2];
// }
// // method 3:
// public int majorityElement(int[] nums) {
// // time: O(n) 27.18%
// // space: O(n) 8.82%
// Map<Integer, Integer> map = new HashMap<>();
// int res = -1;
// for (int num : nums) {
// if (map.containsKey(num)) {
// map.put(num, map.get(num) + 1);
// } else {
// map.put(num, 1);
// }
// if (map.get(num) > nums.length / 2) res = num;
// }
// return res;
// }
}

复制代码

AChris

03/08/2019 Day31

Leetcode 200. Number of Islands
Importance【5】

解题思路：
这题主要是暴力解决+DFS/BFS。
具体来说。暴力解决是指，遍历矩阵中的每一个点，看是否为1。然后对每一个点用 DFS/BFS 来搜索该点相邻的点，并将它们设置为其他数，表示这个岛屿已经被发现了。

设置成的数，可以是0，这样最快，最省空间，但不可以将grid回复到原来的样子。
如果要将 grid 在 count 完岛屿之后，恢复到原来的样子，可以将设置成的数变成是1、2然后在搜索之后进行恢复。

class Solution {
// method 1: DFS
public int numIslands(char[][] grid) {
// time: O(m*n) 99.99%
// space: O(m*n) 63.72% since the max depth of the dfs tree is m*n
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
int rowNum = grid.length;
int colNum = grid[0].length;
int res = 0;
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j, rowNum, colNum);
res++;
}
}
}
return res;
}
private void dfs(char[][] grid, int i, int j, int rowNum, int colNum) {
if (i < 0 || i >= rowNum || j < 0 || j >= colNum || grid[i][j] == '0') return;
// if we do not want to restore the original graph, we can use 0
// if we want to restore the original graph, we should use another number except from 0
grid[i][j] = '0';
dfs(grid, i+1, j, rowNum, colNum);
dfs(grid, i-1, j, rowNum, colNum);
dfs(grid, i, j+1, rowNum, colNum);
dfs(grid, i, j-1, rowNum, colNum);
return;
}
// // method2 : BFS
// class Coordinate {
// int x;
// int y;
// public Coordinate (int x, int y) {
// this.x = x;
// this.y = y;
// }
// }
// public int numIslands(char[][] grid) {
// // time: O(m*n) 9.68%
// // space: O(m*n) 9.02%
// if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
// int rowNum = grid.length;
// int colNum = grid[0].length;
// int res = 0;
// Queue<Coordinate> queue = new LinkedList<> ();
// for (int i = 0; i < rowNum; i++) {
// for (int j = 0; j < colNum; j++) {
// if (grid[i][j] == '1') {
// // Initialize the BFS
// queue.add(new Coordinate(i, j));
// // use the BFS to set all num in this island to be 0
// while (!queue.isEmpty()) {
// Coordinate cur = queue.poll();
// int x = cur.x;
// int y = cur.y;
// if (x < 0 || x >= rowNum || y < 0 || y >= colNum || grid[x][y] == '0') {
// continue;
// } else {
// grid[x][y] = '0';
// queue.add(new Coordinate(x+1, y));
// queue.add(new Coordinate(x-1, y));
// queue.add(new Coordinate(x, y+1));
// queue.add(new Coordinate(x, y-1));
// }
// }
// res++;
// }
// }
// }
// return res;
// }
}

复制代码

AChris

03/09/2019 Day32

Leetcode 200. Number of Islands
Importance【4】

解题思路：典型的动态规划问题
两种方法，
第一种，设置两个变量，分别是 rob, notrob，代表抢和不抢当前节点所能得到的钱，注意，在每一个循环最开始的时候，还没有更新 rob notrob，此时这两个变量代表对于上一个节点的对应值
第二种，正常设置int[]

class Solution {
// method 1
public int rob(int[] nums) {
// time: O(n) 100%
// space: O(1) 10.11%
if (nums == null || nums.length == 0) return 0;
int notrob = 0, rob = 0;
for (int i = 0; i < nums.length; i++) {
int currob = notrob + nums[i];
notrob = Math.max(notrob, rob);
rob = currob;
}
return Math.max(notrob, rob);
}
// // method 2
// public int rob(int[] nums) {
// // time: O(n) 100%
// // space: O(n) 12.74%
// if (nums == null || nums.length == 0) return 0;
// if (nums.length == 1) return nums[0];
// int[] res = new int[nums.length];
// res[0] = nums[0];
// res[1] = Math.max(nums[0], nums[1]);
// for (int i = 2; i < nums.length; i++) {
// res[i] = Math.max(res[i - 2] + nums[i], res[i - 1]);
// }
// return res[nums.length - 1];
// }
}

复制代码

AChris

03/10/2019 Day33

Leetcode 200. Number of Islands
Importance【4】

解题思路：
一道挺有意思的题目。不难，但挺有启发的。

基本思路就是，把现在数组一个一个设置成想要的样子。
设置一个指针 toBeSet。
首先遍历所有的数，然后遇见不为 0 的数就把 toBeSet 的位置的数设置成那个数，然后把toBeSet。
因为 #(设置的数) <= 遇到的数，所以不会跳过的数只会是0，不会漏掉不是0的数。
然后，遍历一遍之后，把 toBeSet 以及之后的数设置成 0

class Solution {
public void moveZeroes(int[] nums) {
// time: O(n) 100%
// space: O(1) 95.01%
if (nums == null || nums.length == 0) return;
int toBeSet = 0;
for (int num : nums) {
if (num != 0) nums[toBeSet++] = num;
}
while (toBeSet < nums.length) nums[toBeSet++] = 0;
return;
}
}

复制代码

补充内容 (2019-3-11 10:55):
题目更正：LeetCode 283. Move Zeroes

AChris

03/29/2019 Day34
LeetCode 322. Coin Change
Importantce【5】

前段时间在忙离散优化的考试，真的超级难，所以一段时间没有刷，现在继续！

解题思路：
主要是利用dynamic programming。
关键在于定义 f[i][j] ：用coin i, i+1, i+2,....得到数量是 j 的钱的最少的硬币数量。
base case主要是 f[n][0] = 0, f[n][1/2/3/...] = inf

方法一：从第n行算第n-1行
方法二：对方法一优化，利用第n行算第n-1行的初始值，再利用n-1行之间的关系算最优解

class Solution {
// // method1:
// public int coinChange(int[] coins, int amount) {
// // time: O(n * m * m) 5.03%
// // space: O(n * m) 84.68%
// // f[i][j]: min # of coins to use from [i, i+1, i+2, ...] to get value j
// // base case: f[n][0] = 0, f[n][j!=0] = inf
// // induction: f[i][j] = min( f[i+1][j],
// // f[i+1][j - coins[i]] + 1,
// // f[i+1][j - 2 * coins[i]] + 2,
// // f[i+1][j - 3 * coins[i]] + 3,
// // ... )
// int[][] f = new int[coins.length + 1][amount + 1];
// Arrays.fill(f[coins.length], Integer.MAX_VALUE);
// f[coins.length][0] = 0;
// for (int i = coins.length - 1; i >= 0; i--) {
// for (int j = 0; j <= amount; j++) {
// int maxK = j / coins[i];
// f[i][j] = f[i+1][j];
// for (int k = 1; k <= maxK; k++) {
// // CAUTION: cannot use Integer.MAX_VALUE to add with some other number
// int prev = f[i+1][j - k * coins[i]];
// if (prev < Integer.MAX_VALUE) {
// f[i][j] = Math.min(f[i][j], prev + k);
// }
// }
// }
// }
// if (f[0][amount] == Integer.MAX_VALUE) return -1;
// else return f[0][amount];
// }
// method2:
public int coinChange(int[] coins, int amount) {
// time: O(n * m) 90.89%
// space: O(n * m) 88.04%
// f[i][j]: min # of coins to use from [i, i+1, i+2, ...] to get value j
// base case: f[n][0] = 0, f[n][j!=0] = inf
// induction: f[i][j] = min( f[i+1][j],
// f[i+1][j - coins[i]] + 1,
// f[i+1][j - 2 * coins[i]] + 2,
// f[i+1][j - 3 * coins[i]] + 3,
// ... )
int[][] f = new int[coins.length + 1][amount + 1];
Arrays.fill(f[coins.length], Integer.MAX_VALUE);
f[coins.length][0] = 0;
for (int i = coins.length - 1; i >= 0; i--) {
for (int j = 0; j <= amount; j++) {
f[i][j] = f[i + 1][j];
if (j >= coins[i]) {
int prev = f[i][j - coins[i]];
if (prev < Integer.MAX_VALUE) {
f[i][j] = Math.min(f[i][j], prev + 1);
}
}
}
}
if (f[0][amount] == Integer.MAX_VALUE) return -1;
else return f[0][amount];
}
}

复制代码

AChris

04/29/2019 Day35
LeetCode 119. Pascal's Triangle II
Importantce【4】

class Solution {
public List<Integer> getRow(int rowIndex) {
// time: O(n) 84.47%
// space: O(n) 100%
List<Integer> lastrow = new ArrayList<> ();
lastrow.add(1);
for (int i = 1; i <= rowIndex; i++) {
lastrow = createLayer(lastrow);
}
return lastrow;
}
private List<Integer> createLayer(List<Integer> lastrow) {
List<Integer> res = new ArrayList<> ();
res.add(1);
for (int i = 0; i <= lastrow.size() - 2; i++) {
int num = lastrow.get(i) + lastrow.get(i+1);
res.add(num);
}
res.add(1);
lastrow = res;
return lastrow;
}
}

复制代码

补充内容 (2019-4-4 08:23):
解题思路：先生成某一行，然后根据上一行依次产生下一行。

注意，加入通过function（lastrow）把一个 list 传到另一个子函数里面，那么，在子函数里面，各种add、remove的话，可以体现在原函数的lastrow里的

补充内容 (2019-4-4 08:24):
但是，如果lastrow = some_other_row，那么，lastrow这个原函数的lastrow的copy的值被改变了，并不会影响原函数里的lastrow的值。

AChris

04/4/2019 Day36
LeetCode 66. Plus One
Importantce【4】

解题思路：
从后往前依次对digits进行遍历，直到不用进位顺利加1。
如果都需要进位，那么最后重新生成一个数，开头是1，其他全是0。

class Solution {
public int[] plusOne(int[] digits) {
// time: O(n) 100%
// space: O(n) 26.28%
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
int[] newDigits = new int[digits.length + 1];
newDigits[0] = 1;
return newDigits;
}
}

复制代码

AChris

04/5/2019 Day37
LeetCode 236. Lowest Common Ancestor of a Binary Tree
Importantce【4】

解题思路：
这题的题目中有两个重要的前提条件：
1.所有的node的val都是unique的
2.要找的p和q都一定在p中存在

具体解法是递归。对于每一个node，如果他的subtree下面
如果有 p 就返回p；
如果有q，就返回q；
如果都有，就返回自己。
具体看 https://www.youtube.com/watch?v=13m9ZCB8gjw

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// [url]https://www.youtube.com/watch?v=13m9ZCB8gjw[/url]
// time: O(n) 70.51%
// space: O(logn) 67.93%
if (root == null) return null;
if (root.val == p.val || root.val == q.val) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
if (left == null && right == null) return null;
return left != null? left : right;
}
}

复制代码

AChris

04/6/2019 Day37
LeetCode 572. Subtree of Another Tree
Importantce【4】

解题思路：
这题的关键是将找是否是subtree的问题转化为是否是same tree的问题，然后，在通过递归来解决是否是 same tree的问题。

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
// time: O(n) 99.64%
// space: O(logn) 90.11%
if (s == null && t!= null) return false;
if (sameTree(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean sameTree(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right);
}
}

复制代码

刷题skill+编程cultivation+记录

浏览过的版块