剑指offer：45-48记录

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]

输出: "102"

示例 2:

输入: [3,30,34,5,9]

输出: "3033459"

提示:

0 < nums.length <= 100

说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数

拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

思路：贪心，具体证明略，其他文章写过。

class Solution {

public String minNumber(int[] nums) {

List strList = new ArrayList<>();

for (int num : nums) {

strList.add(String.valueOf(num));

}

strList.sort((s1, s2) -> (s1 + s2).compareTo(s2 + s1));

StringBuilder sb = new StringBuilder();

for (String str : strList) {

sb.append(str);

}

return sb.toString();

}

}

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

示例 1:

输入: 12258

输出: 5

解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

字符串dp，看代码很容易看懂。

注意str.charAt(i - 2) != '0'必须加上，不加的例子：

class Solution {

public int translateNum(int num) {

String str = String.valueOf(num);

int len = str.length();

int[] dp = new int[len + 1];

dp[0] = 1;

for (int i = 1; i < len+1; ++i) {

dp[i] += dp[i-1];

if (i>1 && str.charAt(i - 2) != '0' && str.substring(i - 2, i).compareTo("25") < 1)

dp[i] += dp[i - 2];

}

return dp[len];

}

}

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

输出: 12

解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

0 < grid.length <= 200

0 < grid[0].length <= 200

思路：经典dp，来一个超级标准的不压缩空间的一看就懂的写法吧。

class Solution {

public int maxValue(int[][] grid) {

if (grid.length == 0 )

return 0 ;

int[][] dp = new int[grid.length][grid[0].length] ;

dp[0][0] = grid[0][0] ;

for (int i=1 ; i

dp[i][0] = grid[i][0]+ dp[i-1][0] ;

}

for (int j=1 ; j

dp[0][j] = grid[0][j] + dp[0][j-1] ;

}

for (int i=1 ; i< grid.length ; i++) {

for (int j=1 ; j < grid[0].length ; j++) {

dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j] ;

}

}

return dp[grid.length-1][grid[0].length-1] ;

}

}

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

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

s.length <= 40000

滑动窗口的维护五花八门：

for循环往右扩，左端点起辅助作用，保证窗口符合要求：

class Solution {

public int lengthOfLongestSubstring(String s) {

int res = 0;

Set set = new HashSet<>();

for(int l = 0, r = 0; r < s.length(); r++) {

char c = s.charAt(r);

while(set.contains(c)) {

set.remove(s.charAt(l++));

}

set.add(c);

res = Math.max(res, r - l + 1);

}

return res;

}

}

机器翻译

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。