1、链表
删除结点时注意释放空间，防止内存泄漏
注意把next指向NULL，防止野指针
1.1 两个链表的第一个公共结点
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *node1 = headA;
ListNode *node2 = headB;
while (node1 != node2) {
node1 = node1 != NULL ? node1->next : headB;
node2 = node2 != NULL ? node2->next : headA;
}
return node1;
}
};
1.2 复杂链表的复制
方法一 哈希
代码
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return head;
unordered_map<Node *, Node *> m;
Node virhead(0, NULL, NULL);
Node *p = &virhead, *q = head;
while (q) {
p->next = new Node(q->val, NULL, NULL);
m.insert(make_pair(q, p->next));
q = q->next;
p = p->next;
}
p = &virhead, q = head;
while (q) {
p->next->random = m[q->random];
q = q->next;
p = p->next;
}
return virhead.next;
}
};
方法二
- 复制每一个节点，使得复制后的节点都在当前节点的下一个节点
- 原生链表的节点的指向任意节点，使复制的节点也都指向某一任意节点
- 重新连接节点，把原生节点重新连接起来，把克隆后的节点连接起来
图示：
代码
//不需要额外空间
public static Node copyListWithRand2(Node head){
if (head == null ){
return null;
}
Node curr = head;
//拷贝链表，并且把链表连接起来
while(curr != null){
Node next = curr.next;
Node copy = new Node(curr.val);
curr.next = copy;
copy.next = next;
curr = next;
}
//指定随即指针
curr = head;
while(curr != null){
Node next = curr.next.next;//原节点的下一个节点
Node currCopy = curr.next;//当前的拷贝节点
currCopy.random = curr.random!=null?curr.random.next:null;//指定随机指针节点
curr = next;//当前节点指向下一个节点
}
//拆分链表
curr = head;
Node res = curr.next;//用于返回的拷贝头节点
while (curr != null){
Node next = curr.next.next;//原节点的下一个节点
Node curCopy = curr.next;//拷贝节点
curr.next = next;//将原节点指向下一个原节点
curCopy.next = next!=null?next.next:null;//拷贝节点的下一个节点指向下一个原节点的下一个节点
curr = next;//将当前节点指向下一个原节点
}
return res;
}
2、二叉树
2.1 重建二叉树
- 先序、中序建树
- 中序、后序建树
先序、中序建树
/**
* 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:
unordered_map<int, int> mino;
TreeNode* _build(vector<int>& pre, int pl, int pr, vector<int>& ino, int il, int ir) {
if (pl > pr || il > ir) return NULL;
int imid = mino[pre[pl]], pmid = pl + imid - il;
TreeNode *node = new TreeNode;
node->val = pre[pl];
node->left = _build(pre, pl + 1, pmid, ino, il, imid - 1);
node->right = _build(pre, pmid + 1, pr, ino, imid + 1, ir);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() <= 0 || inorder.size() <= 0) return NULL;
for (int i = 0; i < inorder.size(); ++i) mino[inorder[i]] = i;
return _build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
};
2.2 树的子结构
/**
* 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:
bool check(TreeNode *a, TreeNode *b) {
if (!b) return true;
if (!a) return false;
if (a->val != b->val) return false;
return check(a->left, b->left) && check(a->right, b->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (!A || !B) return false;
if (A->val == B->val && check(A, B)) return true;
if (isSubStructure(A->left, B) || isSubStructure(A->right, B)) return true;
return false;
}
};
/**
* 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:
bool check(TreeNode* a, TreeNode *b) {
if (!b) return true;
if (!a || a->val != b->val) return false;
return check(a->left, b->left) && check(a->right, b->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
return (A && B) && (check(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B));
}
};
2.3 二叉树中和为某一值的路径
/**
* 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:
void dfs(vector<vector<int>> &res, vector<int> &temp, TreeNode *root, int sum) {
if (!root) return ;
sum -= root->val;
temp.push_back(root->val);
if (!sum && !root->left && !root->right) res.push_back(temp);
dfs(res, temp, root->left, sum);
dfs(res, temp, root->right, sum);
temp.pop_back();
return ;
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> temp;
dfs(res, temp, root, sum);
return res;
}
};
2.4 二叉搜索树的第k大节点
思路
中序遍历的结果是升序序列，倒着中序遍历便是降序，便可求得第k大
/**
* 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:
bool inorder(TreeNode *root, int &k, int &res) {
if (!root) return false;
if (inorder(root->right, k, res)) return true;
if (--k == 0) {
res = root->val;
return true;
}
if (inorder(root->left, k, res)) return true;
return false;
}
int kthLargest(TreeNode* root, int k) {
int res = 0;
inorder(root, k, res);
return res;
}
};
2.5 二叉搜索树的最近公共祖先
代码——递归
最坏情况退化为链表
时间复杂度：O(n)
空间复杂度：O(n)
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
else if (p->val >root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
return root;
}
};
代码——迭代
最坏情况退化为链表
时间复杂度：O(n)
空间复杂度：O(1)
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int pval = p->val, qval = q->val;
while (root) {
if (pval < root->val && qval < root->val) root = root->left;
else if (pval > root->val && qval > root->val) root = root->right;
else return root;
}
return root;
}
};
2.6 二叉树的最近公共祖先
解题思路
根据 left 和 right ，可展开为四种情况；
- 当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q，返回 null；
- 当 left 和 right 同时不为空 ：说明 p, q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
- 当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
- p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ）；
- p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
- 当 left 不为空 ， right 为空 ：与情况 3. 同理；
代码
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || p->val == root->val || q->val == root->val) return root;
TreeNode *l = lowestCommonAncestor(root->left, p, q);
TreeNode *r = lowestCommonAncestor(root->right, p, q);
if (!l) return r;
if (!r) return l;
return root;
}
};
2.7 二叉搜索树与双向链表
解题思路
利用中序遍历
代码
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if (!root) return root;
_build(root);
head->left = pre;
pre->right = head;
return head;
}
void _build(Node *node) {
if (!node) return ;
_build(node->left);
if (!pre) head = node;
else pre->right = node;
node->left = pre;
pre = node;
_build(node->right);
return ;
}
private :
Node *pre, *head;
};
3、贪心
3.1 剪绳子2
尽量转换成 3^a^ * 2^b^ 的形式
class Solution {
public:
long long quick_pow(long long a, long long b, long long c) {
long long res = c, mod = 1e9 + 7;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res % mod;
}
int cuttingRope(int n) {
if (n < 3) return 1;
if (n == 3) return 2;
int a = n % 3, b = n / 3;
if (a == 0) return (int)quick_pow(3, b, 1);
else if (a == 2) return (int)quick_pow(3, b, 2);
else return (int)quick_pow(3, b - 1, 4);
}
};
4、 二分
4.1 在排序数组中查找数字 I
class Solution {
public:
int _find(vector<int> &arr, int key) {
int l = 0, r = arr.size() - 1, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (arr[mid] <= key) l = mid + 1;
else r = mid - 1;
}
return l;
}
int search(vector<int>& nums, int target) {
return _find(nums, target) - _find(nums, target - 1);
}
};
4.2 0～n-1中缺失的数字
class Solution {
public:
int missingNumber(vector<int>& nums) {
int l = 0, r = nums.size(), mid;
while (l < r) {
mid = (l + r) >> 1;
if (nums[mid] == mid) l = mid + 1;
else r = mid;
}
return l;
}
};
5、动态规划
5.1 股票的最大利润
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() <= 0) return 0;
int cost = prices[0], res = 0;
for (int i = 1; i < prices.size(); ++i) {
res = (res > prices[i] - cost ? res : prices[i] - cost);
cost = (cost < prices[i] ? cost : prices[i]);
}
return res;
}
};
5.2 把数字翻译成字符串
class Solution {
public:
int translateNum(int num) {
int now = 1, last = 1;
string s = to_string(num);
for (int i = 2; i <= s.size(); ++i) {
int temp = now;
if (s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 25)) now += last;
last = temp;
}
return now;
}
};
5.3 n个骰子的点数
思路
简单的dp问题
状态：dp(i, j) 表示 i 个骰子组成和 j 有多少种可能
状态转移方程：dp(i, j) = dp(i - 1, j - 1) + ... +dp(i - 1, j - 6)
代码
class Solution {
public:
vector<double> twoSum(int n) {
int cnt = n * 6 - n + 1; // 求得有多少种可能点数和
vector<double> res(cnt, 0);
for (int i = 0; i < 6; ++i) res[i] = 1;
// 滚动数组
for (int i = 2; i <= n; ++i) {
for (int j = i * 6 - i; j >= 0; --j) { // 采用滚动数组，所以倒着搜
for (int l = 1; l < 6 && j - l >= 0; ++l) {
// 当前的状态可以由n-1个骰子的 dp(n-1, j-1) + ... + dp(n-1, j-6)，相加得到
// 因为当前增加了一个骰子，所以所有骰子最少和由n-1变为n，即res[j]的值就是dp(n-1, j-1)
res[j] += res[j - l];
}
}
}
for (int i = 0; i < cnt; ++i) {
res[i] = res[i] * (1.0 / pow(6, n));
}
return res;
}
};
6、位运算
6.1 不用乘除做加法
class Solution {
public:
int add(int a, int b) {
while (b != 0) {
int c = (unsigned int)(a & b) << 1; // 计算二进制需要进位的地方
a ^= b;
b = c;
}
return a;
}
};
6.2 二进制中1的个数
class Solution {
public:
int hammingWeight(uint32_t n) {
if (!n) return 0;
int res = 0;
while (n) {
n = n & (n - 1);
++res;
}
return res;
}
};
6.3 数组中数字出现的次数 I
思路
设a、b是数组中只出现一次的元素
- 先将数组所有元素进行异或，可得到 a ^ b
- 取 a ^ b 最后一个 1 的位置将数组进行划分（取任何一个 1 的位置划分都可以）
- 再将被划分为两部分的数组分别异或，即可得到a、b
代码
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
vector<int> res(2, 0);
int x = 0, y = 1;
for (int i = 0; i < nums.size(); ++i) x ^= nums[i];
while ((y & x) == 0) y <<= 1;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] & y) res[0] ^= nums[i];
else res[1] ^= nums[i];
}
return res;
}
};
6.4 数组中数字出现的次数 II
解题思路
因为每个数字出现的次数只有 1 和 3，所以当一个数字出现三次的时候就等同于出现 0 次
- one 标记出现一次，two 标记出现两次
- 一个数位出现一次时 one 为 1，two 为 0
- 一个数位出现两次时 one 为 0，two 为 1
- 一个数位出现三次和未出现过时时 one 为 0，two 为 0
代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = 0, two = 0;
for (int x : nums) {
one = one ^ (x & ~two);
two = two ^ (x & ~one);
}
return one;
}
};
其他
1.矩阵螺旋输出
输出顺序：
- 第一行
- 最后一列（少第一行）
- 最后一行（比第一行少首尾两列）
- 第一列（少第一行）
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if (!matrix.size()) return res;
int n = matrix.size(), m = matrix[0].size();
int starti = 0, endi = n - 1, startj = 0, endj = m - 1;
while (starti <= endi && startj <= endj) {
for (int j = startj; j <= endj; ++j) res.push_back(matrix[starti][j]);
for (int i = starti + 1; i <= endi; ++i) res.push_back(matrix[i][endj]);
if (starti < endi && startj < endj) {
for (int j = endj - 1; j > startj; --j) res.push_back(matrix[endi][j]);
for (int i = endi; i > starti; --i) res.push_back(matrix[i][startj]);
}
++starti, --endi, ++startj, --endj;
}
return res;
}
};
1.2 数组中出现次数超过一半的数字
解题思路
本题常见解法如下：
哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，最终超过数组长度一半的数字则为众数。此方法时间和空间复杂度均为 O(N)。
数组排序法： 将数组 nums 排序，由于众数的数量超过数组长度一半，因此 数组中点的元素 一定为众数。此方法时间复杂度 O(N log N)。
摩尔投票法： 核心理念为 “正负抵消” ；时间和空间复杂度分别为 O(N) 和 O(1)；是本题的最佳解法。
摩尔投票法：
- 票数和： 由于众数出现的次数超过数组长度的一半；若记 众数 的票数为 +1，非众数 的票数为 -1 ，则一定有所有数字的 票数和 > 0。
- 票数正负抵消： 设数组 nums 中的众数为 x，数组长度为 n。若 nums 的前 a 个数字的 票数和 = 0，则 数组后 (n-a)个数字的 票数和一定仍 >0 （即后 (n-a) 个数字的 众数仍为 x）。
算法原理：
- 为构建正负抵消，假设数组首个元素 n~1~为众数，遍历统计票数，当发生正负抵消时，剩余数组的众数一定不变 ，这是因为（设真正的众数为 x）：
- 当 n~1~ = x： 抵消的所有数字中，有一半是众数 x。
- 当 n~1~ != x： 抵消的所有数字中，少于或等于一半是众数 x。
- 利用此特性，每轮假设都可以 **缩小剩余数组区间 **。当遍历完成时，最后一轮假设的数字即为众数（由于众数超过一半，最后一轮的票数和必为正数）。
算法流程:
- 初始化： 票数统计 votes = 0， 众数 x；
- 循环抵消： 遍历数组 nums 中的每个数字 num；
- 当 票数 votes等于 0 ，则假设 当前数字 num 为 众数 x ；
- 当 num = x时，票数 votes自增 1 ；否则，票数 votes 自减 1 。
- 返回值： 返回 众数 x 即可。
代码
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0, cnt = 0;
for (int i = 0; i < nums.size(); i++) {
if (cnt == 0) x = nums[i];
cnt += (x == nums[i] ? 1 : -1);
}
return x;
}
};
1.3 构建乘积数组
解题思路
从前往后扫一遍，再从后往前扫一遍即可
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
vector<int> res(a.size());
res[0] = 1;
for (int i = 1; i < res.size(); ++i) res[i] = res[i - 1] * a[i - 1];
int temp = 1;
for (int i = res.size() - 2; i >= 0; --i) {
temp *= a[i + 1];
res[i] *= temp;
}
return res;
}
};
