/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 思路：
// dfs 将每个节点的val和head比
// 如果一样就调用check方法
// 左右比较下一个节点相不相等
bool judge(ListNode *head, TreeNode *root) {
if (head == nullptr) return true;
if (root == nullptr) return false;
if (root->val != head->val) return false;
return judge(head->next, root->left) || judge(head->next, root->right);
}
bool isSubPath(ListNode* head, TreeNode* root) {
if (head == nullptr) return true;
if (root == nullptr) return false;
if (root->val == head->val && judge(head, root)) return true;
else return isSubPath(head, root->left) || isSubPath(head, root->right);
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 完全二叉树的性质
// 如果节点总数是n
// 那么最后一层的数量是n - (2 * m - 1) (m为倒数第二层的节点数量)
// k = m * 2 - 1
// 那么这 (n - k)个节点中 左子树最多l个节点
// (n - k - l)就是最后一层右子树的节点
// 也就是将判断n个节点的树是不是完全二叉树的问题
// 转换成了判断整个树左子树节点 == (k - 1) / 2 + l
// (k = 上层所有节点总和 l = 当前层的左子树节点)
int nodeCount(TreeNode *root) {
if (root == nullptr) return false;
return nodeCount(root->left) + nodeCount(root->right) + 1;
}
bool judge(TreeNode *root, int n, int m) {
if (root == nullptr) return n == 0;
if (n == 0) return false;
if (n == 1) return root->right == nullptr && root->left == nullptr;
int k = max(0, 2 * m - 1);
int l = min(m, n - k);
int r = n - k - l;
return judge(root->left, (k - 1) / 2 + l, m / 2) && judge(root->right, (k - 1) / 2 + r, m / 2);
}
bool isCompleteTree(TreeNode* root) {
if (root == nullptr) return false;
// m 记录倒数第二层的节点
int n = nodeCount(root), m = 1, cnt = 1;
while (cnt + 2 * m <= n) {
m *= 2;
cnt += m;
}
return judge(root, n, m);
}
};/*
// 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:
// 中序遍历
// 记录一个pre节点
// pre为上一次中序遍历的最后一个节点
// 将cur接到pre的下一个即可
Node *head, *pre;
void in_order(Node *root) {
if (root == nullptr) return ;
in_order(root->left);
// pre == nullptr 表示pre是第一个插入链表的节点
if (pre == nullptr) {
head = root;
} else {
pre->right = root;
}
root->left = pre;
pre = root;
in_order(root->right);
return ;
}
Node* treeToDoublyList(Node* root) {
if (root == nullptr) return nullptr;
head = pre = nullptr;
in_order(root);
pre->right = head;
head->left = pre;
return head;
}
};class Solution {
public:
// 状态压缩
// 如果我能赢 那么我的对手就输
// 这就是一个简单的状态转移
// 递归
bool dfs(int mask, int n, int total) {
if (total <= 0) return true;
// 对于每个n
// 都去递归他的全部的可能性
// 就是搜索
for (int i = 1; i <= n; i++) {
// mask 的第i位标记是否被使用过
if (mask & (1 << i)) continue;
if (i >= total) return true;
// 当前出手的元素为i
// 所以总和 - i
if (!dfs(mask | (1 << i), n, total - i)) return true;
}
return false;
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
// mask标记当前选了多少数
int n = maxChoosableInteger, mask = 0;
// 特例????
if ((1 + n) * n / 2 < desiredTotal) return false;
return dfs(mask, n, desiredTotal);
}
};但是这种大暴力搜索带来的问题就是时间复杂度超级高，并且我们可以通过分析看到，会遍历很多重复的节点
所以引入了记忆化搜索
当我们用到mask的时候不是去递归，而是先看一下mask在哈希表中有无记录
就可以直接返回结果了
class Solution {
public:
// 状态压缩
// 如果我能赢 那么我的对手就输
// 这就是一个简单的状态转移
// 递归
// But 超时了
// 记忆化搜索
// 自变量 mask
// 为什么不是mask和total？
// 因为total是随着mask的变化而变化的
// 用哈希表记录
unordered_map<int, bool> h;
bool dfs(int mask, int n, int total) {
if (h.find(mask) != h.end()) return h[mask];
if (total <= 0) return true;
for (int i = 1; i <= n; i++) {
if (mask & (1 << i)) continue;
// return 会返回赋值表达式的结果
if (i >= total || !dfs(mask | (1 << i), n, total - i)) return h[mask] = true;
}
return h[mask] = false;
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
// mask标记当前选了多少数
int n = maxChoosableInteger, mask = 0;
// 特例????
if ((1 + n) * n / 2 < desiredTotal) return false;
return dfs(mask, n, desiredTotal);
}
};class Solution {
public:
// 本质上是脑筋急转弯题
// 因为只有2 * 5才能凑出10来
// 而且随便一个数他的2的因子的个数一定多于5的数目
// 所以这不就变成求因子5的个数了！
int trailingZeroes(int n) {
int ans = 0;
int m = 5;
// 这里有个技巧
// 就是25 50 这种实际上由若干5 * 5组成的
// 需要排除掉 这些只算做一次5
// 每隔25出现一次
// 所以m *= 5就能简单的排除掉了
while (n / m) {
ans += (n / m);
m *= 5;
}
return ans;
}
};class Solution {
public:
vector<int> nums;
Solution(vector<int>& nums) : nums(nums) {
srand(time(0));
}
vector<int> reset() {
return nums;
}
vector<int> shuffle() {
vector<int> ret(nums);
for (int i = 0; i < ret.size(); ++i) {
swap(ret[i], ret[rand() % ret.size()]);
}
return ret;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
*//**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 先考虑对于链表
// 构造前缀和
// 用一个哈希表记录当前位置的前缀和
// 然后每到当前节点就统计一下和值
// 然后在哈希表中查一下前面的节点的前缀和是否在哈希表中存在
// 并且链表本质上就是退化的树
// 树看成有两个指针的链表不就得了
// 对于链表是顺序遍历
// 对于树直接递归不就得了
using ll = long long;
unordered_map<ll, ll> h;
ll count(TreeNode *root, ll sum, ll target) {
if (root == nullptr) return 0;
sum += root->val;
ll ans = h[sum - target];
h[sum] += 1;
ans += count(root->left, sum, target);
ans += count(root->right, sum, target);
h[sum] -= 1;
return ans;
}
ll pathSum(TreeNode* root, ll targetSum) {
h.clear();
h[0] = 1;
return count(root, 0, targetSum);
}
};
class Solution {
public:
// 假设出现次数不够的字符串为红色标记
// 那么我们要找的字符串肯定不可能在红色标记处出现呀
// 只能在他们分割成的子串中出现
// 所以这样不就缩小了问题规模么！
// 可以用递归来做了
// 技巧：
// 4个点可以分成5段
// 但是这样是不好处理的
// 不妨将最后一段加上一个虚拟分割点
// 这样每个子串就是当前分割点向前走就完事了
int longestSubstring(string s, int k) {
unordered_map<char, int> cnt;
vector<int> sp;
for (auto x : s) cnt[x] += 1;
for (int i = 0; s[i]; ++i) {
if (cnt[s[i]] < k) sp.push_back(i);
}
sp.push_back(s.size());
// 对于"ababbc"
// 分割点的位置是5 6
// 也就是c和最后的'\0'
// for (auto x : sp) cout << x << endl;
if (sp.size() == 1) return s.size();
int pre = 0, ans = 0;
for (auto p : sp) {
int len = p - pre;
if (len >= k) {
// 递归处理pre开始 len长的
// pre 从 0 开始
// p从第一个分割点开始
// pre~p就是子串们
ans = max(ans, longestSubstring(s.substr(pre, len), k));
}
pre = p + 1;
}
return ans;
}
};class Solution {
public:
// 假设出现次数不够的字符串为红色标记
// 那么我们要找的字符串肯定不可能在红色标记处出现呀
// 只能在他们分割成的子串中出现
// 所以这样不就缩小了问题规模么！
// 可以用递归来做了
// 技巧：
// 4个点可以分成5段
// 但是这样是不好处理的
// 不妨将最后一段加上一个虚拟分割点
// 这样每个子串就是当前分割点向前走就完事了
int longestSubstring(string s, int k) {
unordered_map<char, int> cnt;
vector<int> sp;
for (auto x : s) cnt[x] += 1;
for (int i = 0; s[i]; ++i) {
if (cnt[s[i]] < k) sp.push_back(i);
}
sp.push_back(s.size());
// 对于"ababbc"
// 分割点的位置是5 6
// 也就是c和最后的'\0'
// for (auto x : sp) cout << x << endl;
if (sp.size() == 1) return s.size();
int pre = 0, ans = 0;
for (auto p : sp) {
int len = p - pre;
if (len >= k) {
// 递归处理pre开始 len长的
// pre 从 0 开始
// p从第一个分割点开始
// pre~p就是子串们
ans = max(ans, longestSubstring(s.substr(pre, len), k));
}
pre = p + 1;
}
return ans;
}
};class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
// i 控制循环次数
// j 记录最低位（控制n）
// k 记录最高位（控制ans）
// 每次j往前走一位
// k往后走一位
for (uint32_t i = 0, j = 1, k = (1 << 31); i < 32; i++, j <<= 1, k >>= 1) {
if (n & j) ans |= k;
}
return ans;
}
};class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
for (uint32_t i = 0, j = 1; i < 32; ++i, j <<= 1) {
cout << j << endl;
ans += ((n & j) != 0);
}
return ans;
}
};class Solution {
public:
int myAtoi(string s) {
// flag 记录符号
// pre 和 d 记录max的除去个位的前面和个位
// 在后面处理进位用到
int flag = 1, pre = INT_MAX / 10, d = INT_MAX % 10;
int ind = 0, num = 0;
while (s[ind] == ' ') ++ind;
if (s[ind] == '-') flag = -1, ++ind;
else if (s[ind] == '+') ++ind;
for (; s[ind]; ++ind) {
if (s[ind] < '0' || s[ind] > '9') break;
// 为什么可以用一套逻辑处理正数和负数？
// 因为INTMAX和INTMIN就差了1
// 比INTMAX大只能是INTMIN了
if (num > pre || (num == pre && (s[ind] - '0') > d)) {
if (flag > 0) return INT_MAX;
return INT_MIN;
}
num = num * 10 + (s[ind] - '0');
}
return num * flag;
}
};class RandomizedSet {
public:
// val -> ind
unordered_map<int, int> h;
vector<int> vec;
RandomizedSet() {
srand(time(0));
}
bool insert(int val) {
if (h.find(val) != h.end()) return false;
h[val] = vec.size();
vec.push_back(val);
return true;
}
bool remove(int val) {
if (h.find(val) == h.end()) return false;
swap(vec[h[val]], vec[vec.size() - 1]);
h[vec[h[val]]] = h[val];
h[vec[vec.size() - 1]] = vec.size() - 1;
h.erase(h.find(val));
vec.pop_back();
return true;
}
int getRandom() {
return vec[rand() % vec.size()];
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/class RandomizedSet {
public:
set<int> s;
vector<int> vec;
RandomizedSet() {
srand(time(0));
}
bool insert(int val) {
if (s.count(val) > 0) return false;
s.insert(val);
vec.push_back(val);
return true;
}
bool remove(int val) {
if (s.count(val) <= 0) return false;
int ind = 0;
for (int i = 0; i < vec.size(); ++i) {
if (vec[i] == val) ind = i;
}
swap(vec[ind], vec[vec.size() - 1]);
s.erase(val);
vec.pop_back();
return true;
}
// 配合vector
// 每次删除的时候pop_back();
// 每次增加的时候push_back();
// getRandom每次从vector随机选择一个
int getRandom() {
return vec[rand() % vec.size()];
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/class Solution {
public:
// 核心思想
// 让小的尽可能往前挪
// 输入：num = "1432219", k = 3
// 输出："1219"
// 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
// 你看看这不就是根单调栈一模一样么
// 2进去吧234全弹出去了
// 也就是单调栈最多出栈k个元素
// 最后栈中的元素就是结果
string removeKdigits(string num, int k) {
if (k >= num.size()) return "0";
// mono stack
// 从这里看出来单调栈是一种思维方式
// 用什么样的结构都能实现单调栈！
string ret;
for (auto x : num) {
while (k && ret.size() && ret.back() > x) ret.pop_back(), k -= 1;
ret.push_back(x);
}
// 这里会有两种情况 k = 0 || k != 0
// k != 0的时候还可以接着删呢
// 又因为栈中的元素是单增的
// 所以删除末尾就可以
if (k) ret = ret.substr(0, ret.size() - k);
int ind = 0;
while (ret[ind] == '0') ++ind;
ret = ret.substr(ind, ret.size());
if (ret == "") ret = "0";
return ret;
}
};class Solution {
public:
// 子序列和子串是不一样的
// 子序列可以不连续的
// "bcabc" 之所以可以删除bc
// 是因为bc在后面还出现了
// 不是因为字典序的原因
// 其实有点像单调栈的
// 当出现一个较小的字母
// 我们自然是希望它能尽可能往前去
//
// 入栈条件：当前字母在栈中出现过了
// 如果重复压入会的到一个更垃圾的序列
string removeDuplicateLetters(string s) {
string ret;
// cnt 记录当前元素后面还有没有栈末尾的字符
unordered_map<char, int> cnt;
for (auto x : s) cnt[x] += 1;
// 记录栈中的元素
// 出现了就不用入栈了
unordered_set<char> h;
for (auto x : s) {
if (h.count(x) <= 0) {
while (ret.size() && ret.back() > x && cnt[ret.back()]) {
h.erase(h.find(ret.back()));
ret.pop_back();
}
h.insert(x);
ret.push_back(x);
}
cnt[x] -= 1;
}
return ret;
}
};class Solution {
public:
// 找规律
// 因为x是递增的 所以xj > xi
// 写成yi + yj + (xj - xi)
// = yj + xj + (yi - xi)
// j点坐标 + i点坐标差的最大值
// 也就是从i 到 j
// 这不就是在滑动窗口中找最大值
// 递减的单调队列
int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
deque<int> q;
q.push_back(0);
int ans = INT_MIN;
for (int i = 1; i < points.size(); ++i) {
// 控制窗口大小
// xj - xi > k
while (q.size() && points[i][0] - points[q.front()][0] > k) q.pop_front();
if (q.size()) {
// (yi - xi) + yj + xj
// 找最大值
ans = max(ans, points[i][0] - points[q.front()][0] + points[i][1] + points[q.front()][1]);
}
// 有yi - xi大
// 这就是我们判断的规则
// 就是男神 就能把他打出去
while (q.size() && points[i][1] - points[i][0] > points[q.back()][1] - points[q.back()][0]) q.pop_back();
q.push_back(i);
}
return ans;
}
};