給一個大小為 n 的陣列，找出出現次數超過 n/2 的元素。(可以預期這個元素一定存在)

這個是計數題，數一遍 n 並且統計出現次數，就能找到 majority element。

 Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        import collections
        counter =  collections.Counter(nums)
        n = len(nums)
        for key in counter:
            if counter[key] >= n/2:
                return key

C#

public class Solution {
    public int MajorityElement(int[] nums) {
        var counter = new Dictionary();
        int halfN = nums.Length/2 + (nums.Length%2==1 ? 1: 0);
        foreach(var num in nums)
        {
            counter[num] = 1 + (counter.ContainsKey(num) ? counter[num]: 0);
            if(counter[num] >= halfN)
            {
                return num;
            }
        }    
        return 0;
    }
}

給一個字串，找出第一個沒有重複的字符位置，如果沒有則回傳 -1 。

沒有重複，代表該字符的計數為 1，只要找出最早的計數為 1 個字符。

最快的情形是跑一遍 N ，再挑出符合的，沒有那就是 -1 。

Python

class Solution:    
    def firstUniqChar(self, s: str) -> int:    
        import collections
        counter = collections.Counter(s)
        for key in counter:
            if counter[key] == 1: return s.index(key)
        return -1

C#

public class Solution {
    public int FirstUniqChar(string s) {
        var counter = new Dictionary();
        foreach(var c in s)
        {
            counter[c] = 1 + (counter.ContainsKey(c) ? counter[c] : 0);
        }
        foreach(var item in counter)
        {
            if(item.Value == 1)
            {
                return s.IndexOf(item.Key);
            }
        }
        return -1;
    }
}

給一個整數，回傳一個bit位互補(即 OR 後的 bit 每一位都是1)的數。
(這題跟 1009 Complement of Base 10 Integer 是相同的，只是換了名)

這題的邏輯很簡單，找出一個與 num 相同 bit 位長度且每一位都是 1 的數，再用 XOR 去求解。

為了必避免C#的int溢位，所以使用推進的方式，而不是由高位減一。

Python

class Solution:
    def findComplement(self, num: int) -> int:
        return ((1 << num.bit_length()) - 1 ) ^ num

C#

public class Solution {
    public int FindComplement(int num) {
        int r = 1;
        while(r < num)
            {r = (r << 1) + 1;}
        return r ^ num;
    }
}

給兩個字串：ransomNote、magazine，問 ransomNote 是否能從 magazine 裡面的宇符組成。

嗯，這是一個電影會見到的情節吧…

方法很簡單，就是 ransomNote 的每個字符出現次數要比 magazine 的少或等於。

Python

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for c in set(ransomNote):
            if ransomNote.count(c) > magazine.count(c):
                return False            
        return True

C#

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        var charSet = new HashSet(ransomNote);
        foreach(var c in charSet)
        {
            if(ransomNote.Count(p => p == c ) > magazine.Count(p => p == c ))
                return false;  
        }      
        return true;
    }
}

給兩個字串 J、S ，J裡面的字符是代表jewel，問 S 裡面有幾個 jewel。

這是一個相當簡單的問題，重點會放在用什麼作為搜尋的方式。

為了快速，這裡會使用 hash 家族的資料型態讓搜尋更快速。

如果是Python會用 set 或 dict 都可以，我用 collections.Counter， 只是換一點寫法。collection.Counter 是 dict 類的。

如果是C#，我直接用 string 的 Contains() ，其實做法都大同小異。 

Python

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        counter = Counter(S)
        return sum([counter[j] for j in set(J)])

C#

public class Solution {
    public int NumJewelsInStones(string J, string S) {
        int result = 0;
        foreach(var s in S)
        {
            if(J.Contains(s))
                result += 1;
        }
        return result;        
    }
}

給一個 n 代表目前有 n 個版本，要透過 isBadVersion(version) 的函數去找到第一個 True(即BadVersion)的版本號。

這題如果是有使用git去控制版本，那應該是很生活化的搜尋思維。

首先決定搜尋法，這裡使用二分搜尋法去解。

左為 l 右為 r，每次都從 m = (r-l)//2+l 位置找，我之前不太能掌握 l, r 與 m 的替換，到底是 >=, <=, m+1, m 的關係要如何連結起來，當我試著想用 r 去貼齊 target 的位置 ，就比較了解該怎麼寫對。

不過這題也不會有這樣的困擾。

由於版本會從 1 開始， l (L)= 1 ，而 r 要等於 n + 1 ，不過最壞的陷阱來了。若 n = 2147483647 ，那麼就會發生溢位，所以要做一點小修改。(如果是Python就不用擔心了)

Python

class Solution:    
    def firstBadVersion(self, n):
        l, r = 1, n+1 
        while l < r:
            m = (r-l)//2 + l
            if isBadVersion(m):
                r = m
            else:
                l = m+1            
        return r

C#

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int l=1; int r= n;   
        int m = (r-l+1)/2+l;
        while(l < r)
        {            
            if (IsBadVersion(m))
            {
                r = m;
            }
            else
            {
                l = m+1;
            }
            m = (r-l)/2+l;
        }
        return r;
    }
}

給一串二進位二元樹跟一串二進位數列，是否能依數列的值到達葉(leaf)，也就是底層。

這算是「搜尋法」，只要有基本的暴力破解法觀念也可以順利解出。

如果要優化時空，使用遞迴函數就可以快速解出。

Python

class Solution:
    def isValidSequence(self, root: TreeNode, arr: List[int]) -> bool:
        if root and arr and root.val == arr[0]:
            if len(arr) == 1 and root.right is None and root.left is None: return True
            return self.isValidSequence(root.left, arr[1:]) or self.isValidSequence(root.right, arr[1:]) 
        else:
            return False

C#

public class Solution {        
    public bool IsValidSequence(TreeNode root, int[] arr) {
        int l = 0; 
        int r = arr.Length;
        var stack = new List(){root};
        while(l 0)
        {
            int n = stack.Count;
            for(int i = 0; i < n; i++)
            {
                var node = stack[0];
                if(node.val==arr[l])
                {
                    if(l == r-1 && node.left is null && node.right is null)
                        return true;
                    if(!(node.left is null)){stack.Add(node.left);}
                    if(!(node.right is null)){stack.Add(node.right);}                        
                }                
                stack.RemoveAt(0);
            }
            l++;
        }
        return false;
    }
}

給一串非空的二元樹，找出最大的路徑總和。

如果要使用遞迴的想法：以尋找當前的節與左右兩邊子樹最大的路徑，可以找到通過該節的最大路徑。

如果要住上傳，那會是左右或零取大者加自身再上傳。

因此遞迴函數要有兩種：
1.回傳值是到該點的最大路徑。
2.由1.得到左右最大的路徑，去計算通過該點的最大路徑。

Python

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.result = root.val
        def dfs(node):
            if not node: return 0
            rsum = dfs(node.right)
            lsum = dfs(node.left)
            maxPath = node.val+max(0, rsum, lsum)
            self.result = max(maxPath, node.val+lsum+rsum, self.result)
            return maxPath              
        dfs(root)
        return self.result

C#

public class Solution {    
    public int result;
    
    public int MaxPathSum(TreeNode root) {
        result = root.val;
        dfs(root);
        return result;
    }
    
    public int dfs(TreeNode node)
    {
        if(node is null){return 0;}    
        var values = new int[2];
        int rsum = dfs(node.right);
        int lsum = dfs(node.left);
        values[0] = Math.Max(node.val + rsum, node.val + lsum);
        values[0] = Math.Max(node.val, values[0]);
        values[1] = node.val + lsum + rsum;
        result = Math.Max(Math.Max(values[0],values[1]),result);
        return values[0];
    }
}