把数字翻译成字符串
剑指 Offer 46. 把数字翻译成字符串 - 力扣（Leetcode）
题目要求
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
例子：
1
2
3
| 输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
|
提示：
思路分析
动态规划
- dp[i]含义：长度位
i时一共有dp[i]种翻译方案；
- 求关系式：
- dp[i] = dp[i-1] + dp[i-2]; (10<= temp <= 25)
- dp[i] = dp[i-1];
- 初始值：dp[0] = 1 dp[1] = 1;
不使用dp数组：通过斐波那契数列：f(n) = f(n-1) + f(n-2);
代码实现
动态规划
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 translateNum(int num) {
if(num <= 9){
return 1;
}
char[] arr = String.valueOf(num).toCharArray();
int len = arr.length;
int[] dp = new int[len+1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=len;i++){
int temp = 10 * (arr[i-2] - '0') + (arr[i-1] - '0');
if(temp>=10 && temp <= 25){
dp[i] = dp[i-1] + dp[i-2];
}else{
dp[i] = dp[i-1];
}
}
return dp[len];
}
}
|
动态规划+不使用dp数组
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
29
| class Solution {
public int translateNum(int num) {
if(num <= 9){
return 1;
}
char[] arr = String.valueOf(num).toCharArray();
int len = arr.length;
int a = 1,b = 1,c = 1;
for(int i=2;i<=len;i++){
int temp = 10 * (arr[i-2] - '0') + (arr[i-1] - '0');
if(temp>=10 && temp <= 25){
c = a + b;
}else{
c = b;
}
a = b;
b = c;
}
return c;
}
}
|
礼物的最大价值
剑指 Offer 47. 礼物的最大价值 - 力扣（Leetcode）
题目要求
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
例子：
1
2
3
4
5
6
7
8
| 输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
|
提示：
0 < grid.length <= 2000 < grid[0].length <= 200
思路分析
动态规划
-
dp[i][j] 的含义：当走到ij这个位置时，礼物最大价值位dp[i][j];
-
关系式：dp[i][j] = max(dp[i-1][j] ,dp[i][j-1]) + grid[i][j];
-
初始值：
-
dp[0][0] = grid[0][0];
-
for循环遍历：
拓展：将二维数组转换位一维数组，一行一样来计算；
代码实现
动态规划
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 maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int j=1;j<n;j++){
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
}
|
拓展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] dp = new int[n];
dp[0] = grid[0][0];
for(int j=1;j<n;j++){
dp[j] = dp[j-1] + grid[0][j];
}
for(int i=1;i<m;i++){
dp[0] = dp[0] + grid[i][0];
for(int j=1;j<n;j++){
dp[j] = Math.max(dp[j],dp[j-1])+grid[i][j];
}
}
return dp[n-1];
}
}
|
最长不含重复字符的子字符串
剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（Leetcode）
题目要求
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
例子：
1
2
3
4
5
6
7
8
9
10
11
12
| 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
提示：
思路分析
动态规划
-
dp数组含义：当字符串s[i]结尾时，不含重复字符的子字符串长度为dp[i]；
-
关系式：
是否在区间出现，假设出现过且下标为k；
- dp[i] = dp[i-1] +1; (i-k > dp[i-1])
- dp[i] = i - k; (i-k <= dp[i-1])
-
初始值：dp[0] = 1;
拓展：dp数组可以优化为单个变量，因为我们只用到了dp[i-1]，例如dp[i-2],dp[i-3]都没有使用，产生了浪费；
代码实现
动态规划
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
29
30
| class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() <= 0){
return 0;
}
Map<Character,Integer> map = new HashMap<>();
int[] dp = new int[s.length()];
int res = 1;
dp[0] = 1;
map.put(s.charAt(0),0);
for(int i=1;i<s.length();i++){
if(!map.containsKey(s.charAt(i))){
dp[i] = dp[i-1] +1;
}else{
int k = map.get(s.charAt(i));
dp[i] = i - k <= dp[i-1] ? i-k : dp[i-1] + 1;
}
res = Math.max(res,dp[i]);
map.put(s.charAt(i),i);
}
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
29
30
| class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() <= 0){
return 0;
}
Map<Character,Integer> map = new HashMap<>();
int dp = 1;
int res = 1;
map.put(s.charAt(0),0);
for(int i=1;i<s.length();i++){
if(!map.containsKey(s.charAt(i))){
dp = dp+1;
}else{
int k = map.get(s.charAt(i));
dp= i - k <= dp? i-k : dp+ 1;
}
res = Math.max(res,dp);
map.put(s.charAt(i),i);
}
return res;
}
}
|
丑数
剑指 Offer 49. 丑数 - 力扣（Leetcode）
题目要求
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
例子：
1
2
3
| 输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
|
提示：
1 是丑数。n 不超过1690。
思路分析
动态规划
- dp数组含义：dp[i]表示第i个丑数；
- 关系式：dp[i] = min(dp[a]x2,dp[b]x3,dp[c]x5);
- 初始值：dp[1] = 1;
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int nthUglyNumber(int n) {
int a=1,b=1,c=1;
int[] dp = new int[n+1];
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
if(dp[i] == dp[a]*2) a++;
if(dp[i] == dp[b]*3) b++;
if(dp[i] == dp[c]*5) c++;
}
return dp[n];
}
}
|
第一个只出现一次的字符
剑指 Offer 50. 第一个只出现一次的字符 - 力扣（Leetcode）
题目要求
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
例子：
1
2
3
4
5
| 输入：s = "abaccdeff"
输出：'b'
输入：s = ""
输出：' '
|
提示：
0 <= s 的长度 <= 50000
思路分析
有序哈希表
通过遍历所给字符串，使用哈希表存放字符以及使用boolean值标记它出现的情况(因为只要出现次数超过1次以上就不符合条件了，因此使用boolean进行标记比使用Integer更合理且节省空间，还能简化代码逻辑)，最后将第一个出现且只出现一次的返回即可；
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public char firstUniqChar(String s) {
if(s==null || s.length() <=0){
return ' ';
}
Map<Character,Boolean> map = new LinkedHashMap<>();
for(int i=0;i<s.length();i++){
map.put(s.charAt(i),!map.containsKey(s.charAt(i)));
}
for(Map.Entry<Character,Boolean> m:map.entrySet()){
if(m.getValue()){
return m.getKey();
}
}
return ' ';
}
}
|
微信
