剑指offer-动态规划

剑指 Offer 48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

1. 解题思路

询问的是最长子字符串的长度,对于这道题而言,用滑动窗口算法是比较直观的,利用哈希表记录窗口中各个字符的出现次数,一旦出现大于2的,就进行窗口的收缩。

但是使用动态规划要怎么解?我们知道动态规划的三要素是状态、选择、状态转移方程

鉴于是子串,那么我们可以这样定义状态:设dp[i]为以s[i]结尾的最长子串

选择:每次是否和前面的那个串连接成为新的串

状态转移方程

状态转移方程需要考虑:

• 如果在s[i]左边相同的字符s[j],在dp[i-1]中描述的子串中,此时串的长度不能继承之前的结果,而应该要重新计算
• 如果在s[i]左边相同的字符s[j],不在dp[i-1]中描述的子串中,此时串的长度可以继承之前的结果
  • 不在的情况可以分为两种
  • 左边压根没有相同的元素
  • 左边有相同的元素,但是不在dp[i-1]所描述的那个子串中

条件怎么写呢?

i是s[i]的下标,j是s[j]的下标,假设dp[i-1]是以s[i-1]结尾的最长子串,那么这个子串在字符串中的下标区间就是[i-1-dp[i-1]+1,i-1],这个+1是下标计算公式来的,可以手工演算

那么我们就只要判断j是否位于这个区间就可以了,也就是

是否有j>=i-dp[i-1]&&j<=i-1

整理一下就是dp[i-1]>=i-j的时候,这时候j位于区间里面,那么长度的话就是由s[j]和s[i]的位置来决定

首先我们用公式计算i-j+1代表[j,i]有这么多个数,然后s[j]是不能算进去的,所以这时候dp[i] = i-j

如果不在区间里面的话,这时候就是说,可以继承之前的结果,并且把s[i]算进去,因此dp[i] = dp[i-1]+1

2. AC代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        if(length == 0){
            return 0;
        }
        if(length == 1){
            return 1;
        }
        Map<Character,Integer> map = new HashMap<>();
        //定义dp数组
        int[] dp = new int[length];
        dp[0] = 1;
        map.put(s.charAt(0),0);
        int max = 1;
        for(int i = 1;i<dp.length;i++){
            if(map.get(s.charAt(i))!=null){
                Integer j = map.get(s.charAt(i));
                if(dp[i-1] >= i-j){
                    dp[i] = i-j;
                }else{
                    dp[i] = dp[i-1]+1;
                }
            }else{
                dp[i] = dp[i-1]+1;
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

1. 解题思路

这道题问的是方案数,方案数一般都是用动态规划进行求解的

既然是动态规划的话,那么就涉及到状态、选择、状态转移方程了。

状态:既然是字符串问题,那么可以这样定义以s[i]结尾的字符串有dp[i]种翻译方式

选择:选择的,由于这道题求的是最大的翻译方法,因此具有一种贪心的特质,在这种特质下:

如果xixi-1可以被翻译,那么dp[i]=dp[i-1]+dp[i-2]

如果xixi-1不可以被翻译,那么dp[i] = dp[i-1]

下面讲一下这个递推的式子是怎么出来的

dp[i-2]:就是以s[i-2]为结尾的字符串,这个的话其实就是将xixi-1看作为一个整体,这个整体如何翻译是确定的,因此只需要加上dp[i-2]的数量即可

dp[i-1]:就是以s[i-1]为结尾的字符串,这个的话其实就是将xi看作单独一个,这个单独的个体是如何翻译是确定的,因此只需要加上dp[i-1]的数量即可

• base-case

dp[0]=dp[1]=1

2.AC代码

class Solution {
    public int translateNum(int num) {
        //将num变成字符串
        String s = String.valueOf(num);
        int length = s.length();
        if(length == 0){
            return 0;
        }
        int[] dp = new int[length+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i<=length;i++){
            //判断是否可以是一个整体
            int target = (s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0');
            //System.out.println(target);
            if(target <10 || target > 25){
                dp[i] = dp[i-1];
            }else{
                dp[i] = dp[i-1]+dp[i-2];
            }
        }
        return dp[length];
    }
}