首页 > 其他分享 >[剑指offer] 动态规划篇

[剑指offer] 动态规划篇

时间：2023-09-26 21:35:49浏览次数：31  
标签：return offer int length array 动态 规划 public dp

JZ42 连续子数组的最大和

/* 贪心 */
public class JZ42_1
{
    public static int FindGreatestSumOfSubArray(int[] array)
    {
        int sum = 0, res = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++)
        {
            sum += array[i];
            res = Math.max(res, sum);
            if (sum < 0)
                sum = 0;
        }
        return res;
    }
}

/*
* dp
* dp[i]:以 array[i] 结尾的连续子数组最大和。
* 状态转移方程： dp[i] = Math.max(dp[i-1] + array[i], array[i]);
* */
public class JZ42_2
{
    public static int FindGreatestSumOfSubArray(int[] array)
    {
        int[] dp = new int[array.length];
        int res = array[0];
        dp[0] = array[0];
        for (int i = 1; i < array.length; i++)
        {
            dp[i] = Math.max(array[i], dp[i - 1] + array[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

JZ85 连续子数组的最大和(二)

/* 贪心(与JZ42类似) */
public class JZ85_1
{
    public static int[] FindGreatestSumOfSubArray(int[] array)
    {
        int sum = 0, mmax = Integer.MIN_VALUE, len = -1, start = 0, idx = 0;
        for (int i = 0; i < array.length; i++)
        {
            sum += array[i];
            if (mmax == sum)
            {
                if (i - idx + 1 > len)
                {
                    len = i - idx + 1;
                    start = idx;
                }
            }
            if (mmax < sum)
            {
                mmax = sum;
                len = i - idx + 1;
                start = idx;
            }
            if (sum < 0)
            {
                idx = i + 1;
                sum = 0;
            }
        }
        int[] res = new int[len];
        System.arraycopy(array, start, res, 0, len);
        return res;
    }
}

/*
 * dp
 * dp[i]:以 array[i] 结尾的连续子数组最大和。
 * 状态转移方程： dp[i] = Math.max(dp[i-1] + array[i], array[i]);
 * (与JZ42类似)
 * */
public class JZ85_2
{
    public static int[] FindGreatestSumOfSubArray(int[] array)
    {
        int[] dp = new int[array.length];
        int mmax = array[0], idx = 0, start = 0, len = 1;
        dp[0] = array[0];
        for (int i = 1; i < array.length; i++)
        {
            dp[i] = dp[i - 1] + array[i];
            if (dp[i] < array[i])
            {
                dp[i] = array[i];
                idx = i;
            }
            if (mmax == dp[i])
            {
                if (i - idx + 1 > len)
                {
                    len = i - idx + 1;
                    start = idx;
                }
            }
            if (mmax < dp[i])
            {
                len = i - idx + 1;
                start = idx;
                mmax = dp[i];
            }
        }
        int[] res = new int[len];
        System.arraycopy(array, start, res, 0, len);
        return res;
    }
}

JZ69 跳台阶

/*
* dp
* dp[n]: 跳 n 级台阶,有 dp[n] 种跳法
* 状态转移方程: dp[n]=dp[n-1]+dp[n-2]
* */
public class JZ69_1
{
    public static int jumpFloor(int number)
    {
        if (number <= 2) return number;
        int[] dp = new int[number + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= number; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[number];
    }
}

/* 递归 */
public class JZ69_2
{
    public static int jumpFloor(int number)
    {
        if (number <= 2) return number;
        return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
}

JZ10 斐波那契数列

/* 递推 */
public class JZ10_1
{
    public static int Fibonacci(int n)
    {
        if (n < 3) return 1;
        int x1 = 1, x2 = 1;
        for (int i = 3; i <= n; i++)
        {
            x2 = x1 + x2;
            x1 = x2 - x1;
        }
        return x2;
    }
}

/* 递归+备忘录 */
public class JZ10_2
{
    public static int[] memo = new int[50];

    public static int Fibonacci(int n)
    {
        if (memo[n] != 0) return memo[n];
        if (n <= 2) return 1;
        else
        {
            memo[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
            return memo[n];
        }
    }
}

JZ19 正则表达式匹配⭐

/* 递归 */
public class JZ19_1
{
    public static boolean match(String str, String pattern)
    {
        return match(str, 0, pattern, 0);
    }

    private static boolean match(String str, int sIdx, String pattern, int pIdx)
    {
        if (str.length() == sIdx && pattern.length() == pIdx) return true;
        if (pattern.length() == pIdx) return false;
        boolean res = false;
        if (pIdx + 1 < pattern.length() && pattern.charAt(pIdx + 1) == '*')
            if (sIdx < str.length() && (str.charAt(sIdx) == pattern.charAt(pIdx) || pattern.charAt(pIdx) == '.'))
                return match(str, sIdx, pattern, pIdx + 2) || match(str, sIdx+1, pattern , pIdx + 2) || match(str, sIdx+1, pattern, pIdx);
            else
               return match(str, sIdx, pattern, pIdx + 2);
        else
        {
            if (sIdx < str.length() && (str.charAt(sIdx) == pattern.charAt(pIdx) || pattern.charAt(pIdx) == '.'))
                return match(str, sIdx + 1, pattern, pIdx + 1);
            else return false;
        }
    }
}

/* dp */
public class JZ19_2
{
    public boolean match(String str, String pattern)
    {
        int n = str.length();
        int m = pattern.length();
        boolean[][] f = new boolean[n + 1][m + 1];

        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (j == 0)
                    f[i][j] = i == 0;
                else
                {
                    if (pattern.charAt(j - 1) != '*')
                    {
                        if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.'))
                            f[i][j] = f[i - 1][j - 1];
                    }
                    else
                    {
                        if (j >= 2)
                            f[i][j] |= f[i][j - 2];
                        if (i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.'))
                            f[i][j] |= f[i - 1][j];
                    }
                }
            }
        }
        return f[n][m];
    }
}

JZ71 跳台阶扩展问题

/* 找规律 */
public class JZ71_1
{
    public static int jumpFloorII(int number)
    {
        return (int) Math.pow(2,number-1);
    }
}

/* dp */
public class JZ71_2
{
    public static int jumpFloorII(int number)
    {
        if (number <= 2) return number;
        int[] dp = new int[number + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= number; i++)
            for (int j = 0; j < i; j++)
                dp[i] += dp[j];
        return dp[number];
    }
}

JZ70 矩形覆盖

/* 找规律 */
public class JZ70_1
{
    public static int rectCover(int target)
    {
        if (target == 0) return 0;
        if (target <= 2) return target;
        return rectCover(target - 1) + rectCover(target - 2);
    }
}

JZ63 买卖股票的最好时机(一)⭐

/*
 * dp
 * dp[i][0]: 第i天不持股; dp[i][1]: 第i天持股;
 * 状态转移方程:
 * dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
 * dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
 * */
public class JZ63_1
{
    public static int maxProfit(int[] prices)
    {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1] = -prices[0];
        dp[0][0] = 0;
        for (int i = 1; i < prices.length; i++)
        {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

JZ47 礼物的最大价值

/* dp */
public class JZ47_1
{
    public static int maxValue(int[][] grid)
    {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++)
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        for (int i = 1; i < m; i++)
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        return dp[m - 1][n - 1];
    }
}

/* dfs+memo */
public class JZ47_2
{
    public static int[][] memo;

    public static int maxValue(int[][] grid)
    {
        int m = grid.length, n = grid[0].length;
        memo = new int[m][n];
        return dfs(grid, m - 1, n - 1);
    }

    public static int dfs(int[][] grid, int x, int y)
    {
        if (memo[x][y] != 0) return memo[x][y];
        if (x == 0 && y == 0) return memo[x][y] = grid[0][0];
        if (x == 0) return memo[x][y] = grid[x][y] + dfs(grid, x, y - 1);
        if (y == 0) return memo[x][y] = grid[x][y] + dfs(grid, x - 1, y);
        return memo[x][y] = grid[x][y] + Math.max(dfs(grid, x, y - 1), dfs(grid, x - 1, y));
    }
}

JZ48 最长不含重复字符的子字符串

/* 滑动窗口 */
public class JZ48_1
{
    public static int lengthOfLongestSubstring(String s)
    {
        int res = Integer.MIN_VALUE, left = 0, right = 0;
        while (right < s.length())
        {
            while (left < right && s.substring(left, right).contains("" + s.charAt(right)))
                left++;
            right++;
            res = Math.max(res, right - left);
        }
        return res;
    }
}

public class JZ48_2
{
    public static int lengthOfLongestSubstring(String s)
    {
        int[] dp = new int[s.length()];
        int[] start = new int[s.length()];
        int res = 1;
        dp[0] = 1;
        start[0] = 0;
        for (int i = 1; i < s.length(); i++)
        {
            if (s.substring(start[i - 1], i).contains("" + s.charAt(i)))
            {
                int temp = s.substring(start[i - 1], i).indexOf("" + s.charAt(i)) + start[i - 1];
                dp[i] = i - temp;
                start[i] = temp + 1;
            }
            else
            {
                dp[i] = dp[i - 1] + 1;
                start[i] = start[i - 1];
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

JZ46 把数字翻译成字符串⭐

/* dp */
public class JZ46_1
{
    public static int solve(String nums)
    {
        if (nums.length() == 0) return 0;
        if (nums.charAt(0) == '0') return 0;
        if (nums.length() == 1) return 1;
        int[] dp = new int[nums.length()];
        dp[0] = 1;
        dp[1] = 1;
        if (new Integer(nums.substring(0, 2)) <= 26 && nums.charAt(1) != '0')
            dp[1]++;
        for (int i = 2; i < nums.length(); i++)
        {
            if (nums.charAt(i) == '0')
            {
                if (nums.charAt(i - 1) == '1' || nums.charAt(i - 1) == '2')
                    dp[i] = dp[i - 2];
                else
                    break;
            }
            else
            {
                dp[i] = dp[i - 1];
                if (nums.charAt(i - 1) != '0' && new Integer(nums.substring(i - 1, i + 1)) <= 26)
                    dp[i] += dp[i - 2];
            }

        }
        return dp[nums.length() - 1];
    }
}

/* 递归 */
public class JZ46_2
{
    public int solve(String nums)
    {
        return back(nums.toCharArray(), 0);
    }

    public int back(char[] nums, int start)
    {
        if (start == nums.length) return 1;
        if (nums[start] == '0') return 0;
        int res1 = back(nums, start + 1);
        int res2 = 0;
        if ((start < nums.length - 1) && (nums[start] == '1' || (nums[start] == '2' && nums[start + 1] <= '6')))
            res2 = back(nums, start + 2);
        return res1 + res2;
    }
}

标签：return,offer,int,length,array,动态,规划,public,dp
From： https://www.cnblogs.com/VividBinGo/p/17731222.html

相关文章

  • 动态展示缩放背景图
          有时候在渲染用户上传的图片时，需要根据不同图片宽高进行展示，若固定宽高，则会对图片一定程度的拉伸，导致图片变形，此时直接根据relation 相对位置，使图片的框和背景框动态缩放，宽则同宽，长则同长，直接上效果图           .srcbox-i......
  • 大数据职业规划
    为什么报大数据？1.便宜2.随便选的简历：技能深的一个不会，浅的c++,java,python,网络初级HCIA坚持两个原则，脚踏实地，循序渐进网络工程hcia想学的东西sqlpythonflinkspark ......
  • 动态规划——数位DP 学习笔记
    动态规划——数位DP学习笔记定义引入数位DP往往都是这样的题型：给定一个区间\([l,r]\)，求这个区间中满足某种条件的数的总数。简单的暴力代码如下：intans=0;for(inti=l;i<=r;++i)if(check(i))++ans;而当数据规模过大，暴力枚举就\(\mathbbT\)飞了，因此......
  • 大龄程序员，S业109天，面试22家，收到4个offer，涨薪百分之十
    前言作为一名刚刚接触编程的初学者，被这个领域的神奇魅力所深深吸引。代码犹如魔法棒，能够改变世界，为我们的生活带来便捷和创新。然而，现实往往与理想相去甚远。随着时间的推移，逐渐发现当前的环境并不理想。在这个竞争激烈的行业中，工作机会显得愈发稀缺。即使拥有扎实的编程技能，也可能......
  • 欧拉系统、CentOS系统、Linux 系统。。。初始化磁盘，设置动态扩容
    欧拉系统、CentOS系统、Linux系统。。。初始化磁盘，设置动态扩容初始化磁盘，设置动态扩容登录root用户查看磁盘fdisk-l查看磁盘格式化磁盘，将磁盘设置成动态扩容格式fdisk/dev/vdc创建分区fdisk-l查看到/dev/vdc磁盘依次输入np回车回车回车t......
  • EasyExcel动态表头导出（支持多级表头）
    EasyExcel动态表头导出（支持多级表头）在很多业务场景中，都会应用到动态表头的导出，也会涉及到多级表头的导出，如下图所示通过EasyExcel，我们可以快速实现这一需求，具体代码如下DynamicHeaderimportjava.util.List;/***@Author:<ahref="mailto:[email protected]">Fxsen</a>......
  • 线性规划学习
    线性规划学习笔记\(1\)线性规划定义定义\(1.1\)\(\bullet\)已知一组实数\(a_1,a_2,\cdots,a_n\)，以及一组变量\(x_1,x_2,\cdots,x_n\)，在这些变量的一个线性函数定义为\(f(x_1,x_2,\cdots,x_n)=\sum_{i=1}\limits^na_ix_i\)。\(\bullet\)等式\(f(x_1,x_2,\cdots......
  • 信2105-3孟德昊阅读笔记规划
    这学期建民老师要求了我们每人进行不少于三本书的阅读，并给了我们很多的可读书籍的选择。我打算选择《软件需求》《软件需求模式》《敏捷软件需求》三本书来进行阅读，并作出相应的读书笔记，在读完之后进行认真的读书讨论，真正做到完全理解书中的内容，不是为了读书而读书，而是为了自己而......
  • 动态规划——区间DP 学习笔记
    动态规划——区间DP学习笔记不含四边形不等式优化。定义线性动态规划的局限性在于，它只能顺推或倒退，而不能有子区间依赖的问题。区间动态规划是线性动态规划的扩展，它将问题划分为若干个子区间，并通过定义状态和状态转移方程来求解每个子区间的最优解，最终得到整个区间的最优解。......
  • 【C++】动态内存管理 ⑤ ( 基础数据类型数组 内存分析 | 类对象 内存分析 | malloc 分
    文章目录一、基础数据类型数组内存分析1、malloc分配内存delete释放内存2、new分配内存free释放内存二、类对象内存分析1、malloc分配内存delete释放内存2、new分配内存free释放内存博客总结:C语言中使用malloc分配的内存,使用free进行释放;C++语言中......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99