Leetcode剑指Offer刷题指南:
解法一:快排
设数组 nums 中任意两数字的字符串为 x 和 y
若拼接字符串 x + y > y + x ,则 x “大于” y ;
反之,若 x + y < y + x ,则 x “小于” y
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 sb = new StringBuilder();
for (String s : strs) {
sb.append(s);
}
return sb.toString();
}
private void quickSort(String[] strs, int left, int right) {
if (left < right) {
//找基准
int mark = getMark(strs, left, right);
quickSort(strs, left, mark - 1);
quickSort(strs, mark + 1, right);
}
}
private int getMark(String[] strs, int left, int right) {
String tmp = strs[left];
//从后向前找比基准小的数
while (left < right) {
while (left < right && (strs[right] + tmp).compareTo(tmp + strs[right]) >= 0) {
right--;
}
strs[left] = strs[right];
//从前向后找比基准大的数
while (left < right && (strs[left] + tmp).compareTo(tmp + strs[left]) <= 0) {
left++;
}
strs[right] = strs[left];
}
strs[left] = tmp;
return left;
}
}
解法二:小根堆
class Solution {
public String minNumber(int[] nums) {
Queue<String> queue = new PriorityQueue<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//字典序列小的放在堆顶
return (o1 + o2).compareTo(o2 + o1);
}
});
for (int num : nums) {
queue.add("" + num);
}
StringBuilder res = new StringBuilder();
while (!queue.isEmpty()) {
res.append(queue.poll());
}
return res.toString();
}
}
解法一:Set + 遍历
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> set = 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);
// 若有重复,提前返回 false
if (set.contains(num)) {
return false;
}
// 添加此牌至 Set
set.add(num);
}
// 最大牌 - 最小牌 < 5 则可构成顺子
return max - min < 5;
}
}
解法二:排序 + 遍历
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]) {
// 若有重复,提前返回 false
return false;
}
}
// 最大牌 - 最小牌 < 5 则可构成顺子
return nums[4] - nums[joker] < 5;
}
}
文章评论