蛇梯棋

題目：N x N 的棋盤 board 上，按從 1 到 N*N 的數字給方格編號，編號 從左下角開始，每一行交替方向。例如，一塊 6 x 6 大小的棋盤，編號如下：

r 行 c 列的棋盤，按前述方法編號，棋盤格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那個蛇或梯子的目的地將會是 board[r][c]。

玩家從棋盤上的方格 1 （總是在最后一行、第一列）開始出發(fā)。

每一回合，玩家需要從當前方格 x 開始出發(fā)，按下述要求前進：

選定目標方格：選擇從編號 x+1，x+2，x+3，x+4，x+5，或者 x+6 的方格中選出一個目標方格 s ，目標方格的編號 <= N*N。

該選擇模擬了擲骰子的情景，無論棋盤大小如何，你的目的地范圍也只能處于區(qū)間 [x+1, x+6] 之間。

傳送玩家：如果目標方格 S 處存在蛇或梯子，那么玩家會傳送到蛇或梯子的目的地。否則，玩家傳送到目標方格 S。

注意，玩家在每回合的前進過程中最多只能爬過蛇或梯子一次：就算目的地是另一條蛇或梯子的起點，你也不會繼續(xù)移動。

返回達到方格 N*N 所需的最少移動次數，如果不可能，則返回 -1。

示例：
輸入：[
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
輸出：4
解釋：
首先，從方格 1 [第 5 行，第 0 列] 開始。
你決定移動到方格 2，并必須爬過梯子移動到到方格 15。
然后你決定移動到方格 17 [第 3 行，第 5 列]，必須爬過蛇到方格 13。
然后你決定移動到方格 14，且必須通過梯子移動到方格 35。
然后你決定移動到方格 36, 游戲結束。
可以證明你需要至少 4 次移動才能到達第 NN 個方格，所以答案是 4。
提示：
2 <= board.length = board[0].length <= 20
board[i][j] 介于 1 和 NN 之間或者等于 -1。
編號為 1 的方格上沒有蛇或梯子。
編號為 N*N 的方格上沒有蛇或梯子。

思路：這個題的題目的廣度優(yōu)先。這沒啥問題。但是完完全全的廣搜肯定超時，這里應該是還要加個記憶功能。比如到了點x用3步，那么以后4,5,6步到x的都不要計算了。除了這個應該沒什么了，畢竟就是一個中等題目，我去試試代碼。
第一版代碼：

class Solution {
    public int snakesAndLadders(int[][] board) {
        int len = board.length;
        //其實圖是順著跑的，所以我們完全能把這個抻直了
        int[] b = new int[len*len];
        boolean flag = true;
        int idx = 0;
        for(int i = len-1;i>=0;i--) {
            if(flag) {
                for(int j = 0;j<len;j++) b[idx++] = board[i][j];
                flag = false;
            }else {
                for(int j = len-1;j>=0;j--) b[idx++] = board[i][j];
                flag = true;
            }
        }
        //現在只要把b跳通關就行了。
        boolean[] d = new boolean[b.length];
        int ans = 0;
        Queue<Integer> queue = new  LinkedList<Integer>();
        queue.add(0);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int t = 0;t<size;t++) {
                int temp = queue.poll();
                for(int i = 1;i<=6;i++) {
                    if(temp+i>=d.length) break;
                    int v = b[temp+i];
                    //減1是因為填充數字從1開始，下標從0開始
                    int next = b[temp+i] == -1? temp+i:b[temp+i]-1;
                    if(next == len*len-1) return ans+1;
                    if(!d[next]) {
                        queue.add(next);
                        d[next] = true;
                    }
                }
            }
            ans++;
        }
        return -1;
    }
}

講真這個題思路上和我最開始想的差別不大，但是細節(jié)處理上，比如矩陣理直了計算。還有如果在子集中返回的話ans要+1.還有判斷temp+i是不是溢出。反正各種細節(jié)我都是面向測試案例改的。。細節(jié)比較多。因為這個代碼已經是超過百分百了，所以我就不多說了，直接下一題。

最小差值

題目：給你一個整數數組 A，對于每個整數 A[i]，可以選擇 x = -K 或是 x = K （K 總是非負整數），并將 x 加到 A[i] 中。在此過程之后，得到數組 B。返回 B 的最大值和 B 的最小值之間可能存在的最小差值。

示例 1：
輸入：A = [1], K = 0
輸出：0
解釋：B = [1]
示例 2：
輸入：A = [0,10], K = 2
輸出：6
解釋：B = [2,8]
示例 3：
輸入：A = [1,3,6], K = 3
輸出：3
解釋：B = [4,6,3]
提示：
1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000

思路：這個題怎么說呢，乍一看還挺簡單的。但是細想也不是。本來覺得是最大值減k，最小值+k，后來發(fā)現萬一最大最小就差1，這樣加減k指不定差的更大了，所以說這個題還要具體情況具體分析。但是總的來講一個我的想法第一次遍歷找出最大值和最小值。然后如果這兩個值同向加減的差值（比如都+k或者都-k）小于最大值減，最小值加。那么這個差值就是最大值。反正大的減，小的加。然后中間的每一個元素看往上加的差值大還是往下減的差值大。大概思路就這樣，我去實現下試試。
第一版代碼：

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int len = nums.length-1;
        int cha = nums[len]-nums[0];
        //說明最大值最小值的差異小于大減k，小加k的結果，所以應該做相同符號的操作。
        if(cha <= Math.abs(cha-2*k)) return cha;
        //到這說明一定是有加有減，所以肯定存在相鄰的兩個元素，一個是加k，一個是-k。
        for(int i = 0;i<nums.length-1;i++) {
            //因為數組排序了，所以小的加大的減是肯定的。
            int max1 = Math.max(nums[len]-k, nums[i]+k);
            int min1 = Math.min(nums[0]+k, nums[i+1]-k);
            cha = Math.min(cha, max1-min1);
        }
        return cha;
    }
}

注意這里的最小值是最大值和最小值的差值。因為所有元素+k或者-k的結果就是這個差值。所以這個差值也算是保底。然后注釋里說的比較明確了，排序好了的元素，絕對有一個分解點，前一個元素-k，后一個元素+k。我們只要遍歷一遍取最小結果就行了。我這個代碼性能還好，超過百分之九十四的人就不多說了，繼續(xù)下一題。

在線選舉

題目：在選舉中，第 i 張票是在時間為 times[i] 時投給 persons[i] 的?，F在，我們想要實現下面的查詢函數： TopVotedCandidate.q(int t) 將返回在 t 時刻主導選舉的候選人的編號。在 t 時刻投出的選票也將被計入我們的查詢之中。在平局的情況下，最近獲得投票的候選人將會獲勝。

示例：
輸入：["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
輸出：[null,0,1,1,0,0,1]
解釋：
時間為 3，票數分布情況是 [0]，編號為 0 的候選人領先。
時間為 12，票數分布情況是 [0,1,1]，編號為 1 的候選人領先。
時間為 25，票數分布情況是 [0,1,1,0,0,1]，編號為 1 的候選人領先（因為最近的投票結果是平局）。
在時間 15、24 和 8 處繼續(xù)執(zhí)行 3 個查詢。
提示：
1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times 是嚴格遞增的數組，所有元素都在 [0, 10^9] 范圍中。
每個測試用例最多調用 10000 次 TopVotedCandidate.q。
TopVotedCandidate.q(int t) 被調用時總是滿足 t >= times[0]。

思路：這個題感覺比較簡單，實現容易，但是怎么性能好的實現是考點。首先因為time是嚴格遞增的，并且范圍是10的九次方，所以數組下標代替值是不行的。所以初步想法是一個多維數組。然後其實比如我們想知道第12分鐘的結果，其實本質上不用知道票數，只要知道誰領先就行了。這樣在查詢的時候也比較方便。所以我打算在初始化的時候就獲取到個個時間點的領先人。然後在查詢的時候用二分來確定當前截止時間的領先人是誰。至于保存方法初步決定用二維數組，第一個元素存時間，第二個元素存領先人。主要邏輯代碼寫在構造函數中。思路就是這樣，我去實現試試。
第一版代碼：

class TopVotedCandidate {
    List<Vote> A;
    public TopVotedCandidate(int[] persons, int[] times) {
        A = new ArrayList();
        Map<Integer, Integer> count = new HashMap();
        int leader = -1;  // current leader
        int m = 0;  // current number of votes for leader

        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i], t = times[i];
            int c = count.getOrDefault(p, 0) + 1;
            count.put(p, c);

            if (c >= m) {
                if (p != leader) {  // lead change
                    leader = p;
                    A.add(new Vote(leader, t));
                }

                if (c > m) m = c;
            }
        }
    }

    public int q(int t) {
        int lo = 1, hi = A.size();
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (A.get(mi).time <= t)
                lo = mi + 1;
            else
                hi = mi;
        }

        return A.get(lo - 1).person;
    }
}

class Vote {
    int person, time;
    Vote(int p, int t) {
        person = p;
        time = t;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */

emmm...這是參考了題解的代碼，自己寫越寫越麻煩。所以直接搬運代碼了，哈哈?？偠灾@個題我是覺得難度還好，我之前因為沒想到單獨寫個數據結構的類然後各種list套map啥的才寫崩了的。而且不得不吐槽這個官方題解的性能也不咋地，我再去看看性能第一的代碼：

class TopVotedCandidate {
    int[] lead ;
    Map<Integer,Integer> num = new HashMap<>();

    public TopVotedCandidate(int[] persons, int[] times) {
        lead = new int[times[times.length-1]+1];
        int leadnow = persons[0];
        int vote = 1;
        Arrays.fill(lead,-1);
        lead[times[0]]=leadnow;
        num.put(leadnow,vote);
        for(int i = 1;i<persons.length;i++){
            if(persons[i]==leadnow){
                vote++;
            }else{
                int intnow = num.getOrDefault(persons[i],0)+1;
                num.put(persons[i],intnow);
                if(intnow>=vote){
                    leadnow=persons[i];
                    vote=intnow;
                }
            }
            lead[times[i]]=leadnow;
            num.put(leadnow,vote);
        }
        for(int i=1;i<lead.length;i++){
            if(lead[i]==-1){
                lead[i]=lead[i-1];
            }
        }
    }
    
    public int q(int t) {
        if(t>=lead.length){
            return lead[lead.length-1];
        }
        return lead[t];
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */

這個代碼中是用了一個數組把所有時間的當前領先人都記錄了。因為時間范圍是10的九次方，所以這個數組最大也是10的九次方長度。但是每次查詢不用二分了，可以直接定位到時間點。感覺就是典型是空間換時間的做法。別的也沒啥了。這個題就這樣吧，下一題。

最后一塊石頭的重量2

題目：有一堆石頭，用整數數組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結果如下：

如果 x == y，那么兩塊石頭都會被完全粉碎；

如果 x != y，那么重量為 x 的石頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。

最后，最多只會剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒有石頭剩下，就返回 0。

示例 1：
輸入：stones = [2,7,4,1,8,1]
輸出：1
解釋：
組合 2 和 4，得到 2，所以數組轉化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數組轉化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數組轉化為 [1,1,1]，
組合 1 和 1，得到 0，所以數組轉化為 [1]，這就是最優(yōu)值。
示例 2：
輸入：stones = [31,26,33,21,40]
輸出：5
示例 3：
輸入：stones = [1,2]
輸出：1
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100

思路：這個題怎么說呢，最后一次粉碎，肯定是盡可能兩個石頭越相似結果越小。所以這個題目可以變種為：將所有石子分成兩堆，盡量兩堆的重量相等。也就是算出石子總和/2，然後盡量從stones中挑出部分元素組成最接近target的元素。思路就這樣，我去實現試試。
第一版本的dfs代碼超時了，但是因為我覺得總思路是對的，所以依然貼出來分享下：

class Solution {
    int ans;
    double target;
    public int lastStoneWeightII(int[] stones) {
        //這個題怎么說呢，最后一次粉碎，肯定是盡可能兩個石頭越相似結果越小。
        //所以這個題目可以變種為：將所有石子分成兩堆，盡量兩堆的重量相等
        int sum = 0;
        for(int i : stones) sum += i;
        Arrays.sort(stones);
        target = sum*1.0/2;
        ans = 0;
        //現在的做法變成了盡量從stones中挑出部分元素組成最接近target的元素。
        //每個元素可以選擇選或者不選。然後去遍歷。不知道超時不超時
        dfs(stones,stones.length-1,0);
        return sum-2*ans;
    }
    public void dfs(int[] stones,int temp,int sum) {
        if(temp<0) return;
        if(sum == target) {
            ans = sum;
            return;
        }else if(sum>target){
            return;//當前sum都已經比結果集大了。不用繼續(xù)走了。
        }else if(sum>ans && sum< target){
            ans = sum;
        }
        dfs(stones, temp-1, sum+stones[temp]);//選擇當前元素
        dfs(stones, temp-1, sum);//不選當前元素
    }
}

第二版代碼（01背包問題）：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        //這個題怎么說呢，最后一次粉碎，肯定是盡可能兩個石頭越相似結果越小。
        //所以這個題目可以變種為：將所有石子分成兩堆，盡量兩堆的重量相等
        int sum = 0;
        for(int i : stones) sum += i;
        Arrays.sort(stones);
        int target = sum/2;
        //現在的做法變成了盡量從stones中挑出部分元素組成最接近target的元素。
        //每個元素可以選擇選或者不選。然後去遍歷。不知道超時不超時
        //這里遞歸超時，所以改用dp。這個題也可以簡化為01背包問題
        int[][] dp = new int[stones.length+1][target+1];//因為下標從0開始。
        for(int i = 1;i<dp.length;i++) {
            for(int j = 1;j<dp[0].length;j++) {
                if(j>=stones[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-stones[i-1]]+stones[i-1]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return sum-2*dp[stones.length][target];
    }
}

首先該說不說這個問題確實是01背包問題。其次我也確實是過了。問題是同樣的dp。人家性能那樣，我這個性能這樣。。上面代碼的優(yōu)化空間我能想到的是當前行數據只和上一行有關，所以這里可以用壓縮的方式兩個一維數組來回倒騰，省空間。但是又因為數據范圍最大才30.省的也有限。至于別的暫時想不到了，我直接去看看性能第一的代碼：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int st:stones)
            sum+=st;
        for(int i=(sum>>1);;i--){
            if(helper(stones,0,0,i))
                return sum-2*i;
        }
    }
    
    boolean helper(int[] nums,int idx,int sum,int target){
        if(sum==target)
            return true;
        if(sum>target)
            return false;
        if(idx==nums.length)
            return false;
        return helper(nums,idx+1,sum+nums[idx],target)
            ||helper(nums,idx+1,sum,target);
    }
}

代碼邏輯比較簡單，也挺好懂的。但是問題是，為什么性能定義的代碼是用dfs做出來的？我的思路就超時。。。有點小心痛?？偠灾@個代碼挺容易懂的。就是從sum/2開始判斷。如果能湊出這個數則true，否則false。sum/2湊不出來則遞減繼續(xù)湊。其實本質上還是找最接近target的點?？赡苁侨思姨幚淼膹碗s度低吧，哎 ，下一題下一題。

排序數組

題目：給你一個整數數組 nums，請你將該數組升序排列。

示例 1：
輸入：nums = [5,2,3,1]
輸出：[1,2,3,5]
示例 2：
輸入：nums = [5,1,1,2,0,0]
輸出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

思路：很奇怪這個題為什么在這里出來了。還是中等難度的。。難不成是會超時么？我目前的想法是快排。畢竟這個用的比較習慣。我去試試這個題的考點是什么。
第一版代碼：

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums, int left, int right) {
        if(left>=right) return;
        int mid = (right-left)/2+left;
        quickSort(nums, left, mid);
        quickSort(nums, mid+1, right);
        merge(nums,left,right,mid+1);
    }
    public void merge(int[] nums,int left,int right,int mid) {
        int[] temp = new int[right-left+1];
        int l = left;
        int r = mid;
        int idx = 0;
        while(l<mid && r<=right) {
            if(nums[l]<nums[r]) {
                temp[idx++] = nums[l++];
            }else {
                temp[idx++] = nums[r++];
            }
        }
        while(l<mid) temp[idx++] = nums[l++];
        while(r<=right) temp[idx++] = nums[r++];
        for(int i = left;i<=right;i++) {
            nums[i] = temp[i-left];
        }
    }
}

我也很難說明白為什么寫著寫著變成歸并排序了。。但是既然都寫出來了所以就對付寫完了。歸并性能不咋地，下面繼續(xù)用快排試試，第二版代碼：

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums, int left, int right) {
        if(left>=right) return;
        int l = left;
        int r = right;
        int temp = nums[(r-l)/2+l];//把最左元素看成標準值
        while(l<r) {
            while(r>=left && nums[r]>temp) r--;//找到第一個小于目標值的元素
            while(l<right && nums[l]<temp) l++;//前面都比temp小。找到第一個大于的元素
            if(l <= r) {//這里添加等于是為了讓r是
                int cur = nums[r];
                nums[r] = nums[l];
                nums[l] = cur;
                r--;
                l++;
            }
        }
        //到這里我們確定left-r的值都是小于等于
        quickSort(nums, left, r);
        quickSort(nums, l, right);
    }
}

快排倒是實現了，性能依然不行，所以我決定做個大膽的嘗試，用空間換時間。數據范圍正負5w依然打算用數組下標代替值試試。最終版代碼：

class Solution {
    public int[] sortArray(int[] nums) {
        int[] d = new int[100001];
        for(int i : nums) d[i+50000]++;
        int idx = 0;
        for(int i = 0;i<d.length;i++) {
            int n = d[i];
            while(n>0) {
                nums[idx++] = i-50000;
                n--;
            }
        }
        return nums;
    }
}

這個性能一下子就上來了。怎么說呢，當數據量多的時候確實是這樣最性能好，反正是超過百分之九十九的人了，所以這個排序就這樣了。
本篇筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關注。也祝大家工作順順利利，生活健健康康！另外最近在看面試題，歡迎小伙伴們推薦下比較好的課程或者學習資料喲~