0x00 前言

本文在 CS-Notes/LeetCode 的基础上又进一步做了整理与补充。

  • 链表
  • 树
  • 栈和队列
  • 哈希表
  • 字符串
  • 数组与矩阵
  • 图
  • 位运算

反转链表

题目很好理解，难度也不高，关键是实现细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *p = pHead;
        ListNode *nex = nullptr;
        while(p != nullptr) {
            nex = p->next;
            p->next = pre;
            
            pre = p;
            p = nex;
        }
        return pre;
    }
};
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
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        // 1. 统计组数 n
        ListNode *p = head;
        int cnt = 0, n = 0;
        while(p != NULL) {
            cnt++;
            if(cnt == k) {
                n++, cnt = 0;
            }
            p = p->next;
        }
        if(n == 0)     // 无需翻转
            return head;
        
        // 2. 按组翻转链表
        ListNode *pre, *nex;
        ListNode *preHead, *preTail;
        ListNode *curHead, *curTail;
        // init
        p = head;
        while(n--) {    // 总共翻转n组，且必能翻转n组，无需判断NULL
            // 2.1 组内翻转
            cnt = 0;
            pre = NULL;
            curHead = p, curTail = NULL;    // 翻转前保存当前组的首尾结点
            while(cnt < k) {    // 翻转当前组
                nex = p->next;
                p->next = pre;
                
                pre = p;
                p = nex;
                cnt++;
            }
            // 当前组内翻转完成，交换首尾结点
            curTail = curHead;
            curHead = pre;
            // 2.2 组间翻转
            // 前一个组的尾preTail连到当前组的头curHead，当前组的尾curTail连到后一个组的头p
            if(curTail == head) {    // 如果当前在第一组，则修改整个链表头head
                head = curHead;
                curTail->next = p;
            } else {
                preTail->next = curHead;
                curTail->next = p;
            }
            
            preHead = curHead;
            preTail = curTail;
        }
        return head;
    }
};

树的遍历

层序遍历

牛客网 - 求二叉树的层序遍历

【题目描述】

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）。

【题解】

此题的难度不在于层序遍历，而在于它的输出形式 —— vector<vector<int>> 。

那该如何得到按层的序列呢？我们回顾一下层序遍历的过程：

  • 在层序遍历开始前，队列中只有根结点，即第一层的结点数为1；
  • 接着取出根结点并访问，把它的两个孩子结点加入队列中。注意了！这个时候队列中只有它的两个孩子结点，即下一层的结点。
  • 如果我们一次遍历完这两个结点，那么此时队列中就只有这两个结点的孩子结点，即再下一层的结点。

据此，我们可以在遍历之前，先获得队列大小 size ，即当前层的结点数，然后把这些节点都取出来遍历完之后，队列中的元素就都更新为了下一层的结点了。

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
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int> > res;
        if(root == NULL) return res;
        // get level sequence by layers
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int numLayer = q.size();    // 当前层的结点数
            vector<int> vec;
            while(numLayer--) {
                TreeNode *cur = q.front();
                q.pop();
                vec.push_back(cur->val);         

                if(cur->left != NULL) q.push(cur->left);
                if(cur->right != NULL) q.push(cur->right);
            }
            /*if(vec.size() > 0) */res.push_back(vec);
        }
        return res;
    }
};