剑指 Offer 45. 把数组排成最小的数 难度:medium
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
此题求拼接起来的最小数字,本质上是一个排序问题。设数组 nums 中任意两数字的字符串为 x 和 y ,则规定 排序判断规则 为:
根据以上规则,套用任何排序方法对 nums 执行排序即可。
Python:
class Solution:
def minNumber(self, nums: List[int]) -> str:
def quick_sort(l , r):
if l >= r: return
i, j = l, r
while i < j:
while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1
while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1
strs[i], strs[j] = strs[j], strs[i]
strs[i], strs[l] = strs[l], strs[i]
quick_sort(l, i - 1)
quick_sort(i + 1, r)
strs = [str(num) for num in nums]
quick_sort(0, len(strs) - 1)
return ''.join(strs)
Java:
class Solution {
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);
}
}
剑指 Offer 61. 扑克牌中的顺子 难度:easy
从若干副扑克牌中随机抽 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
根据题意,此 5 张牌是顺子的 充分条件 如下:
max−min<5
因而,可将问题转化为:此 55 张牌是否满足以上两个条件?
Python:
class Solution:
def isStraight(self, nums: List[int]) -> bool:
joker = 0
nums.sort() # 数组排序
for i in range(4):
if nums[i] == 0: joker += 1 # 统计大小王数量
elif nums[i] == nums[i + 1]: return False # 若有重复,提前返回 false
return nums[4] - nums[joker] < 5 # 最大牌 - 最小牌 < 5 则可构成顺子
Java:
class Solution {
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 则可构成顺子
}
}