双指针
回文字符串
680. 验证回文字符串 Ⅱ
由于每次可以删除一个字符，所以从两端开始向中间扫描，如果有不同的字符则判断删除前一个或者后一个看是否构成回文串。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
bool validPalindrome(string s) {
int len = s.length();
string t = s;
reverse(s.begin(), s.end());
if(t == s)
return true;
int l = -1, r = len;
while(++l < --r){
if(s[l] != s[r]){
return isPalidrome(s, l, r - 1) || isPalidrome(s, l + 1, r);
}
}
return true;
}
bool isPalidrome(string s, int i, int j){
while(i < j){
if(s[i++] != s[j--])
return false;
}
return true;
}
};
环形链表
141. 环形链表
用两个快慢指针，一个每次前进一格，一个每次前进两个。如果有环则这两个指针一定会相遇。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL)
return false;
ListNode *slow = head, *fast = head -> next;
while(fast != slow){
if(fast == NULL || fast -> next == NULL)
return false;
slow = slow -> next;
fast = fast -> next -> next;
}
return true;
}
};
链表
相交链表
160.相交链表
用两个指针，一个指向A，一个指向B链表，当有一个到末尾的时候指向另一个链表。如果有相交则最后一定会指向同一个结点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* l1 = headA, *l2 = headB;
while (l1 != l2) {
if(l1 == NULL)
l1 = headB;
else
l1 = l1 -> next;
if(l2 == NULL)
l2 = headA;
else
l2 = l2 -> next;
}
return l1;
}
};
反转链表
206. 反转链表
递推
用一个指针存储下一个结点和上一个结点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL || head -> next == NULL)
return head;
ListNode *last = NULL;
while(head -> next != NULL){
ListNode *temp = head -> next;
head -> next = last;
last = head;
head = temp;
}
head -> next = last;
return head;
}
};
递归
递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？假设列表为：$n_1 → … → n_{k-1} → n_k → n_{k+1} → … → n_m → Ø$
若从节点$ nk+1 $到 $nm $已经被反转，而我们正处于 $nk$。
$n_1 → … → n_{k-1} → n_k → n_{k+1} ← … ← n_m$
我们希望$ n_{k+1} $的下一个节点指向 $n_k$。
所以，1
nk.next.next = nk;
要小心的是$ n_1$ 的下一个必须指向 $Ø$ 。如果你忽略了这一点，你的链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。
1 | class Solution { |
删除链表的倒数第N个节点
用一个fast指针先向前走n步，然后slow指针和fast指针一起走直到fast走到倒数第二个，然后操作一下删除就可以了。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/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *fast = head;
while(n--)
fast = fast -> next;
if(fast == NULL)
return head -> next;
ListNode *slow = head;
while(fast -> next != NULL){
fast = fast -> next;
slow = slow -> next;
}
// cout << slow -> val << endl;
if(slow -> next != NULL)
slow -> next = slow -> next -> next;
else
slow = NULL;
return head;
}
};
树
平衡二叉树
110.平衡二叉树
判断一棵树是不是平衡二叉树，判断左右结点的高度差是否相差不到1，若不是则不为平衡二叉树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
bool isbalance = true;
int dfs(TreeNode* t)
{
if(t == NULL)
return 0;
int l = dfs(t -> left);
int r = dfs(t -> right);
if(abs(l - r) > 1)
isbalance = false;
return max(l, r) + 1;
}
bool isBalanced(TreeNode* root) {
dfs(root);
return isbalance;
}
};
合并二叉树
617. 合并二叉树
将两棵树合并成一棵1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
TreeNode* merge(TreeNode* t1, TreeNode* t2)
{
if(t1 == NULL && t2 == NULL)
return NULL;
if(t1 == NULL)
return t2;
if(t2 == NULL)
return t1;
t1 -> left = merge(t1 -> left, t2 -> left);
t1 -> right = merge(t1 -> right, t2 -> right);
t1 -> val += t2 -> val;
return t1;
}
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
return merge(t1, t2);
}
};
路径总和 III
437. 路径总和 III
最初想的一个暴力的方法，把每个结点可以形成的数都存到vector中遍历相加，很慢。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
40class Solution {
public:
// map<TreeNode*, map<int, int> > mp;
int cnt;
vector<int> dfs(TreeNode* t, int sum){
vector<int> res;
if(t == NULL)
return res;
if(t -> left == NULL && t -> right == NULL)
{
if(t -> val == sum)
cnt++;
res.push_back(t -> val);
return res;
}
vector<int> l = dfs(t -> left, sum);
vector<int> r = dfs(t -> right, sum);
for(auto idx: l)
{
res.push_back(idx + t -> val);
if(idx + t -> val == sum)
cnt++;
}
for(auto idx: r)
{
res.push_back(idx + t -> val);
if(idx + t -> val == sum)
cnt++;
}
res.push_back(t -> val);
if(t -> val == sum)
cnt++;
return res;
}
int pathSum(TreeNode* root, int sum) {
dfs(root, sum);
return cnt;
}
};
正解应该是两个递归，答案应该是当前结点和为sum的个数加上左结点和为sum的个数加上右结点和为sum的个数。
计算和为sum可以dfs直到叶子结点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if(root == NULL)
return 0;
int res = 0;
res = pathSum(root -> left, sum) + pathSum(root -> right, sum) + dfs(root, sum);
return res;
}
int dfs(TreeNode* t, int sum)
{
if(t == NULL)
return 0;
int res = (sum == t -> val);
res += dfs(t -> left, sum - t -> val) + dfs(t -> right, sum - t -> val);
return res;
}
};
对称二叉树
101. 对称二叉树
判断一棵二叉树是不是对称，想了半天没想出来。
后来把根结点的其中一棵子树反转判断是否和另一棵相等即可。
好像不是正解。先放个代码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/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* rv(TreeNode* root)
{
if(root == NULL)
return NULL;
TreeNode* l = rv(root -> left);
TreeNode* r = rv(root -> right);
root -> left = r;
root -> right = l;
return root;
}
bool isSame(TreeNode* a, TreeNode* b)
{
if(a == NULL && b == NULL)
return true;
if(a == NULL || b == NULL)
return false;
if(a -> val != b -> val)
return false;
return isSame(a -> left, b -> left) && isSame(a -> right, b -> right);
}
bool isSymmetric(TreeNode* root) {
if(root == NULL)
return true;
TreeNode* t1 = root -> left;
TreeNode* t2 = rv(root -> right);
return isSame(t1, t2);
}
};
正解可以用一个递归处理。注意判断是不同子树上的两棵子树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
bool isOkay(TreeNode* l, TreeNode* r)
{
if(l == NULL && r == NULL)
return true;
if(l == NULL || r == NULL)
return false;
if(l -> val != r -> val)
return false;
return isOkay(l -> left, r -> right) && isOkay(l -> right, r -> left);//判断是对应对称的两棵子树
}
bool isSymmetric(TreeNode* root) {
if(root == NULL)
return true;
return isOkay(root -> left, root -> right);
}
};
打家劫舍
337. 打家劫舍 III
当前结点取或者不取，简单的树形dp一下，每次记录取或者不取的最大值。一遍dfs1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
pair<int, int> dfs(TreeNode* root)
{
pair<int, int> res;
if(root == NULL)
return make_pair(0, 0);
if(root -> left == NULL && root -> right == NULL)
return make_pair(root -> val, 0);
pair<int, int> l = dfs(root -> left);
pair<int, int> r = dfs(root -> right);
res.first = l.second + r.second + root -> val;
res.second = max(l.first, l.second) + max(r.first, r.second);
return res;
}
int rob(TreeNode* root) {
if(root == NULL)
return 0;
pair<int, int> ret = dfs(root);
cout << ret.first << ' ' << ret.second << endl;
return max(ret.first, ret.second);
}
};
二叉树中第二小的节点
671. 二叉树中第二小的节点
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
如果有节点的值不大于它的子节点的值，所以我们只要判断一下当前结点和左右两个结点的是否相等，如果相等就继续往下处理。
否则就是一组备选答案。
然后dfs回来的时候，看两个结点的值，如果两个值不为-1，则返回两者中较小的。
如果有一个不为-1，则返回这个值。
或者返回-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
25
26class Solution {
public:
int dfs(TreeNode* root){
if(root == NULL)
return -1;
if(root -> left == NULL && root -> right == NULL)
return -1;
int lv = root -> left -> val;
int rv = root -> right -> val;
if(lv == root -> val)
lv = dfs(root -> left);
if(rv == root -> val)
rv = dfs(root -> right);
if(lv != -1 && rv != -1)
return min(lv, rv);
if(lv == -1)
return rv;
return lv;
}
int findSecondMinimumValue(TreeNode* root) {
if(root == NULL)
return -1;
int ret = dfs(root);
return ret;
}
};
二叉树的前序遍历
144. 二叉树的前序遍历
二叉树的前序遍历非递归写法。
用一个栈，先存放右结点，再存放左结点，进行遍历。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
vector<TreeNode*> st;
st.push_back(root);
while(st.size()){
TreeNode* now = st.back();
res.push_back(now -> val);
st.pop_back();
if(now -> right)
st.push_back(now -> right);
if(now -> left)
st.push_back(now -> left);
}
return res;
}
};
二叉树的后序遍历
145. 二叉树的后序遍历
由于前序是root -> left -> right
而后序是left -> right -> root
所以我们只需要把前序入栈的顺序反一下，再取个反就可以了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(root == NULL)
return res;
vector<TreeNode*> st;
st.push_back(root);
while(st.size()){
TreeNode* now = st.back();
res.push_back(now -> val);
st.pop_back();
if(now -> left)
st.push_back(now -> left);
if(now -> right)
st.push_back(now -> right);
}
reverse(res.begin(), res.end());
return res;
}
};
二叉树的中序遍历
94. 二叉树的中序遍历
中序遍历的非递归写法，用一个额外结点now。
每次遍历左子树直到叶子结点，将一路上所有的左结点都加入栈。
然后将当前的右结点设为now1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
if(root == NULL)
return res;
stack<TreeNode*> st;
TreeNode* now = root;
while(st.size() || now != NULL){
while(now != NULL){
st.push(now);
now = now -> left;
}
TreeNode* t = st.top();
st.pop();
res.push_back(t -> val);
now = t -> right;
}
return res;
}
};
分治
数组中的第K个最大元素
215. 数组中的第K个最大元素
arrangeK表示将前k大的k个元素置于数组右侧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
33class Solution {
public:
void arrangeK(vector<int>& nums, int k, int l, int r)
{
if(l > r)
return;
int key = nums[l];
int a = l, b = r;
while(a != b)
{
while(nums[b] >= key && a < b)
b--;
while(nums[a] <= key && a < b)
a++;
swap(nums[a], nums[b]);
}
swap(nums[l], nums[a]);
if(r - a + 1 == k)
return;
else if(r - a + 1 > k)
arrangeK(nums, k, a + 1, r);
else
arrangeK(nums, k - (r - a + 1), l, a - 1);
}
int findKthLargest(vector<int>& nums, int k) {
int len = nums.size();
arrangeK(nums, k, 0, len - 1);
int res = INT_MAX;
for(int i = len - 1; i >= len - k; i--)
res = min(res, nums[i]);
return res;
}
};