题目二 递归改动态规划

8.2 1h
image.png

思路

  • 首先所求问题，最后一步一定是 （表达式）运算符（表达式）这样的格式 例如 (1&0)^(1)，那么组合个数就是符合条件两边表达式个数的乘积，最后一步的运算符可以有多个把这些加起来就是最终答案
  • 我们的子问题就是 被拆后的表达式返回true 或者 false 的组合个数有多少种，这种范围上的问题就可以用递归来求解 参数可以设置为left right desired 返回类型为个数

  • basecase 为 left=right时候 看desired的情况

    题目三

    9.1 1h37m
    image.png

    思路

  • 先理解题意，给定一个集合A里面包含26个字母，根据这个集合产生子序列要求如下，子序列不得有重复的字母，子序列必须是升序。

  • 然后对子序列进行编码（相当于排序1,2,3），子序列短的排前面，子序列长度一样字典序小的排在前面如下图

image.png

  • 下面举个实际的例子进行求解

image.png

  • djv 长度为3 前面肯定有长度为1的所有子序列和长度为2的所有子序列，所以编码在这之后
  • 长度为3的子序列比较麻烦，第一个位置可以是a、b、c，后面跟着两个长度为2的子序列，然后第一字符到d就开始第二个字符变动了 从a到i 跟上面的过程一样
  • 定义两个函数 一个得到我们指定长度的子序列有多少个，一个是固定首个字符和后面的长度来求解符合子序列有多少个，这两个函数是递归的

    代码

题目四 子串动态规划

8.2 1h28mimage.png

思路

image.png

  • 这题的意思是让我们找出子串满足没有重复字符 并且是最长的
  • 子数组子串问题我们要考虑动态规划，想下以i位置为结尾的无重复子串的最长长度。
  • 考虑一下会影响i位置最长子串的瓶颈
  1. 假设i位置是a，然后i位置前面最近的一个a，最长长度不会超过他俩之间的字符个数这是第一个瓶颈
  2. 还有就是i-1位置上的最长长度，最长长度不会超过这个长度+1，这是第二瓶颈
  • 所以i-1位置最长子串头部字符和跟i位置相同的字符最近的 它俩哪个值大取哪个长度
  • 我们可以用数组来代替哈希表保存离i位置最近的字符的位置

    代码

题目五 编辑距离问题

8.2 1h40m
image.png

  • 我们将str1 编辑成str2所需要的代价成为距离，求最小编辑距离

    思路

    image.png

  • 先假设str1的长度跟str2的长度一样，str1的字符下标从0到5，我们画一张二维表帮助理解动态规划

  • 二维表行和列为i和j，代表字符串的长度，0是空串
  • 那么dp[i][j]就表示 我们将str1[0…i-1]编辑成str2[0….j-1]的最小编辑距离，这里面i-1指的是多长的字符串的前缀
  • 现在我们把空串的情况解决，就是二维表里第0行和第0列的情况 ，填完以后我们可以对dp[i][j]的情况进行分类讨论

    dp[i][j]状态转移方程讨论

    image.pngimage.png
  1. 第一种情况 将我们的以i-1为末尾的str1的前缀全部替换成以j-2为末尾的str2前缀，这样的最小距离加上add代价 dp[i][j] = dp[i][j-1]+add
  2. 第二种情况 将我们的以i-2为末尾的str1的前缀全部替换成以j-1为末尾的str2前缀，这样的最小距离加上del代价 dp[i][j] = dp[i-1][j]+del
  3. 第三种情况 将我们的以i-2为末尾的str1的前缀全部替换成以j-2为末尾的str2前缀，这样的最小距离加上rep代价 dp[i][j] = dp[i-1][j-1]+rep
  4. 第四种情况 如果第三种替换的字符相等就不用替换了

image.png

题目六 贪心

8.2 2h2m
image.png

思路

image.png

  • 尽可能让字符串的头部为小的值，比如我们保留a，但是有可能是bba这种情况 我们不能把所有b去掉，所以有以下贪心策略
  • 贪心策略，利用一个map来保存每个字符出现的个数，然后遍历过程中对每个出现的字符去map做减1操作
  • 直到出现map中一个字符为0时，表示这个范围中删除所有字符只保留一个也能让所有字符都活着
  • 然后我们在这个范围上选ascii码最小的保留，然后去掉保留字符前面的所有字符，以及字符串中所有重复的保留字符

    代码

    1. public static String remove(String str){
    2.       //判断条件要谨慎使用==
    3.       if(str.length()<2||str==null){
    4.           return str;
    5.       }
    6.       int[] map = new int[256];
    7.       for (int i = 0; i < str.length(); i++) {
    8.           map[str.charAt(i)]++;
    9.       }
    10.       int minAsciiIndex = 0 ;
    11.       for (int i = 0; i < str.length(); i++) {
    12.               map[str.charAt(i)] --;
    13.               //找到这个范围上最小的ascii码 的index
    14.               minAsciiIndex = str.charAt(i) < str.charAt(minAsciiIndex) ? i : minAsciiIndex;
    15.               if(map[str.charAt(i)]==0)break;
    16.       }
    17.       String liveChar = String.valueOf(str.charAt(minAsciiIndex));
    18.       return liveChar + remove(str.substring(minAsciiIndex+1).replaceAll(liveChar,""));
    19.   }