剑指offer:45-48记录

举报
兔老大 发表于 2021/04/19 23:10:57 2021/04/19
【摘要】 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" 示例 2: 输入: [3,30,34,5,9] 输出: "3033459"   提示: 0 < nums.length <= 100 说明: 输出结果可能非常大,所以你需要返回一个字符串...

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

示例 1:

输入: [10,2]
输出: "102"
示例 2:

输入: [3,30,34,5,9]
输出: "3033459"
 

提示:

0 < nums.length <= 100
说明:

输出结果可能非常大,所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

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


  
  1. class Solution {
  2. public String minNumber(int[] nums) {
  3. List<String> strList = new ArrayList<>();
  4. for (int num : nums) {
  5. strList.add(String.valueOf(num));
  6. }
  7. strList.sort((s1, s2) -> (s1 + s2).compareTo(s2 + s1));
  8. StringBuilder sb = new StringBuilder();
  9. for (String str : strList) {
  10. sb.append(str);
  11. }
  12. return sb.toString();
  13. }
  14. }

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

 

示例 1:

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

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

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


  
  1. class Solution {
  2. public int translateNum(int num) {
  3. String str = String.valueOf(num);
  4. int len = str.length();
  5. int[] dp = new int[len + 1];
  6. dp[0] = 1;
  7. for (int i = 1; i < len+1; ++i) {
  8. dp[i] += dp[i-1];
  9. if (i>1 && str.charAt(i - 2) != '0' && str.substring(i - 2, i).compareTo("25") < 1)
  10. dp[i] += dp[i - 2];
  11. }
  12. return dp[len];
  13. }
  14. }

在一个 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,来一个超级标准的不压缩空间的一看就懂的写法吧。


  
  1. class Solution {
  2. public int maxValue(int[][] grid) {
  3. if (grid.length == 0 )
  4. return 0 ;
  5. int[][] dp = new int[grid.length][grid[0].length] ;
  6. dp[0][0] = grid[0][0] ;
  7. for (int i=1 ; i<grid.length ; i++) {
  8. dp[i][0] = grid[i][0]+ dp[i-1][0] ;
  9. }
  10. for (int j=1 ; j<grid[0].length ; j++) {
  11. dp[0][j] = grid[0][j] + dp[0][j-1] ;
  12. }
  13. for (int i=1 ; i< grid.length ; i++) {
  14. for (int j=1 ; j < grid[0].length ; j++) {
  15. dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j] ;
  16. }
  17. }
  18. return dp[grid.length-1][grid[0].length-1] ;
  19. }
  20. }

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

 

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
 

提示:

s.length <= 40000

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

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


  
  1. class Solution {
  2. public int lengthOfLongestSubstring(String s) {
  3. int res = 0;
  4. Set<Character> set = new HashSet<>();
  5. for(int l = 0, r = 0; r < s.length(); r++) {
  6. char c = s.charAt(r);
  7. while(set.contains(c)) {
  8. set.remove(s.charAt(l++));
  9. }
  10. set.add(c);
  11. res = Math.max(res, r - l + 1);
  12. }
  13. return res;
  14. }
  15. }

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/104776865

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。