头像

小呆呆

墨染空粉丝团




在线 


活动打卡代码 LeetCode 377. 组合总和 Ⅳ

小呆呆
18天前

状态表示
f[i][j]:所有从前i个位置中选,且总体积恰好是j的所有方案

状态计算
f[i][j] = f[i][j] + f[i - 1][j - a(k)]
由于最多可以选i个位置,因此i1枚举到m
由于最大体积是j,因此j0枚举到m
由于第i个位置可以选a(k)k0枚举到n,即nums[k]

结果:f[1][m] + f[2][m] + ... f[m][m]

class Solution {
    static int mod = Integer.MAX_VALUE;
    public int combinationSum4(int[] nums, int m) {
        int n = nums.length;
        long[][] f = new long[m + 1][m + 1];
        f[0][0] = 1;
        long res = 0;
        for(int i = 1;i <= m;i ++)
        {
            for(int j = 0;j <= m;j ++)
            {
                for(int k = 0;k < n;k ++)
                {
                    if(j >= nums[k])
                        f[i][j] = (f[i][j] + f[i - 1][j - nums[k]]) % mod;
                }
            }
            res = (res + f[i][m]) % mod;
        }

        return (int)res;
    }
}


活动打卡代码 AcWing 2816. 判断子序列

小呆呆
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i ++) cin >> a[i];
    for(int i = 0;i < m;i ++) cin >> b[i];
    int i = 0, j = 0;
    while(i < n && j < m)
    {
        if(a[i] == b[j]) i ++;
        j ++;
    }
    if(i == n) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



小呆呆
1个月前

题目描述

给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] = [ui, vi] ,表示 ui 和 vi 之间有一条无向边。

一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。

连通三元组的度数 是所有满足此条件的边的数目:一个顶点在三元组内,而另一个顶点不在三元组内。

请你返回所有连通三元组中度数的 最小值 ,如果图中没有连通三元组,那么返回 -1 。

样例

trios1.png

输入:n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
输出:3
解释:只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。

trios2.png

输入:n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
输出:0
解释:有 3 个三元组:
1) [1,4,3],度数为 0 。
2) [2,5,6],度数为 2 。
3) [5,6,7],度数为 2 。

算法分析

119ac458ecd98d43f733f28e3549d0f.png

  • 1、题目求的东西,找出图中的所有连通三元组,如上所示是其中一个,计算出连通三元组的最小度数,即除了内部的边以外,其他外部相连的边的总和,图中与a点相连的额外边数是2,与b点相连的额外边数是3,与c点相连的额外边数是2,因此该连通三元组的度数是2 + 3 + 2 = 7
  • 2、如何快速计算出连通三元组的度数,统计出每个点与它相连的边数,如图中所示d[a] = 4,d[b] = 5,d[c] = 4,连通三元组内部有3条边,每条边的贡献值是2,即共使用了6次,可以直接该连通三元组的度数是d[a] + d[b] + d[c] - 6
  • 3、知道原理后,使用邻接矩阵建图,g[a][b] = true表示a可以到达b,统计出所有点的度数d[x],最后3重循环枚举所有3元组,如这3个点是连通的,则调用2中的公式更新连通三元组的最小度数

时间复杂度 $O(n^3)$

C++ 代码

const int N = 410;
bool g[N][N];
int d[N];
class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        memset(g, 0, sizeof g);
        memset(d, 0, sizeof d);
        for(auto& p : edges)
        {
            int a = p[0], b = p[1];
            g[a][b] = g[b][a] = true;
            d[a] ++, d[b] ++;
        }
        int res = INT_MAX;
        for(int i = 1;i <= n;i ++)
            for(int j = i + 1;j <= n;j ++)
                if(g[i][j])
                    for(int k = j + 1;k <= n;k ++)
                        if(g[i][k] && g[j][k])
                            res = min(res, d[i] + d[j] + d[k] - 6);
        if(res == INT_MAX) res = -1;
        return res;
    }
};



小呆呆
1个月前

题目描述

给你一个整数数组 nums ,其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次:

  • 选择任意一个袋子,并将袋子里的球分到 2 个新的袋子中,每个袋子里都有 正整数 个球。
    • 比方说,一个袋子里有 5 个球,你可以把它们分到两个新袋子里,分别有 1 个和 4 个球,或者分别有 2 个和 3 个球。
      你的开销是单个袋子里球数目的 最大值 ,你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

样例

输入:nums = [9], maxOperations = 2
输出:3
解释:
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球,所以开销为 3 并返回 3 。
输入:nums = [2,4,8,2], maxOperations = 4
输出:2
解释:
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球,所以开销为 2 并返回 2 。
输入:nums = [7,17], maxOperations = 2
输出:7

提示:

1 <= nums.length <= 10^5
1 <= maxOperations, nums[i] <= 10^9


算法分析

引理(分数的上取整转换下取整)

2020-04-15_182406.jpg

二分

  • 1、对于题目意思,对于每个袋子的球,可以分到 2 个新的袋子中,每个袋子里都有 正整数 个球。题目要求求的是所有袋子中,单个袋子里球的数目的最大值的最小值
  • 2、通过二分法计算出单个袋子里球的数目的最大值的最小值,若给定单个袋子的数目的最大值是x,且当前袋子的数目是k,可以将k分成$\lceil \frac{k}{x} \rceil$份,即需要操作$res = \lceil \frac{k}{x} \rceil - 1$ 份,若res <= m表示满足条件

时间复杂度 $O(nlogC)$

nnum数组的长度,C是值大小

C++ 代码

class Solution {
public:
    bool check(vector<int> &nums, int m, int x)
    {
        int res = 0;
        for(int k : nums)
        {
            res = res + (k + x - 1) / x - 1;
        }
        return res <= m;
    }
    int minimumSize(vector<int>& nums, int m) {
        //求所有袋子中,单个袋子里球的数目的最大值的最小值
        int l = 1, r = 1e9;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(nums, m, mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};



小呆呆
1个月前

题目描述

给你一个字符串 s ,返回 s同构子字符串 的数目。由于答案可能很大,只需返回对 10^9 + 7 取余 后的结果。

同构字符串 的定义为:如果一个字符串中的所有字符都相同,那么该字符串就是同构字符串。

子字符串 是字符串中的一个连续字符序列。

样例

输入:s = "abbcccaa"
输出:13
解释:同构子字符串如下所列:
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13
输入:s = "xy"
输出:2
解释:同构子字符串是 "x" 和 "y" 。
输入:s = "zzzzz"
输出:15

提示:

  • 1 <= s.length <= 10^5
  • s 由小写字符串组成

算法分析

双指针

  • 1、可以发现,对于某个子字符串aaaaa...na的连串,一共有(1 + n) * n / 2个同构子字符串
  • 2、通过双指针算法,截取出每一段相同符号的连续字符,累加到res即可

时间复杂度 $O(n)$

C++ 代码

const int mod = 1000000000 + 7;
typedef long long LL;
class Solution {
public:
    LL get(int x)
    {
        return (LL)(1 + x) * x / 2;
    }
    int countHomogenous(string s) {
        int n = s.size();
        LL res = 0;
        for(int i = 0;i < n;i ++)
        {
            int j = i;
            while(j < n && s[j] == s[i]) j ++;
            res = (res + get(j - i)) % mod;
            i = j - 1;
        }
        return res;
    }
};



小呆呆
1个月前

题目描述

给你一个仅由字符 '0''1' 组成的字符串 s 。一步操作中,你可以将任一 '0' 变成 '1' ,或者将 '1' 变成 '0'

交替字符串 定义为:如果字符串中不存在相邻两个字符相等的情况,那么该字符串就是交替字符串。例如,字符串 "010" 是交替字符串,而字符串 "0100" 不是。

返回使 s 变成 交替字符串 所需的 最少 操作数。

样例

输入:s = "0100"
输出:1
解释:如果将最后一个字符变为 '1' ,s 就变成 "0101" ,即符合交替字符串定义。
输入:s = "10"
输出:0
解释:s 已经是交替字符串。
输入:s = "1111"
输出:2
解释:需要 2 步操作得到 "0101" 或 "1010" 。

提示:

  • 1 <= s.length <= 10^4
  • s[i]'0''1'

算法分析

  • 1、最终结果只有两种,分别是
    情况1:01010…
    情况2:10101…

  • 2、分别计算出变成情况1 和 变成情况2 各自需要多少操作数,取最小值即可

时间复杂度 $O(n)$

C++ 代码

class Solution {
public:
    int minOperations(string s) {
        int n = s.size();
        int a = 0, b = 0;
        for(int i = 0;i < n;i ++)
        {
            if(i % 2 == 0) {
                if(s[i] == '1') a ++;
                else b ++;
            } else {
                if(s[i] == '0') a ++;
                else b ++;
            }
        }
        return min(a, b);
    }
};


新鲜事 原文

小呆呆
2个月前
祝各位新年快乐,学业进步hh


活动打卡代码 AcWing 1371. 货币系统

小呆呆
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100000 + 10;
int n, m;
long long f[N];
int main()
{
    cin >> n >> m;
    f[0] = 1;
    for(int i = 0;i < n;i ++)
    {
        int x;
        cin >> x;
        for(int j = x;j <= m;j ++)
            f[j] += f[j - x];
    }
    cout << f[m] << endl;

    return 0;

}


活动打卡代码 AcWing 1432. 棋盘挑战

小呆呆
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;
int n;
int col[N], dg[N * 2], udg[N * 2]; 
int ans = 0;
int path[N];
void dfs(int y)
{
    if(y >= n)
    {
        ans ++;
        if(ans <= 3)
        {
            for(int i = 0;i < n;i ++)
            {
                cout << path[i] << " ";
            } 
            cout << endl;
        }
        return ;
    }

    for(int x = 0;x < n;x ++)
    {
        if(!col[x] && !dg[y - x + n] && !udg[x + y])
        {
            path[y] = x + 1;
            col[x] = dg[y - x + n] = udg[x + y] = true;
            dfs(y + 1);
            col[x] = dg[y - x + n] = udg[x + y] = false;
            path[y] = 0;
        }
    }
}
int main()
{
    cin >> n;
    dfs(0);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 754. 平方矩阵 II

小呆呆
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n;
int a[N][N];
int main()
{
    while(true)
    {
        cin >> n;
        if(n == 0) break;

        for(int i = 1;i <= n;i ++)
            for(int j = i, k = 1;j <= n;j ++, k ++)
            {
                a[i][j] = k;
                a[j][i] = k;
            }

        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= n;j ++)
            cout << a[i][j] << " ";
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}