292. Nim 游戲

你和你的朋友，兩個(gè)人一起玩 Nim 游戲：桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者。你作為先手。

你們是聰明人，每一步都是最優(yōu)解。 編寫一個(gè)函數(shù)，來判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲。

輸入: 4
輸出: false
解釋: 如果堆中有 4 塊石頭，那么你永遠(yuǎn)不會(huì)贏得比賽；
因?yàn)闊o論你拿走 1 塊、2 塊 還是 3 塊石頭，最后一塊石頭總是會(huì)被你的朋友拿走。

思路：我該怎么拿。
我如果后手拿，
第一次先手拿完之后，我拿到剩余石頭數(shù)目為4的倍數(shù)，然后不管對面怎么拿，我都拿4-X；
我如果先手拿，
如果是已經(jīng)4的倍數(shù)，不管怎么拿，對面都會(huì)拿4-X；那么最后一定對面贏，我贏不了。
如果不是4的倍數(shù)，我先拿到剩余只是4的倍數(shù)，無論對面怎么拿，我都拿4-X；我穩(wěn)贏。

因此，先手拿 概率是75% 后手是1/4；

代碼：因?yàn)?是2的2次方，用與操作代替%； hash&(n-1) = hash %n;(HashMap源碼)

class Solution {
    public boolean canWinNim(int n) {
        return (n&3)==0?false :true;
    }
}

192. 統(tǒng)計(jì)詞頻

寫一個(gè) bash 腳本以統(tǒng)計(jì)一個(gè)文本文件 words.txt 中每個(gè)單詞出現(xiàn)的頻率。

為了簡單起見，你可以假設(shè)：

• words.txt只包括小寫字母和 ' ' 。
• 每個(gè)單詞只由小寫字母組成。
• 單詞間由一個(gè)或多個(gè)空格字符分隔。
  假設(shè) words.txt 內(nèi)容如下：

the day is sunny the the
the sunny is is
你的腳本應(yīng)當(dāng)輸出（以詞頻降序排列）：

the 4
is 3
sunny 2
day 1

思路：本題是腳本統(tǒng)計(jì)題，用awk命令即可。
awk中，可以將字符串當(dāng)作索引。 $i指的是文本中當(dāng)前行的第i個(gè)字符；
sort默認(rèn)是從小到大 -r逆序 -k指第幾列 -n為按照數(shù)值大小排序

awk '{for(i=1;i<=NF;i++){words[$i]++}} END{for(word in words){print word,words[word]}}' words.txt | sort -k2 -nr

146. LRU緩存機(jī)制

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值。當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

思路： 用linkedHashMap，linkedHashMap構(gòu)造器如下：
linkedHashMap(int capacity, double loadfactor, boolean accessOrder){

}; 其中，accessOrder表示的是排序方式，默認(rèn)為false，即：按照插入順序排序。若為true，則按照訪問順序排序從小到大排序。

class LRUCache {

    LinkedHashMap<Integer,Integer> map;
    int size;
    int count;

    public LRUCache(int capacity) {
        map = new LinkedHashMap(capacity,0.75F,true);
        count = 0;
        size = capacity;
    }
    
    public int get(int key) {
        return map.getOrDefault(key,-1);
    }
    
    public void put(int key, int value) {

        if(map.containsKey(key)){
            map.put(key,value);
            return;
        }
        if(count==size){
        // 刪除linkedHashMap中的第一個(gè)結(jié)點(diǎn)，用iterator迭代器更保險(xiǎn)
            Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
            Iterator<Map.Entry<Integer, Integer>> iterator = entries.iterator();
            if(iterator.hasNext()){
                iterator.next();
                iterator.remove();
            }
            count--;
        }
        map.put(key,value);
        count++;
        
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

460. LFU緩存

設(shè)計(jì)并實(shí)現(xiàn)最不經(jīng)常使用（LFU）緩存的數(shù)據(jù)結(jié)構(gòu)。它應(yīng)該支持以下操作：get 和 put。

get(key) - 如果鍵存在于緩存中，則獲取鍵的值（總是正數(shù)），否則返回 -1。
put(key, value) - 如果鍵不存在，請?jiān)O(shè)置或插入值。當(dāng)緩存達(dá)到其容量時(shí)，它應(yīng)該在插入新項(xiàng)目之前，使最不經(jīng)常使用的項(xiàng)目無效。在此問題中，當(dāng)存在平局（即兩個(gè)或更多個(gè)鍵具有相同使用頻率）時(shí)，最近最少使用的鍵將被去除。

思路： 最少~ 想到最小堆。因此采用HashMap存儲(chǔ)key，value；堆存儲(chǔ)順序的方法。
HashMap<Integer,Node>，其中Node包含value信息。
堆存儲(chǔ)Node，根據(jù)Node的frequency及時(shí)間排序。
Node(int key, int value , int cnt, long time);

class LFUCache {
    private Map<Integer, Node> m;
    private PriorityQueue<Node> q;
    private int size;
    private int capacity;

    public LFUCache(int capacity) {
        size = 0;
        m = new HashMap<>();
        q = new PriorityQueue<>((n1, n2) -> {
            if (n1.getCnt() != n2.getCnt())
                return n1.getCnt() - n2.getCnt();
            return (int) (n1.getTime() - n2.getTime());
        });
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!m.containsKey(key))
            return -1;
        Node node = m.get(key);
        touch(node);
        return node.getValue();
    }

    private void touch(Node node) {
        node.setCnt(node.getCnt() + 1);
        node.setTime(System.nanoTime());
        q.remove(node);
        q.add(node);
    }

    public void put(int key, int value) {
        if (capacity <= 0)
            return;
        if (m.containsKey(key)) {
            Node node = m.get(key);
            node.setValue(value);
            touch(node);
            return;
        }
        if (size == capacity) {
            Node poll = q.poll();
            m.remove(poll.getKey());
            size -= 1;
        }
        Node node = new Node(key, value, 1, System.nanoTime());
        q.add(node);
        m.put(key, node);
        size += 1;
    }
}

class Node {
    private int key;
    private int value;
    private int cnt;
    private long time;
    Node(int key,int value,int cnt, long time){
        this.key = key;
        this.value = value;
        this.cnt = cnt;
        this.time = time;
    }
    public int getKey() {return key; }
    public void setKey(int key) { this.key = key; }
    public int getValue() { return value; }
    public void setValue(int value) { this.value = value; }
    public int getCnt() { return cnt; }
    public void setCnt(int cnt) {this.cnt = cnt; }
    public long getTime() { return time; }
    public void setTime(long time) { this.time = time; }
}

470. 用 Rand7() 實(shí)現(xiàn) Rand10()

已有方法 rand7 可生成 1 到 7 范圍內(nèi)的均勻隨機(jī)整數(shù)，試寫一個(gè)方法 rand10 生成 1 到 10 范圍內(nèi)的均勻隨機(jī)整數(shù)。

不要使用系統(tǒng)的 Math.random() 方法。
思路：
這題重點(diǎn)在生成等概率的隨機(jī)數(shù)。 7（rand7()-1）可以生成 0,7,14,``` 在此基礎(chǔ)上，加上1~7 就可以填滿1~49；并且每個(gè)數(shù)字出現(xiàn)的次數(shù)都是1. 如果直接rand7()rand7()，中間很多數(shù)字調(diào)用不到。 如果不是7，如1 直接+1，得到1~-13，中間很多數(shù)字重復(fù)了。

優(yōu)化方案：大于40的9個(gè)數(shù)也是等概率的，因此可以利用這9個(gè)數(shù)，繼續(xù)生成等概率的數(shù)
(nums-40-1)*7 ，再用7填滿中間的空

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        int nums = (rand7()-1)*7+rand7();
        return  nums >40 ? rand10() :nums%10+1;
    }
}

792. 匹配子序列的單詞數(shù)

給定字符串 S 和單詞字典 words, 求 words[i] 中是 S 的子序列的單詞個(gè)數(shù)。
示例:
輸入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
輸出: 3
解釋: 有三個(gè)是 S 的子序列的單詞: "a", "acd", "ace"。</pre>

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int count = 0;
        int[] dp = new int[words.length];
        for(int i=0;i<words.length;i++){
            if(i>0&&words[i].equals(words[i-1])){
                if(dp[i-1]==1){
                    dp[i] = dp[i-1];
                    count++;
                }
                continue;
            }
            
            if(juage(S,words[i])){
                dp[i]=1;
                count++;
            }
        }
        return count;
    }

    public boolean juage(String s, String b){
        int sL = s.length();
        int bL = b.length();
        int i=0;
        int j=0;
        while(i!=sL&&j!=bL){
            if(s.charAt(i)==b.charAt(j)){
                i++;
                j++;
            }
            else{
                i++;
            }
        }
        if(j==bL){
            return true;
        }
        return false;
    }
}

741. 摘櫻桃

一個(gè)N x N的網(wǎng)格(grid) 代表了一塊櫻桃地，每個(gè)格子由以下三種數(shù)字的一種來表示：

• 0 表示這個(gè)格子是空的，所以你可以穿過它。
• 1 表示這個(gè)格子里裝著一個(gè)櫻桃，你可以摘到櫻桃然后穿過它。
• -1 表示這個(gè)格子里有荊棘，擋著你的路。

你的任務(wù)是在遵守下列規(guī)則的情況下，盡可能的摘到最多櫻桃：

• 從位置 (0, 0) 出發(fā)，最后到達(dá) (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿過值為0或者1的格子）；
• 當(dāng)?shù)竭_(dá) (N-1, N-1) 后，你要繼續(xù)走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
• 當(dāng)你經(jīng)過一個(gè)格子且這個(gè)格子包含一個(gè)櫻桃時(shí)，你將摘到櫻桃并且這個(gè)格子會(huì)變成空的（值變?yōu)?）；
• 如果在 (0, 0) 和 (N-1, N-1) 之間不存在一條可經(jīng)過的路徑，則沒有任何一個(gè)櫻桃能被摘到。

示例 1:
輸入: grid =
[[0, 1, -1],
[1, 0, -1],
[1, 1, 1]]
輸出: 5
解釋：
玩家從（0,0）點(diǎn)出發(fā)，經(jīng)過了向下走，向下走，向右走，向右走，到達(dá)了點(diǎn)(2, 2)。
在這趟單程中，總共摘到了4顆櫻桃，矩陣變成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接著，這名玩家向左走，向上走，向上走，向左走，返回了起始點(diǎn)，又摘到了1顆櫻桃。
在旅程中，總共摘到了5顆櫻桃，這是可以摘到的最大值了。
</pre>

說明:

• grid 是一個(gè) N * N 的二維數(shù)組，N的取值范圍是1 <= N <= 50。
• 每一個(gè) grid[i][j] 都是集合 {-1, 0, 1}其中的一個(gè)數(shù)。
• 可以保證起點(diǎn) grid[0][0] 和終點(diǎn) grid[N-1][N-1] 的值都不會(huì)是 -1。

思路：動(dòng)態(tài)規(guī)劃分別求兩次最優(yōu)解，其答案并不是最優(yōu)解，只是次優(yōu)解。必須綜合考慮。

1. 看成兩個(gè)人同時(shí)從(0,0)走向(m-1,m-1)；坐標(biāo)分別為（r1,c1）、（r2、c2）；
   同時(shí)走，即c2 = r1+c1-r2;
2. 同時(shí)走，則dp有四個(gè)方向。分別是 下下、右右、下右、右下
   因此用遞歸dp（grid,memo，r1,c1,r2);

class Solution {
    public int cherryPickup(int[][] grid) {
        
        // 求最優(yōu)解，用dp；求匹配/用backtrace
        int m = grid.length;
        int memo[][][] = new int[m][m][m];
        for (int[][] layer: memo)
            for (int[] row: layer)
                Arrays.fill(row, Integer.MIN_VALUE);
        int res = dp(grid,memo,0,0,0);
        return Math.max(res,0);
    }

    public int dp(int[][] grid,int[][][] memo,int r1,int c1, int r2){
        int c2  =r1+c1-r2;
        if(r1==grid.length||r2==grid.length||c1==grid.length||c2==grid.length||grid[r1][c1]==-1||grid[r2][c2]==-1){
            return -99999;
        }
        if(r1==grid.length-1&&c1==grid.length-1){
            return grid[r1][c1];
        }
        if(memo[r1][c1][r2]!=Integer.MIN_VALUE){
            return memo[r1][c1][r2];
        }
        int ans = 0;
        if(r1!=r2){
            ans = max(dp(grid,memo,r1+1,c1,r2+1),dp(grid,memo,r1+1,c1,r2),dp(grid,memo,r1,c1+1,r2+1),dp(grid,memo,r1,c1+1,r2) ) + grid[r1][c1] + grid[r2][c2];
        }else{
            ans = max(dp(grid,memo,r1+1,c1,r2+1),dp(grid,memo,r1+1,c1,r2),dp(grid,memo,r1,c1+1,r2+1),dp(grid,memo,r1,c1+1,r2)) + grid[r1][c1];
        }
        memo[r1][c1][r2] = ans;
        return ans;
    }

    public int max(int a, int b,int c,int d){
        a = Math.max(a,b);
        a = Math.max(a,c);
        a = Math.max(a,d);
        return a;
    }
}

410. 分割數(shù)組的最大值

給定一個(gè)非負(fù)整數(shù)數(shù)組和一個(gè)整數(shù) m，你需要將這個(gè)數(shù)組分成 *m *個(gè)非空的連續(xù)子數(shù)組。設(shè)計(jì)一個(gè)算法使得這 *m *個(gè)子數(shù)組各自和的最大值最小。

注意:
數(shù)組長度 *n *滿足以下條件:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

示例:
輸入:
nums = [7,2,5,10,8]
m = 2

輸出:
18

解釋:
一共有四種方法將nums分割為2個(gè)子數(shù)組。
其中最好的方式是將其分為[7,2,5] 和 [10,8]，
因?yàn)榇藭r(shí)這兩個(gè)子數(shù)組各自的和的最大值為18，在所有情況中最小。</pre>

思路：
dp； dp難問題主要是兩種：

1. 最大的最小值/最小的最大值：這種需要找到dp[i][j]與子問題的動(dòng)態(tài)轉(zhuǎn)移方程。然后遍歷每一種可能去max/min；如：雞蛋掉落，本題。
2. 直接dp維度不夠，需要dp[][][];如摘櫻桃，移除盒子。

假設(shè)dp[i][j]是nums[0~i]經(jīng)k次分割得到的最小的最大值。假設(shè)最后一刀劃在k上面，那么：
dp[i][j] = max(dp[k][j-1],sum(nums[k~i]));因?yàn)樾枰玫阶钚〉淖畲笾担虼吮闅vk；取最小的。

class Solution {
    public int splitArray(int[] nums, int m) {
        int[][] memo = new int[nums.length][m+1];
        int res = Integer.MAX_VALUE;
        res = Math.min(res,dp(nums,nums.length-1,m,memo));
        return res;
    }

    public int dp(int[] nums , int i, int m,int[][] memo){
        if(m>i+1){
            return 0;
        }
        if(m==1){
            return sum(nums,0,i);
        }
        if(memo[i][m]!=0){
            return memo[i][m];
        }
        int minValue = Integer.MAX_VALUE;
        for(int k=0;k<i;k++){
            minValue = Math.min(minValue,Math.max(dp(nums,k,m-1,memo),sum(nums,k+1,i)));
        }  
        memo[i][m] = minValue;
        return minValue;
    }

    public int sum(int[] nums, int i, int j){
        
        int maxValue = 0;
        for(int k=i;k<=j;k++){
            maxValue += nums[k];
        }
        return maxValue;
    }
}

446. 等差數(shù)列劃分 II - 子序列

難度困難45 收藏 分享 切換為英文 關(guān)注 反饋

如果一個(gè)數(shù)列至少有三個(gè)元素，并且任意兩個(gè)相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。

例如，以下數(shù)列為等差數(shù)列:

1 2 3 4 5

示例：

輸入：[2, 4, 6, 8, 10]

輸出：7

解釋：
所有的等差子序列為：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        long ans = 0;
        Map<Integer, Integer>[] cnt = new Map[n];
        for (int i = 0; i < n; i++) {
            cnt[i] = new HashMap<>(i);
            // f[i][diff] 表示以 A[i]為結(jié)尾，差為diff的子序列數(shù)目（長度為2個(gè)以上的子序列數(shù)目）
            // f[i][A[i]-A[j]] = f[j][A[i]-A[j]] + 1;
            // 可能出現(xiàn)重復(fù)的情況 A[i]-A[j] 重復(fù)。即j值重復(fù)。
            // 那么，f[i][A[i]-A[j]] += f[j][A[i]-A[j]] + 1;
            // 其中 +1 指增加了[A[i],A[j]];
            // 舉例  若f[j][1] 包含  {2,3} {1,2,3}
            // 那么 f[i][1] 包含 {2,3,4} {1,2,3,4} {3,4} 
            // 用n個(gè)HashMap存 f[j][diff]的值；
            // 存的是該A[i]為結(jié)尾的數(shù)組，Map為 diff:count
            for (int j = 0; j < i; j++) {
                long delta = (long)A[i] - (long)A[j];
                if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE) {
                    continue;
                }
                int diff = (int)delta;
                int sum = cnt[j].getOrDefault(diff, 0);
                int origin = cnt[i].getOrDefault(diff, 0);
                cnt[i].put(diff, origin + sum + 1);
                ans += sum;
            }
        }
        return (int)ans;        
    }
}

4. 尋找兩個(gè)有序數(shù)組的中位數(shù)

給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。

請你找出這兩個(gè)有序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))。

你可以假設(shè) nums1 和 nums2 不會(huì)同時(shí)為空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

則中位數(shù)是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

則中位數(shù)是 (2 + 3)/2 = 2.5</pre>

思路：
要求復(fù)雜度為O(log(m+n))，則不能單純合并鏈表排序去中間的。
可以看成是在排序數(shù)組中取第K小的數(shù)。K = （m+n）/2;
將K/2；分別在該nums1和nums2中找到該索引，并比較值。較小值不可能為第K個(gè)數(shù)。因此舍棄較小值所在數(shù)組的1~K/2；如K=7；

image.png

image.png

舍棄之后，K = K-K/2 = 4；即，重新求第4小的數(shù)。

image.png

image.png

image.png

image.png

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //處理任何一個(gè)nums為空數(shù)組的情況
        if (m == 0) {
            if (n % 2 != 0)
                return 1.0 * nums2[n / 2];
            return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
        }
        if (n == 0) {
            if (m % 2 != 0)
                return 1.0 * nums1[m / 2];
            return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
        }
        int total = m + n;
        if((total&1)==1){
            return findKth(nums1,0,nums2,0,total/2+1);
        }    
        else{
            return (findKth(nums1,0,nums2,0,total/2) + findKth(nums1,0,nums2,0,total/2+1))/2.0;
        }
    }

    public int findKth(int[] nums1, int index1, int[] nums2 ,int index2, int k){

        if(index1>=nums1.length){
            return nums2[index2+k-1];
        }
        if(index2>=nums2.length){
            return nums1[index1+k-1];
        }
        if (k == 1){
            return Math.min(nums1[index1], nums2[index2]);
        }
        int mid1 = Integer.MAX_VALUE;
        int mid2 = Integer.MAX_VALUE;
        if((index1+k/2-1)<nums1.length){
            mid1 = nums1[index1+k/2-1];
        }
        if(index2+k/2-1<nums2.length){
            mid2 = nums2[index2+k/2-1];
        }
        // 如果mid2>mid1 或者mid2為無窮，則nums[index1+k/2]肯定不是第K大的數(shù)值。
        if(mid1<mid2){
            return findKth(nums1,index1+k/2,nums2,index2,k-k/2);
        }else{
            return findKth(nums1,index1,nums2,index2+k/2,k-k/2);
        }
    }
}

327. 區(qū)間和的個(gè)數(shù)

給定一個(gè)整數(shù)數(shù)組 nums，返回區(qū)間和在 [lower, upper] 之間的個(gè)數(shù)，包含 lower 和 upper。
區(qū)間和 S(i, j) 表示在 nums 中，位置從 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

說明:
最直觀的算法復(fù)雜度是 O(n²) ，請?jiān)诖嘶A(chǔ)上優(yōu)化你的算法。

示例:

輸入: nums = [-2,5,-1], lower = -2, upper = 2,
輸出: 3
解釋: 3個(gè)區(qū)間分別是: [0,0], [2,2], [0,2]，它們表示的和分別為: `-2, -1, 2。

思路：暴力法較簡單，不再討論。
這題類似于求數(shù)組中逆序?qū)Φ膫€(gè)數(shù)：歸并排序。
區(qū)間和為連續(xù)的和；因此，用前綴和來做。
即用sum[i]表示，0~i區(qū)間內(nèi)的nums之和。
那么 區(qū)間和表示為 s[j]-s[i] 及 [i,j]的區(qū)間和。
s[j] - s[i] >= lower && s[j] - s[i] <= upper 即滿足條件。

如果存在下面這個(gè)序列，左邊藍(lán)色部分是有序的，右邊黃色部分是有序的，求有多少個(gè)答案滿足：

0≤S[i]?S[j]≤4,S[i]∈黃色，S[j]∈藍(lán)色

image.png

我們嘗試求解:
首先Left指針指向藍(lán)色部分最左端，Lower指針和Upper指針指向黃色部分最左端。

image.png

image.png

此時(shí)Upper - Lower就是Left（-1）所對應(yīng)的個(gè)數(shù)，這里等于0，因?yàn)閁pper和Lower之后的值更大，更不可能滿足要求。

接著向左移動(dòng)Left，但是Upper和Lower并不需要往后移動(dòng)。
因此Left（0）對應(yīng)個(gè)數(shù)為0，繼續(xù)移動(dòng)Left,并相應(yīng)地移動(dòng)Upper和Lower得到：
可以得到Left(7)對應(yīng)個(gè)數(shù)為2,最后移動(dòng)Left，Upper和Lower得到：
可以得到Left(9)對應(yīng)個(gè)數(shù)為0。
因此最后答案為2，并且我們通過線性的實(shí)現(xiàn)就完成了求解過程，因?yàn)長eft,Upper,Lower都只向右掃描了一遍。
我們回顧一下歸并排序，歸并排序能夠?qū)蓚€(gè)有序序列在線性時(shí)間復(fù)雜度下完成合并，我們這里是類似的。

// 歸并的坑： 注意 一： left=right 時(shí)（即一個(gè)數(shù)字時(shí)，需要判斷該數(shù)字是否滿足條件） 
//注意二： 需要使用long類型。
class Solution {
    int res = 0;
    public int countRangeSum(int[] nums, int lower, int upper) {
        int left = 0;
        int right = nums.length-1;
        if(right<0){
            return 0;
        }
        long[] sum = new long[nums.length];
        long count = 0;
        for(int i=0;i<nums.length;i++){
           count += nums[i];
           sum[i] = count;
        }
        merge(sum,left,right,lower,upper);
        return res;
    }

    public void merge(long[] nums, int left, int right, int lower, int upper){

        if(left>=right){
            if(nums[left]>=lower&&nums[left]<=upper){
                res++;
            }
            return;
        }
        int mid = (left+right)/2;
        merge(nums,left,mid,lower,upper);
        merge(nums,mid+1,right,lower,upper);
        mergeSort(nums,left,mid,right,lower,upper);
    }

    public void mergeSort(long[] nums, int left, int mid, int right, int lower, int upper){
        long[] temp = new long[nums.length];
        int index = left;
        int leftStart= left;
        int leftEnd = mid;
        int rightStart = mid+1;
        int rightEnd = right;
        int lowerIndex = mid+1;
        int upperIndex = mid+1;
        int numElements = rightEnd - leftStart + 1;
        for(int i=leftStart;i<=leftEnd;i++){
            while(lowerIndex<=right&&nums[lowerIndex]-nums[i]<lower){
                lowerIndex++;
            }
            while(upperIndex<=right&&nums[upperIndex]-nums[i]<=upper){
                upperIndex++;
            }
            res += upperIndex-lowerIndex;
        }

        while(leftStart<=leftEnd&&rightStart<=rightEnd){
                        
            if(nums[leftStart]<nums[rightStart]){
                temp[index++] = nums[leftStart++];
            }else{
                temp[index++] = nums[rightStart++];
            }
        }

        if(leftStart>leftEnd){
            while(rightStart<=rightEnd){
                temp[index++] = nums[rightStart++];
            }
        }else{
            while(leftStart<=leftEnd){
                temp[index++] = nums[leftStart++];
            }
        }
          for(int i = 0; i < numElements; i++,rightEnd--) {
            nums[rightEnd] = temp[rightEnd];
          }
    }
}

664. 奇怪的打印機(jī)

有臺奇怪的打印機(jī)有以下兩個(gè)特殊要求：

1. 打印機(jī)每次只能打印同一個(gè)字符序列。
2. 每次可以在任意起始和結(jié)束位置打印新字符，并且會(huì)覆蓋掉原來已有的字符。

給定一個(gè)只包含小寫英文字母的字符串，你的任務(wù)是計(jì)算這個(gè)打印機(jī)打印它需要的最少次數(shù)。

示例 1:

輸入:* "aaabbb"
輸出: 2
解釋: 首先打印 "aaa" 然后打印 "bbb"。
</pre>

示例 2:

輸入: "aba"
輸出: 2
解釋: 首先打印 "aaa" 然后在第二個(gè)位置打印 "b" 覆蓋掉原來的字符 'a'。</pre>

思路：
用dp[i][j]表示從打印s[i~j]的最小使用次數(shù)。
其中s[i]肯定是一次打印。那么在s[i~j]中找到與s[i]相同或的s[k]，s[i]==s[k]，
那么可以用一次打印從i~打印到k。這樣可以減少一次打印s[k]的次數(shù)。那么dp[i][k] = dp[i][k-1];
dp[i][j] = dp[i][k-1] + dp[k+1][j];
在所有滿足條件的k中選擇最小的：于是有
dp[i][j] = Math.min(dp[i][k-1]+dp[k+1][j])；
如果不存在滿足條件的k，那么默認(rèn)就打印一個(gè)s[i]，即初始化dp[i][j] = 1 + dp[i+1][j]；

class Solution {
    int[][] memo;
    public int strangePrinter(String s) {

        // dp[i][j] 打印s[i~j]所需要的次數(shù)。
        // s[i] = s[k]，則可以從i打印到k，一次打印s[k]，且dp[i][k] = dp[i][k-1];
        // dp[i][j] = min(dp[i][k-1]+dp[k+1][j])
        int n = s.length();
        memo = new int[n][n];
        int i=0;
        return dp(s,0,n-1);
    }

    public int dp(String s , int i, int j){
        if(i>j){
            return 0;
        }
        if(memo[i][j]!=0){
            return memo[i][j];
        }
        int res = dp(s, i+1, j) + 1;
        int index = 0;
        for(int k=i+1;k<=j;k++){
            if(s.charAt(i)==s.charAt(k)){
                res = Math.min(res,dp(s,i,k-1)+dp(s,k+1,j));
            }
        }
        memo[i][j] = res;
        return res;
    }
}