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;i<indices.length;i++) {
            chars[indices[i]] = s.charAt(i);
        }

        return new String(chars);
    }
}

1502. 判断能否形成等差数列

给你一个数字数组 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;i<arr.length;i++) {
            if (i+2 < arr.length) {
                //可进行等差中项判断的条件
                if (arr[i] + arr[i+2] != arr[i+1]*2) {
                    return false;  //不满足返回结果
                }
            }
        }

        return true;
    }
}

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

题解：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> jiaoji = new HashSet<>();
        for (int i=0;i<nums1.length;i++) {
            for (int j=0;j<nums2.length;j++) {
                if (nums1[i] == nums2[j]) {
                    jiaoji.add(nums1[i]);
                    break;
                }
            }
        }

        int[] jiaojiArray = new int[jiaoji.size()];
        int pos = 0;
        Iterator iterator = jiaoji.iterator();
        while (iterator.hasNext()) {
            jiaojiArray[pos] = (int) iterator.next();
            pos++;
        }

        return jiaojiArray;
    }
}

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<arr.length;i++) {
            //获取当前该数的二进制1的个数
            int count = Integer.bitCount(arr[i]);
            //因为0 <= arr[i] <= 10^4
            arrays[i] = count*100000 + arr[i];   
        }

        Arrays.sort(arrays);

        for (int i=0;i<arrays.length;i++) {
            arrays[i] = arrays[i]%100000;
        }

        return arrays;
    }
}