小yi的blog

从前很忙

算法练习

发表于 阅读次数： Valine：
本文字数： 16k 阅读时长 ≈ 15 分钟
  • 说明：题目来源网络，由于本人水平有限，代码可能存在错误

笔试题

字节：链接

存在n+1个房间，每个房间依次为房间1 2 3…i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] strategy = new int[n + 1];
        for(int i = 1; i <= n; i++){
            strategy[i] = scanner.nextInt();
        }
        System.out.println(step(n, strategy));
    }
    private static long step(int n, int[] strategy){
        //思路：到达i时，i前面的所有房间必定访问了偶数次
        long[] dp = new long[n + 2];//存储第一次到房间i所需步数
        dp[1] = 0;
        if(n == 1)return 1;
        long mod = 1000000007;
        for(int i = 2; i <= n + 1; i++){
            //dp[i] = dp[i-1] + dp[i-1] + 1 - dp[p[i-1]] + 1
            dp[i] = (2*dp[i - 1])%mod - dp[strategy[i - 1]] + 2;
        }
        return dp[n + 1]%mod;
    }
}

面试题

排序算法

image-20210206204838244

冒泡排序

沉石法，大的往后交换。

优化：外循环每次判断上次是否发生交换，如果没交换可以提前结束排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 9, 1};
        sort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    public static void sort(int[] arr){
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            for(int j = 0; j < len - i - 1; j++){//注意这里的len - i - 1
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

选择排序

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组 的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。 选择排序需要 ~N2 /2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要 这么多的比较和交换操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 9, 1};
        sort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void sort(int[] arr){
        int len = arr.length;
        for(int i = 0; i < len; i++){
            int min = i;
            for(int j = i + 1; j < len; j++){
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            swap(arr, min, i);
        }
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻 元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class InserSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 9, 1};
        sort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void sort(int[] arr){
        int len = arr.length;
        for(int i = 1; i < len; i++){//从第1个往前插
            for(int j = i; j > 0; j--){
                if(arr[j] < arr[j - 1]){
                    swap(arr, j, j - 1);
                }
            }
        }
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

归并排序

  • 思路：使用递归分别排好左右两侧顺序，再使用merge合并，将排好序的help数组拷贝进原数组对应位置
  • 思想：分治
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 9, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void sort(int[] arr, int low, int high){
        if(low == high) return; 

        int mid = low + (high - low)/2;

        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
    private static void merge(int[] arr, int left, int mid, int right){
        int[] temp = new int[right - left + 1];
        int p1 = left;
        int p2 = mid + 1;
        int i = 0; //temp下标
        while(p1 <= mid && p2 <= right){
            temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];  
        }
        //剩余部分:两个之一
        while(p1 <= mid){
            temp[i++] = arr[p1++];
        }
        while(p2 <= right){
            temp[i++] = arr[p2++];
        }
        for(int j = 0; j < temp.length; j++){
            arr[left + j] = temp[j];
        }
    }
}

快速排序

  • 经典快排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class ClassicQuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 9, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void sort(int[] arr, int l, int r){
        if(l < r){
            int p = partition(arr, l, r);
            sort(arr, l, p - 1);
            sort(arr, p + 1, r);
        }
    }
    private static int partition(int[] arr, int l, int r){
        int less = l - 1;
        while(l < r){
            if(arr[l] < arr[r]){
                swap(arr, ++less, l++);
            }else{
                l++;
            }
        }
        swap(arr, less + 1, r);
        return less + 1;
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
  • 随机快排 + 荷兰国旗三向切分partition优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 9, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void sort(int[] arr, int left, int right){
        if(left >= right) return;//靠，这里很关键，必须判断大小，不然下面返回的less、more可能会越界
        int x = left + (int) (Math.random() * (right - left + 1));
        swap(arr, x, right);
        int[] p = partition(arr, left, right);
        sort(arr, left, p[0]);
        sort(arr, p[1], right);       
    }
    private static int[] partition(int[] arr, int left, int right){
        int less = left - 1;
        int more =  right;
        while(left < more){
            if(arr[left] < arr[right]){
                swap(arr, ++less, left++);
            }else if( arr[left] > arr[right]){
                swap(arr, --more, left);
            }else{
                left++;
            }
        }
        swap(arr, more, right);
        return new int[]{less, more + 1};
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

堆排序

  • 创建一个堆 H[0……n-1]；
  • 创建一个大根堆
  • 堆顶和堆尾交换：即每次把最大值放在最后
  • 重复第三步骤

多种实现方式：个人觉得下面方式最为简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 9, 1};
        buildMaxHeap(arr);
        for(int i = arr.length - 1; i > 0; i--){
            swap(arr, i, 0);
            heapify(arr, 0, i);
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void buildMaxHeap(int[] arr){
        // int len = arr.length;
        // for(int i = 0; i < len; i++){//heapInsert：向上调整
        //     while(arr[i] > arr[(i - 1) / 2]){
        //         swap(arr, i, (i - 1) / 2);
        //         i = (i - 1) / 2; 
        //     }
        // }
        for(int i = arr.length/2; i >= 0; i--){
            heapify(arr, i, arr.length);
        }
        
    }
    private static void heapify(int[] arr, int i, int heapSize){
        // int l = i * 2 + 1;       
        // while(l < heapSize){//非递归实现
        //     int large = l + 1 <= heapSize && arr[l] > arr[l + 1] ? l : l + 1;
        //     large = arr[large] > arr[i] ? large : i;
        //     if(large == i) break;//自己最大，退出
        //     swap(arr, large, i);
        //     i = large; //新node
        //     l = i * 2 + 1; //新左儿子
        // }
        int l = i * 2 + 1, r = i * 2 + 2, largest = i; //l:左孩子，r：右孩子，i:父节点
        if (l < heapSize && arr[l] > arr[largest]) {
            largest = l; //先与左孩子比较
        } 
        if (r < heapSize && arr[r] > arr[largest]) {
            largest = r;//再与右孩子比较
        }
        if (largest != i) {//如果孩子节点更大，交换
            swap(arr, i, largest);
            heapify(arr, largest, heapSize); //递归调整下一个子树
        }
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

LeetCode

双指针

有序数组的 Two Sum
  • 题目描述：在有序数组中找出两个数，使它们的和为 target。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class TwoSum {
    //题目描述：在有序数组中找出两个数，使它们的和为 target。
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 6};
        int[] ans = solution(arr, 8);
        for (int i : ans) {
            System.out.println(arr[i]);
        }
    }
    private static int[] solution(int[] arr, int target){
        int len = arr.length;
        int l = 0, r = len - 1;
        while(l < r){
            if(arr[l] + arr[r] > target){
                r--;
            }else if(arr[l] + arr[r] < target){
                l++;
            }else{
                break;
            }
        }
        return new int[]{l, r};
    }
}
两数平方和
  • 题目描述：判断一个数是否为两个数的平方和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class SumOfSquare{
    // 题目描述：判断一个数是否为两个数的平方和。
    public static void main(String[] args) {
        int a = 4;
        int b = 5;
        int c = 3;
        System.out.println(solution(a));
        System.out.println(solution(b));
        System.out.println(solution(c));
    }
    private static boolean solution(int num){
        int i = 0;
        // int j = num/2;
        int j = (int) Math.sqrt(num);
        while(i <= j){
            if(i * i + j * j == num){
                return true;
            }else if(i * i + j * j > num){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }
}
反转字符串中的元音
  • 使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;
public class ReverseVowelOfString {
    //编写一个函数，该函数将字符串作为输入，并且仅反转字符串的元音。
    public static void main(String[] args) {
        String str1 = solution("hello");
        String str2 = solution("leetcode");
        System.out.println(str1);
        System.out.println(str2);
    }
    public static String solution(String str){
        Set<Character> set = new HashSet<>(
            Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')
        );
        int l = 0; 
        int r = str.length() - 1;
        char[] ans = new char[str.length()];
        while(l <= r){
            Character L = Character.valueOf(str.charAt(l));
            Character R = Character.valueOf(str.charAt(r));
            if(!set.contains(L)){
                ans[l++] = L;
            }else if(!set.contains(R)){
                ans[r--] = R;
            }else{ //(set.contains(L) && set.contains(R))
                ans[l++] = R;
                ans[r--] = L;
            }
        }
        return new String(ans);
    }
    
}
回文串判断
  • 题目描述：可以删除一个字符，判断是否能构成回文字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class ValidPalindrome {
    //题目描述：可以删除一个字符，判断是否能构成回文字符串。
    public static void main(String[] args) {
        String str1 = "abba";
        String str2 = "abab";
        String str3 = "abbc";
        System.out.println(check1(str1));
        System.out.println(check1(str2));
        System.out.println(check1(str3));
    }
    public static boolean check1(String str) {
        int l = 0, r = str.length() - 1;
        while( l < r){
            if(str.charAt(l) != str.charAt(r)){
                return check2(str, l + 1, r) || check2(str, l, r - 1);
            }
            l++;
            r--;
        }
        return true;
    }
    private static boolean check2(String str, int l, int r){
        while(l < r){
            if(str.charAt(l) != str.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}
归并两个有序数组
  • 题目描述：把归并结果存到第一个数组上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MergeSortedArray {
    //归并有序数组,把归并结果存到第一个数组上
    //注意：这题要求不使用额外空间，为了方便，从后面开始遍历，不需要交换
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 3 ,5, 6, 0, 0};
        int[] arr2 = new int[]{2, 4};
        solution(arr1, arr2);
        for (int i : arr1) {
            System.out.println(i);
        }
    }
    private static void solution(int[] arr1, int[] arr2){
        int i = arr1.length - 1;
        int j = arr2.length - 1;
        int k = i - j - 1; //arr1的真实size - 1
        while(j >= 0 && k >= 0){
            if(arr1[k] < arr2[j]){
                arr1[i--] = arr2[j--];
            }else{
                arr1[i--] = arr1[k--];
            }
        }
    } 
}
判断链表是否有环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class LinkedListCycle{
    //题目：判断链表是否存在环
    //思路：看是否存在环
    static class Node{
        Integer val;
        Node next;
        Node(Integer val){
            this.val = val;
        }
    }
    //快慢指针
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2 ,3, 4, 5, 6};
        Node head =  new Node(1);
        Node p = head;
        Node p2 = new Node(0);
        Node tail = new Node(0);
        for(int i = 1; i < arr.length; i++){//尾插法
            Node temp = new Node(arr[i]);
            p.next = temp;
            p = p.next;
            if(arr[i] == 2){
                p2 = temp;
            }
            if(arr[i] == 6){
                tail = temp;
            }
        }
        //tail.next = p2; //加环
        System.out.println(check(head));
        
    }
    private static boolean check(Node head){
        Node p1 = head;
        Node p2 = p1.next;
        while(p2 != null && p2.next != null){
            if(p1.val == p2.val){
                return true;
            }else{
                p1 = p1.next;
                p2 = p2.next.next;
            }
        }
        return false;
    }
}
最长子序列
  • 题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个 相同长度的结果，返回字典序的最小字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class FindLongestWord {
    //题目描述：删除 s 中的一些字符，
    //使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个
    //相同长度的结果，返回字典序的最小字符串。
    //题解：通过删除字符串 s 中的一个字符能得到字符串 t，
    //可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串
    //是否为另一个字符串的子序列。
    public static void main(String[] args) {
        String s = "abpcpleaf";
        String[] d = new String[]{"ale", "apple", "bleaf", "monkey", "plea"};
        System.out.println(solution(s, d));
    }
    private static String solution(String s, String[] d){
        int len = d.length;
        String longMinSub = ""; //最长最小字典序子串
        for(int i = 0; i < len; i++){
            if(isSubStr(s, d[i])){
                String temp = d[i];
                int len1 = longMinSub.length();
                int len2 = temp.length();
                if(len1 <  len2){
                    longMinSub = temp;
                }else if(len1 == len2){
                    if(longMinSub.compareTo(temp) > 0){
                        longMinSub = temp;
                    }
                }
            }
        }
        return longMinSub;
    }
    private static boolean isSubStr(String s, String target){
        //双指针法：判断 target 是否是 s 的子串
        int i = 0, j = 0;
        while(i < s.length() && j < target.length()){
            if(s.charAt(i) == target.charAt(j)){
                j++; //j匹配上才++
            }
            i++; //i不管是否匹配都要++
        }
        return j == target.length();
    }
}

排序

topk问题
  • 题目描述：找到第 k 大的元素。

堆排法，时间复杂度 O(NlogK)，空间复杂度 O(K)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class FindTopK {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 5 ,6 ,4};
        int k = 2;
        System.out.println(find(arr, k));   
    }
    private static int find(int[] arr, int k){
        //法1：用大根堆实现topk
        int len = arr.length;
        buildMaxHeap(arr);
        while(k-- > 1){
            swap(arr, 0, len - 1);
            heapify(arr, 0, len - 1);
            len--;
        }
        return arr[0];       
    }
    private static void buildMaxHeap(int[] arr){
        int len = arr.length;
        for(int i = len/2; i >= 0; i--){
            heapify(arr, i, len);
        }
    }
    private static void heapify(int[] arr, int index, int heapSize){
        int l = 2 * index + 1;
        int largeIdx = index;
        if(l < heapSize && arr[largeIdx] < arr[l]){
            largeIdx = l;
        }
        if(l + 1 < heapSize && arr[largeIdx] < arr[l + 1]){
            largeIdx = l + 1;
        }
        if(largeIdx != index){//需要交换才递归
            swap(arr, largeIdx, index);
            heapify(arr, largeIdx, heapSize); 
        }      
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

快排快速选择法，时间复杂度 O(N)，空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class FindTopK2 {
    //随机快排+三向切分partition版本
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 5 ,6 ,4};
        System.out.println(quickSort(arr, 0, arr.length - 1, 1));
        System.out.println(quickSort(arr, 0, arr.length - 1, 2));
        System.out.println(quickSort(arr, 0, arr.length - 1, 3));
        System.out.println(quickSort(arr, 0, arr.length - 1, 4));
        System.out.println(quickSort(arr, 0, arr.length - 1, 5));
        System.out.println(quickSort(arr, 0, arr.length - 1, 6));
    }
    private static int quickSort(int[] arr, int l, int r, int k){
        int idx = l + (int)Math.random() * (r - l + 1);
        swap(arr, idx, r);
        int index = partition(arr, l, r);
        if(index < arr.length - k){
            return quickSort(arr, index + 1, r, k);
        }else if(index > arr.length - k){
            return quickSort(arr, l, index - 1, k);
        }else{
            return arr[index];
        }

    }
    private static int partition(int[] arr, int l, int r){
        int less = l - 1;
        int more = r;
        while(l < more){
            if(arr[l] < arr[r]){
                swap(arr, ++less, l++);
            }else if(arr[l] > arr[r]){
                swap(arr, --more, l);
            }else{
                l++;
            }
        }
        swap(arr, more, r);
        return more;
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
出现频率最多的k个元素
  • 思路：和topk原理一样，只不过多一个hash表来将频率转为个数。

注意：

  • topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是 nlogk
  • 避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。

[注意]

  • 求前 k 大，用小根堆，求前 k 小，用大根堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
public class TopKFrequent {//小根堆
    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 2, 2, 3};
        int k = 2;
        int[] ans = topKFrequent(nums, k);
        for (int i : ans) {
            System.out.println(i);
        }
    }
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }
        //技巧：int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}
按颜色进行排序
  • 题目描述：只有 0/1/2 三种颜色。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class SortColor {
    //荷兰国旗问题
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 2, 1, 0, 0};
        sort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    private static void sort(int[] arr){
        int less = -1;
        int more = arr.length;
        int index = 0;
        while(index < more){
            if(arr[index] == 0){
                swap(arr, ++less, index++);
            }else if(arr[index] == 2){
                swap(arr, --more, index);
            }else{
                index++;
            }
        }
    }
    private static void swap(int[] arr, int i ,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

贪心

  • 题目描述：每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于等于一个孩子的满足度，该孩子 才会获得满足。求解最多可以获得满足的孩子数量。