1.4万

yxc
yxc的机器人a

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> h;
int m = nums.size();
vector<int> s(m + 1);
for (int i = 1; i <= m; i++) s[i] = s[i - 1] + nums[i - 1];
h[0] = 1;
int res = 0;
for (int i = 1; i <= m; i++) {
if (h.count(s[i] - k)) res += h[s[i] - k];
h[s[i]]++;
}
return res;
}
};


class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> sum(n + 1);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
unordered_set<int> s;
for (int i = 2; i <= n; i++) {
s.insert(sum[i - 2] % k);
if (s.count(sum[i] % k)) return true;
}
return false;
}
};


class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> f (m + 1, vector<int>(n + 1));
//  f[i][j][k]  表示  前i个字符串中 0 不超过 j, 1 不超过 k的数目
//  f[i][j][k] = f[i - 1][j - a][k - b] + 1// a 是0  的数目，b 是 1的数目。
for (int i = 0; i < strs.size(); i++) {
int a = 0, b = 0;
for (auto ch : strs[i]) {
if (ch == '0') a++;
else b++;
}
for (int j = m; j >= a; j--) {
for (int k = n; k >= b; k--) {
f[j][k] = max(f[j][k], f[j - a][k - b] + 1);
}
}
}
return f[m][n];
}
};


class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int l = -1e9, r = 1e9;
while (l < r) {
int mid = l + r >> 1;
int i = matrix[0].size() - 1;
int cnt = 0;
for (int j = 0; j < matrix.size(); j++) {
while (i >= 0 && matrix[j][i] > mid) i--;
cnt += i + 1;
}
if (cnt >= k) r = mid;
else l = mid + 1;
}
return r;
}
};


class Solution {
public:
bool isIsomorphic(string s, string t) {
char hs[300] = "";
char ht[300] = "";
for (int i = 0; i < s.size(); i++) {
if (hs[s[i]] && hs[s[i]] != t[i] || ht[t[i]] && ht[t[i]] != s[i]) return false;
hs[s[i]] = t[i];
ht[t[i]] = s[i];
}
return true;
}
};


class Solution {
public:
int trailingZeroes(int n) {
int res = 0;
while (n) res += n / 5, n /= 5;
return res;
}
};


class Solution {
public:
string convertToTitle(int columnNumber) {
string res;
while (columnNumber > 0) {
columnNumber--;
res += (columnNumber % 26) + 'A';
columnNumber /= 26;
}
reverse(res.begin(), res.end());
return res;
}
};


class Solution {
public:
int divide(int dividend, int divisor) {
typedef long long ll;
bool is_minus = false;
if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0) is_minus = true;
vector<ll> num;
ll a = abs(dividend), b = abs(divisor);
for (ll i = b; i <= a; i = i + i) num.push_back(i);
ll res = 0;
for (int i = num.size() - 1; i >= 0; i--) {
if (a >= num[i]) {
a -= num[i];
res += (1ll << i);
}
}
if (is_minus) res = -res;
if (res < INT_MIN || res > INT_MAX) return INT_MAX;
return res;
}
};



/**
* 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) {}
* };
*/
//二叉树的前序遍历 moris写法。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
while (root) {
if (root->left) {
auto p = root->left;
while (p->right && p->right != root) p = p->right;
if (!p->right) {
res.push_back(root->val);
p->right = root;
root = root->left;
} else {
p->right = NULL;
root = root->right;
}
} else {
res.push_back(root->val);
root = root->right;
}
}
return res;
}
};

// 二叉树的中序遍历 moris写法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
auto cur = root;
while (cur) {
if (cur->left) {
auto l = cur->left;
while (l->right && l->right != cur) l = l->right;
if (!l->right) {
l->right = cur;
cur = cur->left;
} else {
res.push_back(cur->val);
l->right = NULL;
cur = cur->right;
}
} else {
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};

// 二叉树的后续遍历 moris写法。

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
while (root) {
if (root->right) {
auto p = root->right;
while (p->left && p->left != root) p = p->left;
if (!p->left) {
res.push_back(root->val);
p->left = root;
root = root->right;
} else {
p->left = NULL;
root = root->left;
}
} else {
res.push_back(root->val);
root = root->left;
}
}
reverse(res.begin(), res.end());
return res;
}
};



class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
auto cur = root;
while (cur) {