数组
二分查找
- 二分查找： 前提是数组为有序数组，同时题目还强调数组中无重复元素。想清楚对区间的定义，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。1
2
3
4
5
6
7
8
9
10int search(vector<int>& nums, int target) { // 第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
int left = 0, right = nums.size()-1;
while (left <= right) { // 要使用 <= ，因为left == right有意义
int middle = left + (right - left) / 2; // 避免left + right溢出
if (nums[middle] > target) { right = middle - 1; } // 因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
else if (nums[middle] < target) { left = middle + 1; }
else { return middle;}
}
return -1; // 当right < left，说明不存在targrt
} - 二分查找第一个位置： 找出给定目标值在数组中的第一个位置（和结束位置）。
1
2
3
4
5
6
7
8
9
10
11
12
13int l = 0, r = nums.length - 1;
int first = -1;
while(l <= r) {
int i = (l + r)/ 2;
if(nums[i] == target) {
r = i - 1;
first = i; // 重点, 如果找最后一个位置的话就是 l = i + 1;
} else if(nums[i] < target) {
l = i + 1;
}else {
r = i - 1;
}
} - 二分查找插入 ：在排序数组中寻找是否存在一个目标值，且如果不存在数组中的时候需要返回按顺序插入的位置。可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 target 的下标」，此时需要对二分法稍作修改，不断用二分法逼近查找第一个大于等于 target 的下标 。
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (nums[mid] >= target)
right = mid - 1;
else left = mid + 1;
}
return l;
}
} - x 的平方根
1
双指针
- 原地移除 （快慢指针法）通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。（前后指针）
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。1
2
3
4
5
6
7
8
9
10int removeElement(vector<int>& nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != val) { // 此时快指针指向 新数组（原数组去除了val）中的元素
nums[slow] = nums[fast]; // 用慢指针，直接在原数组的基础上得到去除了 val 的新数组
slow++;
}
}
return slow;
} - 盛最多水的容器：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
初始化：双指针 i, j 分列水槽左右两端；循环收窄：选定两板高度中的短板，向中间收窄一格，同时更新面积最大值 res，直至双指针相遇时跳出。 - 两数之和II ：
滑动窗口
- 所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，用一个for循环代替两个for循环的功能实现，从而将O(n^2)暴力解法降为O(n)。只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置，问题是 如何移动滑动窗口的起始位置。
- 最小连续子数组： 找出数组中满足其和 ≥ target 的长度最小的 连续子数组 并返回其长度
1
2
3
4
5
6
7
8
9
10
11int minSubArrayLen(int target, vector<int>& nums) {
int i = 0, j = 0, sum = 0, ans = INT_MAX ; // i 滑动窗口起始位置，j 滑动窗口结束位置，当前活动窗口内和
for (; j < nums.size(); j++) {
sum = sum + nums[j]; // j 后移
while (sum >= target) {
ans = (j - i + 1) < ans ? (j - i + 1) : ans;
sum = sum - nums[i++]; // i 前移
}
} // ！！！ O(n):不要以为for里放一个while就以为是O(n^2)啊，主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。
return ans == INT_MAX ? 0 : ans; // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
}
模拟实现
数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力。
螺旋数组，打印数组。。。
链表
- 链表操作中的头结点处理：在 Java 中，处理链表的头结点可以直接使用原始链表进行删除操作，也可以采用设置虚拟头结点的方式进行操作。虚拟头结点是一个不存储任何实际数据的头结点，它可以简化链表操作，避免对头结点进行特殊处理。
- 需要用到头结点时，使用 ListNode* cur = head 进行链表操作，不要直接使用头结点操作！！！
- 空指针的判断：使用
if (ptr != null)来判断一个对象是否为空。Java 中的空指针用null关键字（不是一个宏定义）表示，而不是像 C++ 中的nullptr。 - 设计链表： 设计节点的结构，链表的结构和五个函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75class MyLinkedList {
class ListNode { // 设计链表中节点的数据结构
int val; // 节点上存储的元素
ListNode next; // 指向下一个节点的指针
ListNode(int x) { // 节点的构造函数
val = x;
next = null;
}
}
ListNode dummyhead; // 虚拟（假）头结点
int size; // 记录链表长度，在add, delete操作前进行判断
public MyLinkedList() {
dummyhead = new ListNode(0);
size = 0;
}
public int get(int index) { // 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
if (index < 0 || index >= size) return -1;
ListNode cur = dummyhead.next;
while (index-- > 0) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) { // 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
ListNode cur = new ListNode(val);
cur.next = dummyhead.next;
dummyhead.next = cur;
size++;
}
public void addAtTail(int val) { // 将值为 val 的节点追加到链表的最后一个元素
ListNode cur = dummyhead;
ListNode tail = new ListNode(val);
while (cur.next != null) {
cur = cur.next;
}
cur.next = tail;
size++;
}
public void addAtIndex(int index, int val) { // 在链表中的第 index 个节点之前添加值为 val 的节点。
if (index < 0) { // 根据下标判断插入位置
addAtHead(val);
} else if (index == size) {
addAtTail(val);
} else if (index > size) {
return;
} else {
ListNode cur = dummyhead;
ListNode node = new ListNode(val);
while (index-- > 0) {
cur = cur.next;
}
node.next = cur.next;
cur.next = node;
size++;
}
}
public void deleteAtIndex(int index) { // 如果索引 index 有效，则删除链表中的第 index 个节点。
if (index < 0 || index >= size) return;
ListNode cur = dummyhead;
while (index-- > 0) {
cur = cur.next;
}
ListNode nex = cur.next.next;
cur.next = nex;
size--;
}
} - 链表翻转：
- 环： 相遇
1.判断有无环： 定义快慢指针，慢的先走，快的后走，一次一步。若有环，快指针必然追上满指针，且相遇位置必然在环内。
2.确定环的入口： 定义两个指针，一个位于链表头指针，一个位于快慢指针相遇位置。这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
哈希表
- 在 Java 中，哈希（Hash）是将数据映射到固定大小的散列值的技术。哈希函数用于将输入数据转换为散列值，通常用于快速查找或存储数据。通过调用对象的
hashCode()方法获得数据的散列码（hash code）。同时，Java 中也提供了java.util.Objects类，其中包含了hash()方法，用于计算对象的哈希值。
Java 的标准库提供了java.util包中的一些类和接口，比如HashMap、HashSet等。 - 什么时候使用哈希法？当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
- 四数之和II： 四个数组各组一个元素，四元素和为0。找出四数的不同组合个数。
两个哈希表：map1，map2，分别记录 num1与num2 各种组合的和的个数，num3与num4 各种组合的和的个数
for(auto pair : map1)，若 map2[0 - pair.first] 存在，则 ans += pair.second * map2[0 - pair.first] - 三数之和： 一个数组，找出其中三个元素和为0。找出所有不重复的三元组。
一层循环（a） + 每层循环中双指针（b，c）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end()); // 首先将数组排序
for(int i = 0; i < nums.size() - 2; i++) { // 一层for循环（a）
if (nums[i] > 0) break;
if (i>0 && nums[i]==nums[i-1]) continue; // 去重a！！！
int left = i + 1; // 循环内定义双指针（b，c）
int right = nums.size() - 1;
while (left < right) { // 循环条件！！
// 不要在这里直接先去重b，c，免得一个答案都没有
if (nums[i] + nums[left] + nums[right] == 0) {
ans.push_back({nums[i], nums[left], nums[right]});
// 一定要先执行上一句代码，即先找到一个答案 【0,0,0,0,0】
// 再去执行下两句，去重b，c！！！
while (left<right && nums[left]==nums[left+1]) left++;
while (left<right && nums[right]==nums[right-1]) right--;
// 找到答案，左右指针同时收缩 【-2，0，0,2,2】
left++;
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) left++;
else if (nums[i] + nums[left] + nums[right] > 0) right--;
}
}
return ans;
} - 四数之和： 和三数之和是一个思路，都是使用双指针法, 基本解法就是在三数之和的基础上再套一层for循环。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
字符串
- Java 中并没有像 Cpp中的
getline函数，而是可以使用Scanner或者BufferedReader从控制台读取一行文本。1
2
3
4
5import java.util.Scanner;
// ...
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine(); // ...
scanner.close();1
2
3BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = reader.readLine();
reader.close(); - 翻转字符串里的单词： 移除多余空格、将整个字符串反转、将每个单词反转
移除多余空格：参考快慢指针原地去除数组特定元素的方法（题目见）
翻转问题：考虑 部分翻转 + 整体翻转
同构字符串：需要我们判断 s 和 t 每个位置上的字符是否都一一对应，即 s 的任意一个字符被 t 中唯一的字符对应，同时 t 的任意一个字符被 s 中唯一的字符对应。这也被称为「双射」的关系。
因此，我们维护两张哈希表，第一张哈希表 s2t 以 s 中字符为键，映射至 t 的字符为值，第二张哈希表 t2s 以 t 中字符为键，映射至 s 的字符为值。从左至右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突（即遍历 s 当前下标 i 已经存在映射 s2t.get(s.charAt(i)) 且不为 t.charAt(i)，或遍历 t 当前下标 i 已经存在映射 t2s.get(t.charAt(i)) 且不为 s.charAt(i)）说明两个字符串无法构成同构，返回 false - KMP模式匹配： 当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
子串和主串匹配出现冲突 -> 寻找子、主串匹配冲突位置前部分的最长相等前后缀（查冲突位置前一位在前缀表中的值[next数组]） -> 子串匹配位置返回到相等前缀后一位（即冲突位置在next中的值），主串匹配位置不移动（也即返回到相等后缀后一位），再次开始匹配。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32void getNext(int* next, const string& s) { // 1. 利用模式串s，构造前缀表next
int j = 0; // （若j为 -1，前缀表要进行统一减一的操作）
next[0] = 0; // next[i] 表示 i（包括i）之前最长相等的前后缀长度
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j > 0 && s[i] != s[j]) { // j前后缀不相同了（要保证大于0，因为下面有取j-1作为数组下标的操作
j = next[j - 1]; // 向前回退（注意这里，是要找前一位的对应的回退位置了
}
if (s[i] == s[j]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
int strStr(string haystack, string needle) { // 2. 用模式串needle 匹配主串haystack
if (needle.size() == 0) return 0;
int next[needle.size()];
getNext(next, needle); // 用模式串创建next数组 O(n)
int j = 0; // 模式串中当前匹配位置
for (int i = 0; i < haystack.size(); i++) { // O(m)，则KMP算法为O(m+n)
while(j > 0 && haystack[i] != needle[j]) { // 不匹配，j 寻找之前匹配的位置
j = next[j - 1];
}
if (haystack[i] == needle[j]) { // 匹配，j和i同时向后移动
j++;
}
if (j == needle.size() ) { // 文本串s里出现了模式串t
return (i - needle.size() + 1);
}
}
return -1;
}
栈与队列
- 匹配问题都是栈的强项： 括号匹配，相邻元素匹配，逆波兰式匹配（注意后从栈中弹出的数，是操作符的左操作数），，
- 滑动窗口最大值： 给定数组 nums，有大小为 k 的滑动窗口从数组的最左侧一位位移向最右侧。每次返回滑动窗口中的最大值。
单调队列：维护一个单调递增（减）的队列，最大（小）值在队首。单调队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小（小到大）的。具体做法是：
pop()时：若要从滑动窗口中去掉的元素，其值等于此时单调队列队首值（即最大值），那么将队首元素从deque.front()弹出。滑动窗口每次向右滑动，先pop()，后push()。
push()时：从双向队列末尾push数值，若大于前面的数，那么将前面的数从deque.back()弹出，直到push的数值小于等于其前面元素的数值为止。这样就保持了队列里的数值是单调从大到小的了，且最大值在队首deque.front()。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class MyQueue {
public: // !!！ 注意别漏了public，否则默认private无法从变量访问
deque<int> que;
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
int front() { return que.front(); }
}; - 前 K 个高频元素： 给定一个非空的整数数组，返回出现频率前 k 高的元素。
优先级队列：其实就是一个披着队列外衣的堆，对外接口只是从队头取元素，从队尾添加元素，且优先级队列内部元素是自动依照元素的权值排列。 缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。每次pop()弹出堆顶元素。priority_queue：c++中已实现的数据结构，其底层实现等同于堆，从小到大排就是小顶堆，从大到小排就是大顶堆。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class mycomparison { // 小顶堆
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
unordered_map<int, int> map; // 要统计元素出现频率
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++; }
// 对频率排序, 维护一个大小固定为k的小顶堆，扫面所有频率的数值
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
for (auto pair : map) {
pri_que.push(pair);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
LinkedList（双向链表）
在 Java 中，LinkedList 是双向链表的实现，每个元素都包含一个指向前一个元素和一个指向后一个元素的指针。这使得插入和删除操作在链表中非常高效，但随机访问较慢。以下是 LinkedList 的一些常见用法：
1 | import java.util.LinkedList; |
Deque（双端队列）
Deque 是双端队列容器的实现，支持在两端进行高效的插入和删除操作，并且允许随机访问。
1 | import java.util.Deque; |
PriorityQueue（优先队列）
在 Java 中，PriorityQueue 可以实现最大堆和最小堆。默认情况下是最小堆，可通过提供自定的比较器来实现最大堆或最小堆。
1 | import java.util.PriorityQueue; |
1 | // 实现最小堆： |
二叉树
- 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则为满二叉树。
- 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。 - 二叉搜索树 BST：具有有序性质，适用于快速查找、插入和删除操作。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树 - 平衡二叉搜索树 AVL： 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
递归（traversal）三要素: 确定递归函数的参数和返回值 -> 确定终止条件 -> 确定单层递归的逻辑
- 深度优先遍历：
前序遍历（递归法，迭代法）， 中序遍历（递归法，迭代法）， 后序遍历（递归法，迭代法）
也可以利用栈实现迭代形式的遍历。 - 广度优先遍历：
层序遍历（迭代法）一个二叉树。就是从左到右一层一层的去遍历二叉树。借用队列来实现。
学会二叉树的层序遍历，可以一口气打下十题：二叉树的右视图，二叉树的层平均值，在每个树行中找最大值，填充每个节点的下一个右侧节点指针，填充每个节点的下一个右侧节点指针II，二叉树的最大深度，二叉树的最小深度，，，1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void traversal(TreeNode* cur, vector<int>& vec) { // 前序遍历（递归法）
if (cur == NULL) return;
vec.push_back(cur->val); // 先 中间节点
traversal(cur->left, vec); // 再 左子树
traversal(cur->right, vec); // 再 右子树
}
vector<int> preorderTraversal(TreeNode* root) { // 前序遍历（迭代法）
stack<TreeNode*> st; // 中、后序遍历的迭代法无法与之简单类比，但存在统一迭代法
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right); // 右（空节点不入栈）
if (node->left) st.push(node->left); // 左（空节点不入栈）
} // 要先加入右孩子再加入左孩子呢,这样出栈的时候才是中左右的顺序。
return result;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20vector<vector<int>> levelOrder(TreeNode* root) { // 层序遍历模板
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
for (int i = 0; i < size; i++) { // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
// for(int i = 0; i < node->children.size(); i++) { // 如果有多个孩子节点
// if(node->children[i]) que.push(node->children[i]) }
}
result.push_back(vec);
}
return result;
} - 翻转二叉树： 前序遍历，翻转左右子树，翻转左、右子树的左右子树。
- 平衡二叉树： 同时操作两个二叉树。判断对称二叉树不是比较左右节点，要比较的是根节点的左子树与右子树是不是相互翻转的，即其实我们要比较的是两个树（这两个树是根节点的左右子树）
1
2
3
4
5
6
7
8
9
10bool compare(TreeNode* left, TreeNode* right) {
// 首先排除空节点的情况、数值不相同的情况
if ((left == NULL && right != NULL)||(left != NULL && right == NULL)) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
// 左右节点都不为空，且数值相同的情况; 此时才做递归，做下一层的判断
bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左
return outside && inside; // 左子树：中、 右子树：中 （逻辑处理）
} - 二叉树最大深度： 二叉树的最大深度就是根节点的最大深度。一个节点的最大深度 = max{ 左孩子的最大深度， 右孩子的最大深度 }
1
2
3int maxDepth(TreeNode* root) {
if (root == null) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right)); } - 二叉树最小深度： 不能简单地认为一点的最小深度为 1 + min{左,右孩子的深度}，要从根到
叶子节点的路径才能算一个深度值。（根到一个中间节点，其某一孩子为空指针，的路径不算一个深度）1
2
3
4
5
6int traversal(TreeNode* root) {
if(!root) return 0;
if(!root->left && !root->right) return 1;
if(!root->left) return 1 + traversal(root->right);
if(!root->right) return 1 + traversal(root->left);
return 1 + min(traversal(root->left), traversal(root->right)); } - 二叉搜索树： 二叉搜索树可是有序的。遇到在二叉搜索树上求什么最值啊，差值之类的，就把想成在它通过中序遍历转换成的一个有序数组上求最值，求差值，，
- 二叉搜索树中的众数： 遍历+双指针，，，，
- 从前序与中序遍历序列构造二叉树： 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20Map<Integer, Integer> indexMap;
// 每次结合preorder和inorder数组确定一个根节点（画图看很清晰）
public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right,
int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) return null;
TreeNode root = new TreeNode(preorder[preorder_left]);
int inorderIndex = indexMap.get(preorder[preorder_left]);
int leftSize = inorderIndex - inorder_left;
// 递归地确定当前根节点的左右子树的根节点
root.left = myBuildTree(preorder, inorder, preorder_left+1, preorder_left+leftSize, inorder_left, inorderIndex-1);
root.right = myBuildTree(preorder, inorder, preorder_left+leftSize+1, preorder_right, inorderIndex+1, inorder_right);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
indexMap = new HashMap<>();
int n = inorder.length;
// 记录当前根节点（preorder数组第一位）在inorder数组中的位置
for(int i = 0; i < n; i++) indexMap.put(inorder[i], i);
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
} - 二叉树求最小公共祖先： 需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) { // 递归结束条件
return root;
}
// 后序遍历
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) { // 若未找到节点 p 或 q
return null;
}else if(left == null && right != null) { // 若找到一个节点
return right;
}else if(left != null && right == null) { // 若找到一个节点
return left;
}else { // 若找到两个节点
return root;
}
}
}
图
深度优先搜索（DFS）
- DFS从起始节点开始，沿着一条路径一直访问到最深处，然后回溯到上一层，继续访问其他路径。它通过递归或栈实现，保证深度遍历直到底部，然后回溯继续探索其他路径。
- dfs的代码框架: （其实dfs就是回溯，其实二叉树的前中后序遍历就是dfs）
1
2
3
4
5
6
7
8
9
10
11void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
} - 所有可能的路径： 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）。 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21List<List<Integer>> ans; // 结果路劲列表
List<Integer> path; // 当前路劲
// index表示从当前深搜到哪个节点
public void dfs(int[][] graph, int index) {
if(index == (graph.length - 1)) {
ans.add(new ArrayList<>(path)); // ！！不要ans.add(path); 否则加入的是引用的同一个对象
return;
}
for(int i = 0; i < graph[index].length; i++) {
path.add(graph[index][i]);
dfs(graph, graph[index][i]);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
path = new ArrayList<Integer>();
ans = new ArrayList<List<Integer>>();
path.add(0);
dfs(graph, 0);
return ans;
}
广度优先搜索（BFS）
- BFS从起始节点开始，依次访问其邻居节点，然后访问邻居节点的邻居，以此类推。它通过队列实现，保证先访问离起始节点近的节点，再访问离起始节点远的节点。
- 广搜代码模板：（该模板针对的 是 四方格地图模型）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited 标记访问过的节点，不要重复访问
// x, y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que; // 定义队列
que.push({x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
while(!que.empty()) { // 开始遍历队列里的元素
pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
int curx = cur.first;
int cury = cur.second; // 当前节点坐标
for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())
continue; // 坐标越界了，直接跳过
if (!visited[nextx][nexty]) { // 如果节点没被访问过
que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
}
}
}
}
贪心算法
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
难点就是如何通过局部最优，推出整体最优。靠自己手动模拟，如果模拟可行就可以试一试贪心策略，如果不可行可能需要动态规划。
如何验证可不可以用贪心算法呢？最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
如果需要严格的数学证明，一般有两种方法：数学归纳法、反证法。
可以说：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
贪心一般解题步骤
一般分为如下四步：
1.将问题分解为若干个子问题 2. 找出适合的贪心策略 3. 求解每一个子问题的最优解 4. 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，，，做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。
最大子序和： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：输入 [-2,1,-3,4,-1,2,1,-5,4]，输出 6。解释: 连续子数组 [4,-1,2,1] 的和最大，为 6
解答：直接遍历一路加过去就行，记录目前的“连续和”以及最大“连续和”，当目前的“连续和”为负数时置0，“重新”开始计算“连续和”。
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。全局最优：选取最大“连续和”摆动序列：
买卖股票的最佳时机 II： 给定股票每天的价格，计算所能获取的最大利润，可以尽可能地完成更多的交易（多次买卖一支股票）。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有 一股 股票。
解答：想到选一个低的买入，再选个高的卖，再选一个低的买入…..循环反复。即最终利润是可以分解的，把利润分解为每天为单位的维度，而不是从 0 天到第 n 天整体去考虑，那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1])…..(prices[1] - prices[0])。最大利润就是取其中的所有正值之和。跳跃游戏 II：
加油站：环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
解答：首先如果总油量减去总消耗大于等于零，那么一定可以跑完一圈，即各个站点的加油站 剩油量rest[i]=gas[i] - cost[i] 相加之和一定是大于等于零的。令 i 从0开始累加 rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。分发糖果：ratings[] 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：1、每个孩子至少分配到 1 个糖果。2、相邻两个孩子评分更高的孩子会获得更多的糖果。
解答：这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。先确定右边评分大于左边的情况（也就是从前向后遍历）只要右边评分比左边大，右边的孩子就多一个糖果；再确定左孩子大于右孩子的情况（从后向前遍历）只要左边评分比右边大，左边的孩子就多一个糖果。1
2
3
4
5
6
7
8
9
10for(int i = 1; i < n; i++) {
if(ratings[i] > ratings[i-1]) candys[i] = candys[i-1] + 1;
}
for(int i = n-2; i >= 0; i--) {
if(ratings[i] > ratings[i+1]) {
// 此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量），取最大值。
// 即局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
candys[i] = max(candys[i], candys[i+1] + 1);
}
}
回溯算法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。
回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作。
回溯法解决的问题都可以抽象为树形结构，所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
回溯（backtracking）三步曲：回溯函数模板返回值及参数 -> 函数终止条件 -> 回溯搜索的遍历过程
回溯函数模板：
1
2
3
4
5
6
7
8
9
10
11void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}- 组合问题： 给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合;
示例: 输入: n = 4, k = 2 输出: [ [1,2], [1,3], [1,4], [2,3],[2,4], [3,4] ]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
private:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果
void backtracking(int n, int k, int startIndex) { // startIndex记录下一层递归，搜索的起始位置
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
path.push_back(i); // 处理节点
backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索从i+1开始
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
}; - 子集问题： 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [], [1], [1, 2], [1,2,3], ]
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！ - 分割回文串： 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
示例: 输入: “aab” 输出: [ [“aa”,”b”], [“a”,”a”,”b”] ]
其实切割问题类似组合问题，例如对于字符串abcdef：
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。
！！！一定建立起for循环横向遍历，递归纵向遍历的概念！！！1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void backtracking(string s, int startindex) {
if (startindex >= s.size()) { // 0.终止条件_遍历到“叶子结点”，一组成功样例
ans.push_back(path);
return;
}
for (int i = startindex; i < s.size(); i++) {
if (ishuiwen(s.substr(startindex, i - startindex + 1))) {
path.push_back(s.substr(startindex, i - startindex + 1));
} else {
continue; // 1.处理节点：切割startindex~i的子串
} // ！！不要在终止条件里处理节点！！
backtracking(s, i + 1); // 2.处理完节点后遍历
path.pop_back(); // 3.回溯
}
} - 排列问题： 给定一个 没有重复 数字的序列，返回其所有可能的全排列。排列是有序的，即[1,2] 和 [2,1] 是两个集合。
示例：输入[1,2,3]，输出 [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// 元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1
// 所以处理排列问题不使用startIndex，i从0开始遍历。
if (used[i] == true) continue; // path里已经收录的元素，直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
// used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
hhh
动态规划
- 动态规划，Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
- 动态规划算法一般分为自顶向下的记忆化搜索和自底向上的递推方法。自顶向下方法使用递归来解决问题，但在递归过程中使用记忆数组（或哈希表）来保存已经计算过的子问题的解，以避免重复计算。自底向上方法则从子问题的基础解逐步构建出问题的解。(递归到动规的一般转化方法：递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始，逐步填充数组，相当于计算递归函数值的逆过程。)
- 动态规划通常适用于具备以下特点的问题：
1. 重叠子问题： 问题的解可以由多个子问题的解组合而来，这些子问题可能会被重复解决。
2. 最优子结构： 问题的最优解可以通过其子问题的最优解构造得到。
3. 无后效性： 当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
动态（DP）规划五步曲 1. 确定dp数组（dp table）以及下标的含义 -> 2. 确定递推公式 -> 3. dp数组如何初始化 -> 4. 确定遍历顺序 -> 5. 举例推导dp数组
- 01背包问题： 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
1.dp数组以及下标含义：使用二维数组dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.递推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
3.dp数组初始化：关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
4.遍历顺序：先遍历物品、先遍历背包重量都可以。把dp表遍历填满就行。
5.举例推导dp：做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！1
2
3
4
5
6
7
8
9
10
11
12
13
14void test_2_wei_bag_problem1() {
int bagweight = 4;
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0)); // 二维数组
for (int j = weight[0]; j <= bagweight; j++) dp[0][j] = value[0]; // 初始化
for (int i = 1; i < weight.size(); i++) { // 遍历物品
for (int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
cout << dp[weight.size() - 1][bagweight] << endl;
} - 打家劫舍： 每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
1.dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2.dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])；决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑 i-1 房，（注意这里是考虑，并不是一定要偷i-1房！）
3.dp数组初始化：递推公式的基础就是dp[0] 和 dp[1]；dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值
4.遍历顺序：dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！
5.举例推导dp数组
打家劫舍II： 房子首尾相连。
情况一：考虑不包含首尾元素； 情况二：考虑包含首元素，不包含尾元素； 情况三：考虑包含尾元素，不包含首元素
答案即情况二、三之间的大的值 - 最长递增子序列：找到整数数组 nums 中最长严格递增子序列的长度。例如，[3,6,2,7] 是 [0,3,1,6,2,2,7] 的子序列。
定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取！！！1
2
3for(int i = 1; i < n; i++) {
for(int j = 0; j < i; j++) {
if(nums[i] > nums[j] && (1 + dp[j]) > dp[i]) dp[i] = dp[j] + 1; // 返回dp[]最大值 }} - 股票问题： 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
dp[i][0] 表示第i天持有股票所得最多现金 ；dp[i][1] 表示第i天不持有股票所得最多现金。
dp[i][0] = max(dp[i - 1][0], -prices[i]); dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]); - 子序列问题：
- 单词拆分： 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
输入 s = “leetcode”, wordDict = [“leet”, “code”]。返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。1
2
3
4
5
6
7
8
9
10
11
12
13Set<String> set = new HashSet(wordDict); // 直接用数组构建set
boolean[] dp = new boolean[s.length() + 1]; // 考虑dp数组长度和元素意义！！
Arrays.fill(dp, false);
dp[0] = true; // 注意初始情况！！
for(int i = 1; i <= s.length(); i++) {
for(int j = 0; j < i; j++) {
if(dp[j] && set.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];