头像

bruce




在线 



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

/**
 * 91 解码字符方式
 * 一条包含字母 A-Z 的消息通过以下方式进行了编码:
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 给定一个只包含数字的非空字符串,请计算解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。
 * 
 * 示例 1:
 * 输入:s = "12"
 * 输出:2
 * 解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
 * 
 * 示例 2:
 * 输入:s = "226"
 * 输出:3
 * 解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
*/

/**
 * 方法 1,使用滑窗,分别对长度为1,和长度为2的长度进行累加他们的有效解码方式,但是这个题目做错了
 * 1226按照这个方法的解码方案是:
 * [1 2 2 6] [12 22 26] [1 22 26] [1 2 26]
*/
int numDecodings(string s)
{

    bool flag = false;
    int n = s.size();
    int res = 0, k = 0;

    for (int i = 0; i < n; i++)
    {
        int t = s[i] - '0';
        if (t >= 1 && t <= 26)
            flag = true;
        else
            flag = false;
        k = k * 10 + t;
    }
    for (int j = 0; j <= n - 2; j++)
    {
        string temp = s.substr(j, 2);
        int ans = (temp[0] - '0') * 10 + temp[1] - '0';

        if (ans > 0 && ans <= 26)
            res++;
        else
            break;
    }

    if (flag)
        res += 1;
    return res;
}

/**
 * 方法 2, 使用动态规划来做
 * 状态表示:dp[i]表示前i个字符组成的有效解码方法的个数
 * dp[0] = 1;
 * dp[i]最后可以划分最后一位数字要么是1位数字满足1-9,要么是两位数字满足11-26才可以
 * dp[i] = dp[i-1] + dp[i-2]
*/
int numDecodings(string s)
{
    int n = s.size();
    s = ' ' + s;
    vector<int> dp(n + 1, 0);
    dp[0] = 1; // 如果1个数都没有的话那么就是空,就是1种方案
    for (int i = 1; i <= n; i++)
    {
        if (s[i] >= '1' && s[i] <= '9')
            dp[i] += dp[i - 1];
        if (i > 1)
        {
            // 判断两位数是不是在10-26之间
            int t = (s[i - 1] - '0') * 10 + s[i] - '0';
            if (t >= 10 && t <= 26)
                dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}



活动打卡代码 LeetCode 91. 解码方法

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

/**
 * 91 解码字符方式
 * 一条包含字母 A-Z 的消息通过以下方式进行了编码:
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 给定一个只包含数字的非空字符串,请计算解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。
 * 
 * 示例 1:
 * 输入:s = "12"
 * 输出:2
 * 解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
 * 
 * 示例 2:
 * 输入:s = "226"
 * 输出:3
 * 解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
*/

/**
 * 方法 1,使用滑窗,分别对长度为1,和长度为2的长度进行累加他们的有效解码方式,但是这个题目做错了
 * 1226按照这个方法的解码方案是:
 * [1 2 2 6] [12 22 26] [1 22 26] [1 2 26]
*/
int numDecodings(string s)
{

    bool flag = false;
    int n = s.size();
    int res = 0, k = 0;

    for (int i = 0; i < n; i++)
    {
        int t = s[i] - '0';
        if (t >= 1 && t <= 26)
            flag = true;
        else
            flag = false;
        k = k * 10 + t;
    }
    for (int j = 0; j <= n - 2; j++)
    {
        string temp = s.substr(j, 2);
        int ans = (temp[0] - '0') * 10 + temp[1] - '0';

        if (ans > 0 && ans <= 26)
            res++;
        else
            break;
    }

    if (flag)
        res += 1;
    return res;
}

/**
 * 方法 2, 使用动态规划来做
 * 状态表示:dp[i]表示前i个字符组成的有效解码方法的个数
 * dp[0] = 1;
 * dp[i]最后可以划分最后一位数字要么是1位数字满足1-9,要么是两位数字满足11-26才可以
 * dp[i] = dp[i-1] + dp[i-2]
*/
int numDecodings(string s)
{
    int n = s.size();
    s = ' ' + s;
    vector<int> dp(n + 1, 0);
    dp[0] = 1; // 如果1个数都没有的话那么就是空,就是1种方案
    for (int i = 1; i <= n; i++)
    {
        if (s[i] >= '1' && s[i] <= '9')
            dp[i] += dp[i - 1];
        if (i > 1)
        {
            // 判断两位数是不是在10-26之间
            int t = (s[i - 1] - '0') * 10 + s[i] - '0';
            if (t >= 10 && t <= 26)
                dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}



活动打卡代码 LeetCode 87. 扰乱字符串

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

/**
 * 87 扰乱字符串即可
 * 给定一个字符串然后用二叉树来表示,然后挑选一个叶子节点翻转,
 * 翻转之后组成新的字符串即可
 * 判断s1是不是干扰之后产生的字符串s2
*/

/**
 * 方法 1,使用递归来做
*/
bool isScramble(string s1, string s2)
{
    int n = s1.size(), m = s2.size();
    if (s1 == s2)
        return true;
    string bs1 = s1, bs2 = s2;
    sort(bs1.begin(), bs1.end()), sort(bs2.begin(), bs2.end());
    if (bs1 != bs2)
        return false;

    for (int i = 1; i <= n - 1; i++)
    {
        // s1的前i个字符和s2的前i个字符
        if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i)))
            return true;
        // s1的前i个字符和s2的后i个字符来做
        if (isScramble(s1.substr(0, i), s2.substr(m - i)) && isScramble(s1.substr(i), s2.substr(0, m - i)))
            return true;
    }
    return false;
}




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

/**
 * 303 给定一个数组,然后求解这个数组的前缀和
*/

class NumArray
{
public:
    vector<int> s;
    NumArray(vector<int> &nums)
    {
        s.resize(nums.size() + 1);
        for (int i = 1; i <= nums.size(); i++)
        {
            s[i] = s[i - 1] + nums[i - 1];
        }
    }

    int sumRange(int i, int j)
    {
        i++, j++;
        return s[j] - s[i - 1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */



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

/**
 * 363,给定一个二维数组,然后求计算这个不超过k的最大值
*/

/**
 * 方法 1,使用二维数组的前缀和来做即可,但是暴力解法,时间复杂度是O(n^2 * m^2)
*/
int maxSumSubmatrix1(vector<vector<int> > &matrix, int k)
{
    if (matrix.empty() || matrix[0].empty())
        return 0;
    int m = matrix.size(), n = matrix[0].size(), res = INT_MIN;
    int sum[m][n];
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int t = matrix[i][j];
            if (i > 0)
                t += sum[i - 1][j];
            if (j > 0)
                t += sum[i][j - 1];
            if (i > 0 && j > 0)
                t -= sum[i - 1][j - 1];
            sum[i][j] = t;
            // 计算从0,0到ij的子矩阵的最大值部分
            for (int r = 0; r <= i; ++r)
            {
                for (int c = 0; c <= j; ++c)
                {
                    int d = sum[i][j];
                    if (r > 0)
                        d -= sum[r - 1][j];
                    if (c > 0)
                        d -= sum[i][c - 1];
                    if (r > 0 && c > 0)
                        d += sum[r - 1][c - 1];
                    if (d <= k)
                        res = max(res, d);
                }
            }
        }
    }
    return res;
}

/**
 * 方法 2,使用二分 + 二维数组矩阵
*/
int maxSumSubmatrix(vector<vector<int> > &matrix, int k)
{
    int m = matrix.size(), n = matrix[0].size();
    int ans = INT_MIN;

    for (int lo = 0; lo < n; lo++)
    {
        vector<int> row(m, 0);
        for (int hi = lo; hi < n; hi++)
        {
            set<int> pre;
            int sum = 0;

            pre.insert(0);
            for (int i = 0; i < m; i++)
            {
                row[i] += matrix[i][hi];
                sum += row[i];
                auto it = pre.lower_bound(sum - k);
                if (it != pre.end())
                    ans = max(ans, sum - *it);
                pre.insert(sum);
            }
        }
    }

    return ans;
}




bruce
16小时前
class NumMatrix
{
public:
    vector<vector<int> > s;
    NumMatrix(vector<vector<int> > &matrix)
    {
        if(matrix.empty() || matrix[0].empty()) return ;
        int n = matrix.size(), m = matrix[0].size();
        s = vector<vector<int>>(n+1, vector<int>(m+1, 0));
        for(int i = 1;i<=n;i++)
        {
            for(int j = 1;j<=m;j++)
            {
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }

    int sumRegion(int x1, int y1, int x2, int y2)
    {
        x1++, y1++, x2++, y2++;
        return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */


活动打卡代码 LeetCode 97. 交错字符串

bruce
16小时前

    class Solution {
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        int n = s1.size(), m = s2.size();
        if(s3.size() != n+m) return false;
        s1  = ' ' + s1, s2 = ' ' + s2, s3 = ' '+ s3;

        vector<vector<bool>>f(n+1, vector<bool>(m+1));

        for(int i = 0;i<=n;i++)
        {
            for(int j = 0;j<=m;j++)
            {
                if(i==0 && j==0) f[i][j] = true;
                else
                {
                    if(i && s1[i] == s3[i+j]) f[i][j] = f[i-1][j];
                    if(j && s2[j] == s3[i+j]) f[i][j] = f[i][j] || f[i][j-1];
                }
            }
        }
        return f[n][m];
    }
};




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

/**
 * 221 给定一个二维矩阵,然后矩阵中有1或者0,求解由1构成的正方形的最大面积
*/

/**
 * 方法 1,使用动态规划来做;
 * f[i][j] 表示用ij结尾的正方形的最大长度;
 * f[i][j]的初始化,i表示行,j表示列,然后如果j等于0的话,
 * 说明正方形的列的长度宽度是0列,不管i是多少行,宽度都是1,
 * 否则f[i][j]等于f[i][j-1]上一个列的宽度+1;=>f[i][j] = f[i][j-1] + 1;
 * 
*/
class Solution
{
public:
    int maximalSquare(vector<vector<char> > &s)
    {
        int n = s.size();
        if (n == 0)
            return 0;
        int m = s[0].size();
        // int n = s.size(), m = s[0].size();

        // 状态fij表示ij结尾的格子的最长宽度是多少
        vector<vector<int> > f(n, vector<int>(m));
        // 状态初始化部分

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                // 如果s[i][j]是1的话,说明有值
                if (s[i][j] == '1')
                {
                    // j=0表示只有1列,宽度是1
                    if (j == 0)
                        f[i][j] = 1;
                    // 否则ij表示的是f[i][j-1] + 1;
                    else
                        f[i][j] = f[i][j - 1] + 1;
                }
                else
                    f[i][j] = 0; // 如果s[i][j]等于0的话,那么就是宽度为0
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int len = INT_MAX;
                for (int k = i; k < n; k++)
                {
                    len = min(len, f[k][j]);
                    if (len == 0)
                        break;
                    // 这里u表示的高度,然后和85题目不一样的是u和len相同表示正方形,不是矩形
                    int u = (k - i + 1);
                    if (len == u)
                        ans = max(ans, len * u);
                }
            }
        }
        return ans;
    }
};

/**
 * 方法 2,使用动态规划来做,和上面的思路一样,但是写法不一样
 * 边界条件处理完了,再来看一般情况的递推公式怎么办,对于任意一点dp[i][j],
 * 由于该点是正方形的右下角,所以该点的右边,下边,右下边都不用考虑,
 * 关心的就是左边,上边,和左上边。这三个位置的dp值 suppose 都应该算好的,
 * 还有就是要知道一点,只有当前 (i, j) 位置为1,dp[i][j] 才有可能大于0,
 * 否则 dp[i][j] 一定为0。当 (i, j) 位置为1,
 * 此时要看 dp[i-1][j-1], dp[i][j-1],和 dp[i-1][j] 这三个位置,
 * 我们找其中最小的值,并加上1,就是 dp[i][j] 的当前值了,
 * 这个并不难想,毕竟不能有0存在,所以只能取交集,
 * 最后再用 dp[i][j] 的值来更新结果 res 的值即可,
*/
int maximalSquare(vector<vector<char> > &matrix)
{
    if (matrix.empty() || matrix[0].empty())
        return 0;
    int m = matrix.size(), n = matrix[0].size(), res = 0;
    vector<vector<int> > dp(m, vector<int>(n, 0));

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (i == 0 || j == 0)
                dp[i][j] = matrix[i][j] - '0';
            else if (matrix[i][j] == '1')
            {
                // ij这个位置的左上,上边,左边的三个情况取最小即可
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
            res = max(res, dp[i][j]);
        }
    }
    return res * res;
}


活动打卡代码 LeetCode 221. 最大正方形

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

/**
 * 221 给定一个二维矩阵,然后矩阵中有1或者0,求解由1构成的正方形的最大面积
*/

/**
 * 方法 1,使用动态规划来做;
 * f[i][j] 表示用ij结尾的正方形的最大长度;
 * f[i][j]的初始化,i表示行,j表示列,然后如果j等于0的话,
 * 说明正方形的列的长度宽度是0列,不管i是多少行,宽度都是1,
 * 否则f[i][j]等于f[i][j-1]上一个列的宽度+1;=>f[i][j] = f[i][j-1] + 1;
 * 
*/
class Solution {
public:
    int maximalSquare(vector<vector<char>>& s) {
        int n = s.size();
        if (n == 0)
            return 0;
        int m = s[0].size();
        // int n = s.size(), m = s[0].size();

        // 状态fij表示ij结尾的格子的最长宽度是多少
        vector<vector<int>>f(n, vector<int>(m));
        // 状态初始化部分

        for(int i = 0;i<n;i++)
        {
            for(int j = 0; j<m; j++)
            // 如果s[i][j]是1的话,说明有值
            if(s[i][j] == '1')
            {
                // j=0表示只有1列,宽度是1
                if(j == 0) f[i][j] = 1;
                // 否则ij表示的是f[i][j-1] + 1;
                else f[i][j] = f[i][j-1] + 1;
            }
            else f[i][j] = 0; // 如果s[i][j]等于0的话,那么就是宽度为0
        }

        int ans = 0;
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                int len = INT_MAX;
                for(int k = i;k<n;k++)
                {
                    len = min(len, f[k][j]);
                    if(len == 0) break;
                    // 这里u表示的高度,然后和85题目不一样的是u和len相同表示正方形,不是矩形
                    int u = (k - i + 1); 
                    if(len == u)  ans = max(ans, len * u);
                }
            }
        }
        return ans;
    }
};



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

/**
 * 115 不同的序列
 * 给定字符s和t,计算s的子序列中t出现的次数
*/

/**
 * 方法 1,使用动态规划来做
 * f[i][j]表示s的1到i的所有子序列和t的[1-j]相等的子序列
 * 状态计算:选择f[i] 和不选择f[i] = f[i-1][j]
 * 选择f[i-1][j-1]
*/

int numDistinct(string s, string t)
{
    int n = s.size(), m = t.size();
    s = ' '+ s, t = ' ' + t;
    vector<vector<long long> > f(n + 1, vector<long long>(m + 1));

    // 如果原字符串不是空,但是子字符串是空的话,那么返回1,因为空串也是任意一个字符串的子串
    for (int i = 0; i <= n; i++)
        f[i][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            // 不选择s[i]
            f[i][j] = f[i - 1][j];
            // 选择s[i]
            if (s[i] == t[j])
                f[i][j] += f[i - 1][j - 1];
        }
    return f[n][m];
}