Leetcode119 楊輝三角 II

給定一個非負索引 k，其中 k ≤ 33，回傳楊輝三角的第 k 行，

每日一題，楊輝三角應該是學編程的入門題了，記得上大一的時候，編個楊輝三角的作業，編了一晚上才寫出來，真是難忘的回憶啊，

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> prev = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i++){
            List<Integer> temp = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                if (j == 0 || j == i){
                    temp.add(1);
                }else{
                    temp.add(prev.get(j - 1) + prev.get(j));
                }
            }
            prev = temp;
        }
        return prev;
    }
}

Leetcode870 優勢洗牌

給定兩個大小相等的陣列 A 和 B，A 相對于 B 的優勢可以用滿足 A[i] > B[i] 的索引 i 的數目來描述，

回傳 A 的任意排列，使其相對于 B 的優勢最大化，

話說貪心的思想感覺就是生活中的經驗，比如這題就是已知對方的戰斗力，要安排己方的戰斗力能在回合制游戲中打過對面，那么可以先進行排序，如果己方有能戰勝對方的，就安排一個人和對方打，如果沒有打得過的，就安排一個最弱的下等馬去打，

class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        int n = A.length;
        int[] res = new int[n];
        //對A，B進行排序，對B排序記錄一下位置的索引
        Arrays.sort(A);
        int[][] help = new int[n][2];
        for(int i = 0; i < n; i++){
            help[i][0] = B[i];
            help[i][1] = i;
        }
        Arrays.sort(help, (x, y) -> (x[0] - y[0]));
        int i = 0, j = n - 1, k = n - 1;
        //按貪心的思路遍歷
        while (i <= j){
            if (help[k][0] < A[j]){
                res[help[k][1]] = A[j];
                j--;
            }else{
                res[help[k][1]] = A[i];
                i++;
            }
            k--;
        }
        return res;
    }
}

Leetcode923 三數之和的多種可能

給定一個整數陣列 A，以及一個整數 target 作為目標值，回傳滿足 i < j < k 且 A[i] + A[j] + A[k] == target 的元組 i, j, k 的數量，

由于結果會非常大，請回傳 結果除以 10^9 + 7 的余數，

和經典的三數之和的做法基本一致，就是要額外考慮一種情況，

class Solution {
    final int mod = 1000000007;
    public int threeSumMulti(int[] arr, int target) {
    	//三數之和要先排下序
        Arrays.sort(arr);
        int n = arr.length, res = 0;
        for(int k = 0; k < arr.length; k++){
        	//小剪枝
            if (arr[k] > target) break;
            int i = k + 1, j = n - 1;
            //排序玩用雙指標
            while (i < j){
                int temp = arr[i] + arr[j] + arr[k];
                //大于目標值，就讓大的減一，反之相同
                if (temp > target){
                    j--;
                }else if (temp < target){
                    i++;
                    //如果等于目標值，且arr[i] != arr[j]，計算下有多少個相同的元素
                }else if (arr[i] != arr[j]){
                    int countI = 1, countJ = 1;
                    while (i < j - 1 && arr[i] == arr[i + 1]){
                        countI++;
                        i++;
                    }
                    while (i < j - 1 && arr[j] == arr[j - 1]){
                        countJ++;
                        j--;
                    }
                    i++;
                    j--;
                    res += countI * countJ;
                    res %= mod;
                }else {
                    //不想等的可能性，比如[1,1,2,2,2,2]，相等于從4個挑兩個，就是C42
                    res += (j - i + 1) * (j - i) / 2;
                    res %= mod;
                    break;
                }
            }
        }
        return res;
    }
}