Python

class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        min_now = max_now = A[0]        
        nmin = nmax = nsum = A[0]
        for num in A[1:]:
            min_now = min(num, min_now + num)
            nmin = min(nmin, min_now)
            max_now = max(num, max_now + num)
            nmax = max(nmax, max_now)
            nsum += num
        if nsum == nmin: return nmax
        return max(nsum - nmin, nmax)

C#

public class Solution {
    public int MaxSubarraySumCircular(int[] A) {
        int min_now = A[0]; int max_now = A[0];
        int nmin = A[0]; int nmax = A[0]; int nsum = A[0];
        for(int i = 1; i < A.Length; i++)
        {
            int num = A[i];
            min_now = (min_now + num < num) ? min_now + num : num;
            nmin = nmin < min_now ? nmin : min_now;
            max_now = (max_now + num > num) ? max_now + num : num;
            nmax = nmax > max_now ? nmax : max_now;
            nsum += num;
        }
        if(nsum == nmin){return nmax;}
        return (nmax > nsum - nmin) ? nmax : nsum - nmin;
    }
}

要實作 trie ，有 insert, search 和 startsWith 的功能。

trie 很實用，但在 algorithm 中，不太好用上這樣的方法解題。昨日在學 cisco ，就使用 trie 來加速指今輸入。

由於 Leetcode 有教學，這裡就不多說如何解題。(如果懂 trie 是怎樣的型態就會知道要怎麼寫)

Python

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        now = self.trie
        for char in word:
            if char not in now: now[char] = {}                
            now = now[char]
        now['exist'] = True
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        now = self.trie
        for char in word:
            if char not in now: return False
            now = now[char]
        return 'exist' in now 
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        now = self.trie
        for char in prefix:
            if char not in now: return False
            now = now[char]
        return True 

C#

class TrieNode
{
    public bool End;
    public Dictionary Next;
    public TrieNode() {   
        Next = new Dictionary();
        End = false;
    }
}

public class Trie {
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void Insert(string word) {
        TrieNode now = root;
        foreach(char c in word)
        {
            if(!(now.Next.ContainsKey(c)))
            {
                now.Next[c] = new TrieNode();
            }
            now = now.Next[c];
        }
        now.End = true;
    }
    
    /** Returns if the word is in the trie. */
    public bool Search(string word) {
        TrieNode now = root;
        foreach(char c in word)
        {            
            if(now.Next.ContainsKey(c))
            {
                now = now.Next[c];
            }
            else
            {
                return false;
            }
        }
        return now.End;        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public bool StartsWith(string prefix) {
        TrieNode now = root;
        foreach(char c in prefix)
        {            
            if(now.Next.ContainsKey(c))
            {
                now = now.Next[c];
            }
            else
            {
                return false;
            }
        }
        return true;
    }
} 

Python

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        result = "0"
        for i, c in enumerate(num):
            while c < result[-1] and k:
                result = result[:-1]
                k -= 1
            if k == 0:
                result += num[i:]
                break               
            result += c
                
        if k: result = result[:-k]
        result = result.lstrip("0")
        if result: return result
        return "0" 

C#

public class Solution {
    public string RemoveKdigits(string num, int k) {
        string result = "0";
        int n = result.Length;
        for(int i = 0; i < num.Length; i++)
        {            
            n = result.Length;
            while(num[i]  0)
            {                
                result = result.Substring(0, n - 1);
                k -= 1;
                n -= 1;
            }
            if(k == 0)
            {
                n = num.Length;
                result = result + num.Substring(i, n - i);
                break;
            }
            result += num[i];            
        }
        n = result.Length;
        if(k > 0)
        {
            result = result.Substring(0, n - k);
        }
        result = result.TrimStart('0');
        if(result.Length == 0)
        {
            return "0";
        }            
        return result;            
    }
}

Python

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:        
        l, r = 0, len(nums)-1
        while l < r:
            m = (r-l)//2 + l
            if nums[m-m%2] == nums[m+1-m%2]:
                l = m+1
            else:
                r = m
        return nums[r]

C#

public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        int l = 0; int r = nums.Length-1;
        while(l < r)
        {
            int m = (r-l)/2 + l;
            if(nums[m - m%2] == nums[m - m%2 + 1])
            {
                l = m + 1;
            }
            else
            {
                r = m;
            }
        }
        return nums[r];
    }
}

給一個二維陣列，要把[sr][sc]位置上的顏色(值)換成 newColor，像是油漆桶工具，回傳取代過後的二維陣列。

這題是「遞迴函數」的基本題。

遇到在這種二維陣列的題型，選一個點上下左右找，為了避免同一位置重複找，用hash類紀錄找過的位置作檢查。

如果用 for迴圈 要思考整體是由左上至右下找，會不會因此有漏網之魚，如果有，還是得回歸 遞迴函數。

Python

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        rows, cols = len(image), len(image[0])
        oldColor = image[sr][sc]       
        
        @lru_cache(None)
        def search(y, x):
            if y < 0 or x < 0 or y == rows or x == cols:
                return 
            if image[y][x] == oldColor:
                image[y][x] = newColor
                search(y-1, x)
                search(y+1, x)
                search(y, x-1)
                search(y, x+1)            
                
        if oldColor != newColor: search(sr, sc)            
        return image

C#

public class Solution {
    int rows;
    int cols;
    public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
        var oldColor = image[sr][sc];
        rows = image.Length;
        cols = image[0].Length;
        if(oldColor != newColor)
        {
            Fill(image, sr, sc, newColor, oldColor);
        }
        return image;
    }
    
    public void Fill(int[][] image, int y, int x, int newColor, int oldColor)
    {
        if(y >= 0 && y = 0 && x < cols && image[y][x] == oldColor)
        {
            image[y][x] = newColor;
            Fill(image, y-1, x, newColor, oldColor);
            Fill(image, y+1, x, newColor, oldColor);
            Fill(image, y, x-1, newColor, oldColor);
            Fill(image, y, x+1, newColor, oldColor);
        }
    }    
}

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        from collections import defaultdict
        beTrust = defaultdict(int)
        candidates = set(range(1,N+1))
        for t in trust:
            beTrust[t[1]] += 1
            if t[0] in candidates: candidates.discard(t[0])
        for c in list(candidates):
            if beTrust[c] != N-1:
                candidates.discard(c)
        if len(candidates) == 1:
            return candidates.pop()
        return -1

C#

public class Solution {
    public int FindJudge(int N, int[][] trust) {        
        var candidates = new HashSet();        
        var beTrusted = new Dictionary();        
        for(int i=1; i <= N; i++)
        {
            candidates.Add(i);
            beTrusted[i]=0;
        }
        foreach(var t in trust){
            beTrusted[t[1]] += 1;
            if(candidates.Contains(t[0]))
            {
                candidates.Remove(t[0]);
            }            
        }
        int result = -1;
        foreach(var c in candidates)
        {
            if(beTrusted[c] == N-1)
            {
                if(result==-1)
                {
                    result = c;
                }
                else
                {
                    return -1;
                }
            }
        }
        return result;
    }
}