剑指Offer.46-把数字翻译成字符串&48-最长不含重复字符的子字符串
剑指Offer.46-把数字翻译成字符串&
剑指Offer.48-最长不含重复字符的子字符串
剑指 Offer 46. 把数字翻译成字符串
思路
该题是一道将数字翻译为字符串的题目,是斐波那契数列的变种问题。需要找到斐波那契数列的递进关系
状态转移方程组
情况1：当读取第一个数字的时候一定能够被翻译为1个字母，故dp[0]=1,dp[1]=1，当读取到第二个字母时，若其与前一个数字组合无法被翻译成新的字母时，此时依旧只有1种翻译的方法，dp[i]=dp[i-1]
当第二个字母能够与第一个字母一起被翻译为一个字母时，dp[i] = dp[i-2] + dp[i-1]
1
2
| f(i) = f(i-2) + f(i-1)
f(i) = f(i-1)
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int dp[] = new int[s.length() + 1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=s.length() ;i++){
String subNum = String.valueOf(s.charAt(i-2));
subNum += s.charAt(i-1);
Integer snum = Integer.parseInt(subNum);
if(snum >=10 && snum <= 25){
dp[i] = dp[i-1] + dp[i-2];
} else{
dp[i] = dp[i-1];
}
}
return dp[s.length()];
}
}
|
剑指 Offer 48. 最长不含重复字符的子字符串
问题描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度
状态转移方程
首先定义f(i)表示以第i个字符结尾不包含重复字符的最长子串长度，当第i个字符在之前没有出现过时，f(i)=f(i-1)+1直接进行加1操作。
当第i个字符已经出现过，需要分两种情况进行讨论，首先计算第i个字符距离上次出现的字符的距离，将其记为d,这意味着两个重复字符之间的子串中没有其他重复的字符。当d小于或者等于f(i-1)时，等于上次字符出现的位置在f(i-1)对应的子串中，新无重复最大子串的长度即为d。
当d大于f(i-1)时，证明上次该字符上次出现的位置不在上个无重复最长子串中，可直接在其后进行追加，故此时f(i)=f(i-1)+1，将条件合并后得到状态转移方程。
1
2
| dp[i] = dp[i-1]+1
dp[i] = j-i
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<>();
int res = 0,tmp = 0;
for(int j=0;j<s.length();j++){
int i = map.getOrDefault(s.charAt(j),-1);
map.put(s.charAt(j),j);
tmp = tmp < j - i?tmp+1:j-i;
res = Math.max(res,tmp);
}
return res;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> window = new HashMap<Character,Integer>();
int left = 0;
int right = 0;
int max = 0;
while(right < s.length()){
Character r = s.charAt(right);
right++;
if(window.containsKey(r)){
window.put(r,window.get(r)+1);
}else{
window.put(r,1);
}
while(window.get(r) > 1){
Character l = s.charAt(left);
left++;
window.put(l,window.get(l)-1);
}
max = Math.max(right-left,max);
}
return max;
}
}
|