給字串 s 和字串 t，找出 s 是否為 t 的子順序。子順序是相對位置不變，但中間可以刪減部分字元。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:        
        if not s: return True
        for i, c in enumerate(t):
            if c == s[0]:
                return self.isSubsequence(s[1:], t[i+1:])
        return False

C#

public class Solution {
    public bool IsSubsequence(string s, string t) {
        int n = s.Length;
        if(n == 0){return true;}
        int si = 0;
        foreach(char c in t)
        {
            if(c == s[si])
            {
                si += 1;
                if(si == n){return true;}
            }
        }
        return false;
    }
}

Python(除二餘數)

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 1: return n == 1
        return self.isPowerOfTwo(n//2) if n % 2 == 0 else False

Python(bit存在只有1個1)

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n < 1: return False
        while n & 1 == 0:
            n >>= 1
        return n >> 1 == 0 

Python(最高位為1)

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n == (1 << (n.bit_length()-1)) 

C#

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if(n <= 1){return n == 1;}
        return n % 2 == 0 ? IsPowerOfTwo(n/2): false;
    }
}

Python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp  = [0] * (amount+1)
        dp[0] = 1
        for coin in coins: 
            for i in range(coin, amount+1):                
                dp[i] += dp[i - coin]
        return dp[-1]

C#

public class Solution {
    public int Change(int amount, int[] coins) {
        var dp = new int[amount+1];
        dp[0] = 1;
        foreach(int coin in coins)
        {
            for(int i = coin; i <= amount; i++)
            {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

Python

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x: (-x[0], x[1]))
        result = []
        for p in people:
            result.insert(p[1], p)
        return result

C#

public class Solution {
    public int[][] ReconstructQueue(int[][] people) {
        var sorted = people.OrderBy(x => (-x[0], x[1])).ToArray();
        var result = new List();
        foreach(var pair in sorted)
        {
            result.Insert(pair[1], pair);
        }
        return result.ToArray();
    }
}

Python

class Solution:

    def __init__(self, w: List[int]):
        total = sum(w)
        self.w = []
        accu = 0
        for i in range(1, len(w)):
            accu += w[i] / total
            self.w.append(accu)

    def pickIndex(self) -> int:
        l, r = 0, len(self.w)
        t = random.random()
        while l < r:
            m = (r - l)//2 + l
            if self.w[m] < t:
                l = m + 1
            else:
                r = m 
        return l

C#

public class Solution {

    double[] ws;
    Random random = new Random();
        
    public Solution(int[] w) {
        var total = w.Sum() * 1.0;
        ws = new double[w.Length];
        ws[0] = w[0] / total; 
        for(int  i = 1; i < w.Length; i++)
        {
            ws[i] = ws[i-1] + w[i] / total;
        }
    }
    
    public int PickIndex() {
        var t = random.NextDouble();
        int l = 0; int r = ws.Length;
        while(l < r)
        {
            int m = (r-l)/2 + l;
            if(ws[m] < t)
                l = m + 1;
            else
                r = m;                
        }
        return l;
    }
}

Python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        ls = len(s)
        for i in range(ls//2):
            s[i], s[ls-1-i] = s[ls-1-i], s[i] 

C#

public class Solution {
    public void ReverseString(char[] s) {
        int l = s.Length-1;
        for(int i = 0; i < (l+1)/2; i++)
        {
            char lc = s[i];
            s[i] = s[l-i];
            s[l-i] = lc;
        }
    }
}

Python(DP)

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        
        n = len(costs)//2
        
        @lru_cache(None)
        def dfs(n1, n2):
            if n1 + n2 == n*2:
                return 0
            
            i = n1 + n2
            path = set()
            if n1 < n:
                path.add(costs[i][0] + dfs(n1+1, n2))
            if n2 < n:
                path.add(costs[i][1] + dfs(n1, n2+1))            
            return min(path)
        
        return dfs(0,0)

Python

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:        
        costs.sort(key = lambda x: x[0] - x[1])
        n = len(costs)//2  
        result = 0
        for i in range(n):
            result += costs[i][0] + costs[i+n][1] 
        return result

C#

public class Solution {
    public int TwoCitySchedCost(int[][] costs) {        
        int n = costs.Length / 2;
        int result = 0;
        int[][] sorted_costs =  costs.OrderBy(x => (x[0]-x[1])).ToArray();
        for(int i = 0; i < n; i++)
            result += sorted_costs[i][0] + sorted_costs[i+n][1];
        return result;
    }
}

Python

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

C#

public class Solution {
    public void DeleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

反轉二元樹。

這題被啟發的述說蠻好笑的，會寫軟體，但不會在白板寫出反轉二元樹。
有時候會被簡單卡關是難免的。

要反轉二元樹，也就是左右對調，node.left, node.right = node.right, node.left，如此運作下去到底。

我也沒有一次到位，不過很快就察覺到該怎麼寫。

Python

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack.extend([node.left, node.right])
        return root

C#

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if(root is null){return root;}
        var stack = new Stack();        
        stack.Push(root);
        while(stack.Count > 0)
        {
            var node = stack.Pop();
            var temNode = node.right;
            node.right = node.left;
            node.left = temNode;
            if (!(node.right is null))
                stack.Push(node.right);
            if (!(node.left is null))            
                stack.Push(node.left);
        }
        return root;
    }
}

Python(邊際欄列)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:  
	from functools import lru_cache      
        rows, cols = len(word1)+1, len(word2)+1        
        @lru_cache(None)
        def dfs(row, col):
            if row == 0 or col == 0:
                return max(row, col)
            other = set()     
            if row > 0 or col > 0:
                if word1[row-1] == word2[col-1]:
                    ans = dfs(row-1, col-1)
                else:
                    if row > 0 and col > 0:               
                        other.add(dfs(row-1, col-1))
                    if row > 0:
                        other.add(dfs(row-1, col))
                    if col > 0:
                        other.add(dfs(row, col-1))
                    ans = min(other)+1
            return int(ans)

        return dfs(rows-1, cols-1)

C#

public class Solution {
    public int MinDistance(string word1, string word2) {
        var memo = new int[word1.Length+1, word2.Length+1];
        for(int i = 0; i < word1.Length+1; i++)
            memo[i, 0] = i; 
        for(int j = 0; j < word2.Length+1; j++)
            memo[0, j] = j;        
        for(int i = 1; i < word1.Length + 1; i++)
        {
            for(int j = 1; j < word2.Length + 1; j++)
            {
                if(word1[i-1] == word2[j-1])
                    memo[i, j] = memo[i-1, j-1];
                else
                {
                    memo[i, j] = Math.Min(memo[i-1, j], memo[i, j-1]);
                    memo[i, j] = Math.Min(memo[i, j], memo[i-1, j-1]) + 1;                     
                }
            }
        }
        return memo[word1.Length, word2.Length];
    }
}