3259. 超级饮料的最大强化能量

date:2024-11-1 tag:动态规划

题解

使用动态规划解题，分别定义dpA[i]``dpB[i]为时间i时的最大总强化能量。
结果为long long型，定义vectordpA(n,0)同时初始化dpA[0]。
动态转移方程dpA[i]=max(dp[i-1],dpB[i-2])+energyDrinkA[i]
考虑i=1时，可能为选i=0后就2切换。(i>1?dpB[i-2]:0)
返回max(dpA[n-1],dpB[n-1])

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n=energyDrinkA.size();
        vector<long long>dpA(n,0);
        vector<long long>dpB(n,0);
        dpA[0]=energyDrinkA[0];
        dpB[0]=energyDrinkB[0];
        for(int i=1;i<n;++i){
            dpA[i]=max(dpA[i-1],(i>1?dpB[i-2]:0))+energyDrinkA[i];
            dpB[i]=max(dpB[i-1],(i>1?dpA[i-2]:0))+energyDrinkB[i];
        }
        return max(dpA[n-1],dpB[n-1]);
    }
};

113. 路径总和 II

date:2024-11-2 tag:DFS

题解

用深度优先搜索，res为结果，current为中间搜索数组。
targetSum 为0且当前位置root左右子树为空时，表示找到了一个结果，加入到res中。
否则就遍历左或右子树，root为空时，表示找不到结果，直接返回return,root不为空，更新targetSum值，将当前的root->val加入到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
/**
 * 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:
    void dfs(TreeNode*root,vector<vector<int>>&res,int targetSum,vector<int>&current){
        if(root==nullptr)return;
        current.emplace_back(root->val);
        targetSum-=root->val;
        if(targetSum==0&&root->left==nullptr&&root->right==nullptr){
            res.emplace_back(current);
        }else{
        dfs(root->left,res,targetSum,current);
        dfs(root->right,res,targetSum,current);}
        current.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>>res;
        vector<int>current;
        dfs(root,res,targetSum,current);
        return res;
    }
};

129. 求根节点到叶节点数字之和

date:2024-11-3 tag:深度优先搜索

题解

初始化res为0，current表示中间未达到叶子节点的数，每次遍历如果root不为空，更新current的值，
如果左右节点都为空，将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
/**
 * 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:
    void dfs(TreeNode* root,int &res,int current){
        if(root==nullptr)return;
        current=current*10+root->val;
        if(root->left==nullptr&&root->right==nullptr){
            res+=current;
            return;
        }
        dfs(root->left,res,current);
        dfs(root->right,res,current);
    }
    int sumNumbers(TreeNode* root) {
        int res=0;
        dfs(root,res,0);
        return res;
    }
};
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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func dfs(root *TreeNode,current int,res *int){
    if root==nil{
        return
    }
    current=current*10+root.Val
    if root.Left==nil &&root.Right==nil{
        *res+=current
        return
    }
    dfs(root.Left,current,res)
    dfs(root.Right,current,res)
}
func sumNumbers(root *TreeNode) int {
    res:=0
    dfs(root,0,&res)
    return res
}

633. 平方数之和

date:2024-11-4 tag:双指针

题解

假设left<=right,初始化left=0,right=$\sqrt{c}$

  • $left^2$$+$$right^2$=c,找到结果返回true
  • $left^2$$+$$right^2$>c,减少右边界
  • $left^2$$+$$right^2$<c,增加左边界

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool judgeSquareSum(int c) {
        long left=0,right=(int)sqrt(c);
        while(left<=right){
            long sum=left*left+right*right;
            if(sum==c)return true;
            else if(sum<c){
                left++;
            }
            else{
                right--;
            }

        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func judgeSquareSum(c int) bool {
    left,right:=0,int(math.Sqrt(float64(c)))
    for left<=right{
        sum:=left*left+right*right
        if sum==c{
            return true
        }else if sum>c{
            right--
        }else {
            left++
        }

        
    }
    return false
}

3222. 求出硬币游戏的赢家

date:2024-11-5

题解

bool isAliceturn表示现在需要Alice操作，没有改变状态表示Alice失败，Bob胜利，否则为Bob,
需要拿出总值为115的硬币，实际固定需要1枚75，4枚10。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string losingPlayer(int x, int y) {
        bool isAliceturn=true;
        while(x>=1&&y>=4){
            isAliceturn=!isAliceturn;
            x-=1;
            y-=4;
        }
        return isAliceturn?"Bob":"Alice";
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
func losingPlayer(x int, y int) string {
    isAliceturn:=true
    for x>=1&&y>=4{
        isAliceturn=!isAliceturn
        x-=1
        y-=4
    }
    if(isAliceturn){
        return "Bob"
    }
    return "Alice"
}

3254. 长度为 K 的子数组的能量值 I

date:2024-11-6 tag:数组

题解

初始化result数组存放结果，外循环遍历长度为k的子数组，用isincreating表示数组是否递增，
内循环遍历子数组，j=i+1便于比较nums[j]-nums[j-1]!=1是否递增，不至于越界，返回外循环，以iscreaing的值得出题目中的能量值。
nums.begin()+i,nums.begin()+i+k

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int>result;
        for(int i=0;i<=n-k;++i){
            bool isincreaing=true;
            for(int j=i+1;j<i+k;++j){
                if(nums[j]-nums[j-1]!=1){
                    isincreaing=false;
                    break;
                }
            }
            if(isincreaing){
                result.push_back(*max_element(nums.begin()+i,nums.begin()+i+k));
            }else{
                result.push_back(-1);
            }
        }
        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
func findMax(nums []int) int {
	maxElem := nums[0]
	for _, num := range nums {
		if num > maxElem {
			maxElem = num
		}
	}
	return maxElem
}
func resultsArray(nums []int, k int) []int {
    n:=len(nums);
    result:=[]int{}
    for i:=0;i<=n-k;i++{
        isIncreaing:=true
        for j:=i+1;j<i+k;j++{
            if nums[j]-nums[j-1]!=1{
                isIncreaing=false
                break
            }
        }
        if isIncreaing{
            maxNumber:=findMax(nums[i:i+k])
            result=append(result,maxNumber)
        }else{
            result=append(result,-1)
        }
    }
    return result
}

3255. 长度为 K 的子数组的能量值 II

date:2024-11-7 tag:滑动窗口

题解

这道题和前一道题相同，但是nums的大小提升导致不能for循环里面嵌套循环了，会超时。
直接在nums数组中找到连续上升的个数，表示为cnt,结果数组res大小为n-k+1,
遍历nums,初始化cnt为0，i=0或nums[i]-nums[i-1]==1表示连续上升，增加cnt的值，否则为1
如果发现 cnt≥k，那么下标从 i−k+1 到 i 的这个子数组的能量值为 nums[i]，即 ans[i−k+1]=nums[i]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int>res(n-k+1,-1);
        int cnt=0;
        for(int i=0;i<n;++i){
            if(i==0)cnt++;
            else if(nums[i]-nums[i-1]==1)cnt++;
            else cnt=1;
            if(cnt>=k){
                res[i-k+1]=nums[i];
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func resultsArray(nums []int, k int) []int {
    res:=make([]int,len(nums)-k+1)
    for i:=range res{
        res[i]=-1
    }
    cnt:=0
    for i,cur:=range nums{
        if i==0||cur==nums[i-1]+1{
            cnt++
        }else {
            cnt=1
        }
        if cnt>=k{
            res[i-k+1]=cur
        }
    }
    return res
}

394. 字符串解码

date:2024-11-8 tag:栈

题解

变量声明：使用 countStack 和 stringStack 作为堆栈，分别保存计数和字符串部分。
循环解析字符串：通过 for 循环遍历字符串 s 的每个字符：
若字符为数字（0-9），构造 k 的值。
遇到 ‘[‘ 时，将 k 和 current 推入堆栈，并重置它们。
遇到 ‘]’ 时，从堆栈中弹出计数并重复 current，再将结果组合到之前的字符串。
其他字符则直接添加到 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
func decodeString(s string) string {
    count:=[]int{}
    stackString:=[]string{}
    current:=""
    k:=0
    for _,c:=range s{
        if c>='0'&&c<='9'{
            num,_:=strconv.Atoi(string(c))
            k=k*10+num
        }else if c=='['{
            count=append(count,k)
            stackString=append(stackString,current)
            k=0
            current=""
        }else if c==']'{
            repeatCount:=count[len(count)-1]
            count=count[:len(count)-1]
            decodedString:=stackString[len(stackString)-1]
            stackString=stackString[:len(stackString)-1]
            decodedString+=strings.Repeat(current,repeatCount)
            current=decodedString
        }else{
            current+=string(c)
        }
    }
    return 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
class Solution {
public:
    string decodeString(string s) {
        stack<int>count;
        stack<string>stackString;
        string current;
        int k=0;
        for(char c:s){
            if(isdigit(c)){
                k=k*10+(c-'0');
            }else if(c=='['){
                count.push(k);
                stackString.push(current);
                k=0;
                current.clear();
            }else if(c==']'){
                int reaptedCount=count.top();count.pop();
                string decodedString=stackString.top();stackString.pop();
                while(reaptedCount-->0){
                    decodedString+=current;
                }
                current=decodedString;
            }else{
                current+=c;
            }
        }
        return current;
    }
};

128. 最长连续序列

date:2024-11-8 tag:哈希表

题解

将数组存入哈希表中，便于快速查找，
遍历哈希表元素，如果未找到元素setNum-1表示其不在集合中，更新序列起点，和当前的长度。
从当前setNum开始，检查setNum+1,setNum+2是否在集合中，记录当前连续序列的长度currenLength.
最后更新最大长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int>set(nums.begin(),nums.end());
        int longestLength=0;
        for(int setNum:set){
            if(!set.count(setNum-1)){
                int currentNum=setNum;
                int currentLength=1;
                while(set.count(currentNum+1)){
                    currentLength+=1;
                    currentNum+=1;
                }
                longestLength=max(longestLength,currentLength);
            }
        }
        return longestLength;
    }
};
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
func longestConsecutive(nums []int) int {
    set:=make(map[int]bool)//模拟set哈希表
    longestLength:=0
    for _,num:= range nums{//将nums遍历进入set中
        set[num]=true
    }
    for num:= range set{
        if _,exists:=set[num-1];!exists{//判断哈希表中num-1是否存在，否则重新计算连续序列
            currentLength:=1;
            currentNum:=num
            for{
                if _,exists:=set[currentNum+1];exists{
                    currentLength+=1;
                    currentNum+=1;
                }else{
                    break
                }
            }
            if currentLength>longestLength {//更新最大长度
                longestLength=currentLength
            } 
        }
    }
    return longestLength
}

3242. 设计相邻元素求和服务

date:2024-11-9 tag:哈希表

题解

用hashmap存放二维数组的值和值在数组所在的位置，
用direction存放元素相邻移动和对角线移动位置的变化
根据哈希表找到元素值所在的位置，通过遍历direction访问邻居和对角线元素。

代码

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
51
52
53
54
class NeighborSum {
private:
    vector<vector<int>>grid;
    unordered_map<int,pair<int,int>>pos;

public:
    NeighborSum(vector<vector<int>>& grid) :grid(grid){
        int n=grid.size();
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                pos[grid[i][j]]={i,j};
            }
        }
    }
    
    int adjacentSum(int value) {
        if(pos.find(value)==pos.end())return 0;
        int sum=0;
        int x=pos[value].first;
        int y=pos[value].second;
        vector<pair<int,int>>dir{{1,0},{-1,0},{0,1},{0,-1}};
        for(auto d:dir){
            int dx=x+d.first;
            int dy=y+d.second;
            if(dx>=0&&dx<grid.size()&&dy>=0&&dy<grid.size()){
                sum+=grid[dx][dy];
            }
        }
        return sum;
    }
    
    int diagonalSum(int value) {
        if(pos.find(value)==pos.end())return 0;
        int sum=0;
        int x=pos[value].first;
        int y=pos[value].second;
        vector<pair<int,int>>dir{{-1,-1},{1,1},{1,-1},{-1,1}};
        for(auto d:dir){
            int dx=x+d.first;
            int dy=y+d.second;
            if(dx>=0&&dx<grid.size()&&dy>=0&&dy<grid.size()){
                sum+=grid[dx][dy];
            }
        }
        return sum;
    }
};

/**
 * Your NeighborSum object will be instantiated and called as such:
 * NeighborSum* obj = new NeighborSum(grid);
 * int param_1 = obj->adjacentSum(value);
 * int param_2 = obj->diagonalSum(value);
 */
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
51
52
53
54
55
56
57
58
59
60
 type NeighborSum struct {
    grid          [][]int
    valuePosition map[int][2]int // 用于存储每个值的位置
}

// Constructor 初始化 NeighborSum 结构体
func Constructor(grid [][]int) NeighborSum {
    valuePosition := make(map[int][2]int)
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            valuePosition[grid[i][j]] = [2]int{i, j}
        }
    }
    return NeighborSum{
        grid:          grid,
        valuePosition: valuePosition,
    }
}

// AdjacentSum 计算给定值的相邻位置的和
func (this *NeighborSum) AdjacentSum(value int) int {
    pos, exists := this.valuePosition[value]
    if !exists {
        return 0
    }

    x, y := pos[0], pos[1]
    sum := 0
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上、下、左、右

    for _, dir := range directions {
        nx, ny := x+dir[0], y+dir[1]
        if nx >= 0 && nx < len(this.grid) && ny >= 0 && ny < len(this.grid[0]) {
            sum += this.grid[nx][ny]
        }
    }

    return sum
}

// DiagonalSum 计算给定值的对角线位置的和
func (this *NeighborSum) DiagonalSum(value int) int {
    pos, exists := this.valuePosition[value]
    if !exists {
        return 0
    }

    x, y := pos[0], pos[1]
    sum := 0
    diagonals := [][2]int{{-1, -1}, {-1, 1}, {1, -1}, {1, 1}} // 四个对角方向

    for _, diag := range diagonals {
        nx, ny := x+diag[0], y+diag[1]
        if nx >= 0 && nx < len(this.grid) && ny >= 0 && ny < len(this.grid[0]) {
            sum += this.grid[nx][ny]
        }
    }

    return sum
}

540. 有序数组中的单一元素

date:2024-11-10 tag:二分查找

题解

此题用二分查找解题，初始化左右边界left和right,用nums[mid]表示中间元素，nums[mid^1]表示邻居元素。
nums[mid]==nums[mid^1]说明有值相同的邻居元素，单独的元素在右半部分，left=mid+1更改左边界
否则更改右边界，right=mid;
^为异或运算，对于两个二进制位，如果它们相同则结果是 0，如果它们不同则结果是 1。
mid ^ 1 的作用：实际上是将 mid 的最低有效位（即最后一位）取反：

如果 mid 是 偶数，最低有效位是 0，则 mid ^ 1 会使最低有效位变为 1，结果是 mid + 1。
如果 mid 是 奇数，最低有效位是 1，则 mid ^ 1 会使最低有效位变为 0，结果是 mid - 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]==nums[mid^1]){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return nums[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
func singleNonDuplicate(nums []int) int {
    left,right:=0,len(nums)-1
    for left<right{
        mid:=left+(right-left)/2
        if nums[mid]==nums[mid^1]{
            left=mid+1
        }else{
            right=mid;
        }
    }
    return nums[left]
}

98. 验证二叉搜索树

date:2024-11-10 tag:二叉树

题解

向左子树遍历时，把当前的val设为最大边界，右子树遍历时，将当前的val设为最小边界。
向下遍历时，超过无论是最大还是最小边界都不是二叉搜索树，返回false
结束条件,root为空表示没有超出边界过，返回true
用maxVal和minVal确保初始化不会超出边界。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidFunc(root *TreeNode,minVal,maxVal int)bool{
    if root==nil{
        return true
    }
    if root.Val>=maxVal||root.Val<=minVal{
        return false
    }
    return isValidFunc(root.Left,minVal,root.Val)&&isValidFunc(root.Right,root.Val,maxVal)
}
func isValidBST(root *TreeNode) bool {
    return isValidFunc(root,math.MinInt64,math.MaxInt64)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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:
    bool isValidfunc(TreeNode* root,long long minVal,long long maxVal){
        if(root==nullptr)return true;
        if(root->val<=minVal||root->val>=maxVal)return false;
        return isValidfunc(root->left,minVal,root->val)&&isValidfunc(root->right,root->val,maxVal);
    }
    bool isValidBST(TreeNode* root) {
        return isValidfunc(root,LONG_MIN,LONG_MAX);
    }
};

1547. 切棍子的最小成本

date:2024-11-11 tag:动态规划

题解

定义 dp[i][j] 表示将木棍区间 [i, j] 之间的部分切割成若干段的最小总成本。
dp[0][n] 是最终答案，表示整个木棍的最小切割成本。
len 表示区间的长度，i 是区间的左端点，j 是区间的右端点。
对于每一个区间 [i, j]，我们遍历其中的每一个中间切割点 k，并计算出最小的切割成本。
更新 dp[i][j] 为每次切割的最小成本。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0);
        cuts.push_back(n);
        sort(cuts.begin(),cuts.end());
        int m=cuts.size();
        vector<vector<int>>dp(m,vector<int>(m,0));
        for(int len=2;len<m;++len){
            for(int i=0;i<m-len;++i){
                int j=i+len;
                dp[i][j]=INT_MAX;
                for(int k=i+1;k<j;++k){
                    dp[i][j]=min(dp[i][j], dp[i][k] + dp[k][j] + (cuts[j] - cuts[i]));
                }
            }
        }
        return dp[0][m-1];
    }
};
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
func minCost(n int, cuts []int) int {
    // 将0和n添加到cuts数组中，以方便处理边界
    cuts = append(cuts, 0)
    cuts = append(cuts, n)
    
    // 对cuts数组排序
    sort.Ints(cuts)
    
    m := len(cuts)
    
    // dp[i][j]表示切割区间[i, j]的最小成本
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, m)
    }
    
    // 从小区间开始计算
    for length := 2; length < m; length++ { // length表示区间的长度
        for i := 0; i < m-length; i++ {
            j := i + length
            dp[i][j] = math.MaxInt32 // 初始化为最大值
            
            // 遍历区间中的每个切割点k，选择最小成本
            for k := i + 1; k < j; k++ {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + (cuts[j] - cuts[i]))
            }
        }
    }
    
    return dp[0][m-1] // 结果是切割区间[0, m-1]的最小成本
}

139. 单词拆分

date:2024-11-12 tag:哈希表 动态规划

题解

用哈希表存储字典中的单词，便于查找。
动态规划初始化vectordp(s.size()+1,false),dp[0]=true
遍历字符串s,对于一个位置i，遍历不大于i的j,看是否存在dp[j]且在哈希表中找到set[s[j:i]]存在，将位置i为true,退出子循环。set.count(s.substr(j,i-j))
结果为dp[n]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> set(wordDict.begin(),wordDict.end());
        int n=s.size();
        vector<bool>dp(n+1,false);
        dp[0]=true;
        for(int i=1;i<=n;++i){
            for(int j=0;j<i;++j){
                if(dp[j]&&set.count(s.substr(j,i-j))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func wordBreak(s string, wordDict []string) bool {
    set:=make(map[string]bool)
    for _,val:=range wordDict{
        set[val]=true
    }
    n:=len(s)
    dp:=make([]bool,n+1)
    dp[0]=true
    for i:=1;i<=n;i++{
        for j:=0;j<i;j++{
            if dp[j]&&set[s[j:i]]{
                dp[i]=true
                break
            }
        }
    }
    return dp[n]
}

3258. 统计满足 K 约束的子字符串数量 I

date:2024-11-13

题解

用大小为2的数组存放当前字符串中0和1的数量，遍历字符串，用数组存放子字符串的0和1数目，每次更新判断是否超过k，退出循环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int n=s.size();
        int res=0;
        for(int i=0;i<n;++i){
            int count[2]={0};
            for(int j=i;j<n;++j){
                count[s[j]-'0']++;
                if(count[0]>k&&count[1]>k){
                    break;
                }
                res++;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func countKConstraintSubstrings(s string, k int) int {
    n:=len(s)
    res:=0
    for i:=0;i<n;i++{
        count:=[2]int{}
        for j:=i;j<n;j++{
            count[s[j]-'0']++
            if count[0]>k&&count[1]>k{
                break
            }
            res++
        }
    }
    return res
}

49. 字母异位词分组

date:2024-11-14 tag:哈希表

题解

用hashMap解题，对每个字符串，将排序好的字符串作为key,排序后和key相同的字符串作为val.
然后遍历hashmap的key，将哈希表的所有val加入到字符串数组result中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string,vector<string>>hashMap;
        for(auto str:strs){
            string temp=str;
            sort(temp.begin(),temp.end());
            hashMap[temp].push_back(str);
        }
        vector<vector<string>>result;
        for(auto sortMap:hashMap){
            result.push_back(sortMap.second);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func groupAnagrams(strs []string) [][]string {
    hashMap:=make(map[string][]string)
    for _,str:=range strs{
        chars:=strings.Split(str,"")//字符串转化成字符切片，按照空字符串 "" 分割，得到一个字符切片
        sort.Strings(chars)//排序字符切片
        key:=strings.Join(chars,"")//字符切片转化成字符串
        hashMap[key]=append(hashMap[key],str)
    }
    result:=make([][]string,0,len(hashMap))
    for _,val:=range hashMap{
        result=append(result,val)
    }
    return result
}

3239. 最少翻转次数使二进制矩阵回文 I

date:2024-11-15 tag:数组

题解

对于每一行 row，计算这一行变成回文最少需要翻转多少次。
对于行，计算grid[i][j]!=grid[i][n-1-j]的次数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int countRow=0,countVol=0;
        for(int i=0;i<m;++i){
            for(int j=0;j<n/2;j++){
                countRow+=grid[i][j]!=grid[i][n-1-j];
            }
        }
        for(int j=0;j<n;j++){
            for(int i=0;i<m/2;i++){
                countVol+=grid[i][j]!=grid[m - 1 - i][j];
            }
        }
        return min(countRow,countVol);
    }
};

240. 最少翻转次数使二进制矩阵回文 II

date:2024-11-16 tag:数组

题解

见代码

代码

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
51
52
53
54
55
56
57
class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;

        //  检查四个对称点，确保回文
        for (int i = 0; i < m / 2; ++i) {
            for (int j = 0; j < n / 2; ++j) {
                // 统计四个对称点的 1 的数量
                int cnt1 = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j];
                // 最小翻转次数：使这四个点全为 1 或全为 0
                ans += min(cnt1, 4 - cnt1);
            }
        }

        //  处理中心点（当矩阵行和列都是奇数时）
        if (m % 2 && n % 2) {
            // 中心点位于 (m / 2, n / 2)，必须是回文，所以它只能为 0
            ans += grid[m / 2][n / 2];
        }

         //处理中间行（如果行数是奇数）
        int diff = 0, cnt1 = 0;
        if (m % 2) {
            for (int j = 0; j < n / 2; ++j) {
                int left = grid[m / 2][j];
                int right = grid[m / 2][n - 1 - j];
                if (left != right) {
                    // 如果对称点不同，翻转一个即可
                    diff++;
                } else {
                    // 如果对称点相同，统计 1 的数量
                    cnt1 += left * 2;
                }
            }
        }

         //处理中间列（如果列数是奇数）
        if (n % 2) {
            for (int i = 0; i < m / 2; ++i) {
                int top = grid[i][n / 2];
                int bottom = grid[m - 1 - i][n / 2];
                if (top != bottom) {
                    // 如果对称点不同，翻转一个即可
                    diff++;
                } else {
                    // 如果对称点相同，统计 1 的数量
                    cnt1 += top * 2;
                }
            }
        }

        //  处理额外的约束：1 的总数必须是 4 的倍数
        return ans + (diff > 0 ? diff : cnt1 % 4);
    }
};

825. 适龄的朋友

date:2024-11-17 tag:双指针

题解

题目的三个条件可以看成：

  1. 不向小于15岁的发
  2. 不向年龄小于自己的发
    将ages数组排序，定义x,y为互发请求的范围。
    x为第一个>=15的排序ages下标
    y为第一个大于当前遍历数age的下标

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int res=0;
        int x=0,y=0,n=ages.size();
        sort(ages.begin(),ages.end());
        for(auto age:ages){
            if(age<=14){
                continue;
            }
            while(ages[x]<=0.5*age+7){//第一个年龄大于14的用户
                x++;
            }
            while(y+1<n&&ages[y+1]<=age){//第一个大于age的位置
                y++;
            }
            res+=y-x;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func numFriendRequests(ages []int) int {
    x,y,n:=0,0,len(ages)
    res:=0
    sort.Ints(ages)
    for _,age:=range ages{
        if age<=14{
            continue
        }
        for ages[x]*2<=age+14{
            x++
        }
        for y+1<n&&age>=ages[y+1]{
            y++
        }
        res+=y-x
    }
    return res
}

661. 图片平滑器

date:2024-11-18 tag:数组

题解

用一个二维数组dirs来存放一个点位可以移动的位置，cnt表示四周元素的个数，sum表示四周元素的和
遍历img数组，对于一个位置img[i][j]遍历dirs数组看四周的数是否存在。增加cnt的值，修改sum的值
修改res[i][j]

代码

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:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m = img.size(), n = img[0].size();
        vector<vector<int>> dirs{{1, 0},   {-1, 0}, {0, -1}, {0, 1},
                                 {-1, -1}, {1, -1}, {-1, 1}, {1, 1}};
        vector<vector<int>> res(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int cnt = 1, sum = img[i][j];
                for (auto dir : dirs) {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    if (x < m && x >= 0 && y < n && y >= 0) {
                        cnt++;
                        sum += img[x][y];
                    }
                }
                res[i][j] = sum / cnt;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func imageSmoother(img [][]int) [][]int {
	m, n := len(img), len(img[0])
	dirs := [][]int{{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}}
    res := make([][]int, m)
    for i := range res {
        res[i] = make([]int, n)
    }
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			cnt, sum := 1, img[i][j]
			for _, dir := range dirs {
				x, y := i+dir[0], j+dir[1]
				if x >= 0 && x < m && y >= 0 && y < n {
					cnt++
					sum += img[x][y]
				}
			}
			res[i][j] = sum / cnt
		}
	}
	return res
}

3243. 新增道路查询后的最短距离 I

date:2024-11-19 tag:bfs

题解

初始化邻接表，每次增加道路时，需要加入到邻接表中。
遍历道路，每次增加道路，将道路加入到邻接表中。
广度优先搜索邻接表，找出到达n-1的距离

代码

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
class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n,
                                             vector<vector<int>>& queries) {
        vector<vector<int>> neighbors(n);
        for (int i = 0; i < n - 1; ++i) {
            neighbors[i].push_back(i + 1);
        }
        vector<int>res;
        for(auto querie:queries){
            neighbors[querie[0]].push_back(querie[1]);
            res.push_back(bfs(n,neighbors));
        }
        return res;
    }
    int bfs(int n,const vector<vector<int>>&neighbors){
        vector<bool>visited(n,false);//判断位置是否遍历过
        visited[0]=true;
        queue<pair<int,int>>q;//存放当前遍历的位置和走过的距离
        q.push({0,0});
        while(!q.empty()){
            auto [node,distance]=q.front();
            q.pop();
            if(node==n-1){
                return distance;
            }
            for(int neighbor:neighbors[node]){
                if(!visited[neighbor]){
                    visited[neighbor]=true;
                    q.push({neighbor,distance+1});
                }
            }
        }
        return -1;
    }
};

42. 接雨水

date:2024-11-20 tag:双指针

题解

使用left,right表示位置，初始化分别为0和len(height)，maxLeft, maxRight表示目前位置
当两个指针未相遇时，每次更新maxLeft和maxRigh.
当height[left]<height[right]时必有maxLeft<maxRight
maxLeft-height[left]表示当前格子接到的雨水。
同理maxRight-height[right]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int left=0,right=height.size()-1;
        int maxLeft=0,maxRight=0;
        int res=0;
        while(left<right){
            maxLeft=max(maxLeft,height[left]);
            maxRight=max(maxRight,height[right]);
            if(height[left]<height[right]){
                res+=maxLeft-height[left];
                left++;
            }else{
                res+=maxRight-height[right];
                right--;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func trap(height []int) int {
    res:=0
    left,right:=0,len(height)-1
    maxLeft,maxRight:=0,0
    for left<right{
        maxLeft=max(maxLeft,height[left])
        maxRight=max(maxRight,height[right])
        if height[left]<height[right]{
            res+=maxLeft-height[left]
            left++
        }else{
            res+=maxRight-height[right]
            right--
        }
    }
    return res
}
func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

3248. 矩阵中的蛇

date:2024-11-21 tag:

题解

无

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int finalPositionOfSnake(int n, vector<string>& commands) {
        int x=0,y=0;
        for(const auto &command:commands){
            switch (command[0]){
                case 'U':x--;break;
                case 'D':x++;break;
                case 'L':y--;break;
                case 'R':y++;break;
            }
        }
        return x*n+y;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func finalPositionOfSnake(n int, commands []string) int {
    x,y:=0,0
    for _,command:=range commands{
        switch command{
            case "UP":
                x--
            case "DOWN":
                x++
            case "RIGHT":
                y++
            case "LEFT":
                y--
        }
    }
    return x*n+y
}

3233. 统计不是特殊数字的数字数量

date:2024-11-22

题解

只有两个真因数，且不包括自己，说明只有1和平方数。
[1,$\sqrt{2}$]的范围内遍历所有质数，将平方从[l,r]范围内去除。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int nonSpecialCount(int l, int r) {
        int n = sqrt(r);
        vector<int> v(n + 1);
        int res = r - l + 1;
        for (int i = 2; i <= n; i++) {
            if (v[i] == 0) {
                if (i * i >= l && i * i <= r) {
                    res--;
                }
                for (int j = i * 2; j <= n; j += i) {
                    v[j] = 1;
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func nonSpecialCount(l int, r int) int {
    n:=int(math.Sqrt(float64(r)))
    res:=r-l+1
    v:=make([]int,n+1)
    for i:=2;i<=n;i++{
        if v[i]==0{
            if i*i>=l&&i*i<=r{
                res--
            }
            for j:=i*2;j<=n;j+=i{
                v[j]=1
            }
        }
    }
    return res
}