把数字翻译成字符串

题目描述

思路

动态规划+自下而上

状态转换方程：根据逼近结果的可能性来切入

db[n]=db[n-1]+db[n-2] 如果在[10,25]

db[n]=db[n-1] 如果在[0,10)或(25,max]

边界点：

db[0]=db[1]=1

返回结果：

db[n]

代码实现

class Solution {
    public int translateNum(int num) {
        String num_=num+"";
        int db1=1,db2=1;
        //注意subString()不包括结束索引
        for(int i=2;i<=num_.length();i++){
            String tmp=num_.substring(i-2,i);
            if(tmp.compareTo("10")>=0&&tmp.compareTo("25")<=0){
                int tmp_=db1;
                db1+=db2;
                db2=tmp_;
            }else{
                db2=db1;
            }
        }
        return db1;
    }
}

复杂度分析

时间复杂度

O(N)

空间复杂度

O(N)

反思不足

思路

根据逼近结果可能性切入，差不多想到了状态转换方程，但没有特别清晰

分类时也没考虑到0x的情况

java se

String

compareTo(String)方法可以按字典序比较两个字符串的大小,等0小负大正

substring(int,int)截取字符串，不包含右

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

题目描述

思路

动态规划+哈希表

要不断更新最近连续字符串的长度，并且与最大长度进行比较更新

如果更新最近连续字符串的长度，分情况，如果当前字符非重复，直接+1，如果重复，则要得到上个重复字符后面的字符长度并+1，这个可以通过减索引实现。

通过索引间的差值也可以起到判定是不是在最近连续子字符串内。

状态转换方程就在文字中

动态规划+线性遍历

不用哈希表存储上次元素的位置，而是从头到尾挨个找

双指针+哈希表

两个指针，一个用于维护不重复指针的左边界，一个用于向前开拓不重复子字符串的长度，并根据二者的差值实时更新最大值

双指针在维护边界这件事上可谓是如鱼得水

代码实现

动态规划+哈希表

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null){
            return 0;
        }
        int max=0;
        int lastLen=0,len=0;
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(!map.containsKey(c)){
                map.put(c,i);
                len=lastLen+1;
            }else{
                int t=i-map.get(c);
                if(t>lastLen) len=lastLen+1;
                else {
                    len=t;
                }
                map.replace(c,i);
            }
            if(max<len) {
                max=len;
            }
            
            lastLen=len;
        }
        return max;
    }
}

双指针+哈希表

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        for(int j = 0; j < s.length(); j++) {
            if(dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

复杂度分析

时间复杂度

动态规划+哈希表为O(N)，线性遍历则是O(N^2)

空间复杂度

动态规划+哈希表/线性遍历为O(1)，不是O(N)，因为字符的个数是有限的，是用字符做key

反思不足

思路

在确定迭代方程上仍是差一点，可能是见得不够多，也可能真的是不知道该怎么分析，以逼近结尾的可能性分类讨论，确实是很好的切入手段

java se

String

toCharArray()如果是null会空指针异常

replace()方法用于替换键对应的值

原文地址：http://www.cnblogs.com/zhouj-learn/p/16795012.html