date:2025-1-1
题解
按”-“分割字符串,遍历字符串数值,转会为Int型,二进制型,
拼接字符串数组。
代码
1 2 3 4 5 6 7 8
| func convertDateToBinary(date string) string { a:=strings.Split(date,"-") for i:=range a{ x,_:= strconv.Atoi(a[i]) a[i]= strconv.FormatUint(uint64(x),2) } return strings.Join(a,"-") }
|
date:2025-1-2
题解
代码
date:2025-1-7
题解
tolower转化成小写
代码
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public: int countKeyChanges(string s) { int n=s.size(),count=0; for(int i=1;i<n;i++){ if(tolower(s[i])!=tolower(s[i-1])){ count++; } } return count; } };
|
1 2 3 4 5 6 7 8 9 10
| func countKeyChanges(s string) int { count:=0 s=strings.ToLower(s) for i:=1;i<len(s);i++{ if s[i]!=s[i-1]{ count++ } } return count }
|
date:2025-03-08
题解
使用深度优先搜索解题,使用回溯保证每次遍历不会重复,找到的数目等于单词数时返回。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Solution { public: bool exist(vector<vector<char>>& board, string word) { int m=board.size(),n=board[0].size(); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]==word[0]){ if(dfs(board,word,i,j,0)){ return true; } } } } return false; } bool dfs(vector<vector<char>>&board,string &word,int i,int j,int index){ if(index==word.size()){ return true; } if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]!=word[index]){ return false; } char temp=board[i][j]; board[i][j]='#'; bool found=dfs(board,word,i+1,j,index+1)|| dfs(board,word,i-1,j,index+1)|| dfs(board,word,i,j-1,index+1)|| dfs(board,word,i,j+1,index+1); board[i][j]=temp; return found; } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include<iostream> #include<vector> #include<string> using namespace std; int main{ vector<vector<char>>board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]; string word="ABCCED"; bool result=exist(board,word); if(result){ cout<<"true"<<endl; }else{ cout<<"false"<<endl; } } bool exist(vector<vector<char>>&board,string &word){ int m=board.size(),n=board[0].size(); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(dfs(board,word,i,j,0)){ return true; } } } return false; } bool dfs(vector<vector<char>>&board,string &word,int i,int j,int index){ if(index==word.size()){ return true; } if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]!=word[index]){ return false; } char temp=board[i][j]; board[i][j]='#'; bool found=dfs(board,word,i+1,j,index+1)|| dfs(board,word,i-1,j,index+1)|| dfs(board,word,i,j-1,index+1)|| dfs(board,word,i,j+1,index+1); board[i][j]=temp; return found; }
|
date:2025-3-10
题解
回溯解决
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>>result; vector<int>current; vector<bool>used(nums.size(),false); backtrack(result,current,nums,used); return result; } void backtrack(vector<vector<int>>&result,vector<int>¤t,const vector<int>&nums,vector<bool>&used){ if(current.size()==nums.size()){ result.push_back(current); return; } for(int i=0;i<nums.size();i++){ if(!used[i]){ used[i]=true; current.push_back(nums[i]); backtrack(result,current,nums,used); used[i]=false; current.pop_back(); } } } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<iostream> #include<vector> using namespace std; int main(){ int n; cin>>n; vector<int>nums(n); for(int i=0;i<n;i++){ cin>>nums[i]; } vector<vector<int>>result=permute(nums); cout<<"[" for (int i = 0; i < result.size(); i++) { cout << "["; for (int j = 0; j < result[i].size(); j++) { cout << result[i][j]; if (j < result[i].size() - 1) { cout << ","; } } cout << "]"; if (i < result.size() - 1) { cout << ","; } } cout << "]" << endl; } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>>result; vector<int>current; vector<bool>used(nums.size(),false); backtrack(result,current,nums,used); return result; } void backtrack(vector<vector<int>>&result,vector<int>¤t,const vector<int>&nums,vector<bool>&used){ if(current.size()==nums.size()){ result.push_back(current); return; } for(int i=0;i<nums.size();i++){ if(!used[i]){ used[i]=true; current.push_back(nums[i]); backtrack(result,current,nums,used); used[i]=false; current.pop_back(); } } }
|
date:2025-3-10
题解
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>>result; vector<int>current; backtrack(nums,0,current,result); return result; } void backtrack(vector<int>&nums,int index,vector<int>¤t,vector<vector<int>>&result){ result.push_back(current); for(int i=index;i<nums.size();i++){ current.push_back(nums[i]); backtrack(nums,i+1,current,result); current.pop_back(); } } };
|
date:2025-3-10
题解
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<vector<int>>result; vector<int>current; backtrack(candidates,target,current,0,0,result); return result; } void backtrack(vector<int>&candidates,int target,vector<int>¤t,int mid,int start,vector<vector<int>>&result){ if(mid==target){ result.push_back(current); return; } if(mid>target){ return; } for(int i=start;i<candidates.size();i++){ if(mid<target){ current.push_back(candidates[i]); backtrack(candidates,target,current,mid+candidates[i],i,result); current.pop_back(); } } } };
|
date:2025-3-10
题解
回溯,看左右括号数,左括号小于括号对数,右括号小于左括号时加括号。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: vector<string> generateParenthesis(int n) { vector<string>result; string current; backtrack(result,current,0,0,n); return result; } void backtrack(vector<string>&result,string current,int open,int close,int n){ if(current.size()==n*2){ result.push_back(current); return; } if(open<n){ backtrack(result,current+"(",open+1,close,n); } if(close<open){ backtrack(result,current+")",open,close+1,n); } } };
|
date:2025-3-10
题解
一样回溯解决,每个位置,查看到最后是不是回文串,找到后加入到current中,再递归查看是否还存在字串。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>>result; vector<string>current; backtrack(result,current,0,s); return result; } void backtrack(vector<vector<string>>&result,vector<string>¤t,int start,string s){ if(start>=s.length()){ result.push_back(current); return; } for(int end=start;end<s.length();end++){ if(isString(start,end,s)){ current.push_back(s.substr(start,end-start+1)); backtrack(result,current,end+1,s); current.pop_back(); } } } bool isString(int start,int end,string s){ while(start<end){ if(s[start]!=s[end]){ return false; } start++; end--; } return true; } };
|
date:2025-3-11
题解
二分查找解题,存在时会返回位置,不存在时返回大于target的下一个位置。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public: int searchInsert(vector<int>& nums, int target) { int i=0,j=nums.size()-1; while(i<=j){ int mid=i+(j-i)/2; if(nums[mid]<target){ i=mid+1; }else{ j=mid-1; } } return i; } };
|
date:2025-3-11
题解
由于题目二维数组的定义,可以将二维数组转化成一维数组,然后二分查找基本功解题。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m=matrix.size(),n=matrix[0].size(); int i=0,j=n*m-1; while(i<=j){ int mid=i+(j-i)/2; if(matrix[mid/n][mid%n]<target){ i=mid+1; }else if(matrix[mid/n][mid%n]>target){ j=mid-1; }else if(matrix[mid/n][mid%n]==target){ return true; } } return false; } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include<iostream> #include<vector>
using namespace std;
bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(); int i = 0, j = n * m - 1; while (i <= j) { int mid = i + (j - i) / 2; if (matrix[mid / n][mid % n] < target) { i = mid + 1; } else if (matrix[mid / n][mid % n] > target) { j = mid - 1; } else if (matrix[mid / n][mid % n] == target) { return true; } } return false; } int main(){ int m,n,target; cin>>m>>n>>target; vector<vector<int>>matrix(m,vector<int>(n)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ cin>>matrix[i][j]; } } bool res=searchMatrix(matrix,target); if(res){ cout<<"true"<<endl; }else{ cout<<"false"<<endl; } }
|
date:2025-3-11
题解
两个二分查找,先找左边界,再找右边界
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int>result={-1,-1}; if(nums.empty())return result; int left=0,right=nums.size()-1; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]<target){ left=mid+1; }else{ right=mid; } } if(nums[left]!=target)return result; result[0]=left; right=nums.size()-1; while(left<right){ int mid=left+(right-left+1)/2; if(nums[mid]>target){ right=mid-1; }else{ left=mid; } } result[1]=right; return result; } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| #include<iostream> #include<vector> using namespace std; vector<int> searchRange(vector<int>&nums,int target); int main(){ int n,target; cin>>n>>target; vector<int>nums(n); for(int i=0;i<n;i++){ cin>>nums[i]; } vector<int>result; result=searchRange(nums,target); for(int i=0;i<2;i++){ cout<<result[i]; if(i<1){ cout<<","; } } cout<<endl; return 0; } vector<int> searchRange(vector<int>& nums, int target) { vector<int> result = {-1, -1}; if (nums.empty()) return result; int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } if (nums[left] != target) return result; result[0] = left; right = nums.size() - 1; while (left < right) { int mid = left + (right - left + 1) / 2; if (nums[mid] > target) { right = mid - 1; } else { left = mid; } } result[1] = right; return result; }
|
date:2025-3-11
题解
判断中间点在哪个有序数组中,
nums[left]<=nums[mid] 代表左半有序,再判断target是否存在左半区间
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| 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)return mid; if(nums[left]<=nums[mid]){ if(nums[left]<=target&&target<nums[mid]){ right=mid-1; }else{ left=mid+1; } }else{ if(nums[mid]<target&&target<=nums[right]){ left=mid+1; }else{ right=mid-1; } } } return -1; } };
|
date:2025-3-11
题解
找到无序的那一半序列,哪一半序哪边存在最小数。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public: int findMin(vector<int>& nums) { int left=0,right=nums.size()-1; if(nums[left]<=nums[right])return nums[left]; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]>nums[right]){ left=mid+1; }else{ right=mid-1; } } return nums[left]; } };
|
date:2025-3-12
题解
有左括号就压栈,右括号出栈,再看出栈的上一个字符是否对应这个字符的右括号。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public: bool isValid(string s) { stack<char> sta; for(char c:s){ if((c=='(')||(c=='[')||(c=='{')){ sta.push(c); }else{ if(sta.empty()){ return false; } char top=sta.top(); sta.pop(); if((c==')'&&top!='(')|| (c=='}'&&top!='{')|| (c==']'&&top!='[')){ return false; } } } return sta.empty(); } };
|