JN的電腦網路日常 - Page 32 of 39 - 網路教學與日常學習

Leetcode

Leetcode題解 Python：四月挑戰DAY28 First Unique Number

有一個 queue 類別 FirstUnique 特點是要回傳第一個沒有重複的整數。要完成有這項功能的 FirstUnique 。

這個題目倒是沒有 remove 的功能要實現，所以相當容易解決。

要如何知道重複出現？最快的找法就是使用hash 類的資料型態去記錄。

單獨出現過的放在一個 hashtable 不用set是因為我們要保留序列；重複出現的移到第二個 hashtable，並刪除第一個 hashtable 的鍵。

如此 showFirstUnique() 只需要看第一個 hashtable 的第一個鍵，沒有鍵則是 return -1

Python

class FirstUnique:

    def __init__(self, nums: List[int]):
        self.memo = Counter(nums)   
        self.memo2 = defaultdict(int)        
        for key in list(self.memo.keys()):
            if self.memo[key] > 1:
                del self.memo[key]
                self.memo2[key] += 1 

    def showFirstUnique(self) -> int:
        if self.memo:
            for key in self.memo:
                return key
        else:
            return -1


    def add(self, value: int) -> None:
        if value in self.memo2:
            pass
        elif value in self.memo:
            del self.memo[value]
            self.memo2[value] += 1
        else:
            self.memo[value] = 1

Jian Ning
2020-04-28

Leetcode

Leetcode題解 Python & C#：四月挑戰DAY27 Maximal Square

給一個2D矩陣，其中只有 1 或 0 ，找出最大的連續 1 組成的最大正方形面積。

首先來想要怎樣去找任意一個正方形的面積。

如果選定某一位置，那正方形會在往右下延伸、或左上，簡單來說就是四周。

不過這樣相當不容易寫，而且也會效率不佳。

再觀察一下，正方形出現時會有怎樣的情形？

假設有個面積為 4 的正方形：

基礎假設

可以發現組成邊長2的正方形，其相鄰加身自身會有2個連續出現1超過二次。

同理邊長為3的正方形。

計算流程

於是各欄只要計數1的連續出現次數，接下來問題變成要如何從數列中找出最大的正方形面積。

接著要去從數列中求出最大的正方形面積。

我這裡使用暴力破解法，以自身為左右索引的起始點，往左右找有大於自身數值的個數。
如 2 ，只要往左右再找一個，因為自身本身可以當作一個計數。

過程中，數值小於當前的最大面積的邊長也可以跳過不往左右找。

Python

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]: return 0       
        rows,cols= len(matrix), len(matrix[0])
        cur = [0]*cols
        maxSideLength = 0
        for y in range(rows):
            # 逐行掃瞄
            for x in range(cols):
                if matrix[y][x] == "1":
                    cur[x] += 1
                else:
                    cur[x] = 0
            # 檢查連續最大值
            for x in range(cols):                 
                v = cur[x]
                if v <= maxSideLength: continue                    
                v -= 1
                l, r = x, x
                while v:
                    if l > 0 and cur[l-1] >= cur[x]:
                        l-=1
                        v-=1
                        continue
                    if r = cur[x]:
                        r+=1
                        v-=1
                        continue
                    break
                if v==0: 
                    maxSideLength = max(maxSideLength, cur[x])
        return maxSideLength**2

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        if(matrix.Length == 0 || matrix[0].Length == 0){return 0;}
        var cur = new int[matrix[0].Length];
        Array.Fill(cur, 0);
        int maxSideLength = 0;
        
        for(int y = 0; y < matrix.Length; y++)
        {
            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(matrix[y][x]=='1')
                {
                    cur[x] += 1; 
                }
                else
                {
                    cur[x] = 0;
                }               
            }

            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(cur[x] <= maxSideLength)
                {
                    continue;
                }
                int num = cur[x]-1;
                int l = x; int r = x;
                while(num > 0)
                {
                    if(l > 0 && cur[l-1] >= cur[x])
                    {
                        l -= 1;
                        num -= 1;
                        continue;
                    }
                    if(r = cur[x])
                    {
                        r += 1;
                        num -= 1;
                        continue;
                    }
                    break;
                }
                if(num==0)
                {                    
                    maxSideLength = cur[x];
                }
            }
        }
        
        return maxSideLength*maxSideLength;
    }
}

Jian Ning
2020-04-27

Leetcode

Leetcode題解 Python & C#：四月挑戰DAY26 Longest Common Subsequence

給兩個字串，請回傳兩字串有幾個相同的部分？匹配的位置可以不用相鄰，但相對位置要一致。

這不是一般的字串匹配問題，因為匹配的部分可以不相鄰。

換個思維，要如何做到不相鄰的配對？

首先看兩者的[0]位，如果相同，則兩者往右尋找。
若不，則 text2 往下一位 [j+1] 匹配,，因此，對應 text2 的索引 j 的意思是 j 之前的匹配數目。
如果沒有匹配對，那 [j] 就等於上一位 [j-1] 的數目。
此外，因為可以不相鄰，所以 text1[i] text2[j] 沒有匹配到的話，[i][j]也可以從[i-1][j] 得到匹配數目。
於是沒有匹配的話 => [i][j] = max([i-1][j], [i][j-1])

這是正序的方法，若看 Hint ，我第一個寫成反序的遞迴函數，其實道理都相同。

如果有匹配到，數目一定是 +1 ，那是什麼位置的數目 +1 ？
[i-1][j-1]，這邏輯就像一般的字符匹配那般。

流程

Python

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1, l2 = len(text1), len(text2)
        cur = [0] * (l2+1)
        for i in range(l1):
            cur, pre = [0]*(l2+1), cur
            for j in range(l2):
                if text1[i] == text2[j]:
                    cur[j] = pre[j-1] + 1
                else:
                    cur[j] = max(cur[j-1], pre[j])
        return cur[-1]

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        var cur = new int[text2.Length+1];
        Array.Fill(cur, 0);
        for(int i = 0; i < text1.Length; i++)
        {
            var pre = cur;
            cur = new int[text2.Length+1];
            Array.Fill(cur, 0);
            for(int j = 0; j < text2.Length; j++)
            {
                if(text1[i] == text2[j])
                {
                    cur[j+1] = pre[j] + 1;
                }
                else
                {
                    cur[j+1] = (cur[j] > pre[j+1])? cur[j]: pre[j+1];
                }
            }
        }
        return cur[text2.Length];
    }
}

Jian Ning
2020-04-26

Leetcode

Leetcode題解 Python & C#：Constrained Subset Sum

給一串整數陣列，回傳最大非空子集合的最大總和，子集合為連續的 nums[i] nums[j] 組成，j<i 且 j-i <= k。

本來今天高高興興的，結果這一題沒有在時限內完成。光是看懂題目就已經用上三十分鐘。

等到明暸的時候，也無啥時間可寫了。檢討失敗的原因，我想是對這樣的題型陌生吧。

由於是集合，所以可選相同位置上的(如前一組的j，後一組的i)，但每一個位置只會被計算到一次。

因此如果使用深度優先的遞迴函數，我倒是沒寫好在取相同位置的判斷。(我就在這裡卡住)

這顕是DP的題型，因此選擇會紀錄什麼是接下來首先思考的。

如果遞迴函數不適合，那可以攤開變成迴圈，並且由後往前找。

由於一次選擇一定要成對nums[i] nums[j]，因此從 len(nums) – 2 之處開始。(-1位置是無法選一對的)

接者，在 [i+1,i+k] 的範圍中選擇最大的總和，所以DP是紀錄該位置上的總和，然後nums[i] + max([i+1:i+k+1])為dp[i]新的總和。

例題與流程：
[1,-1,1,2,3], 2
[1,-1,1,5,3]
[1,-1,6,5,3]
[1,5,6,5,3]
[7,5,6,5,3]
=> max() => 7

[-1,-2,-3],1
[-1,-2,-3]
[-1,-2,-3]
=> max() => -1

由於 k 可能會很大，如果都跑完一定會超時。但其實在選擇最大值的時候，就已經決定了題目中的子集合的最後一個元素。

如果迴圈[i+1,i+k]超越上次最大值所選的位置，後面也不會有更大的總和，所以當前位置就可以不用再往下選最大總和與自身相加。

去掉不必要的部分，這樣就能加快速度，順利完成此題。

Python

class Solution:
    def constrainedSubsetSum(self, nums, k):
        maxIndex = len(nums)
        for i in range(maxIndex-2, -1, -1):           
            value = nums[i]          
            for j in range(1,min(k+1,maxIndex-i)):
                if value + max(0, nums[i+j]) > nums[i]:
                    nums[i] = value + max(0, nums[i+j])
                    maxIndex = i+j+1
        return max(nums)

public class Solution {
    public int ConstrainedSubsetSum(int[] nums, int k) {
        int maxIndex = nums.Length;
        for(int i = nums.Length-2; i >= 0; i--)
        {
            int v = nums[i];
            int ik = (k+1 < maxIndex-i)? k+1: maxIndex-i;
            for(int j = 1; j < ik; j++)
            {
                int num = v + (nums[i+j] <= 0? 0: nums[i+j]);
                if( num > nums[i])
                {
                    nums[i] = num;
                    maxIndex = i+j+1;  
                }
                
            }
        }
        return nums.Max();
    }
}

Jian Ning
2020-04-26

Leetcode

Leetcode題解 Python：Restore The Array

給一由數字組成的字串，可以在任意位置上切割，但每個切割出來的數字要在[1,k] 之間，而且分割出來的數字不能有前導零的出現，要回傳有幾種可能。

(可能組合數很多，回傳結果對 10^9+7 的取餘)

這題明顯是dp的題目，因為要找出所有組合數，而且答案可能超級大。

如果使用遞迴函數，因為這題的 s.Length 可達 10^5，因此可能會超出最大遞迴深度而報錯。

先繼續講如何設計。

從位置[0]開始，如果左方的數字在[1,k] 之間，可以選擇在這裡切，或是住下一位切。因為要記錄上次的切割位置，所以得設一參數接收。
memo[pos][slicePos]

如果切，往深 dfs(pos+1, pos+1)；不切，dfs(pos+1, slicePos)。

要是下一位是 “0” 或是左方數字 < 1 ，那就只能不切，因為在這遞迴函數只取符合規則的方法數。

接著來思考中止條件。

如果 pos == s.length，檢查左方數字是否在範圍內，決定回傳 1 或 0 。

如果 int(s[slicePos:pos+1]) > k ，超出範圍，即回傳 0 。

python

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n = len(s)
        
        @lru_cache(None)
        def nextPos(i, j):            
            if i == n:
                if j != n and int(s[j:n]) >= 1 and int(s[j:n]) <= k: return 1
                return 0   
            while i < n-1 and s[i+1] == "0": 
                i += 1                                
            lnum = int(s[j:i+1])
            if lnum > k: return 0   
            return (nextPos(i+1, j)+nextPos(i+1, i+1)) % (10**9+7)
        
        # 由於可能超出最大深度，所以先執行一半
        nextPos(len(s)//2, len(s)//2)
        
        return nextPos(0, 0)

Jian Ning
2020-04-25

Leetcode

Leetcode題解 Python & C#：四月挑戰DAY25 Jump Game

給一串非負數列，數列上的元素是最大能跳的次數，從位置[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

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;
    }
}

Jian Ning
2020-04-25

Leetcode

Leetcode題解 Python & C#：四月挑戰DAY24 LRU Cache

編寫一個 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)

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;

    }
}

Jian Ning
2020-04-24

Python

Python 練習網路爬蟲 scrapy

看到有徵網路爬蟲的工讀生，我也想打個小工，如果時間可以配合的話。

但我已經有段時間沒有寫爬蟲程式，爬來佔硬碟空間，因為沒有想到要的資料，但我電腦每天都會運行爬蟲程式。

再次練習，除了css selector等的選擇器經驗不足，感覺自己寫得還有很多可以強化效率的部分。

這次要針對「缺失值」作更好的處理，因為大部分的爬蟲教學是不考慮爬取失敗的時候。

時代變遷，網頁也會改版，沒有永遠適用的爬蟲。一旦不能用，或是抓取的部分跑掉，這是一定要馬上處理好的事情。

因此，注重例外處理與警示是實戰必寫的。當然不寫例外直接跳出也是一種變向的警示，前提是要留意到。

況且，加載失敗也是會讓本來設定提取的部分失敗，導致爬取意外中止。格式跑掉並非是自身的問題，但是會害到你。

使用框架，可以大幅省去針對例外而寫處理的時間，因此我練習 scrapy。

—-分隔線—-

首先，我建議使用 anaconda ，從官網下載的。

如果是第一次用，從「本機」>「內容」>「進階」>「環境變數」>「系統變數」清單「Path」>「編輯」，新增三個「(anaconda的位置)」、「(anaconda的位置)\Scripts」、「(anaconda的位置)\Library\bin」」

這樣就可以用「字元提示命令」(cmd)去執行python(anaconda環境)。

在cmd輸入「pip install scrapy」安裝「scrapy」，安裝完成就可以用「scrapy startproject projectname」建立scrapy專案。

(小技巧：如果我想在 A資料夾建立專案，在「檔案總管」進入 A資料夾，在上方路徑輸入 cmd 後按enter，就能以當前資料夾為工作路徑執行cmd，這樣使用建立專案指令也會建在當前的資料夾

我使用 visual studio 把 scrapy 建立的專案都加進來，這樣方便編輯。

從官網教程學習是不錯的。

如果會使用 requests、BeautifulSoup，寫出scrapy spider絕對沒問題是。

這裡提一下scrapy的優勢，在 selector 沒有選到會是 None，而不像 BeautifulSoup 會報錯，用try except會是效率的拖油瓶。(從leetcode的解題觀察到的)

而且 scrapy 的框架有 items ，把資料統一丟到自定義物件內，省版面也美觀。如果沒用scrapy，我大概也會寫個類別接收資料。

異步爬取也是一點，寫 multiprocessing 或 threading，也是一門功夫，既然會想高效，這自然也是得寫的，如果不用scrapy的話。

資料終究要寫進資料庫，那為什麼一開始就不寫好資料庫的管道？這一塊 scrapy 也幫你準備好了，在 pipelines 這裡。

今天我終於開啟了雲端資料庫，我使用mongoDB Altas。我覺得最難的部分總是一開始的陌生，辦好帳號卻不知道要怎麼下一步。

辦好之後，從「SANDBOX」> Closter > 「CONNECT」可以設定連線代碼，這裡相當貼心，它可以生成可直接用的連線代碼(password要自己改)，複製到code中用pymongo模組連線即可。(參考)

成功連線並寫入一筆資料順利在cloud看到，我已心滿意足，最苦惱的不知道要塞什麼資料。

想學 scrapy ，也可以看 youtube，能搜到不錯的教學，所以我也不贅述。

這裡提供一個 xpath 選擇器的進階用法。 response.xpath(‘A | B’)，用這個就能抓下ptt文章的內文，包括內的文字，我目前沒看到範例有這樣寫的。

相較於 css ，我覺得 xpath 更精確，但我也才昨天開始接觸。 BeautifulSoup 好像沒有 xpath 可用。

目前最讓我苦手的還是 jsonp 仍舊沒有除了 selenium 以外的解法，關於 jsonp 討論不多，jsonp 屬於動態加載，我好像也是為此才看看 scrapy 。

Jian Ning
2020-04-24

Leetcode

Leetcode題解 Python & C#：四月挑戰 Bitwise AND of Numbers Range

給一個範圍 [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

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

Jian Ning
2020-04-23

Leetcode

Leetcode題解 Python & C#：四月挑戰DAY22 Subarray Sum Equals K

給一串整數數列與整數 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

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;
    }
}

Jian Ning
2020-04-22

日常

倉頡輸入法與打字手勢的一周學習歷程

約莫上周二晚間，我測驗我的中打速度，結果只有七十出頭，相當不滿意。再加上那時我的英打一直有按錯鍵的問題，於是想改正我的打字手勢。

渴望變厲害的性格作祟，喚醒心中強大的精力去改變習慣。

習倉頡並不是平易近人的，我發覺網路是有教材，但是幾乎都蠻舊的，說實在也是可用的。

先記憶字根，光是這點就蠻花費時間的。我建議可以在練習中記憶，這樣也可以幫助到拆解字型取碼。

這裡我是使用《五色倉頡試用版》，達到第一階段「記字根」的基本功。一直打，然後配合對照表去理解。

直到裡面的字已經熟練如何拆解。順利的話，一天就能打出許多字。

之後可以進行生活化的練打，不過一定會碰到不會拆解的字，就使用《Follow Me倉頡字典》查詢。

練習的時候，一定要把每一個不會的用查詢的字再打個幾遍，因為下一次還是會碰到，不會就還是得再查詢。

接著，此時一定要去注意字體組合，大部分的字碼輸入是相當有規則的，例如：「見」、「刂」、「頁」、「寺」，熟悉後，可快上一點。

一開始一定很不順手，集中注意力時，也要順便將字碼的位置用肌肉記憶下來，換句話說，就是得不看鍵盤就能找到字碼的位置。

最好連帶將標準打字手勢擺出來，記憶相對位置。這裡推薦使用倉頡之星，使用按鍵練習模式，練到8秒內可以不用看就能盲打即可。(我從別人的網誌下載的倉頡之星 )

我覺得不必瘋狂練打，一天兩小時就可以休息。也不用透過這些軟體練習到每分鐘三十字，生活常用打熟來，自然也就足以擔當你平時用的中文輸入法。

生活常見的詞彙要一定要去用空白鍵去看選詞的種類，一旦背下來，就能打字速度更上一層。

如果可以每分鐘十字以上，接下來的打字就不可以看鍵盤，太注意自己的手指有沒有按對，反而會拖累自己的打字速度。

只要靜下心，能慢慢按出對的字碼來就可以了。錯誤率小於三成就可以盲打階段。

「絕對不可以看鍵盤﹐因為你要把心思拿去思考如何拆字。」一旦做到，每分鐘又可以多打五個字。

我目前大約打字速度落在每分鐘十七字左右，還是會在每次練打使用字典去查拆解。

據這個網頁說，二到四周就能突破每分鐘三十字，如果有心學習就可以。

最近用上番茄鐘，這兩天開始記錄，如果速度呈直線增長，大概可以在第二周時進入到每分鐘三十字，但可能會早一兩天也說不定。

Jian Ning
2020-04-22

Leetcode

Leetcode題解 Python & C#：四月挑戰DAY21 Leftmost Column with at Least a One

給一個 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

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;
    }
}

Jian Ning
2020-04-21

目前趨勢