二叉树前序遍历
无重复字符的最长子串
最小覆盖子串
二叉树前序遍历
问题：
给你一棵二叉树的根节点 root ，返回其节点值的 前序遍历 。
代码示例：
递归法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void postorder(struct TreeNode *root, int *res, int *resSize) {
if (root == NULL) {
return;
}
postorder(root->left, res, resSize);
postorder(root->right, res, resSize);
res[(*resSize)++] = root->val;
}
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = malloc(sizeof(int) * 2001);
*returnSize = 0;
postorder(root, res, returnSize);
return res;
}
迭代法：
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
int *postorderTraversal(struct TreeNode *root, int *returnSize) {
int *res = malloc(sizeof(int) * 2001);
*returnSize = 0;
if (root == NULL) {
return res;
}
struct TreeNode **stk = malloc(sizeof(struct TreeNode *) * 2001);
int top = 0;
struct TreeNode *prev = NULL;
while (root != NULL || top > 0) {
while (root != NULL) {
stk[top++] = root;
root = root->left;
}
root = stk[--top];
if (root->right == NULL || root->right == prev) {
res[(*returnSize)++] = root->val;
prev = root;
root = NULL;
} else {
stk[top++] = root;
root = root->right;
}
}
return res;
}
解题思路：
思路很简单，创建一个临时节点，挨个反转节点之间的关系，临时头结点为temp，每次移动temp和curr即可
无重复字符的最长子串
题目：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int end = 0, start = 0; end < n; end++) {
char alpha = s.charAt(end);
if (map.containsKey(alpha)) {
start = Math.max(map.get(alpha), start);
}
ans = Math.max(ans, end - start + 1);
map.put(s.charAt(end), end + 1);
}
return ans;
}
}
解题思路:
这道题很多人说采用的浮窗法，我觉得说是双指针法更合适。如图：
看上图，题目是找不重复的最长子串，那么就意味着字符串两边的字符肯定是一样的，以此为入手点：
定义一个Map保存字符和他最后出现的位置。
定义一个指针，名字为start，指向字符串最开始，用来记录当前不重复子串的起点。
定义一个指针，一个是从前往后遍历，每次遇到一个字符，将这个字符作为key，他当前的位置作为value存储下来，名字为end
end指针一次向后遍历，同时计算end到start之前的长度，如果这次遍历时取到的字符在Map中存在，那么更新start的位置为Map中存储的上一次的位置和start两者取最大，因为start标记的已经重复过的，如果新值比start小，说明在新值后已经有过一个比他更小的重复段了，他就不是最大的不重复。
最小覆盖子串
题目：
给你一个字符串s、一个字符串t 。返回s中涵盖t所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
示例代码：
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
class Solution {
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
int tLen = t.length();
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = -1;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
while (r < sLen) {
++r;
if (r < sLen && ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {
Iterator iter = ori.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
解题思路：
这里采用的是窗口法，主要的操作流程如下图：
1 创建一个存储Map，记录当前窗口中包含的字母以及对应的数量。
2 创建左右两个指针
3
3.1 如果当前存储map没有包含子字符串，那么右指针向右；
3.2 如果当前存储map有完整包含子字符串，那么左指针向右；
4 如果上面3.2左指针向右移动后不包含，那么异动前就是最小覆盖子串候选结果之一。移动完之后，继续进行第三步的操作，知道得到新的候选结果，比较候选结果中字符的数量，取最小值。
