数据结构和算法二十四

剑指 Offer 45. 把数组排成最小的数

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

示例 1:
         输入: [10,2]
         输出: “102”
示例 2:
         输入: [3,30,34,5,9]
         输出: “3033459”
提示:
         0 < nums.length <= 100
说明:
     1、输出结果可能非常大,所以你需要返回一个字符串而不是整数
     2、拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
解题思路:
此题求拼接起来的最小数字,本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y ,则规定排序判断规则为:

  • 若拼接字符串x+y>y+x ,则x “大于” y ;

  • 反之,若x+y<y+x ,则x “小于” y ;

x “小于” y 代表:排序完成后,数组中x应在y左边;“大于” 则反之。

根据以上规则,套用任何排序方法对nums执行排序即可。
数据结构和算法二十四
算法流程:

  • 初始化: 字符串列表strs ,保存各数字的字符串格式;
  • 列表排序: 应用以上 “排序判断规则” ,对strs执行排序;
  • 返回值: 拼接strs中的所有字符串,并返回。

复杂度分析:

  • 时间复杂度O(NlogN) : N为最终返回值的字符数量(strs列表的长度≤N );使用快排或内置函数的平均时间复杂度为O(NlogN) ,最差为 O(N^2) 。
  • 空间复杂度O(N) : 字符串列表strs占用线性大小的额外空间。

代码:
在此列举 快速排序内置函数 两种排序方法,其他排序方法也可实现。

快速排序

需修改快速排序函数中的排序判断规则。字符串大小(字典序)对比的实现方法:Java 中使用函数 A.compareTo(B);

class Method1{
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void quickSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }
}

内置函数

需定义排序规则:Java定义为 (x, y) -> (x + y).compareTo(y + x) ;

class Method2{
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
}

剑指 Offer 61. 扑克牌中的顺子

题目:从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

示例 1:
         输入: [1,2,3,4,5]
         输出: True
示例 2:
         输入: [0,0,1,2,5]
         输出: True
限制:
         1、数组长度为 5
         2、数组的数取值为 [0, 13].
解题思路:
根据题意,此5张牌是顺子的 充分条件 如下:

除大小王外,所有牌 无重复 ;
设此5张牌中最大的牌为max ,最小的牌为min(大小王除外),则需满足:max−min<5

因而,可将问题转化为:此5张牌是否满足以上两个条件?
数据结构和算法二十四
方法一: 集合 Set + 遍历遍历五张牌,遇到大小王(即0)直接跳过。

  • 判别重复: 利用 Set 实现遍历判重, Set 的查找方法的时间复杂度为O(1) ;
  • 获取最大 / 最小的牌: 借助辅助变量ma和mi ,遍历统计即可。

复杂度分析:

  • 时间复杂度O(N)=O(5)=O(1) : 其中N为nums长度,本题中N≡5 ;遍历数组使用O(N) 时间。
  • 空间复杂度O(N)=O(5)=O(1) : 用于判重的辅助 Set 使用O(N) 额外空间。

数据结构和算法二十四

代码:

class Method1{
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums) {
            if(num == 0) continue; // 跳过大小王
            max = Math.max(max, num); // 最大牌
            min = Math.min(min, num); // 最小牌
            if(repeat.contains(num)) return false; // 若有重复,提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

方法二:排序 + 遍历
先对数组执行排序。

  • 判别重复: 排序数组中的相同元素位置相邻,因此可通过遍历数组,判断nums[i]=nums[i+1] 是否成立来判重。
  • 获取最大 / 最小的牌: 排序后,数组末位元素nums[4] 为最大牌;元素nums[joker]为最小牌,其中joker 为大小王的数量。

复杂度分析:

  • 时间复杂度O(NlogN)=O(5log5)=O(1) : 其中N为nums长度,本题中N≡5 ;数组排序使用O(NlogN) 时间。
  • 空间复杂度O(1) : 变量joker使用O(1)大小的额外空间。

数据结构和算法二十四

代码:

class Method2{
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; // 统计大小王数量
            else if(nums[i] == nums[i + 1]) return false; // 若有重复,提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

总结:

      又是一天过去了,学习需要不停的坚持!其实我们的生活当中处处都是知识!用罗曼·罗兰的话来说就是:“生活中不是缺少美,而是缺少发现美的眼睛”。用物理中的熵增定律来说:“我们其实一直在和熵值在做斗争”!用古话来说就是:“处处留心皆学问,人情练达即文章”!放弃很简单!但是坚持下来是特别难的!但是如果坚持下来了!那定将会有收获的!
      世界上最煎熬的事情莫过于:等待和羁绊,为什么呢?因为都会耗费大量的时间去做,但又不得不做的事,然后感觉还没有收获!不知道小伙伴们是否也有同样的感觉呢?就好比:等的时候总觉得时间在悄悄地溜走,然后想做别的事情又无法去做,等到想做的时候却又没有当时的那种感觉了。再过一段时间又会后悔当时为什么没有去做!可能这就是想和做的本质区别吧!也是将来时和现在时的区别吧!过去已经过去,已经无法挽回!只能立足于现在来规划未来,然后一步一步的去落实!剩余的就靠自己去领悟了!
      最后,愿我们都能在各行各业中能够取得不同的成就,不负亲人、朋友、老师、长辈和国家的期望!能够用自身的所学知识为国家贡献出自己的一份力量!一起加油!
                                                                                                                                                      2021年5月10日夜

上一篇:Python验证的50个常见正则表达式


下一篇:jstl标签库