最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球快看：动态规划解决最值、有多少方案之类问题

来源：博客园

问题一：最长不包含重复字符的子字符串剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）

分析：dp[ i ] 代表以字符 s[ i ] 结尾的 最长不重复子字符串 的长度；对于 i，向前查找最近的相同字符 s[ j ] ,s[ i ] ==s[ j ] ;

对于j，若其 < 0 , 则说明无相同字符，那么 dp[ i ] = dp[ i -1] + 1；


【资料图】

若dp[ i -1] < i - j ;说明相同的字符在区间之外， 此时dp[ i ] = dp[ i -1] + 1；

若dp[ i -1] >= i - j ，说明相同的字符 在区间之内，此时，dp[ i ] = i - j ；

针对第一种情况，可以合并到第二种情况中，因 j < 0 ,dp[ i -1] < i 恒成立，那么dp[ i -1] < i - j 也成立。

思路1： 动态规划 + 线性遍历

每一轮内，向前遍历最近的相同字符，此处 c 就相当于 dp[ i] ;节省空间

时间复杂度 ：O( N2) ; 空间复杂度 ： O( 1);

class Solution {public:    int lengthOfLongestSubstring(string s) {        int a = 0;        int c = 0;        for(int i = 0;i < s.size(); ++i){            int j = i -1;            while(j >= 0 && s[j] != s[i]) --j;            if(i - j > a) a += 1;            else a = i - j;             c = max(c , a);        }        return c;    }};

思路2 ： 动态规划 + 哈希表

哈希表存放最后一次字符出现的位置，

时间复杂度 ：O( N) ; 空间复杂度 ： O( 1);

class Solution {public:    int lengthOfLongestSubstring(string s) {        unordered_mapmp;        int res = 0, tmp = 0,j = 0;        for(int i =0;i < s.size(); ++i){            if(mp.find(s[i]) == mp.end() ) j = -1;            else j = mp[s[i]];            mp[s[i]] = i;            tmp = i - j > tmp ? tmp +1 : i - j;            res = max(res,tmp);        }        return res;    }};

问题二：把数字翻译成字符串剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode）

分析：dp[ i ] 代表以字符 Xi结尾的 翻译方案数量；考虑到 xi和xi-1组成的两位数字可以被翻译；

当可以组合翻译时，除去xi和 xi-1，前面的 x0 -xi-2翻译方案为 dp[ i-2] ；当单独翻译时，除去 xi，前面的 x0-xi-1，翻译方案数量为 dp[i-1] ,

组合翻译对应的数字区间为[10，25]，则 dp[ i ] = dp[ i -1] +dp[ i -2] ；

否则dp[ i ] =dp[ i -1] ；

初始状态：dp[ 0 ] = dp[ 1] = 1; 代表空数组和 一个 数字的翻译方案为1；

思路1 ： 字符串遍历，时间复杂度、空间复杂度都为O(N)

先将数字num转化为字符串 s； 字符串切片比较最后两个字符，与 字符 ‘1’ 或者‘2’ 和 ‘5’，

class Solution {public:    int translateNum(int num) {        string s = to_string(num);        int a =1,b=1;        int c;        for(int i = 2; i <= s.size(); ++i){            string tmp = s.substr(i-2,2);            if(tmp[0] == "1" || tmp[0] == "2" && tmp[1] <= "5") c = a +b;            else c = a;            b = a;            a = c;        }        return a;    }};

思路2 ： 从右向左不断 取余

class Solution {public:    int translateNum(int num) {        int res = num % 10;        num /= 10;        int a = 1,b =1,c =0;        while(num){            int x = num % 10;            num /= 10;            int tmp = x * 10 + res;            if(tmp >= 10 && tmp <= 25) c = a + b;            else c = a;            b = a;            a = c;            res = x;        }        return a;    }};

关键词： 动态规划 时间复杂度 空间复杂度