https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
根据题目描述：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
我们先从左下角 x 开始查找，比 x 小，就向上查找，比 x 大，就向右查找
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
int i = matrix.size() - 1;
int j = 0;
while (i >= 0 && j < matrix[0].size()) {
if (matrix[i][j] > target) i--;
else if (matrix[i][j] < target) j++;
else return true;
}
return false;
}
};
https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
class Solution {
public:
string replaceSpace(string s) {
int count = 0; // 记录空格数
int oldSize = s.size(); // 原始字符串长度
for (int i = 0; i < oldSize; i++) {
if (s[i] == ' ') {
count ++;
}
}
s.resize(2 * count + oldSize);
int newSize = s.size();
for (int p1 = oldSize - 1, p2 = newSize - 1; p1 < p2; p1--, p2--) {
if (s[p1] != ' ') {
s[p2] = s[p1];
} else {
s[p2] = '0';
s[p2 - 1] = '2';
s[p2 - 2] ='%';
p2 -= 2;
}
}
return s;
}
};
https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
从尾到头打印链表，先反转链表再遍历输出是可以的，但是会改变原有链表的结构
可以考虑用栈，先遍历链表，分别进栈，然后再出栈。
用递归也行，递归遍历到最后一个节点，然后再回溯输出，当链表很长时会导致函数调用层级很深，
从而导致函数调用栈移出，鲁棒性太差
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> res;
stack<int> st;
ListNode* node = head;
while (node != NULL) {
st.push(node->val);
node = node->next;
}
while (!st.empty()) {
res.push_back(st.top());
st.pop();
}
return res;
}
};
https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
class Solution {
private:
// 存储 inorder 中值到索引的映射
unordered_map<int, int> map;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); i++) {
map[inorder[i]] = i;
}
return build(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
/*
定义：前序遍历数组为 preorder[preStart..preEnd]，
中序遍历数组为 inorder[inStart..inEnd]，
构造这个二叉树并返回该二叉树的根节点
*/
TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
vector<int>& inorder, int inStart, int inEnd) {
if (preStart > preEnd) {
return nullptr;
}
// root 节点对应的值就是前序遍历数组的第一个元素
int rootval = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = map[rootval];
// 先构造出当前根节点
TreeNode* root = new TreeNode(rootval);
int leftSize = index - inStart;
root->left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root->right = build(preorder, leftSize + preStart + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
};
https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
用s1用来插入，s2用来删除，删除的时候，先把s1的弹出，放到s2，然后删除s2栈顶元素，再把剩下的放到s1
class CQueue {
private:
stack<int> s1, s2;
public:
CQueue() {
}
void appendTail(int value) {
s1.push(value);
}
int deleteHead() {
if (s1.empty()) return -1;
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
int res = s2.top();
s2.pop();
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
return res;
}
};
https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
class Solution {
public:
int minArray(vector<int>& numbers) {
int left = 0, right = numbers.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else if (numbers[mid] < numbers[right]){
right = mid;
} else {
right--;
}
}
return numbers[left];
}
};
https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
保存之前已经得到的数，避免重复计算
class Solution {
public:
int fib(int n) {
int mod = 1e9+7;
if (n == 0 || n == 1) {
return n;
}
int f1 = 1;
int f0 = 0;
for (int i = 2; i <= n; i++) {
long fn = f1 + f0;
f0 = f1;
f1 = fn % mod;
}
return f1;
}
};
青蛙跳台阶
class Solution {
public:
int numWays(int n) {
int mod = 1e9+7;
if (n <= 1) return 1;
int f1 = 1, f0 = 1;
for (int i = 2; i <= n; i++) {
long fn = f1 + f0;
f0 = f1;
f1 = fn % mod;
}
return f1;
}
};
https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while (n > 0) {
n &= n - 1;
res++;
}
return res;
}
};
https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
class Solution {
public:
double myPow(double x, int n) {
long n1 = (long)n; // 防止下面负数处理时溢出
if (x == 1 || n1 == 0) {
return 1;
}
if (n1 < 0) { // 处理负数
x = 1 / x;
n1 = -n1;
}
double res = 1;
while (n1 != 0) {
if (n1 & 1) {
res *= x;
}
// x = x * x; 就是上一步的 x 进行平方，比如 x = x^2（上一步的x） * x^2;
x *= x;
n1 >>= 1;
}
return res;
}
};
https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/
class Solution {
public:
vector<int> printNumbers(int n) {
vector<int> res;
int num = 1;
for (int i = 0; i < n; i++) {
num *= 10;
}
for (int i = 1; i < num; i++) {
res.push_back(i);
}
return res;
}
};
https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* pre = head;
ListNode* cur = head->next;
if (head->val == val) {
return head->next;
}
while (cur != NULL && cur->val != val) {
pre = cur;
cur = cur->next;
}
// 如果删除的节点在链表里面，则会触发第二个条件退出while 循环
if (cur != NULL) {
pre->next = cur->next;
}
// 如果不存在要删除的节点，触发第一个条件退出循环，直接返回头结点
return head;
}
};
https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
while (left < right && nums[left] % 2 == 1) left++; // 找到偶数退出
while (left < right && nums[right] % 2 == 0) right--; // 找到奇数退出
if (left < right) swap(nums[left], nums[right]); // 交换
}
return nums;
}
};
https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
为增强鲁棒性
1. 如果输入的链表头指针为NULL，那么整个链表为空，此时查找倒数第K个节点自然应该返回空；
如果输入的K是0，也即是试图查找倒数第0个节点，由于计数是从1开始的，所以查找0没有意义，返回空
2. 如果链表的节点数少于K，在while 循环中可能会出现指向空指针的下一个指针，所以加一层判断语句
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* slow = head, *fast = head;
if (head == NULL || k == 0) { // 1
return NULL;
}
while (k > 0) {
if (fast != NULL) { // 2
fast = fast->next;
}
k--;
}
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur != NULL) {
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* p1 = l1;
ListNode* p2 = l2;
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val > p2->val) {
p->next = p2;
p2 = p2->next;
} else {
p->next = p1;
p1 = p1->next;
}
p = p->next;
}
if (p1 != nullptr) {
p->next = p1;
}
if (p2 != nullptr) {
p->next = p2;
}
return dummy->next;
}
};
https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
class Solution {
public:
bool compare(TreeNode* A, TreeNode* B) {
//如果B空A不空(B遍历完了，A还没遍历完，那么B是子结构)，或者AB都空（AB都匹配对应上了）
if(B==NULL){
return true;
}
//如果A空，B不空（如果A遍历完了，B还没匹配完，那么肯定就不是子结构）
if(A==NULL){
return false;
}
//如果两个都不空，结点值也不同，那直接返回false
if(A->val!=B->val){
return false;
}
//如果现在结点值和子树结点值相同，再分别检查两个的左右孩子
return compare(A->left, B->left) && compare(A->right, B->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
//如果B一开始就是空树，而题目要求空树不是子结构，所以直接返回错。
if(B == NULL) return false;
//如果要检查的子树不空，但root是空的，那也不用查了，也是错的。
if(A == NULL) return false;
//要么是它本身，要么是它左子树，要么是它的右子树
return compare(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
};
https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (root == NULL) return NULL;
// 避免交换空子树
if (root != NULL && (root->left == NULL && root->right == NULL)) return root;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
if (root->left) mirrorTree(root->left);
if (root->right) mirrorTree(root->right);
return root;
}
};
https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty()) return {};
vector<int> res;
int top = 0, bottom = matrix.size() - 1; // 上下边界
int left = 0, right = matrix[0].size() - 1; // 左右边界
while (true) {
// 从左向右
for (int i = left; i <= right; i++) {
res.push_back(matrix[top][i]);
}
// 每次从左往右执行一次，则要往下移一层
if (++top > bottom) break;
//从上向下
for (int i = top; i <= bottom; i++) {
res.push_back(matrix[i][right]);
}
// 每次从上到下执行一次，则要往左移一列
if (--right < left) break;
// 从右向左
for (int i = right; i >= left; i--) {
res.push_back(matrix[bottom][i]);
}
// 每次从右到左执行一次，则要往上移一行
if (--bottom < top) break;
// 从下向上
for (int i = bottom; i >= top; i--) {
res.push_back(matrix[i][left]);
}
// 每次从下到上执行一次，则要往右移一列
if (++left > right) break;
}
return res;
}
};
https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
把每次最小的元素都保存起来放到另一个辅助栈里
class MinStack {
private:
stack<int> dataS;
stack<int> minS;
public:
/** initialize your data structure here. */
MinStack() {
minS.push(INT_MAX);
}
void push(int x) {
dataS.push(x);
minS.push(std::min(minS.top(), x));
}
void pop() {
dataS.pop();
minS.pop();
}
int top() {
return dataS.top();
}
int min() {
return minS.top();
}
};
https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
1. 如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；
2. 如果下一个弹出的数字不在栈顶，把压栈序列中还没有入栈的数字压入辅助栈，
直到把下一个需要弹出的数字压入栈顶为止。
3. 如果所有的数字都压入栈了，仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> helpS;
int i = 0;
for (int num : pushed) {
helpS.push(num);
while (!helpS.empty() && helpS.top() == popped[i]) {
helpS.pop();
i++;
}
}
return helpS.empty();
}
};
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
使用队列辅助打印，打印根节点时，将子节点存入队列中
class Solution {
private:
vector<int> res;
queue<TreeNode*> queue;
public:
vector<int> levelOrder(TreeNode* root) {
if (root != NULL) queue.push(root);
while (!queue.empty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode* node = queue.front();
queue.pop();
res.push_back(node->val);
if (node->left) queue.push(node->left);
if (node->right) queue.push(node->right);
}
}
return res;
}
};
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
class Solution {
public:
vector<int> res;
bool verifyPostorder(vector<int>& postorder) {
res = postorder;
return dfs(0, postorder.size() - 1);
}
bool dfs(int l, int r)
{
if(l >= r) return true;//退出条件
int root = res[r];//最后一个点是根结点
int k = l;//从最左边开始
while(k < r && res[k] < root) k++;//符合左子树的点
for(int i = k; i < r; i++)//此时的k是右子树的第一个点
{
if(res[i] < root)//如果右子树小于根，说明不符合
return false;
}
return dfs(l, k - 1) && dfs(k, r - 1);//逐步缩小范围
}
};
https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
1. 当用前序的方式访问到某一节点时，我们把该节点添加到路径上，并累加该节点的值
2. 如果该节点为叶子节点并且路径中的节点值刚好等于目标值，则当前的路径符合要求。
3. 如果当前节点不是叶子节点，则继续访问它的子节点。
4. 当前节点访问结束后，递归函数将自动回到它的父节点。因此我们在函数退出之前要在路径上删除当前节点，
并减去当前节点的值，以确保返回父节点时路径，刚好是从根节点到父节点的路径
class Solution {
public:
vector<vector<int>> res; // 最终结果
vector<int> path; // 一次结果的路径
vector<vector<int>> pathSum(TreeNode* root, int target) {
if (root == nullptr) return res;
traverse(root, target, path);
return res;
}
// 递归遍历寻找合适的路径
void traverse(TreeNode* root, int target, vector<int>& path) {
if (root == nullptr) return;
int remain = target - root->val; // 减去当前节点值
if (root->left == nullptr && root->right == nullptr) { // 到达叶子节点
if (remain == 0) { // 判断是否刚好等于目标值
path.push_back(root->val);
res.push_back(path);
path.pop_back();
}
return;
}
// 没有到达叶子节点，继续寻找子节点
path.push_back(root->val);
traverse(root->left, remain, path);
path.pop_back(); // 返回父节点时要还原路径
path.push_back(root->val);
traverse(root->right, remain, path);
path.pop_back();
}
};
https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
Node* cur = head;
unordered_map<Node*, Node*> map;
// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != nullptr) {
map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
// 4. 构建新链表的 next 和 random 指向
while(cur != nullptr) {
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
// 5. 返回新链表的头节点
return map[head];
}
};
https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
class Solution {
public:
Node* pre = nullptr, *head = nullptr;
Node* treeToDoublyList(Node* root) {
if (!root) return root;
dfs(root);
head->left = pre;
pre->right = head;
return head;
}
void dfs(Node* root){
if (!root) return;// 递归边界: 叶子结点返回
dfs(root->left); //左子树
if (pre) pre->right = root;
else head = root; // 保存链表头结点
root->left = pre;
pre = root;
dfs(root->right); //右子树
}
};
https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/
class Solution {
public:
vector<string> res;
vector<string> permutation(string s) {
dfs(s, 0); // 从第0个字符开始
return res;
}
void dfs(string s, int start) {
if(start == s.size() - 1) {
res.push_back(s); // 添加排列方案
return;
}
set<int> st; // 就起个去重的作用
for(int i = start; i < s.size(); i++) {
if(st.find(s[i]) != st.end()) continue; // 重复，因此剪枝
st.insert(s[i]);
swap(s[i], s[start]); // 交换，将 s[i] 固定在第 start 位
dfs(s, start + 1); // 开启固定第 start + 1 位字符
swap(s[i], s[start]); // 恢复交换
}
}
};
https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
票数抵消法：
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0, votes = 0;
for (int num : nums) {
if (votes == 0) x = num;
votes += num == x ? 1 : -1;
}
return x;
}
};
https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
class Solution {
public:
vector<int> res;
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (arr.empty() || k == 0) return res;
sort(arr.begin(), arr.end());
for (int num : arr) {
if (k <= 0) break;
res.push_back(num);
k--;
}
return res;
}
};
https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int preSum = 0; // 前缀和
int maxSum = nums[0];// 最大和
for (int num : nums) {
preSum = max(preSum + num, num);
maxSum = max(preSum, maxSum);
}
return maxSum;
}
};
https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
class Solution {
public:
int countDigitOne(int n) {
long digit = 1;
int res = 0;
int high = n / 10, low = 0, cur = n % 10;
while (high != 0 || cur != 0) {
if (cur == 0) {
res += high * digit;
} else if (cur == 1) {
res += high * digit + low + 1;
} else {
res += (high + 1) * digit;
}
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
};
https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
for (int i = 0; i < nums.size(); i++) {
strs.push_back(to_string(nums[i])); // 将数字常量转换成字符串，再存入字符串数组里
}
quickSort(strs, 0, strs.size() - 1);
string res;
for (string str : strs) {
res.append(str);
}
return res;
}
private:
void quickSort(vector<string>& strs, int l, int r) {
if (l >= r) return;
int i = l, j = r;
while (i < j) {
while (strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;
while (strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
swap(strs[i], strs[j]);
}
swap(strs[i], strs[l]);
quickSort(strs, l, i - 1);
quickSort(strs, i + 1, r);
}
};
https://leetcode.cn/problems/chou-shu-lcof/
丑数的递推性质： 丑数只包含因子 2, 3, 5
因此有 “丑数 = 某较小丑数 × 某因子” （例如：10 = 5×2）。
class Solution {
public:
int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int dp[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
int n2 = dp[a] * 2;
int n3 = dp[b] * 3;
int n5 = dp[c] * 5;
dp[i] = min(min(n2, n3), n5);
if (dp[i] == n2) a++;
if (dp[i] == n3) b++;
if (dp[i] == n5) c++;
}
return dp[n - 1];
}
};
https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char, int> map;
for (int i = 0; i < s.size(); i++) {
map[s[i]]++;
}
for (char str : s) {
if (map[str] == 1)
return str;
}
return ' ';
}
};
https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* p1 = headA, *p2 = headB;
while (p1 != p2) {
if (p1 == nullptr) {
p1 = headB;
} else {
p1 = p1->next;
}
if (p2 == nullptr) {
p2 = headA;
} else {
p2 = p2->next;
}
}
return p1;
}
};
https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
class Solution {
public:
int search(vector<int>& nums, int target) {
// 找左边界
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else right = mid - 1;
}
// 当target 比所有的元素都大，left会越界
if (left >= nums.size() || nums[left] != target) return 0;
int left_bound = left;
// 找右边界
left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
// 当target 比所有的元素都小，right会越界
if (right < 0 || nums[right] != target) return 0;
int right_bound = right;
return right_bound - left_bound + 1;
}
};
https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
平衡二叉树
https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (root == nullptr) return true;
return (abs(depth(root->left) - depth(root->right)) <= 1)
&& isBalanced(root->left) && isBalanced(root->right);
}
int depth(TreeNode* root) {
if (root == 0) return 0;
return max(depth(root->left), depth(root->right)) + 1;
}
};
https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int x = 0, y = 0; // 两个只出现一次的数字
int n = 0; // 用来和数组中的每一位异或，最后得n = x ^ y
int b = 1; // 用来配合 n 分出两个子数组
for (int num : nums) {
n ^= num;
}
// 此时 n = x ^ y, 现在把数组分成两个子数组
while ((n & b) == 0) { // 找到第一个为1的位的位置
b <<= 1;
}
// 遍历数组，让数字都与 b 异或，分离出两个数组
for (int num : nums) {
if (num & b) x ^= num;
else y ^= num;
}
return {x, y};
}
};
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i = 0, j = nums.size() - 1;
while (i < j) {
int s = nums[i] + nums[j];
if (s < target) i++;
else if (s > target) j--;
else return {nums[i], nums[j]};
}
return {0};
}
};
和为s的连续整数序列
https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> findContinuousSequence(int target) {
int i = 1, j = 2, s = 3;
while (i < j) {
if (s == target) {
vector<int> ans;
for (int k = i; k <= j; k++) {
ans.push_back(k);
}
res.push_back(ans);
}
if (s >= target) {
s -= i;
i++;
} else {
j++;
s += j;
}
}
return res;
}
};
https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/
class Solution {
public:
string reverseWords(string s) {
int i = s.size() - 1;
string res;
while (i >= 0) { // 遍历 s
int c = 0; // 记录一个单词的长度
while (i >= 0 && s[i] == ' ') { // 遍历空格，
i--;
}
while (i >= 0 && s[i] != ' ') { // 遍历查找一个单词
i--;
c++;
}
if (c) {
res += s.substr(i + 1, c) + " ";
// substr 返回由 i+1 开始的 c 个字符组成的字符串
// 返回一个单词，后面紧跟一个空格分隔
}
}
return res.substr(0, res.size() - 1); // 最后一个单词后面的空格不要
}
};
https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
局部翻转+整体翻转
class Solution {
public:
string reverseLeftWords(string s, int n) {
/* 反转n前面的字符串 */
reverse(s.begin(), s.begin() + n);
/* 反转n后面的字符串 */
reverse(s.begin() + n, s.end());
/* 反转整个字符串 */
reverse(s.begin(), s.end());
return s;
}
};
https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/
1. 首先把数组排序
2. 统计数组中0的个数
3. 统计排序之后的数组中相邻数字之间的空缺总数
4. 如果空缺总数小于等于0的个数，那么这个数组就是连续的；反之不连续
5. 如果数组中的非0数字重复出现，则该数组是不连续的。
class Solution {
public:
bool isStraight(vector<int>& nums) {
int count = 0; // 0 的个数
sort(nums.begin(), nums.end()); // 数组排序
for (int i = 0; i < 4; i++) {
if (nums[i] == 0) count++; // 统计大小王数量
else if (nums[i] == nums[i + 1]) return false; // 有重复数字不是顺子
}
return nums[4] - nums[count] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
};
https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
约瑟夫环
class Solution {
public:
int lastRemaining(int n, int m) {
int last = 0;
for (int i = 2; i <= n; i++) {
last = (last + m) % i;
}
return last;
}
};
https://leetcode.cn/problems/qiu-12n-lcof/
class Solution {
public:
int res = 0;
int sumNums(int n) {
bool x = n > 1 && sumNums(n - 1) > 0;
res += n;
return res;
}
};
https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/
1. 不考虑进位。0加0,1加1的结果都是0,0加1,1加0的结果都是1。这和异或的结果是一样的
2. 考虑进位。对0加0,0加1,1加0而言，都不会产生进位，只有1加1会向前产生一个进位。
此时可以想象成两个数先做位与运算，然后再左移一位。
3. 把前面两个数相加，重复前两步，直到不产生进位为止。
class Solution {
public:
int add(int a, int b) {
int sum = 0, carry = 0;
while (b) {
sum = a ^ b;
carry = (unsigned int)(a & b) << 1;
a = sum;
b = carry;
}
return a;
}
};
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) return nullptr;
if (p->val > q->val) {
// 保证 p.val <= q.val，便于后续情况讨论
return lowestCommonAncestor(root, q, p);
}
if (root->val >= p->val && root->val <= q->val) {
// p <= root <= q
// 即 p 和 q 分别在 root 的左右子树，那么 root 就是 LCA
return root;
}
if (root->val > q->val) {
// p 和 q 都在 root 的左子树，那么 LCA 在左子树
return lowestCommonAncestor(root->left, p, q);
} else {
// p 和 q 都在 root 的右子树，那么 LCA 在右子树
return lowestCommonAncestor(root->right, p, q);
}
}
};
https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) { //2
return root;
}
if (left == NULL && right == NULL) { //1
return NULL;
}
return left == NULL ? right : left; //3,4
}
};