class Solution {
public:
int maxSubArray(vector<int>& nums) {
long long sum = -10000000000, maxsum = 0;
for (int i = 0; i < nums.size(); i++) {
if (maxsum < 0) maxsum = nums[i];
else maxsum += nums[i];
sum = max(sum, maxsum);
}
return sum;
}
};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if(matrix.empty())return ans;
int n = matrix.size(), m = matrix[0].size(), i = 0, j = 0;
int endi = n - 1, endj = m - 1, si = 0, sj = 0;
if(n==1)return matrix[0];
if(m==1){
while(i<=endi)ans.push_back(matrix[i++][j]);
return ans;
}
while (1) {
if (endi == si && endj == sj) { ans.push_back(matrix[si][sj]); return ans; }
while (j != endj) {ans.push_back(matrix[i][j++]);if (ans.size() == n * m) return ans;}
while (i != endi) {ans.push_back(matrix[i++][j]);if (ans.size() == n * m) return ans;}
while (j != sj) {ans.push_back(matrix[i][j--]);if (ans.size() == n * m) return ans;}
while (i != si) {ans.push_back(matrix[i--][j]);if (ans.size() == n * m) return ans;}
if (ans.size() == n * m) return ans;
endi--, endj--, si++, sj++;
i = si, j = sj;
}
}
};
int vis[100010];
class Solution {
public:
bool bfs(vector<int>nums) {
int n = nums.size();
for(int i=0;i<=n;i++)vis[i]=0;
queue<pair<int, int>>q;
q.push(make_pair(nums[0], 0));
vis[0] = 1;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = cur.second; i <= cur.first + cur.second; i++) {
if (!vis[i] && i < n) {
vis[i] = 1;
q.push(make_pair(nums[i], i));
if (i == n - 1)return true;
}
}
}
return false;
}
bool canJump(vector<int>& nums) {
if(nums.size()==1)return true;
else return bfs(nums);
}
};
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>>ans;
if (intervals.empty())return ans;
else if (intervals.size() == 1)return intervals;
sort(intervals.begin(), intervals.end(), [](vector<int>&a, vector<int>&b) {return a[0] < b[0]; });
int i;
for (i = 1; i < intervals.size(); i++) {
vector<int>&pre = intervals[i - 1], &cur = intervals[i];
if ((cur[0] >= pre[0] && cur[0] <= pre[1]) || (cur[1] <= pre[1])) { cur[0] = min(cur[0], pre[0]); cur[1] = max(cur[1], pre[1]); }
else ans.push_back(pre);
}
--i;
if (ans.empty())ans.push_back(intervals[0]);
vector<int>last = intervals[i], &ans_last = ans[ans.size() - 1];
if ((last[0] >= ans_last[0] && last[0] <= ans_last[1]) || (last[1] <= ans_last[1])) { ans_last[0] = min(last[0], ans_last[0]); ans_last[1] = max(last[1], ans_last[1]); }
else ans.push_back(last);
return ans;
}
};
class Solution {
public:
int lengthOfLastWord(string s) {
int cnt = 0;
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] != ' ') cnt++;
else {
if (!cnt)continue;
else break;
}
}
return cnt;
}
};
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>>ans;
vector<int>tmp;
if (!n)return ans;
else if (n == 1) { tmp.push_back(1); ans.push_back(tmp); return ans; }
for (int i = 0; i < n; i++)tmp.push_back(0);
for (int i = 0; i < n; i++)ans.push_back(tmp);
int num = 1, i = 0, j = 0, sti = 0, stj = 0, endi = n - 1, endj = n - 1;
while (num < n*n) {
while (i == sti && j != endj)ans[i][j++] = num++;
while (i != endi && j == endj)ans[i++][j] = num++;
while (i == endi && j != stj)ans[i][j--] = num++;
while (i != sti && j == stj)ans[i--][j] = num++;
endi--, endj--, sti++, stj++;
i = sti, j = stj;
if (endi == sti && endj == stj)ans[endi][endj] = num;
}
return ans;
}
};
class Solution {
public:
string getPermutation(int n, int k) {
char ans[10];
int cnt = 0;
for (int i = 1; i <= n; i++)ans[cnt++] = ('0' + i);
ans[cnt] = '\0';
while (--k)next_permutation(ans, ans + n);
return ans;
}
};
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int cnt = 1;
ListNode*h = head;
if(h == nullptr)return head;//这样例就nm离谱
while(h->next)h = h->next, cnt++;
h->next = head;
k %= cnt;
cnt -= k;
h = head;
if(!cnt)return head;
while(cnt > 1){
h = h->next;
cnt--;
}
ListNode*new_h = h->next;
h->next = nullptr;
return new_h;
}
};
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[110][110];
for (int i = 0; i < m; i++)dp[i][0] = 1;
for (int i = 0; i < n; i++)dp[0][i] = 1;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
return dp[m - 1][n - 1];
}
};
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if(obstacleGrid.empty())return 0;
long dp[110][110];
int m=obstacleGrid.size(),n=obstacleGrid[0].size();
memset(dp,0,sizeof(dp));
if (obstacleGrid[m-1][n-1])return 0;
dp[0][0]=!obstacleGrid[0][0]?1:0;
for (int i = 1; i < m; i++)dp[i][0] = (dp[i - 1][0] && !obstacleGrid[i][0]) ? 1 : 0;
for (int i = 1; i < n; i++)dp[0][i] = (dp[0][i - 1] && !obstacleGrid[0][i]) ? 1 : 0;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = !obstacleGrid[i][j]?dp[i - 1][j] + dp[i][j - 1]:0;
return dp[m - 1][n - 1];
}
};
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty())return 0;
int dp[210][210], m = grid.size(), n = grid[0].size();
memset(dp, 0x4f4f4f4f, sizeof(dp));
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++)dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int i = 1; i < n; i++)dp[0][i] = dp[0][i - 1] + grid[0][i];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
return dp[m - 1][n - 1];
}
};
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
if (digits[digits.size() - 1] + 1 == 10) {
digits[digits.size() - 1] = 0;
for (int i = digits.size() - 2; i >= 0; i--) {
digits[i]++;
if (digits[i] == 10)digits[i] = 0;
else break;
}
if (!digits[0])digits.insert(digits.begin(), 1);
}
else digits[digits.size() - 1]++;
return digits;
}
};
class Solution:
def addBinary(self, a: str, b: str) -> str:
return str(bin(int(a,2)+int(b,2)))[2:]
class Solution {
public:
int mySqrt(int x) {
return sqrt(x);
}
};
class Solution {
public:
int climbStairs(int n) {
long long a = 0, b = 1;
while (n--) {
long long tmp = b;
b += a;
a = tmp;
}
return b;
}
};
class Solution {
public:
int dp[510][510];
int minDistance(string s1, string s2) {
int n = s1.size(), m = s2.size();
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) dp[0][i] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (s1[i - 1] != s2[j - 1])
dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
else dp[i][j] = dp[i - 1][j - 1];
return dp[n][m];
}
};
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!matrix[i][j]) {
int tmpi = i, tmpj = j;
while (tmpi >= 0 && tmpi <= i)if (matrix[tmpi][j])matrix[tmpi--][j] = -1e4; else tmpi--;
tmpi = i;
while (tmpi < n && tmpi >= i)if (matrix[tmpi][j])matrix[tmpi++][j] = -1e4; else tmpi++;
while (tmpj >= 0 && tmpj <= j)if (matrix[i][tmpj])matrix[i][tmpj--] = -1e4; else tmpj--;
tmpj = j;
while (tmpj < m && tmpj >= j)if (matrix[i][tmpj])matrix[i][tmpj++] = -1e4; else tmpj++;
}
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (matrix[i][j] == -1e4)matrix[i][j] = 0;
}
};
bool binary_s(vector<int>::iterator b,vector<int>::iterator e,int t){
auto l = b, r = e;
while (l != r) {
auto m = l + (r - l) / 2;
if (*m == t)return true;
else if (*m > t)r = m;
else l = m + 1;
}
return false;
}
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())return false;
int n = matrix.size();
for (int i = 0; i < n; i++) {
if (matrix[i][0] < target) {
if (binary_s(matrix[i].begin(), matrix[i].end(), target))return true;
else continue;
}
else if(matrix[i][0]==target)return true;
else return false;
}
return false;
}
};
class Solution {
public:
void sortColors(vector<int>& nums) {
int col[3];
for(auto i:nums)col[i]++;
for(auto&i:nums){
if(col[0]){i=0,col[0]--;}
else if(col[1]){i=1;col[1]--;}
else if(col[2]){i=2;col[2]--;}
}
}
};
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
deque<vector<int>>pipe;
vector<vector<int>>ans;
for (int i = 1; i <= n; i++) {
vector<int>t{ i };
pipe.push_back(t);
}
while (1) {
vector<int>tmp = pipe.front();
if (tmp.size() == k)break;
else {
pipe.pop_front();
int t = *(--tmp.end());
for (int i = t + 1; i <= n; i++) {
vector<int>newtmp = tmp;
newtmp.push_back(i);
pipe.push_back(newtmp);
}
}
}
while (!pipe.empty()) {
ans.push_back(pipe.front());
pipe.pop_front();
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>>ans={{}};
vector<int>tmp;
for(auto num:nums){
int n=ans.size();
for(int i = 0;i < n;i++){
ans.push_back(ans[i]);
ans.back().push_back(num);
}
}
return ans;
}
};
class Solution {
public:
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
set<pair<int, int>>st;
bool dfs(vector<vector<char>>& board, string&word, int x, int y, int n, int m, char c, int pos) {
if (c != word[pos])return false;
else if (pos == word.size() - 1 && c == word[pos])return true;
else {
for (int i = 0; i < 4; i++) {
int tmpx = x + dx[i], tmpy = y + dy[i];
if (tmpx >= 0 && tmpx < n&&tmpy >= 0 && tmpy < m&&st.find({ tmpx,tmpy }) == st.end()) {
st.insert({ tmpx,tmpy });
if (dfs(board, word, tmpx, tmpy, n, m, board[tmpx][tmpy], pos + 1))return true;
st.erase({ tmpx,tmpy });
}
}
return false;
}
}
bool exist(vector<vector<char>>& board, string word) {
char s = word[0];
int n = board.size(), m = board[0].size();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (board[i][j] == s) {
st.insert({ i,j });
if (dfs(board, word, i, j, n, m, s, 0))return true;
st.erase({ i, j });
}
return false;
}
};
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i = 0;
for (int num : nums)if (i < 2 || num > nums[i - 2])nums[i++] = num;
return i;
}
};
class Solution {
public:
bool search(vector<int>& nums, int target) {
int maxv = -1, minv = 1000000, maxpos = -1, minpos = -1, tmppos = -1, n = nums.size();
if(!n)return false;
for (int i = 0; i < n; i++)if (nums[i] > maxv)maxpos = i, maxv = nums[i];
tmppos = maxpos;
while (nums[maxpos] == maxv) {
maxpos = (maxpos + 1) % n;
if (nums[maxpos] != maxv || maxpos == tmppos) { minpos = maxpos, minv = nums[maxpos]; break; }
}
int l = 0, r = n;
while (l < r) {
int m = (l + r) / 2;
if (nums[(m + minpos) % n] == target)return true;
else if (nums[(m + minpos) % n] < target)l = m + 1;
else r = m;
}
return false;
}
};
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
int flag = 1;
ListNode inf(0x3f3f3f3f);
inf.next = head;
ListNode tmp = inf;
ListNode*cur = inf.next;
ListNode*pre = &inf;
while(cur&&flag){
if(cur->next == nullptr){
cur->next = (ListNode*)malloc(sizeof(ListNode));
flag = 0;
}
if(cur->val != (cur->next)->val&&cur->val != pre->val&&cur->val != tmp.val){
pre->next = cur;
pre = pre->next;
cur = cur->next;
}
else{
tmp.val = cur->val;
cur = cur->next;
}
}
pre->next = nullptr;
return inf.next;
}
};
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode*tmp = head;
while (tmp) {
while (tmp->next && tmp->val == tmp->next->val)
tmp->next = tmp->next->next;
tmp = tmp->next;
}
return head;
}
};
class Solution {
public:
int l[210][210], r[210][210], up[210][210];
int maximalRectangle(vector<vector<char>>& maze) {
int n = maze.size(), ans = 0;
if(!n)return 0;
int m = maze[0].size();
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++)
if (maze[i][j] == '1' && maze[i][j - 1] == '1')l[i][j] = l[i][j - 1] + 1;
for (int j = m - 1; j > 0; j--)
if (maze[i][j - 1] == '1' && maze[i][j] == '1')r[i][j - 1] = r[i][j] + 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == '1') {
if (i >= 1 && maze[i - 1][j] == '1') {
l[i][j] = min(l[i][j], l[i - 1][j]), r[i][j] = min(r[i][j], r[i - 1][j]);
up[i][j] = up[i - 1][j] + 1;
}
else up[i][j] = 1;
}
ans = max(ans, (l[i][j] + r[i][j] + 1) * up[i][j]);
}
}
return ans;
}
};
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode ans1(0);
ListNode ans2(0);
ListNode *p1 = &ans1, *p2 = &ans2;
while (head) {
if (head->val < x)p1 = p1->next = head;
else p2 = p2->next = head;
head = head->next;
}
p2->next = nullptr;
p1->next = ans2.next;
return ans1.next;
}
};
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int i = m, j = 0; i < m + n && j < n; i++, j++)nums1[i] = nums2[j];
sort(nums1.begin(), nums1.end());
}
};
class Solution {
public:
int num[10010], vis[10010];
vector<int>ans;
int cnt = 1;
bool dfs(int *tmp,int n) {
if (cnt == pow(2, n))return true;
for (int i = 0; i < n; i++) {
int tmp_ans = 0;
tmp[i] = !tmp[i];
for (int j = 0; j < n; j++)tmp_ans += tmp[j] * (pow(2, n - j - 1));
if (!vis[tmp_ans]) {
vis[tmp_ans] = 1, cnt++;
if (dfs(tmp,n)) { ans.push_back(tmp_ans); return true; }
vis[tmp_ans] = 0, cnt--;
}
tmp[i] = !tmp[i];
}
return false;
}
vector<int> grayCode(int n) {
ans.push_back(0);
vis[0] = 1;
dfs(num,n);
return ans;
}
};
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>>ans;
set<vector<int>>tmp_ans;
tmp_ans.insert(vector<int>());
sort(nums.begin(), nums.end());
for(auto &i : nums){
vector<vector<int>>tmp;
for(auto j : tmp_ans){
j.push_back(i);
tmp.push_back(j);
}
for(auto &j : tmp)tmp_ans.insert(j);
}
for(auto &i : tmp_ans)ans.push_back(i);
return ans;
}
};
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
int dp[100000];
memset(dp, 0, sizeof(dp));
dp[0] = (s[0] != '0');
dp[1] = (s[0] != '0' && s[1] != '0');
for(int i = 2; i <= n; i++){
if(s[i] != '0'){
dp[i] = dp[i - 1];
int tmp = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
if(tmp <= 26 && s[i - 1] != '0')dp[i] += dp[i - 2];
else if(tmp <= 26 && s[i - 1] =='0')dp[i] = dp[i - 2];
}
else dp[i] = 0;
}
return dp[n];
}
};
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode *h = new ListNode(0);
ListNode *pre = h;
h -> next = head;
for (int i = 0; i < m - 1; i++)pre = pre -> next;
ListNode *cur = pre -> next;
for (int i = 0; i < n - m; i++) {
ListNode* tmp = pre -> next;
pre -> next = cur -> next;
cur -> next = cur -> next -> next;
pre -> next -> next = tmp;
}
return h -> next;
}
};
class Solution {
public:
int stoi(string &s) {
if ((s[0] == '0'&&s.size() > 1) || s.size() > 4)return 256;
int ans = 0, l = s.size() - 1;
for (auto &i : s) {
ans += (i - '0') * std::pow(10, l);
l--;
}
return ans;
}
bool judge(string &s1, string &s2, string &s3, string &s4) {
return stoi(s1) <= 255 && stoi(s2) <= 255 && stoi(s3) <= 255 &&
stoi(s4) <= 255;
}
vector<string> restoreIpAddresses(string s) {
int n = s.size();
vector<string> ans;
if (n < 4 || n > 12)return ans;
vector<int> tmp(n - 1);
for (int i = 0; i < 3; i++) *(tmp.rbegin() + i) = 1;
do {
int d1 = -1, d2 = -1, d3 = -1;
for (int i = 0; i < tmp.size(); i++) {
if (tmp[i]) {
if (d1 < 0)d1 = i + 1;
else if (d2 < 0)d2 = i + 1;
else if (d3 < 0)d3 = i + 1;
}
}
string t1(s.begin(), s.begin() + d1);
string t2(s.begin() + d1, s.begin() + d2);
string t3(s.begin() + d2, s.begin() + d3);
string t4(s.begin() + d3, s.end());
if (judge(t1, t2, t3, t4))ans.push_back(string(t1 + "." + t2 + "." + t3 + "." + t4));
} while (next_permutation(tmp.begin(), tmp.end()));
return ans;
}
};
class Solution {
public:
void inorder(vector<int>&ans, TreeNode *cur){
if(cur->left)inorder(ans, cur->left);
ans.push_back(cur->val);
if(cur->right)inorder(ans, cur->right);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>ans;
if(!root)return ans;
inorder(ans, root);
return ans;
}
};
很难过，这题我目前不会。
class Solution {
public:
int numTrees(int n) {
long long k = 1;
for (int i = 1; i <= n; i++) k = k * (4 * i - 2) / (i + 1);
return k;
}
};
class Solution {
public:
bool isValidBST_tmp(TreeNode* cur, TreeNode* minN, TreeNode* maxN){
if(!cur)return true;
if(minN && cur->val <= minN->val || maxN && cur->val >= maxN->val)return false;
return isValidBST_tmp(cur->left, minN, cur) && isValidBST_tmp(cur->right, cur, maxN);
}
bool isValidBST(TreeNode* root) {
return isValidBST_tmp(root, nullptr, nullptr);
}
};
class Solution {
public:
bool bfs(TreeNode*r1, TreeNode*r2){
queue<TreeNode*>q1, q2;
q1.push(r1), q2.push(r2);
if(r1->val != r2->val)return false;
while(!q1.empty() && !q2.empty()){
TreeNode*cur1 = q1.front(); q1.pop();
TreeNode*cur2 = q2.front(); q2.pop();
int lv1 = cur1->left ? cur1->left->val : -1;
int lv2 = cur2->left ? cur2->left->val : -1;
int rv1 = cur1->right ? cur1->right->val : -1;
int rv2 = cur2->right ? cur2->right->val : -1;
if(lv1 != lv2 || rv1 != rv2)return false;
if(cur1->left)q1.push(cur1->left);
if(cur1->right)q1.push(cur1->right);
if(cur2->left)q2.push(cur2->left);
if(cur2->right)q2.push(cur2->right);
}
if(!q1.empty() || !q2.empty())return false;
else return true;
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q)return true;
else if(!p || !q)return false;
else return bfs(p, q);
}
};