3280. 将日期转换为二进制表示

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,"-")
}

729. 我的日程安排表 I

date:2025-1-2

题解

代码

3019. 按键变更的次数

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
}

79. 单词搜索

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;
}

46. 全排列

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>&current,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>&current,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();
            }
        }
    }

78. 子集

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>&current,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();
        }
    }
};

39. 组合总和

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>&current,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();
            }
        }
    }
};

22. 括号生成

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);
        }
    }
};

131. 分割回文串

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>&current,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;
    }
};

35. 搜索插入位置

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;
    }
};

74. 搜索二维矩阵

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;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

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;
}

33. 搜索旋转排序数组

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;
    }
};

153. 寻找旋转排序数组中的最小值

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];
    }
};

20. 有效的括号

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();
    }
};