自学内容网 自学内容网
自学内容网 > 正文

【力扣系列题目】不同路径 组合总和 最大连续1个数 打家劫舍{持续更新中...}

🕗 发布于 2025-01-22 20:51 leetcode  算法  职场和发展  c++  开发语言  

文章目录

不同路径

不同路径

class Solution {
    int dfs(int i, int j, vector<vector<int>>& memo) {
        if (memo[i][j] != 0)
            return memo[i][j];

        if (i == 0 || j == 0)
            return 0;
        if (i == 1 && j == 1)
            return memo[i][j] = 1;

        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }

public:
    int uniquePaths(int m, int n) {
        // 解法一：数学/组合数
        // long long ans = 1;
        // // 第一次y=1 最后一次y=m-1
        // // 第一次x=n 最后一次x=n+m-2
        // for (int x = n, y = 1; y < m; ++x, ++y) {
        //     ans = ans * x / y;
        // }
        // return ans;

        // 解法二: 记忆化搜索
        vector<vector<int>> memo(m + 1, vector<int>(n + 1));
        return dfs(m, n, memo);

        // 解法三：动态规划
        // vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // dp[1][1] = 1;
        // for (int i = 1; i <= m; i++)
        //     for (int j = 1; j <= n; j++) {
        //         if (i == 1 && j == 1)
        //             continue;
        //         dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //     }
        // return dp[m][n];
    }
};

不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        int m = ob.size(), n = ob[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (ob[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];
    }
};

不同路径 III

class Solution {
    bool vis[21][21];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int ret;
    int m, n, step;

public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int bx = 0, by = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 0)
                    step++;
                else if (grid[i][j] == 1) {
                    bx = i;
                    by = j;
                }
        step += 2;
        vis[bx][by] = true;
        dfs(grid, bx, by, 1);
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int i, int j, int count) {
        if (grid[i][j] == 2) {
            if (count == step) // 判断是否合法
                ret++;
            return;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&
                grid[x][y] != -1) {
                vis[x][y] = true;
                dfs(grid, x, y, count + 1);
                vis[x][y] = false;
            }
        }
    }
};

组合总和

组合总和 【无重复数字+无限制选择次数】

class Solution {
    int aim;
    vector<int> path;
    vector<vector<int>> ret;

public:
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
    void dfss(vector<int>& nums, int pos, int sum) {
        if (sum == aim) {
            ret.push_back(path);
            return;
        }
        if (sum > aim || pos == nums.size())
            return;

        for (int i = pos; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfss(nums, i, sum + nums[i]);
            path.pop_back();
        }
    }
    void dfs(vector<int>& nums, int pos, int sum) {
        if (sum == aim) {
            ret.push_back(path);
            return;
        }
        if (sum > aim || pos == nums.size())
            return;

        for (int k = 0; k * nums[pos] + sum <= aim; k++) {
            if (k != 0)
                path.push_back(nums[pos]);
            dfs(nums, pos + 1, sum + k * nums[pos]);
        }

        for (int k = 1; k * nums[pos] + sum <= aim; k++) {
            path.pop_back();
        }
    }
};

组合总和 II 【有重复数字+只能选择一次】

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    int n;
    int aim;

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        ranges::sort(candidates);
        n = candidates.size();
        aim = target;
        dfs(candidates, 0, 0);
        return ans;
    }
    void dfs(vector<int>& candidates, int pos, int sum) {
        if (sum == aim) {
            ans.push_back(path);
            return;
        }

        if (sum > aim || pos == n)
            return;

        for (int i = pos; i < n; i++) {
            if (i > pos && candidates[i] == candidates[i - 1])
                continue;

            path.push_back(candidates[i]);
            dfs(candidates, i + 1, sum + candidates[i]);
            path.pop_back();
        }
    }
};

组合总和 III【「在 9 个数中选择 k 个数」的组合枚举】

class Solution {
    vector<int> path;
    vector<vector<int>> ans;

    int x;
    int xSum;

public:
    void dfs(int cur, int n, int pathSum) {
        if (path.size() + (n - cur + 1) < x || path.size() > x)
            return;

        // accumulate(path.begin(), path.end(), 0) == xSum
        if (path.size() == x && pathSum == xSum) {
            ans.push_back(path);
            return;
        }
        path.push_back(cur);
        dfs(cur + 1, n, cur + pathSum);
        path.pop_back();

        dfs(cur + 1, n, pathSum);
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        x = k;
        xSum = n;
        int pathSum = 0;
        dfs(1, 9, pathSum);
        return ans;
    }
};

组合总和 Ⅳ【无重复数字+爬楼梯】

class Solution {
    // dfs(i) 表示爬 i 个台阶的方案数
    int dfs(int i, vector<int>& nums, vector<int>& memo) {
        if (i == 0)
            return 1;

        int& res = memo[i]; // 注意这里是引用
        if (res != -1)
            return res;

        res = 0;
        for (int x : nums) {
            if (x <= i) {
                res += dfs(i - x, nums, memo);
            }
        }
        return res;
    }

public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> memo(target + 1, -1);
        // return dfs(target, nums, memo);

        vector<unsigned> f(target + 1);
        f[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int x : nums) {
                if (x <= i)
                    f[i] += f[i - x];
            }
        }
        return f[target];
    }
};

最大连续 1 的个数

最大连续 1 的个数【无翻转】

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int maxCount = 0, count = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                count++;
            } else {
                maxCount = max(maxCount, count);
                count = 0;
            }
        }
        maxCount = max(maxCount, count);
        return maxCount;
    }
};

最大连续1的个数 II

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums, int k = 1) {
        int ret = 0;
        int left = 0, zeroNum = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] == 0)
                zeroNum++;

            while (zeroNum > k) // 理解这里的while的必要性【if不错但不好】
            {
                if (nums[left] == 0)
                    zeroNum--;
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

最大连续1的个数 III【翻转K个零】

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        int left = 0, zeroNum = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] == 0)
                zeroNum++;

            while (zeroNum > k) // 理解这里的while的必要性【if不错但不好】
            {
                if (nums[left] == 0)
                    zeroNum--;
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

我不想上课【连续0的个数+翻转k个1】

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int longestOnes(vector<int>& nums, int k) {
    int ret = 0;
    int left = 0, oneNum = 0;
    for (int right = 0; right < nums.size(); right++) {
        if (nums[right] == 1)
            oneNum++;

        while (oneNum > k) {
            if (nums[left] == 1)
                oneNum--;
            left++;
        }
        ret = max(ret, right - left + 1);
    }
    return ret;
}
int main() {
    vector<int> days(31);
    for (int i = 0; i < 31; ++i) {
        cin >> days[i]; // 输入 31 天的课程情况
    }

    cout << longestOnes(days, 1) << endl;

    return 0;
}

打家劫舍

1.打家劫舍【线性房屋】

198. 打家劫舍 - 力扣（LeetCode）

1.0递归+记忆化搜索

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> cache(n, -1);
        return robRecursive(n - 1, nums, cache);
    }

    int robRecursive(int i, vector<int>& nums, vector<int>& cache) {
        if (i < 0)
            return 0;
        if (cache[i] != -1)
            return cache[i];
        return cache[i] = max(robRecursive(i - 1, nums, cache),
                              robRecursive(i - 2, nums, cache) + nums[i]);
        return cache[i];
    }
};

1.1一维数组

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 0)
            return 0;

        // 房子编号0~n-1
        // dp[k] 从0偷到k获得的最大金额
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        if (n == 1)
            return dp[0];

        dp[1] = max(nums[0], nums[1]);
        if (n == 2)
            return dp[1];

        for (int k = 2; k <= n - 1; k++)
        {
            dp[k] = max(dp[k - 1], nums[k] + dp[k - 2]);
        }
        return dp[n - 1];
    }
};

1.2三变量法

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 0)
            return 0;

        int prv = nums[0]; // dp[0]
        if (n == 1)
            return prv;

        int cur = max(nums[0], nums[1]); // dp[1]
        if (n == 2)
            return cur;
        // 房子编号0~n-1
        // dp[k] 从0偷到k获得的最大金额
        for (int i = 2; i < n; i++)
        {
            // dp[k] = max(dp[k - 1], nums[k] + dp[k - 2]);
            int tmp = max(cur, nums[i] + prv);
            prv = cur;
            cur = tmp;
        }

        return cur;
    }
};

1.2三变量法【高手】【推荐】

class Solution {
public:
    int rob(vector<int>& nums) {
        int f0 = 0, f1 = 0;
        for (int x : nums) {
            int new_f = max(f1, f0 + x);
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }
};

1.3双数组法

class Solution
{
public:
    int massage(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 0)
            return 0;
        // f[i] 走到i时 偷nums[i]
        // g[i] 走到i时 不偷nums[i]
        vector<int> f(n);
        vector<int> g(n); // auto g = f;
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = nums[i] + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};

2.打家劫舍2【环形房屋】

打家劫舍2

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

2.1双数组法

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }
    int rob1(vector<int>& nums, int left, int right) {
        if (left > right)
            return 0;

        int n = nums.size();
        vector<int> f(n);
        auto g = f;
        f[left] = nums[left];
        for (int i = left + 1; i <= right; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[right], g[right]);
    }
};

2.2 三变量法【新手】

class Solution
{
public:
    int robRange(vector<int> &nums, int start, int end)
    {
        int n = end - start + 1;
        if (n == 0)
            return 0;

        int prv = nums[start]; // dp[k-2]
        if (n == 1)
            return prv;

        int cur = max(nums[start], nums[start + 1]); // dp[k-1]
        if (n == 2)
            return cur;

        for (int i = start + 2; i <= end; i++)
        {
            // dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2]);
            int tmp = max(cur, nums[i] + prv);
            prv = cur;
            cur = tmp;
        }
        return cur;
    }

    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
            return nums[0];
        else if (n == 2)
            return max(nums[0], nums[1]);
        else if (n == 3)
            return max(max(nums[0], nums[1]), nums[2]);
            
        // 偷nums[0]不能偷nums[1]和nums[n-1] 能偷[2, n - 2]
        // 不偷nums[0] 能偷[1, n - 1]
        return max(nums[0] + robRange(nums, 2, n - 2), robRange(nums, 1, n - 1));
    }
};

2.2 三变量法【高手】【推荐※】

class Solution {
    int rob1(vector<int>& nums, int start, int end) {
        int f0 = 0, f1 = 0;
        for (int i = start; i <= end; i++) {
            int new_f = max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }

public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }
};

3.打家劫舍3【树形DP】

高手思路

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

class Solution {
    pair<int, int> dfs(TreeNode* node) {
        if (node == nullptr) { // 递归边界
            return {0, 0};     // 没有节点，怎么选都是 0
        }
        auto [l_rob, l_not_rob] = dfs(node->left);   // 递归左子树
        auto [r_rob, r_not_rob] = dfs(node->right);  // 递归右子树
        int rob = l_not_rob + r_not_rob + node->val; // 选
        int not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob); // 不选
        return {rob, not_rob};
    }

public:
    int rob(TreeNode* root) {
        auto [root_rob, root_not_rob] = dfs(root);
        return max(root_rob, root_not_rob); // 根节点选或不选的最大值
    }
};

4.删除相邻数字的最大分数

删除相邻数字的最大分数_牛客题霸_牛客网 (nowcoder.com)

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传在这里插入图片描述

  1. 一个数组选了x可以得x分 但是值为x-1和x+1的数将会消失 直到数字全被消失或选择 问最高分数
  2. 遍历数组arr 填充hash arr中的per在hash中作下标 表示 【谁 出现的总和】如4在arr中出现了2次 则hash[4]=8
  3. 由此问题转变为 在hash中 我“偷”了某个下标i 获得了hash[i]分数 与i相邻的就不能偷了

4.1双状态数组

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    const int N = 1e4 + 10;
    int hash[N] = {0};

    int n = 0;
    cin >> n;

    int per = 0;
    int end = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> per;
        end = per > end ? per : end;
        hash[per] += per;
    }
    
    vector<int> f(end + 1, 0);
    vector<int> g(end + 1, 0);

    for (int i = 1; i <= end; i++)
    {
        f[i] = g[i - 1] + hash[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }
    cout << max(f[end], g[end]) << endl;
    return 0;
}

4.2一维数组

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;

    int per = 0;
    int end = 0;

    const int N = 1e4 + 10;
    int hash[N] = {0};
    
    for (int i = 0; i < n; i++)
    {
        cin >> per;
        end = per > end ? per : end;
        hash[per] += per;
    }

    vector<int> dp(end + 1, 0);

    // 房子编号0~n-1
    // dp[k] 从0偷到k获得的最大金额
    dp[0] = hash[0];
    dp[1] = max(hash[0], hash[1]);
    for (int k = 2; k <= end; k++)
    {
        dp[k] = max(dp[k - 1], hash[k] + dp[k - 2]);
    }

    cout << dp[end] << endl;
    return 0;
}

4.3三变量法

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    const int N = 1e4 + 10;
    int hash[N] = {0};

    int n = 0;
    cin >> n;

    int per = 0;
    int end = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> per;
        end = per > end ? per : end;
        hash[per] += per;
    }

    // 房子编号0~n-1
    // dp[k] 从0偷到k获得的最大金额
    int prv = hash[0];               // dp[0]
    int cur = max(hash[0], hash[1]); // dp[1]
    for (int i = 2; i <= end; i++)
    {
        // dp[k] = max(dp[k - 1], hash[k] + dp[k - 2]);
        int tmp = max(cur, hash[i] + prv);
        prv = cur;
        cur = tmp;
    }
    cout << cur << endl;
    return 0;
}

打家劫舍 IV【最小化最大值问题】


原文地址：https://blog.csdn.net/LHRan_ran_/article/details/145289306

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

  • Swift语言的操作系统

    Swift是苹果公司于2014年发布的一种强类型、编译型的编程语言。与Objective-C相比，Swift更加简洁、安全，提供了许多现代化的编程特性，如类型推断、闭包、元组等。Swift的设计目标是

    阅读更多2025-01-22
  • C# 委托和事件(事件)

    回调(callback）函数是Windows编程的一个重要部分。C或C++编程背景，在许多Windows API中使用过回调。VB添加AddressOf关键字后，开发人员就可以利用以前一度受到限制的A

    阅读更多2025-01-22
  • AI赋能Flutter开发：ScriptEcho助你高效构建跨端应用

    Flutter凭借其“一次编写，多端运行”的特性，成为众多开发者的首选跨端开发框架。然而，即使Flutter拥有快速开发的优势，开发者在实际项目中仍然可能面临效率瓶颈，例如UI界面搭建耗时、代码重复编

    阅读更多2025-01-22
  • 【Rabbitmq】Rabbitmq高级特性-发送者可靠性

    首先通过配置可以让交换机、队列、以及发送的消息都持久化。这样队列中的消息会持久化到磁盘，MQ重启消息依然存在。RabbitMQ在3.6版本引入了LazyQueue，并且在3.12版本后会称为队列的默认

    阅读更多2025-01-22
  • C++ random_shuffle函数：从兴起到被替代

    这个函数需要一个随机数生成器，这个生成器必须满足UniformRandomBitGenerator的要求。利用提供的随机数生成器，对序列中的元素进行随机排列。与相比，能够更灵活地使用C++11及更高版

    阅读更多2025-01-22
  • python高级加密算法AES对信息进行加密和解密

    （高级加密标准）是一种广泛使用的对称加密算法，它以字节为单位处理数据，将明文分组加密成密文。AES算法的核心在于一个轮函数，该函数会对数据执行多次变换，包括字节代换、行移位、列混合和轮密钥加。这些操作

    阅读更多2025-01-22
  • docker安装consul并启动的详细步骤

    安装docker以后，你可以尝试安装各类容器，如consul。

    阅读更多2025-01-22
  • python md5加密

    这段代码定义了一个md5_encryption函数，它接受一个字符串作为参数，对该字符串进行MD5加密，然后返回加密后的十六进制字符串。在调用函数时，你可以传入任何需要加密的数据，并打印出其MD5加密

    阅读更多2025-01-22
  • 数据结构-二叉树

    7、双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。//先序创建：根左右 初始化函数，就是把树的所有节点存进去的过程。//中序创建：左根右 初始化函数，就是把树的所以节

    阅读更多2025-01-22
  • django使用踩坑经历

    使用Django过程中的一些踩坑经历

    阅读更多2025-01-22
自学内容网
Copyright © 2015-2025