链表
题目链接：826. 单链表
快速排序
quick sort的一道题目，关于字符串排序的，剑指offer上的。剑指 Offer 45. 把数组排成最小的数
public static void quickSort(int[] arr, int l, int r){
if (l >= r) {
return;
}
int pivot = arr[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while(arr[i] < pivot);
do j--; while(arr[j] > pivot);
if (i < j) swap(arr, i, j);
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
public static void quickSort(int[] arr, int l, int r){
if (l >= r) {
return;
}
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= arr[l]) j--;
while (i < j && arr[i] <= arr[l]) i++;
swap(arr, i, j);
}
swap(arr, i, l);
quickSort(arr, l, i - 1);
quickSort(arr, i + 1, r);
}
Quick Select
和quick sort基本一致吧，就是找出top k元素。其实对于top k元素，找到k或者k-1均可，这里方便起见，直接80行就不换乘 i < k - 1了。
private void quickSelect(int[] nums, int l, int r, int k){
Map<Integer, Integer> temp = map;
if (l >= r) {
return;
}
int pivot = nums[l], i = l, j = r;
while (i < j) {
while (i < j && nums[j] <= pivot) j--;
while (i < j && nums[i] >= pivot) i++;
swap(nums, i, j);
}
swap(nums, i, l);
if (i > k) {
quickSelect(nums, l, i - 1, k);
} else if (i < k) {
quickSelect(nums, i + 1, r, k);
}
}
归并排序
上面的题目一样可以用mergeSort来做，在submission里面可以看。
public static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int mid = l + r >> 1;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
int[] temp = new int[r - l + 1];
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= r) {
temp[k++] = arr[j++];
}
for (int i = 0; i < temp.length; i++) {
arr[l + i] = temp[i];
}
}
二分法
二分查找的边界问题一直很困扰人额，有两种二分查找，一种是求左边界，另一种是求右边界。最直接的题目就是Leetcode 34。既要求左边界，也要求右边界。
注意，这里左边界和右边界只是一种象征，实际的题目不会这么直白。例如LeetCode 875.
回到正题，网上有很多二分查找的模板，这里只写我自己的模板，以下所有的区间全都都是闭区间，思路参考acwing的yxc。
这里有两种情况
区间被分为[l, mid]和[mid + 1, r]
这种情况的意思就是，当我们做check(mid)的时候，mid是否在我们希望的区间内。换句话说，当mid满足条件时，我们是把它放到左区间还是右区间。比如{1,2,2,2,3,4,5,5}，我们要找到2的左边界，那么当我们找到1个“2”的时候，这个2有可能就是我们要找的值，对吧？那么我们就应该让r = mid，把右边不要的部分去掉，再去遍历左边。反之亦然。
这里的终止条件都是l==r！！！！
public static void binarySearch1(int l, int r){
int mid = l + r >> 1;
if (check(mid)){
r = mid;
} else {
l = mid + 1;
}
}
区间被分为[l, mid - 1]和[mid, r]
道理和上面类似，只是此时需要mid = (l + r + 1)/2。原因在于除法是向下取整，存在精读缺失，有可能无限死循环。
public void binarySearch2(int l, int r){
int mid = (l + r + 1)/2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
取模
这样为了防止负数！！！一定要 +mod 再 % mod
private int mod(int a) {
return (a % mod + mod) % mod;
}
快速幂
快速幂就是求大数字a的大数字b次方对p取模。极其重要！！！
private static int process(int a, int b, int p) {
int ans = 1 % p;
while (b > 0) {
if ((b & 1) == 1) {
ans = (int)((ans * 1L * a) % p);
}
a = (int)((a * 1L * a) % p);
b = b >> 1;
}
return ans;
}
最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
二维前缀和
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]; // 求前缀和
}
while (q--) {
int x1,y1,x2,y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
// 算子矩阵的和
printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
}
return 0;
}
单调栈
首先，从名字上来看，单调栈的意思就是，我们通过某些操作，使得栈里的元素都是单调的。
单调栈解决的问题是“给出一个无序数组，找到每个数字左（右）侧离他最近比它大（小）的数字”。如果一个问题能够抽象成这种类型，那么毫无疑问，马上用单调栈。或者说其他变种，类似于LeetCode 155. Min Stack，blog解析见LeetCode 456. 132 Pattern。
举例：给出一个数组a[]，若要找到 a[7]左侧比它大的数字，假设有a[3]和a[5]，那么我们应该选择a[5]而不是a[3]。那么，换句话说，对于任意两个数a[i]和a[j]，如果”a[i] <= a[j] && i < j，那么a[i]可以被抛弃掉，因为对于j后面的数字，a[j]一定是更优的解。”
这种做法的思想可以理解成保守式单调栈，要哪侧的“第一个最大/最小”，就从哪侧开始遍历，保证遍历到每个数的时候，其结果都能确定。
例题：LeetCode 496. Next Greater Element I，该题目的解析link传送门
这里我们写一个模板，是找到每个数字左侧第一个比它大的数字。
public void montonousStack(int[] nums) {
Stack<Integer> stack = new Stack();
for (int num : nums) {
while (!stack.isEmpty() && stack.peek() <= num) {
stack.pop();
}
if (stack.isEmpty()) {
System.out.print("-1 ");
} else {
System.out.printf("%d ", stack.peek());
}
stack.push(num);
}
}
注意：单调栈并不一定是从左向右，或者从右向左！！！
如上面的左侧第一个更大数字，是从左向右遍历的。那么换种思想，我们从右向左遍历：如果当前数字比栈顶或者等于，则压入；若比栈顶大，则不断弹出，直到栈为空或者小于等于栈顶，然后压栈。最后栈底剩下的元素，是没有左侧更大元素的！
这种做法的思想可以理解成探索式单调栈，对于未知的情况，我们先保留，最后再一起处理。
public void montonousStack(int[] nums) {
Stack<Integer> stack = new Stack();
for (int i = nums.length； i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() < nums[i]) {
System.out.printf("index %d left greater element is %d\n", stack.pop(), nums[i]);
}
stack.push(i);
}
while (!stack.isEmpty()) {
System.out.printf("index %d left greater element is %d\n", stack.pop(), -1);
}
}
单调队列
从单调队列这个名称来看，就是解决某些问题的时候，我们维护一个队列，使得队列里面的的数字呈现单调的情况。
单调队列解决的问题可以抽象为“求滑动窗口里的最大值和最小值”，最直接的题目就是LeetCode 239. Sliding Window Maximum。
对于这种问题，我们举个例子，[1, 3, -1, -3, 5, 3, 6, 7]，窗口大小为3，输出每个窗口里面的最小值（和239基本一致，只是有小区别）。 第一个窗口为[1, 3, -1]，我们可以发现，当-1只要还在我们的窗口里的时候，在-1左侧的1和3就绝不可能为最小值。也就是说这两个数对于我们找窗口内最小值完全是冗余的！！！因此，我们需要一种数据结构，保证窗口的正常运转，要能够一边进，一边出，因此我们选择Java里的Deque，双端队列，逻辑如下。
public int[] minSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList();
int n = nums.length;
int[] res = new int[n - k + 1];
for (int i = 0; i < n; i++) {
if (!deque.isEmpty() && i - k + 1 > deque.peekFirst()) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
res[i - k + 1] = nums[deque.peekFirst()];
}
}
return res;
}
}
我们还可以使用数组来模拟双端队列。注意写法。
int N = 100010, hh = 0, tt = -1;
int[] q = new int[N];
public int[] minSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
if (hh <= tt && i - k + 1 > q[hh]) hh++;
while (hh <= tt && nums[q[tt]] >= nums[i]) tt--;
q[++tt] = i;
if (i >= k - 1) {
res[i - k + 1] = nums[q[hh]];
}
}
return res;
}
树
递归的写法没啥好说的，这里强调迭代的写法。
前序遍历
题目链接：前序遍历
这里提供两种遍历思路：
- 遍历时先压右子树，再压左子树。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> list = new ArrayList<Integer>();
TreeNode node = root;
stack.push(node);
while (!stack.isEmpty() && node != null) {
node = stack.pop();
list.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return list;
}
}
- 压栈的目的只是为了回溯找右节点，不是压左右子树，而是访问过的节点。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> list = new ArrayList<Integer>();
TreeNode node = root;
while (！stack.isEmpty() || node != null) {
if (node != null) {
list.add(node.val);
stack.push(node);
node = node.left;
} else {
node = stack.pop().right;
}
}
return list;
}
}
中序遍历
题目链接：中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> list = new ArrayList<Integer>();
TreeNode node = root;
while (node != null) {
if (node.left != null) {
stack.push(node);
node = node.left;
} else {
list.add(node.val);
while (node.right == null && !stack.isEmpty()) {
node = stack.pop();
list.add(node.val);
}
node = node.right;
}
}
return list;
}
}
- 判断节点是否为空
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> list = new ArrayList<Integer>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
list.add(node.val);
node = node.right;
}
}
return list;
}
}
后序遍历
题目链接：后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> list = new ArrayList<Integer>();
TreeNode node = root, lastNode = root;
stack.push(node);
while (!stack.isEmpty() && node != null) {
node = stack.pop();
if ((node.left == null && node.right == null) || node.left == lastNode || node.right == lastNode) {
list.add(node.val);
lastNode = node;
} else {
stack.push(node);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
return list;
}
}
Morris中序遍历
其核心点在于，利用“左子树最右侧节点”来辅助判断是否已经遍历过左子树了。
public List<Integer> inorderTraversal(TreeNode root) {
TreeNode cur = root;
List<Integer> list = new ArrayList<>();
while (cur != null) {
TreeNode mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
list.add(cur.val);
}
} else {
list.add(cur.val);
}
cur = cur.right;
}
return list;
}
并查集
并查集建议观看花花酱的并查集视频讲解
这里使用size来代替rank，也是可以的，复杂度上没有区别。LeetCode 547
class UF {
int[] parents;
int[] sizes;
int count;
public UF(int n) {
parents = new int[n];
sizes = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parents[i] = i;
sizes[i] = 1;
}
}
public int find(int u) {
if (u == parents[u]) {
return u;
}
parents[u] = find(parents[u]);
return parents[u];
}
public void union(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) {
return;
}
if (sizes[pu] < sizes[pv]) {
parents[pu] = pv;
sizes[pv] += sizes[pu];
} else {
parents[pv] = pu;
sizes[pu] += sizes[pv];
}
}
}
Trie
class TrieNode {
TrieNode[] sons;
boolean isWord;
TrieNode() {
sons = new TrieNode[26];
isWord = false;
}
public TrieNode get(char c) {
int idx = c - 'a';
return sons[idx];
}
public boolean containsKey(char c) {
int idx = c - 'a';
return sons[idx] != null;
}
public void add(char c) {
int idx = c - 'a';
sons[idx] = new TrieNode();
}
}
infra + cloud
front-side， visual team 25-30 people
Seattle， 20 engineers， backend engineer
3 teams：
bidding backend system，
SRE team
google cloud，Big Data，
- 确认输入输出，是否会有异常；确认输出输出。比如输入如果没有k个咋办。以及先说明定义的函数。
- 一边说一边说明每一段代码的逻辑，不用念代码；说代码是干啥的就行。
- 可以问面试官要一下hint，要一下example。写完以后主动.
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
5
/ \
4 8
/ / \
11 13 4
/ \ /
7 2 5 1
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
反馈：
- 边界case没确认完全，比如root为null
- overflow没有确认
