給一串非負數列，數列上的元素是最大能跳的次數，從位置[0]出發，回傳是否能到達最後一個索引的布林值。

從位置[0]出發，並記錄剩餘的可跳次數，同時跟當前的元素取最大值。

如果在最後一個索引前可跳次數為零，也代表無法跳到終點，可以提前回傳False。順利遍歷數列的話，則回傳True。

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        remainJump = 1
        nums.pop()
        for num in nums:
            remainJump -= 1
            remainJump = max(remainJump, num)
            if remainJump == 0: return False
        return True

C#

public class Solution {
    public bool CanJump(int[] nums) {
        int remainJumps = 1;
        int index = 0;
        foreach(var num in nums)
        {
            remainJumps -= 1;
            remainJumps = num > remainJumps ? num: remainJumps;
            if (remainJumps==0 && index < nums.Length-1)
            {
                return false;
            }
            index++;
        }
        return true;
    }
}

編寫一個 cache ，採取  Least recent used的方式替換已滿cache。

這道題目，有一個關鍵特點，就是會依照最近的使用次序來決定哪一個要在已滿的情形被先換掉。

所以，要有個能紀錄使用次序的方式。

如果某鍵被使用到，那就把它挪到最後方；如果需要替換，就先刪除第一個鍵。

還要有個記錄對應值的 hashtable ，如果使用 get() ，才能從其中撈出值來。

要實現這樣的功能，python有 OrderedDict 類別可以使用（from collections import OrderedDict)，這是我覺得最快速的方式。

即使不用，用 dict 與 list 也能做出一樣的機制，只是慢上許多。

不然還有一種方式，使用 linkedlist 做出來，因為只要改變指向，所以會比起用 list 刪改還快上不少。

Python

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.cachelist = []

    def get(self, key: int) -> int:
        if key in self.cache:
            self.cachelist.remove(key)
            self.cachelist.append(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:            
            self.cachelist.remove(key)
        elif len(self.cachelist) == self.capacity:
            del self.cache[self.cachelist[0]]
            del self.cachelist[0]
        self.cache[key] = value
        self.cachelist.append(key)

C#

public class LRUCache {
    public int cap;
    public Dictionary cache = new Dictionary();
    public List cachelist = new List();
    
    public LRUCache(int capacity) {
        cap = capacity;
    }
    
    public int Get(int key) {
        if (cache.ContainsKey(key))
        {
            cachelist.Remove(key);
            cachelist.Add(key);
            return cache[key];
        }
        else
        {
            return -1;
        }
    }
    
    public void Put(int key, int value) {
        if(cache.ContainsKey(key))
        {
            cachelist.Remove(key);
        }
        else if(cachelist.Count == cap)
        {
            cache.Remove(cachelist[0]);
            cachelist.Remove(cachelist[0]);
        }
        cachelist.Add(key);
        cache[key] = value;

    }
}

給一個範圍 [m, n] where 0 <= m <= n <= 2147483647，回傳範圍內所有(整數)的 位元且 結果。

說位元計算是我很少碰到的一塊，不熟悉。

設想一個攤開的情形，答案會是最高位起的連續相同部分取 1， 剩下取 0。

1111011
1100000
11xxxxx => x都會出現0

正因為這是二進位，所以 m, n 之間的數字會使得在最高位連續相同的部分之後的各位置都會有 0 的出現。

因此將著重在如何得到目標部分。

如果 m, n 不相同，m, n往右移一位，直到最高位連續相同的部分時，m == n (※這二者不斷位移後的情形)

由於 m, n 都被動過，到這裡要向左移還原剛右移的部分，因此在剛右移的部分加一變數記錄次數。

Python

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        i = 0
        while m != n:
            m >>= 1
            n >>= 1
            i += 1
        return m << i  

C#

public class Solution {
    public int RangeBitwiseAnd(int m, int n) {
        int times = 0;
        while(m != n)
        {
            m >>= 1;
            n >>= 1;
            times++;            
        }
        return m << times;
    }
}

給一串整數數列與整數 k ，請回傳有多少個連續子數列總和為 k 。

看到這種 sum 的問題，心中就先想到 k – sum 是否在某一資料(也許 dict 或 list)內，那資料也是某種 sum。

k – sumA = sumB 利用「交換律」來解。

剛好是連續子數列，加上提示有說到「 sum(i,j) = sum(0,j) – sum(0,i)」，這點出了該如何搭配上交換律。

把出現過的 sum 值保存起來，接著再用 k – sum 去找是否它存在於剛剛保存下來的各sum值內。這是核心的想法。

這裡按照實際撰寫的順序。

先把 0 加入到 memo，其值為 1 ，代表 0 出現過一次。

用一個for迴圈，得到 sum(0, i)，檢查 k – sum(0,i) 是否在 memo 內，如果有則 result += memo[sum(0,i)]。

接著再把 sum(0,i) 加入 memo 中，使 memo 保存各值的出現次數。

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        result = 0
        nsum = 0
        memo = {0:1}
        for num in nums:   
            nsum += num
            if nsum-k in memo:
                result += memo[nsum-k]            
            memo[nsum] = memo.get(nsum, 0) +1
        return result

C#

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        int nsum = 0, result = 0;
        var memo = new Dictionary();
        memo.Add(0,1);
        foreach(int num in nums)
        {
            nsum += num;
            if (memo.ContainsKey(nsum - k))
            {
                result += memo[nsum - k];               
            }
            if (memo.ContainsKey(nsum))
            {
                memo[nsum]++;               
            }
            else
            {
                memo.Add(nsum, 1);
            }
        }
        return result;
    }
}

給一個 BinaryMatrix 類別的物件，該物件有個由 0, 1 組成的二維串列屬性，要找出至少有個1的欄位最小索引，沒有則回傳-1。

該物件有兩個方法，一 get()，只能透過此方法去取得特定位置上的值。二 dimensions()，此方法會回傳列欄大小。

每列的值有經過排序(由小至大)。

如果呼叫 get() 超過1000次，也算失敗。

欄列的大小不超過100。

開始思考要如何找出目標值，除了每排有經過排序，但每欄並沒有提及。

因此除非知道每排最早出現 1 的位置，不然也暫時沒想到更好的方法。

get() 次數限制之下，每排要在 10 次內找出第一個 1 出現位置，最糟要在一百個已經排序的元素中搜查。

使用二分搜查法，50 > 25 > 13 > 7 > 4 > 2 > 1 ，最糟也能在七次內找到第一個 1 的位置。 萬一沒有，索引也會在等於欄數。這樣也能在限制內完成搜查。

Python

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        rows, cols = binaryMatrix.dimensions()
        memo = []
        for row in range(rows):
            l, r = 0 , cols
            while l < r:
                m = (r-l)//2 + l
                if binaryMatrix.get(row, m) == 0:
                    l = m + 1
                else:
                    r = m
            memo.append(r)
        return min(memo) if min(memo) < rows else -1

C#

class Solution {
    public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        int rows = binaryMatrix.Dimensions()[0];
        int cols = binaryMatrix.Dimensions()[1];
        // 使用 Binary search，取得每行上最小的1位置
        int minPos = cols;
        int r,m,l;
        for(int i = 0; i < rows; i++)
        {
            l = 0;
            r = cols;
            while(l < r)
            {
                m = (r-l)/2+l;
                if(binaryMatrix.Get(i,m)==0)
                {
                    l = m + 1;
                }
                else
                {
                    r = m;               
                }
                
            }
            minPos = r < minPos ? r: minPos;
        }      
        return minPos < cols ? minPos: -1;
    }
}

給一串依 preorder 順序遍歷二分樹的值，要還原成二分樹，並回傳根。

這二分樹是嚴格的那種，代表左邊子樹皆小於自身，右邊皆大於自身。

依照 preorder 的順序，先自身，再左邊，再右邊。還原也依此進行。

說到要依順序還原，不管是哪種，都要有保留父節的規劃，因為子節是沒辦法往上回溯的。(或者使用遞迴函數)

※一開始先將 root 生成，最後要回傳它。

這裡使用 stack 的概念來保存父節，一旦目前迴圈的值小於 stack[-1] ，那就添加至左邊，並加入該節至 stack。

如果該節大於 stack[-1]，則檢查 stack[-2] 是否小於目前的值，是則不斷刪去 stack[-1] 直到 stack[-2] 大於目前的值或 stack 只剩一個。

然後把該節指派給 stack[-1].rihgt 後刪除 stack[-1]，並添加該節至 stack 中。

這做法類似實際 preorder 的途徑。

Python3

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        root = TreeNode(preorder.pop(0))
        stack = [root]
        while preorder:
            node = TreeNode(preorder.pop(0))
            if node.val < stack[-1].val:
                stack[-1].left = node
                stack.append(node)
            else:
                while len(stack) >= 2 and stack[-2].val < node.val:
                    del stack[-1]
                stack.pop().right = node
                stack.append(node)              
        return root

C#

public class Solution {
    public TreeNode BstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        List stack = new List{root};
        for(int i = 1; i < preorder.Length; i++)
        {
            TreeNode node = new TreeNode(preorder[i]);
            if(node.val < stack[stack.Count-1].val)
            {
                stack[stack.Count-1].left = node;
                stack.Add(node);
            }
            else
            {
                while(stack.Count>=2 && stack[stack.Count-2].val < node.val)
                    stack.RemoveAt(stack.Count-1);
                stack[stack.Count-1].right = node;
                stack.RemoveAt(stack.Count-1);
                stack.Add(node);
            }
        }        
        return root;
    }
}

除了 stack ，也可以使用「遞迴」解決。
Python 搭配二分搜查

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        if not preorder: return None
        def nextNode(l, r):
            if l==r: return None
            node = TreeNode(preorder[l])        
            l2, r2 = l+1, r
            while l2 < r2:
                m = (r2-l2)//2 + l2
                if preorder[m] < node.val: 
                    l2 = m+1
                else:
                    r2 = m
            node.left = nextNode(l+1, l2)
            node.right = nextNode(l2, r)
            return node
        return nextNode(0, len(preorder))

C# Linq篩選

public class Solution {
    public TreeNode BstFromPreorder(int[] preorder) {
        if(preorder.Length == 0){return null;}
        TreeNode node = new TreeNode(preorder[0]);  
        node.left = BstFromPreorder((from num in preorder where num < preorder[0] select num).ToArray());
        node.right = BstFromPreorder((from num in preorder where num > preorder[0] select num).ToArray());
        return node;
    }
}

今天有C#，因為我看蠻多ASP的工作缺，練習ASP也得加強C#。

給一串數組，經過排序但旋轉過(向右移動?次)，且每個數字不重複，並且要求在時間複雜度 O(log n) 解決。

最直覺地使用 for 迴圈，但時間複雜度會是 O(n) ，不符合要求。

說到 O(log n) ，二分搜尋是最典型的方法。用兩次二分搜尋，一次是找到排序的分界(最大值)，二是從分界往左或右找到目標值。O(log 2n) => O(log n)

設左界 l 右界 r，中間為 m = (r-l)/2 + l 。第一次找將比對目標 t 先設為 nums[0] ，如果 nums[m] > t ，更新 t 並移動左界 l = m+1，否則不更新 t 但移動右界 r = m。

直到 l == r，此時為 nums[l] or nums[r] 都是最大值。

若目標值 target 小於 nums[0] ，表示目標值在最大值右方，否則在最大值左方。針對情況移動右界至nums的長度或左界至0。

再用一次二分搜尋法，這次的比對目標就是 target，當 l 等於 r 時沒有找到就回傳 -1 ，其餘為當下的索引 m 。

PYTHON3

class Solution:       
    def search(self, nums: List[int], target: int) -> int:
        if not nums: return -1
        maxNum = nums[0]
        n = len(nums)
        l, r = 0, n
        while l < r:
            m = (r-l)//2 + l
            if nums[m] >= maxNum:
                maxNum = nums[m]
                l = m+1
            else:
                r = m
        #
        if target < nums[0]: r = n    
        else: l = 0     
        #
        while l < r:
            m = (r-l)//2 + l
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m
            else:
                l = m + 1
        return -1

C#

public class Solution {
    public int Search(int[] nums, int target) {        
        int r = nums.Length;
        if(r==0){return -1;}
        int l = 0;
        int maxNum = nums[0];
        // 先找出最大值的位置
        while(l < r){
            int m = (r-l)/2+l;
            if(nums[m] >= maxNum){
                maxNum = nums[m];
                l = m+1;
            }else{
                r = m;
            }
        }
        //從中間開始找
        if(target < nums[0]){
            r = nums.Length;
        }else{
            l = 0;
        }
        //
        while(l < r){
            int m = (r-l)/2+l;
            if(nums[m] == target){
                return m;
            }else if(nums[m] < target){
                l = m+1;            
            }else{
                r = m;
            }
        }       
        return -1;
    }
}