2022-12-5 leetcode与蓝桥刷题情况_蓝桥杯和leetcode的区别

一、leetcode题目

1.奇怪的打印机

题目描述
有台奇怪的打印机有以下两个特殊要求：

• 打印机每次只能打印由 同一个字符 组成的序列。
• 每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。
• 给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

2.测试用例

输入：

s = “aaabbb”

输出：

2

解释：

首先打印 “aaa” 然后打印 “bbb”。

3.思路(比较难，最初没有思路，看了题解写出的自己代码)

区间DP:

• 因为每次打印必须从第一个数字开始打印，所以
• 当$s[i+j]（0<j<len-i）$与$s[i]$相同时，打印$s[i]$随便就能打印$s[i+j]$，并不需要额外的打印次数。
• $s[i]!=s[j]$,即区间两端的字符不同，那么我们需要分别完成该区间的左右两部分的打印。

4.算法实现

public int strangePrinter(String s) {
	int n = s.length();
    int[][] f = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        f[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                f[i][j] = f[i][j - 1];
            } else {
                int minn = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    minn = Math.min(minn, f[i][k] + f[k + 1][j]);
                }
                f[i][j] = minn;
            }
        }
    }
    return f[0][n - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二、蓝桥题目

1.小明的背包2

题目描述
小明有一个容量为 $V$ 的背包。

这天他去商场购物，商场一共有 $N$ 种物品，第 $i$ 种物品的体积为 $w_i$，价值为 $v_i$ ，每种物品都有无限多个。

小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 11 行包含两个正整数 $N,V$，表示商场物品的数量和小明的背包容量。

第 $2\sim N+1$ 行包含 2 个正整数 $w,v$,表示物品的体积和价值。

$1\le N\le 10^3,1\le V\le 10^3，1\le w_i,v_i\le 10^3$

2.测试用例

输入：

5 20
1 6
2 5
3 8
5 15
3 3

输出：

120

3.思路

完全背包问题，不需要明确的物品阶段划分，所以只需要一维数组$dp$即可，每次计算中动态更新$dp$ 数组的值。

• 状态表示: $dp[i]:$表示背包容量为i时，背包能够容纳的最大价值。
• 状态转移方程式：$dp[i]=max(dp[i-w[k]+v[k])$(k表示遍历的物品索引，w[i]为第i个物品的重量，v[i]为第k个物品的价值
• 边界条件：$dp[0]=0$,背包容量为0时，最大价值也为0;

4.算法实现

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt(), volume = scan.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        int[] dp = new int[volume+1];
        for(int i = 0; i < n; i++){
          w[i] = scan.nextInt();
          v[i] = scan.nextInt();
        }
        for(int i = 1; i <= volume; i++){
          for(int j = 0; j < n; j++){
            if(i >= w[j]){
              dp[i] = Math.max(dp[i], dp[i-w[j]]+v[j]);
            }
          }
        }
        System.out.println(dp[volume]);
        scan.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23