如题。下面这些算法很有启发性，最好背下来。这些代码都是经过测试的，正确性毋庸置疑
合并两个有序的数组
这个算法是对双指针的一个简单使用。用法是将旧指针的内容拷贝到新指针：
给出一个整数数组 A 和有序的整数数组 B，请将数组 B合并到数组 A 中，变成一个有序的升序数组
注意：
可以假设 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，的数组空间大小为 m+n
不要返回合并的数组，返回是空的，将数组 B 的数据合并到 A 里面就好了
数组在[0,m-1]的范围也是有序的
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int *tmp = new int[m];
for(int i = 0; i < m; ++i) tmp[i] = A[i];
int i = 0;
int j = 0;
while( i < m && j < n){
if(tmp[i] < B[j]){
A[i+j] = tmp[i];
++i;
continue;
}
A[i+j] = B[j];
++j;
}
for(; i < m; ++i) A[i+j] = tmp[i];
for(; j < n; ++j) A[i+j] = B[j];
}
};快慢指针
对双指针更高阶的使用。使用快慢指针定位元素
给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如， 给出的链表为: 1→2→3→4→5, n=2 删除了链表的倒数第 n 个节点之后,链表变为 \(1\to 2\to 3\to 5\)
备注： 题目保证 n 一定是有效的 请给出时间复杂度为 \(O(n)\) 的算法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(!head) return head;
ListNode* fast = head;
ListNode* slow = head;
for(int i = 0; i < n && fast; ++i) { fast = fast->next; }
if(!fast) return head->next;
while(fast->next) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
};子数组的最大累加和问题
给定一个数组arr，返回子数组的最大累加和 例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6] 可以累加出最大的和12，所以返回12. 题目保证没有全为负数的数据
时间复杂度为 O(n)，空间复杂度为 O(1)
class Solution {
public:
int maxsumofSubarray(vector<int>& arr) {
int result = INT_MIN;
int sum = 0;
for(int i = 0; i < arr.size(); ++i) {
sum += arr[i];
if(sum > result) result = sum;
if(sum < 0) sum = 0;
}
return result;
}
};二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
class Solution {
public:
TreeNode* Mirror(TreeNode* pRoot) {
if(!pRoot) return pRoot;
swap(pRoot->left, pRoot->right);
Mirror(pRoot->left);
Mirror(pRoot->right);
return pRoot;
}
};回文数字
描述
在不使用额外的内存空间的条件下判断一个整数是否是回文数字
输入整数位于区间 \([−2^{31},2^{31−1}\)] 之内
- 提示：
负整数可以是回文吗？（比如-1）
如果你在考虑将数字转化为字符串的话，请注意一下不能使用额外空间的限制
你可以将整数翻转。但是，如果你做过题目“反转数字”，你会知道将整数翻转可能会出现溢出的情况，你怎么处理这个问题？
class Solution {
int level;
public:
// 获取指定 i 位于 pos 位置的数字
inline int getNumber(int i, int pos) {
// 计算 10 的幂
int power10 = 1;
int j = level - pos;
if(j > 0) {
for(; j > 0; --j) power10 *= 10;
}
i /= power10;
return i % 10;
}
bool isPalindrome(int x) {
if(x < 0) return false;
// 计算 x 有几位
for(int i = x; i; i /= 10) ++level;
// 判断回文
for(int i = 1, j = level; i < j; ++i, --j) {
if(getNumber(x, i) != getNumber(x, j)) return false;
}
return true;
}
};最大堆
void MAX_HEAPIFY(std::vector<int> &arr, int begin, int end) {
int l = begin * 2 + 1;
int r = begin * 2 + 2;
int largest = begin;
if(l <= end && arr[l] > arr[largest]) largest = l;
if(r <= end && arr[r] > arr[largest]) largest = r;
if(largest != begin) {
std::swap(arr[begin], arr[largest]);
MAX_HEAPIFY(arr, largest, end);
}
}
void BUILD_HEAPIFY(std::vector<int> &arr) {
for(int i = arr.size() / 2 - 1; i >= 0; --i) MAX_HEAPIFY(arr, i, arr.size() - 1);
}偶校验
bool isOdd(int a) {
bool odd = false;
while(a) {
odd = !odd;
a = a & (a - 1);
}
return odd;
}C++ 如果需要打印二进制内容，可以使用 cout << bitset<16>(10)
岛屿数量
一个深度遍历的题目，二维的方式，很有代表性
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
题解：[1]
class Solution {
public:
/**
* 判断岛屿数量
* @param grid char字符型vector<vector<>>
* @return int整型
*/
void dfs(vector<vector<char> >& grid, int r, int c) {
if(r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] == '0') return;
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
int solve(vector<vector<char> >& grid) {
if(grid.size() == 0) return 0;
if(grid[0].size() == 0) return 0;
int results = 0;
for(int r = 0; r < grid.size(); ++r) {
for(int c = 0; c < grid[0].size(); ++c) {
if(grid[r][c] == '1') {
++results;
dfs(grid, r, c);
}
}
}
return results;
}
};全排列
有些遗憾吧，当初字节的笔试一题就是全排列，可是当时递归学的不精，题也刚刚开始刷，结果没写出来。现在会写已经是将近一个星期后了
vector<string> results;
void FullArray(int n, string preStr, string str) {
if(n == 1) {
for(char ch: str) { results.push_back(preStr + ch); }
return;
}
for(int i = 0; i < n; ++i) {
auto copyStr = str;
copyStr.erase(copyStr.begin() + i);
FullArray(n - 1, preStr + str[i], copyStr);
}
}括号生成
全排列的一种变形，很有背诵意义：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。[2]
有效括号组合需满足：左括号必须以正确的顺序闭合。
class Solution {
public:
vector<string> results;
void dfs(string partString, int l, int r) {
if(l == 0 && r == 0) {
results.push_back(partString);
return;
}
// 如果 l == r ，只能使用左括号填充
if(l == r) {
dfs(partString + '(', l - 1, r);
} else {
if(l != 0) dfs(partString + '(', l - 1, r);
dfs(partString + ')', l, r - 1);
}
}
vector<string> generateParenthesis(int n) {
if(n <= 0) return {};
dfs({}, n, n);
return results;
}
};假设 n ==3 。则上述的代码在进行括号匹配的过程中，先迭代到 (((，然后右括号补全后一直回退到 ((，这时就需要补全 )，然后补全左括号和右括号。通过栈的回退对括号进行了补全
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。[3]
{ '2', "abc" }, { '3', "def" },
{ '4', "ghi" }, { '5', "jkl" },
{ '6', "mno" }, { '7', "pqrs" },
{ '8', "tuv" }, { '9', "wxyz" }一个对全排列进行的变形
class Solution {
public:
map<char, string> mapping = {
{ '2', "abc" }, { '3', "def" },
{ '4', "ghi" }, { '5', "jkl" },
{ '6', "mno" }, { '7', "pqrs" },
{ '8', "tuv" }, { '9', "wxyz" }
};
vector<string> results;
void FullArray(string str, string partStr) {
if(str.size() == 1) {
string values = mapping[str[0]];
for(char ch: values) { results.push_back(partStr + ch); }
return;
}
string values = mapping[str[0]];
str.erase(str.begin());
for(char ch: values) { FullArray(str, partStr + ch); }
}
vector<string> letterCombinations(string digits) {
if(digits.size() == 0) return {};
FullArray(digits, {});
return results;
}
};约瑟夫环
N 个人围成一圈，从开头向后报数，报数为 M 的倍数的人被淘汰，问最后留下的那个人的初始编号是多少
这题就合乎常理的就是使用一个环形链表。但是这里讲另一个更好的算法
首先我们每次淘汰人都将计数器记零，并将下一个人当作队首。这样每次被淘汰的都是编号为 M 的人。
每次淘汰人都会导致胜出者的编号向前移动 M 位（环形），所以后来会有溢出的情况。
现在将其逆退，每次循环都将胜出者向后移动 M 位，溢出情况使用模运算解决，所以得到下面这样一个逆退式：
代码形式如下：
递归形式：
int YSF(int n, int m) {
if(n == 1) return 0;
return (YSF(n - 1, m) + m) % n;
}非递归形式：
int YSF(int n, int m) {
int pos = 0;
for(int i = 2; i < n; ++i) { pos = (pos + m) % n; }
return pos + 1;
}从递归形式可以看出为什么非递归形式中的 i 需要从 2 开始。这是因为递归形式等于 1 的时候就直接出结果了。 pos == 0 就对应 n ==1 的时候，因此 i 从 2 开始就行了
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。[4]
使用了滑动窗口
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> window;
int r = 0;
int res = 0;
for(int l = 0; l < s.length(); ++l) {
if(l) window.erase(s[l - 1]);
while(r < s.length() && !window.count(s[r])) window.insert(s[r++]);
res = max(res, r - l);
}
return res;
}
};这里说明一下 unordered_set 的 API：
unordered_set 底层是一个哈希表，erase 的作用是删除指定的字符，对于 unordered_set_multiset 而言可能会删除好几个，但是对于 unordered_set 只会删除一个（无重复）
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
暴力解法：
class Solution {
public:
string longestPalindrome(string& s) {
if(s.length() < 2) { return s; }
int maxLen = 1;
int begin = 0;
for(int i = 0; i < s.length() - 1; i++) {
for(int j = i + 1; j < s.length(); j++) {
if(j - i + 1 > maxLen && isPalindrome(s, i, j)) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxLen);
}
bool isPalindrome(string& s, int l, int r) {
while(l < r)
if(s[l++] != s[r--]) { return false; }
return true;
}
};接下来是一个动态规划的思路，但是在 leetcode 上时间和空间反而比暴力慢。思路是官方的思路，这里再阐述一下
假设我们将字符串的左右边界分别记作 \(i,j\) ，那么我们知道只有当字符串 \($s[i-1:j+1\)$] 满足下面方程时，它才是一个回文字符串：
这里 \($s[i:j\)$] 是一个布尔值，当且仅当 \(s\) 是一个回文字符串的时候它才为真
此递归方程的边界条件是：
string longestPalindrome(string& s) {
int n = s.length();
if(n < 2) return s;
vector<vector<bool>> dp(n, vector<bool>(n));
for(int i = 0; i < n; ++i) dp[i][i] = true;
int maxLen = 1;
int beg = 0;
for(int L = 2; L <= n; ++L) {
for(int i = 0; i < n; ++i) {
int j = L + i - 1;
if(j >= n) break;
if(s[i] != s[j]) dp[i][j] = false;
else {
if(j - i < 3) dp[i][j] = true;
else
dp[i][j] = dp[i + 1][j - 1];
}
if(dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
beg = i;
}
}
}
return s.substr(beg, maxLen);
}三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。[5]
注意：答案中不可以包含重复的三元组。
与两数之和不同的是这个不能出现重复的三元组，所以如果使用全排列或者三层暴力循环的话后期需要去重，去重超过可以先对子元素排序，然后插入到 set 中。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if(nums.size() < 3) return {};
set<vector<int>> results;
for(int i = 0; i < nums.size() - 2; ++i) {
for(int j = i + 1; j < nums.size() - 1; ++j) {
for(int k = j + 1; k < nums.size(); ++k) {
if(nums[i] + nums[j] + nums[k] == 0) {
vector<int> a = { nums[i], nums[j], nums[k] };
sort(a.begin(), a.end());
results.insert(a);
}
}
}
}
return {results.begin(), results.end()};
}
};这个根据官方解法给出另一种更好的做法：
关键之处为：既然要求不能重复，那么就通过规定三个元素 \(a\leq b\leq c\) 解决一部分重复，另一部分则通过查看当前迭代的元素是否和上次迭代的元素相同达到去重的效果。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for(int first = 0; first < n; ++first) {
if(first > 0 && nums[first] == nums[first - 1]) continue;
int third = n - 1;
// target 应当等于 nums[second] + nums[third]
int target = -nums[first];
for(int second = first + 1; second < n; ++second) {
if(second > first + 1 && nums[second] == nums[second - 1]) continue;
while(second < third && nums[second] + nums[third] > target) --third;
if(second == third) break;
if(nums[second] + nums[third] == target)
ans.push_back({
nums[first],
nums[second],
nums[third],
});
}
}
return ans;
}
};位运算
下面是一些涉及到位运算的算法：
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。[6]
对于异或我们可以知道：
a^0 = a
a^a = 0
而且异或符合结合律
因此，所有重复的数异或后都得零，不重复的数异或零后得其本身：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for(int val: nums) result ^= val;
return result;
}
};下一个排列
实现获取 下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。[7]
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
按照字典序的下一个排列为：
从后向左找到第一个满足 nums[i] < nums[i+1] 的位置
从后向左找到第一个满足 nums[j] > nums[i] 的位置
交换这两个数
反转 nums[i:]
这样，得到的就是满足下一个字典序的排列
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2;
while(i >= 0 && nums[i] >= nums[i + 1]) --i;
if(i >= 0) {
int j = nums.size() - 1;
while(j >= 0 && nums[i] >= nums[j]) --j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};分解质因数
算法一：
class Solution {
public:
vector<int> factorization(int n) {
vector<int> result;
for(int i = 2; i <= n; ++i) {
while(i != n) {
if(n % i == 0) {
result.push_back(i);
n = n / i;
}
break;
}
}
result.push_back(n);
return result;
}
};滑动窗口
将数组中的 0 移动到末尾。做笔试碰到两次，第二次在考场上想出来的 :)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int i = 0;
int j = 0;
for(; i < n && j < n; ++i) {
if(nums[i] == 0) {
if(j < i) j = i + 1;
while(j < n && nums[j] == 0) ++j;
if(j > n - 1) break;
swap(nums[i], nums[j]);
}
}
}
};LRU
LUR 缓存结构。保证 put 和 get 是 O(1) 的
struct DLinkedNode {
DLinkedNode() = default;
DLinkedNode(int key, int value) : key(key), value(value) { }
int key = 0, value = 0;
DLinkedNode* pre = nullptr;
DLinkedNode* next = nullptr;
};
class LRUCache {
DLinkedNode* head;
DLinkedNode* tail;
unordered_map<int, DLinkedNode*> cache;
int size;
int capacity;
public:
LRUCache(int capacity) : head { new DLinkedNode }, tail { new DLinkedNode }, capacity(capacity), size { 0 } {
head->next = tail;
tail->pre = head;
}
int get(int key) {
if(!cache.count(key)) return -1;
auto node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if(!cache.count(key)) {
auto node = new DLinkedNode(key, value);
cache[key] = node;
addToHead(node);
++size;
if(size > capacity) {
auto removed = removeTail();
cache.erase(removed->key);
delete removed;
--size;
}
} else {
auto node = cache[key];
node->value = value;
moveToHead(node);
}
}
void addToHead(DLinkedNode* node) {
node->pre = head;
node->next = head->next;
head->next->pre = node;
head->next = node;
}
void removeNode(DLinkedNode* node) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
void moveToHead(DLinkedNode* node) {
removeNode(node);
addToHead(node);
}
DLinkedNode* removeTail() {
auto node = tail->pre;
removeNode(node);
return node;
}
};