头像

bruce




在线 



bruce
3小时前
#include <iostream>
#include <vector>
using namespace std;

/**
 * 338 比特进位,给定一个整数n,从0-n之间的数字二进制位含有
 * 多少个1,输出到数组中即可
*/

/**
 * 方法 1,使用双指针,两重循环。时间复杂度高
*/
vector<int> countBits(int num)
{
    vector<int> res;
    for (int i = 0; i <= num; i++)
    {
        int k = i, bitnum = 0;
        while (k)
        {
            if (k & 1)
                bitnum++;
            k >>= 1;
        }
        res.push_back(bitnum);
    }
    return res;
}

/**
 * 方法 2,使用O(n)时间复杂度来做
 * 因为f[i] = f[i>>1] + i&1 的结果
*/
vector<int> countBits(int num)
{
    vector<int> f(num + 1);
    for (int i = 1; i <= num; i++)
    {
        f[i] = f[i >> 1] + (i & 1);
    }
    return f;
}



活动打卡代码 LeetCode 338. 比特位计数

bruce
3小时前
#include <iostream>
#include <vector>
using namespace std;

/**
 * 338 比特进位,给定一个整数n,从0-n之间的数字二进制位含有
 * 多少个1,输出到数组中即可
*/

/**
 * 方法 1,使用双指针,两重循环。时间复杂度高
*/
vector<int> countBits(int num)
{
    vector<int> res;
    for (int i = 0; i <= num; i++)
    {
        int k = i, bitnum = 0;
        while (k)
        {
            if (k & 1)
                bitnum++;
            k >>= 1;
        }
        res.push_back(bitnum);
    }
    return res;
}

/**
 * 方法 2,使用O(n)时间复杂度来做
 * 因为f[i] = f[i>>1] + i&1 的结果
*/
vector<int> countBits(int num)
{
    vector<int> f(num + 1);
    for (int i = 1; i <= num; i++)
    {
        f[i] = f[i >> 1] + (i & 1);
    }
    return f;
}



活动打卡代码 AcWing 282. 石子合并

bruce
19小时前
#include <iostream>
using namespace std;
/**
 * 282 石子合并,区间DP
*/
const int N = 310;
int f[N][N];
int n;
int s[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    for (int i = 1; i <= n; i++)
        s[i] += s[i - 1];

    // 先循环区间长度,然后再循环左右端点
    for (int len = 2; len <= n; len++) 
    {
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;
            for(int k = l; k<r;k++)
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);
            }
        }
    }
    cout<<f[1][n];
}


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

bruce
20小时前
#include <iostream>
using namespace std;

/**
 * 392 求两个字符串的是否是另一个的子序列
*/

/**
 * 方法 1,使用双指针算法来做
*/
class Solution
{
public:
    bool isSubsequence(string s, string t)
    {
        // 判断最长公共子序列
        if (s.size() > t.size())
            return false;
        int index1 = 0, index2 = 0;
        while (index2 < t.size())
        {
            if (s[index1] == t[index2])
            {
                index1++;
                index2++;
            }
            else
                index2++;
        }
        return index1 == s.size();
    }
};

/**
 * 方法 2,使用双指针算法来做,写法更加简洁
*/
bool isSubsequence(string s, string t)
{
    int k = 0;
    for (auto c : t)
    {
        if (s[k] == c)
            k++;
    }
    return k == s.size();
}




bruce
21小时前
// DP做法
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int>f(n);
        int k = 0;
        for(int i=0;i<n;i++)
        {   
            f[i] = 1;
            for(int j = 0;j<i;j++)
            {
                if(nums[j] < nums[i]) f[i] = max(f[i], f[j] + 1);
            }
            k = max(k, f[i]);
        }
        return k;
    }
};



bruce
1天前
#include <iostream>
#include <vector>
using namespace std;

/**
 * 70 爬楼梯
 * 给定一个整数n表示楼梯数,然后每次可以爬1格或者是2格
 * 最后计算n的所有种爬楼梯的方案数即可
 * 
*/

/**
 * 方法 1,使用递归来做,但是会超时
*/
int climbStairs(int n)
{
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

/**
 * 方法 2,使用动态规划来做,时间复杂度为O(n)
 * 状态f[i]表示第i节楼梯的所有方案的总和,那么它和i-1或者是i-2个楼梯方案
 * 总和有关系,所以利用状态方程进行计算即可
*/

int climbStairs2(int n)
{
    vector<int> f(n + 1);
    if (n < 2)
        return n;
    else
    {
        f[0] = 0, f[1] = 1, f[2] = 2;
    }

    for (int i = 3; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}

/**
 * 方法 3,数学归纳
 * n : 0  1  2  3  4  5  6.....
 * s : 1  1  2  3  5  8
*/
int climbStairs3(int n)
{
    int a = 0, b = 1, c = 0;
    while (n--)
    {
        c = a + b;
        a = b, b = c;
    }
    return c;
}



活动打卡代码 LeetCode 70. 爬楼梯

bruce
1天前
#include <iostream>
#include <vector>
using namespace std;

/**
 * 70 爬楼梯
 * 给定一个整数n表示楼梯数,然后每次可以爬1格或者是2格
 * 最后计算n的所有种爬楼梯的方案数即可
 * 
*/

/**
 * 方法 1,使用递归来做,但是会超时
*/
int climbStairs(int n)
{
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

/**
 * 方法 2,使用动态规划来做,时间复杂度为O(n)
 * 状态f[i]表示第i节楼梯的所有方案的总和,那么它和i-1或者是i-2个楼梯方案
 * 总和有关系,所以利用状态方程进行计算即可
*/

int climbStairs2(int n)
{
    vector<int> f(n + 1);
    if (n < 2)
        return n;
    else
    {
        f[0] = 0, f[1] = 1, f[2] = 2;
    }

        for (int i = 3; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}




bruce
1天前
class Solution {
public:
    int minimumTotal(vector<vector<int>>& f) {
        int n = f.size();
        for(int i=n-2; i>=0; i--)
        {
            for(int j = 0; j < i+1; j++)
            {
                f[i][j] = min(f[i+1][j], f[i+1][j+1]) + f[i][j];
            }
        }
        return f[0][0];

    }
};



bruce
1天前
#include<iostream>
using namespace std;

const int N = 1010;
int f[N], a[N];
int n;

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }

    for(int i = 1; i<=n;i++)
    {
        f[i] = 1; // 只有i是一个数
        for(int j = 1; j<i; j++)
        {
            if(a[j]<a[i]) 
                f[i] = max(f[j] + 1, f[i]); 
        }
    }

    int res = 0;
    for(int i = 1; i<=n; i++) res = max(res, f[i]);
    cout<<res<<endl;
}


活动打卡代码 AcWing 898. 数字三角形

bruce
1天前
#include<iostream>
using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];

int main()
{
    cin>>n;
    for(int i = 1; i<=n;i++)
    {
        for(int j = 1; j<=i;j++)
        {
            cin>>a[i][j];
        }
    }

    for(int i = 0; i<=n;i++)
    {
        for(int j = 0;j<=i+1;j++)
            f[i][j] = -INF;
    }

    f[1][1] = a[1][1];
    for(int i=2; i<=n; i++)
    {
        for(int j = 1; j<=i; j++)
        {
            f[i][j] = max(f[i-1][j], f[i-1][j-1] ) + a[i][j];
        }
    }

    int res = -INF;
    for(int i =1; i<=n;i++)
    {
        res = max(res, f[n][i]);
    }
    cout<<res<<endl;

}