LeetCode刷题之排序
1528. 重新排列字符串
给你一个字符串 s 和一个 长度相同 的整数数组 indices 。
请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。
返回重新排列后的字符串。
示例 1：
输入：s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出："leetcode"
解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。
题解：
class Solution {
/**
* 思路：
* 创建一个字符数组，从字符串中依次取出一个字符，存入字符数组对应位置中，该对应位置为indices[i]
*/
public String restoreString(String s, int[] indices) {
char[] chars = new char[indices.length];
for (int i=0;i1502. 判断能否形成等差数列
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
示例 1：
输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
题解：
class Solution {
/**
* 思路：
* 先对数组排序，然后判断每两个相邻数字相差值是否为一个相等的常数
* @param arr
* @return
*/
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr); //直接用Arrays工具类排序
//利用等差中项性质判断是否为等差数列
for (int i=0;i349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
题解：
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet jiaoji = new HashSet<>();
for (int i=0;i 1356. 根据数字二进制下 1 的数目排序
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
示例 1：
输入：arr = [0,1,2,3,4,5,6,7,8]
输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
示例 2：
输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出：[1,2,4,8,16,32,64,128,256,512,1024]
解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。
题解：
class Solution {
/**
* 思路：
* 遍历arr数组，获取每一个数的二进制数1的个数，然后*100000+arr[i]，将该数依次存入整形数组中，
* 然后对该数组进行排序，该排序方式就是依据1的个数数量来排序的。
* 然后对100000进行取余，得到arr[i]原数值
* @param arr
* @return
*/
public int[] sortByBits(int[] arr) {
int[] arrays = new int[arr.length];
for (int i=0;i救生艇
给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
题解：
class Solution {
/**
* 思路分析：想要船只最小化，每艘船要尽可能地先保证装到limit重量
* 问题：有没有可能，某个人的重量是大于limit的，需要一只脚踏两条船
*
* 先对people排序，然后用两个指针分别指向体重最轻和体重最重的人
* 如果最重的和一个最轻的都不能坐一艘船，那么就没人能跟这个最终的坐一艘船了，
* 如果当前最重和最轻的能共乘一条船，那么就给他俩安排一艘船
*/
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int start = 0;
int boatCount = 0;
int end = people.length-1;
while(start limit) {
//超出重量，给最重的人分一条船，让他走
boatCount++;
end--;
} else {
//此时最轻和最重的可以乘坐一条船走
boatCount++;
start++;
end--;
}
}
if(start == end) {
//还剩下一个人
boatCount++;
}
return boatCount;
}
}
面试题61. 扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
题解：
class Solution {
/**
* 思路：先把数组中的0取出来，同时将各个数添加到集合中
* 判断跟后面的数是否连续，如果不连续，则要消耗一个0，直到0消耗完成
*/
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int zeroCount = 0;
List list = new ArrayList<>();
for (int i=0;i 0) {
zeroCount--;
//插入当前正确数据，继续验证
list.add(i+1, list.get(i) + 1);
} else {
return false;
}
}
}
return true;
}
}
共有 0 条评论