菜鸡的原地踏步史03(◐‿◑)

每日一念
改掉自己想到哪写哪的坏习惯

一维动态规划
爬楼梯

class Solution {
    /**
        dp[i] 爬到第i个台阶有dp[i]种爬法
        dp[i] - dp[i - 1] + 1 & dp[i - 2] + 2
     */
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

杨辉三角

class Solution {
    /**
        res.get(i)表示第i层的数组
        首尾设置为1
        res.get(i).get(j) = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j)
     */

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new ArrayList();
        for(int i = 0; i < numRows; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    path.add(1);
                }
                else {
                    path.add(0);
                }
            }
            res.add(path);
            path = new ArrayList();
        }
        for(int i = 2; i < res.size(); i++) {
            for(int j = 1; j < res.get(i).size() - 1; j++) {
                int val = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j);
                res.get(i).set(j, val);
                // System.out.println(res.get(i).get(j));
            }
        }
        return res;
    }
}

打家劫舍

class Solution {
    /**
        dp[i]表示第i家能偷到的最高金额
        dp[i] -- dp[i - 1], dp[i - 2] + nums[i - 1]
     */
    // dp[nums.length]
    public int rob(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);
    }
    // dp[nums.length + 1]
    public int rob(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);
    }
}

完全平方数

class Solution {
    /**
        dp[i] 组成和为i的完全平方数最少数量 -- dp[i - j *j]
        从 < i 的第一个完全平方数开始找
        dp数组需要的最长长度为n + 1
        3 = 1 + 1 + 1 全1组成
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n);
        dp[0] = 0;
        for(int i = 0; i <= n; i++){
            for(int j = 0; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j *j] + 1);
            }
        }
        return dp[n];
    }
}

零钱兑换

class Solution {
    /**
        dp[i] 面值为i的零钱最少可以兑换的硬币数
        不可达值设置成amount + 1
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 不可达值
        dp[0] = 0;
        for(int i = 0; i < dp.length; i++) {
            for(int coin: coins) {
                if(i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
                else {
                    continue;
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

    /**
        不可达值设置成-1
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1); // 不可达值
        dp[0] = 0;
        for(int i = 0; i < dp.length; i++) {
            for(int coin: coins) {
                if(i == coin) {
                    dp[i] = 1;
                }
                else if(i > coin) {
                    if(dp[i - coin] == -1) {
                        continue;
                    }
                    else {
                        if(dp[i] == -1) {
                            dp[i] = dp[i - coin] + 1;
                        }
                        else {
                            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                        }
                    }
                    
                }
            }
        }
        return dp[amount];
    }
}

单词拆分

class Solution {
    /**
        dp[i] 表示前i个字符的组合，可以被字典拼接成
        boolean类型的数组
        dp[s.len + 1]
        dp[j]  + substring(j, i) -- 在word里面

     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> map = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i < dp.length; i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && map.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

最长递增子序列

class Solution {
    /**
        dp[i] 表示元素i结束的最长子序列
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for(int i = 1; i < dp.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxlen = Integer.MIN_VALUE;
        for(int i = 0; i < dp.length; i++) {
            if(dp[i] > maxlen) {
                maxlen = dp[i];
            }
        }
        return maxlen;
    }
}

乘积最大子数组

分割等和子集

class Solution {
    /**
        boolean dp[i] 前i个数字是否存在子集和为i
     */
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum % 2 != 0) {
            return false;
        }
        int mid = sum/2;
        boolean[] dp = new boolean[mid + 1];
        dp[0] = true;
        for(int i = 1; i < nums.length; i++) {
            for(int j = dp.length - 1; j >= nums[i - 1]; j--) {
                if(dp[j - nums[i - 1]]) {
                    dp[j] = true;
                }
            }
        }
        return dp[mid];
    }
}

二维动态规划
不同路径

class Solution {
    /**
        dp[i][j] 表示从start点走到(i, j)的位置，总共有多少条不同路径
        dp[i][j]  dp[i - 1][j] 向右  dp[i][j - 1] 向下
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

最小路径和

class Solution {
    /**
        dp[i][j]表示从左上角到(i, j)位置的最小数字总和
        dp[i][j] 只能由d[i - 1][j]向右，        或者d[i][j - 1]向下
                dp[i - 1][j] + nums[i][j]     dp[i][j - 1] + nums[i][j]   
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

最长回文子串

class Solution {
    /**
        dp[i] 以字符串的第i个位置的字母结尾的最长回文子串
        不太理解
        双指针法能写
        判断是否回文子串 奇数 i 向两边扩散, 偶数i i+1 向两边扩散
     */
    public String longestPalindrome(String s) {
        String res = "";
        for(int i = 0; i < s.length(); i++) {
            String res1 = isPalindrome(s, i, i);
            String res2 = isPalindrome(s, i, i + 1);
            
            res = (res1.length() > res.length()) ? res1 : res;
            res = (res2.length() > res.length()) ? res2 : res;

        }
        return res;
    }
    public String isPalindrome(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }
}

最长公共子序列

class Solution {
    /**
           0 a b c d e
        0  0 0 0 0 0 0
        a  0 1 0 0 0 0
        b  0 1 2 2 2 2
        c  0 1 2 3 3 3
        dp[i][j] text1以i结尾的字符串，和text2以j结尾的字符串，最长匹配到的公共子序列
                 i 和 j结尾的字符能匹配上
                 text1.charAt(i-1) == text2.charAt(j - 1) ? dp[i - 1][j - 1] + 1
                               不能匹配上 dp[i - 1][j], dp[i][j - 1]往前比较，取最大值
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for(int i = 1; i <= text1.length(); i++) {
            for(int j = 1; j <= text2.length(); j++) {
                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

编辑距离

class Solution {
    /**
        dp[i][j] 表示word1以i结尾的子串转换成word2以j结尾的子串需要的最少操作数
        初始化 dp[0][j] = j
               dp[i][0] = i
           0 h o r s e
        0  0 1 2 3 4 5
        r  1 1 
        o  2
        s  3
        i和j处的字符不相等
        dp[i][j] -- dp[i - 1][j] + 1 改i ? 增 or 删 or 替换
                 -- dp[i][j - 1] + 1 改j
                 -- dp[i - 1][j - 1] + 1 替换(i, j)
        i和j处的字符不相等
     */
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 1; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for(int j = 1; j <= word2.length(); j++) {
            dp[0][j] = j;
        }
        for(int i = 1; i <= word1.length(); i++) {
            for(int j = 1; j <= word2.length(); j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/778982.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Autosar Dcm配置-0x85服务配置及使用-基于ETAS软件

Autosar Dcm配置-0x85服务配置及使用-基于ETAS软件

文章目录 前言Dcm配置DcmDsdDcmDsp代码实现总结前言 0x85服务用来控制DTC设置的开启和关闭。某OEM3.0架构强制支持0x85服务，本文介绍ETAS工具中的配置 Dcm配置 DcmDsd 配置0x85服务 此处配置只在扩展会话下支持(具体需要根据需求决定)，两个子服务Disable为0x02,Enable…
阅读更多...
pytest使用报错（以及解决pytest所谓的“抑制print输出”）

pytest使用报错（以及解决pytest所谓的“抑制print输出”）

1. 测试类的类名问题 #codingutf-8import pytestclass TestClass1:def setup(self) -> None:print(setup)def test_01(self) -> None:print(test_01111111111111111111111)def test_02(self) -> None:print(test_02)以上述代码为例&#xff0c;如果类名是Test开头&am…
阅读更多...
Docker部署Seata与Nacos整合

Docker部署Seata与Nacos整合

本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 本文来自 Apache Seata官方文档&#xff0c;欢迎访问官网&#xff0c;查看更多深度文章。 Docker部署Seata与Nacos整合 Docker 部署 Seata 与 Nacos 整合 运行所使用的 demo项目地址 …
阅读更多...
I2C接口+高度集成的电源管理芯片（PMIC）-iML1942

I2C接口+高度集成的电源管理芯片（PMIC）-iML1942

电源管理芯片 - iML1942是一个高度集成的电源管理IC为TFT液晶面板。它具有完整的I2C接口来编程各种参数。该设备包括一个针对AVDD的电流模式升压调节器&#xff0c;一个针对VBK1的同步升压转换器。VGL可选的反相转换器或负电荷泵调节器&#xff0c;VSS1负线性调节器&#xff0c…
阅读更多...
【C++：类的基础认识和this指针】

【C++：类的基础认识和this指针】

C的类与C语言的struct结构体有啥区别&#xff1f; 默认的访问限定符不同 类的简要 关键字&#xff1a;class{}里面是类的主体&#xff0c;特别注意&#xff1a;{}后面的&#xff1b;不可以省略类中的变量叫做成员变量&#xff0c;类中的函数叫做成员函数类中访问有三种访问权限…
阅读更多...
系统集成项目管理工程师第12章思维导图发布

系统集成项目管理工程师第12章思维导图发布

今天发布系统集成项目管理工程师新版第12章脑图的图片版
阅读更多...
Ubuntu基本环境配置

Ubuntu基本环境配置

#Jdk 安装 #--查看 已安装 的jdk软件 java -version # 安装jdk软件(如果有选择请选 y) sudo apt install openjdk-11-jdk # 自行学习 vi 或 vim 学习网址如下&#xff1a; # https://www.runoob.com/linux/linux-vim.html #-- 修改系统级 path : /etc/profile 文件 (注意要…
阅读更多...
加入新数据预测，基于黏菌优化算法SMA优化SVM支持向量机回归预测（多输入单输出）

加入新数据预测，基于黏菌优化算法SMA优化SVM支持向量机回归预测（多输入单输出）

加入新数据预测&#xff0c;基于黏菌优化算法SMA优化SVM支持向量机回归预测&#xff08;多输入单输出&#xff09; 1.数据均为Excel数据&#xff0c;直接替换数据就可以运行程序。 2.所有程序都经过验证&#xff0c;保证程序可以运行。 3.具有良好的编程习惯&#xff0c;程序…
阅读更多...
浏览器打不开网页、但是电脑有网络，解决办法(win11)

浏览器打不开网页、但是电脑有网络，解决办法(win11)

2023.07.06测试有效 华为电脑拿去免费拆机保养后&#xff0c;发现浏览器连接不上网了&#xff0c;但是&#xff01;微信又能登录得上&#xff0c;也就是说电脑还是有网的。 原文链接 一、问题截图 二、解决方法 1.右键打开“网络和Internet设置” 2.打开“代理” 3.将该选项设…
阅读更多...
Linux网络管理

Linux网络管理

一、linux网络管理 1.获取计算机的网络信息 基本语法&#xff1a; #ifconfig #ip address &#xff08;ip a&#xff09; 解析&#xff1a; ens33&#xff1a;默认网卡 lo&#xff1a;环回网卡&#xff0c;127.0.0.1作为固定ip代表本机 virbr0&#xff1a;虚拟网络接口&…
阅读更多...
centos执行yum相关命令报错的可能原因

centos执行yum相关命令报错的可能原因

文章目录 1. 执行yum命令是报下面一大帕拉2. 安装某个包报错&#xff0c;找不到这个包 1. 执行yum命令是报下面一大帕拉 最后一行报错&#xff0c;在repo文件中找不到空baseurl&#xff1a;xxx / x86_64 执行这行命令把这个找不到的 xxx 禁掉即可sudo yum-config-manager --di…
阅读更多...
Go 依赖注入设计模式

Go 依赖注入设计模式

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…
阅读更多...
《QT从基础到进阶·四十三》QPlugin插件多线程问题和只有插件dll没有头文件和lib文件时调用插件中的方法

《QT从基础到进阶·四十三》QPlugin插件多线程问题和只有插件dll没有头文件和lib文件时调用插件中的方法

1、插件和多线程问题&#xff1a; 创建插件对象不能放到多线程执行&#xff0c;不然报错&#xff1a;ASSERT failure in QWidget: "Widgets must be created in the GUlthread. //不能放在多线程执行 QPluginLoader pluginLoader(pluginsDir.absoluteFilePath(fileName))…
阅读更多...
系统测试-缺陷管理学习

系统测试-缺陷管理学习

目录 1、什么是缺陷 2、缺陷的类型 3、缺陷的交付物 4、缺陷报告的基本格式 1、什么是缺陷 就是软件最终的功能实现跟需求不一致的现象就是缺陷 2、缺陷的类型 做少了&#xff0c;做错了&#xff0c;做多了&#xff0c;做差了 3、缺陷的交付物 缺陷报告&#xff1a;也叫…
阅读更多...
Vue中Class数据绑定

Vue中Class数据绑定

Class数据绑定 数据绑定的一个常见需求场景是操作CSS class列表&#xff0c;因为class是attribute&#xff08;属性&#xff09;&#xff0c;我们可以和其他attribute一样使用v-bind 将它们和动态的字符串绑定。但是&#xff0c;在处理比较复杂的绑定时&#xff0c;通过拼接生…
阅读更多...
Wish卖家必读：如何安全有效地进行店铺测评

Wish卖家必读：如何安全有效地进行店铺测评

Wish以其独特的商业模式和先进的技术在电商领域独树一帜。作为北美和欧洲最大的移动电商平台之一&#xff0c;Wish拥有庞大的用户基础&#xff0c;其中90%的卖家来自中国&#xff0c;这不仅显示了其在全球电商市场中的影响力&#xff0c;也反映了其对中国卖家的吸引力。 Wish平…
阅读更多...
免费去马赛克软件，亲测支持视频和图片，这AI功能逆天了！

免费去马赛克软件，亲测支持视频和图片，这AI功能逆天了！

有小伙伴私信问阿星有什么去除马赛克的免费软件&#xff0c;求推荐好用的去马赛克软件。 市面上去马赛克的软件多如牛毛&#xff0c;但真正好用的真不多&#xff0c;而免费的是更少。今天阿星就分享一款 AI智能去马赛克软件&#xff0c;免费使用。软件支持去除图片和视频的马赛…
阅读更多...
打卡第4天----链表

打卡第4天----链表

通过学习基础，发现我的基本功还得需要再练练，思路得再更加清晰明了，这样子做算法题才能驾轻就熟。每天记录自己的进步。 一、两两交换 题目编号：24 题目描述： 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本…
阅读更多...
CS61B Data Structure-Jonathan Lecture2 using objects - OBJECTS METHODS

CS61B Data Structure-Jonathan Lecture2 using objects - OBJECTS METHODS

Recall String s1; // Step 1: declare a String variable s1 new String(); // Step 2: assign it a value, a new empty string objectString s2 new String(); // 1&2 combined今日知识点 situation: pointing to the same object s1 "Yow!";s2 s1; //…
阅读更多...
安装 tesseract

安装 tesseract

安装 tesseract 1. Ubuntu-24.04 安装 tesseract2. Ubuntu-24.04 安装支持语言3. Windows 安装 tesseract4. Oracle Linux 8 安装 tesseract 1. Ubuntu-24.04 安装 tesseract sudo apt install tesseract-ocr sudo apt install libtesseract-devreference: https://tesseract-…
阅读更多...
最新文章

Copyright @ 2022~2023