贪心&比较器

# 561. 数组拆分 (opens new window)

class Solution {
    public int arrayPairSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for(int i=0;i<n;i+=2){
            ans += nums[i];
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 406. 根据身高重建队列 (opens new window)

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //按第一个元素降序，第二个元素升序
        Arrays.sort(people,(a,b)->{
            if(a[0]==b[0]){
                return a[1]-b[1];
            }
            return b[0]-a[0];
        });
        List<int[]> que = new LinkedList<>();
        for(int[] p:people){
            que.add(p[1],p);//p[1]位置放p
        }
        return que.toArray(new int[people.length][2]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 179. 最大数 (opens new window)

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] ss = new String[n];
        for(int i=0;i<n;i++)
            ss[i] = ""+nums[i];
        Arrays.sort(ss,(a,b)->{
            String sa = a+b,sb = b+a;
            return sb.compareTo(sa);
        });
        StringBuilder sb = new StringBuilder();
        for(String s:ss)
            sb.append(s);
        int len = sb.length();
        // 前导0删了
        int k = 0;
        while(k<len-1 && sb.charAt(k)=='0')
            k++;
        return sb.substring(k);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

← 贪心贪心&堆→