因為隔天要早起上班只好寫簡單題目的日子

965. Univalued Binary Tree (easy)

https://leetcode.com/problems/univalued-binary-tree/description/
Submission：https://leetcode.com/problems/univalued-binary-tree/submissions/858848803/

A binary tree is uni-valued if every node in the tree has the same value.

Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.
簡單來說，檢查是否有重複的數字

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        tempSet = set()
        stack = []
        while root or stack:
            while root:
                tempSet.add(root.val)
                if len(tempSet) > 1:
                    return 0
                stack.append(root)
                root = root.left
            temp = stack.pop()
            root = temp.right
        return 1

897. Increasing Order Search Tree (easy)

https://leetcode.com/problems/increasing-order-search-tree/description/
Submission：https://leetcode.com/problems/increasing-order-search-tree/submissions/858846015/
Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.
要把Bst變成只剩下root right的格式

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    #把BST變成 還是BST，不過root最小
    #我的話會直接把他inorder traversal出來用吧
    #由於要練習我不常用的stack inorder，所以這邊都用stack做，要不然用recursion很快就出來了
    def increasingBST(self, root: TreeNode) -> TreeNode:
        rootList = []
        def inorder(root):
            stack = []
            while root or stack:
                while root:
                    stack.append(root)
                    root = root.left
                temp = stack.pop()
                rootList.append(temp.val)
                root = temp.right
        inorder(root)
        ans = prev = TreeNode(rootList[0])
        for i in rootList[1:]:
            temp = TreeNode(i)
            prev.left = None
            prev.right = temp
            prev = prev.right
        return ans

1025. Divisor Game (easy)

https://leetcode.com/problems/divisor-game/description/
Submission：https://leetcode.com/problems/divisor-game/submissions/858840062/
Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:

Choosing any x with 0 < x < n and n % x == 0.
Replacing the number n on the chalkboard with n - x.
Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

這題想了一下，想通了答案就出來了，思考過程在程式區

class Solution:
    #因數遊戲
    #必須選擇n的因數當成下一步驟
    #然後會變成 n - x
    #進行下一步，假設兩人都使出全力，看誰會獲勝
    #1 -> 1 False
    #2 -> 1 1 True
    #3 -> 1 1 1 False
    #4 -> 1 1 1 1 True
    #5 -> 1 1 1 1 1 False
    #6 -> 3 1 1 1 True
    #7 -> False
    #8 -> True
    #9 ->
    #簡單來說就是要讓Alice能夠做出True的選擇
    #讓Alice選擇True之後還想辦法讓Bob選擇False即可
    #透過觀察我們可以知道，除了2以外的所有prime number都會是 False
    #偶數都會是True
    #所以關鍵就是誰是那個1
    #然後觀察到最後，完全不知道dp要用在哪==白癡喔
    #不過證明這件事情確實需要用到dp就是了
    def divisorGame(self, n: int) -> bool:
        if n%2 == 0:
            return True
        else:
            return False

338. Counting Bits (easy)
     https://leetcode.com/problems/counting-bits/description/
     Submission：https://leetcode.com/problems/counting-bits/submissions/858833640/

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

要找出 n以下的數字轉成二進位後，裡面含有多少個1

#一開始的寫法
#利用class的特性做紀錄+作答
class Solution:    
    dp = []
    def countBits(self, n: int) -> List[int]:
        if n <len(self.dp):
            return self.dp[:n+1]
        for i in range(len(self.dp),n+1):
            self.dp.append(bin(i).count("1"))
        return self.dp[:n+1]

#有點沒辦法接受這比較美的做法居然速度沒快多少==
#別人的方法
#要記得：奇數就是2n+1，偶數就是2n
#對於二進位來說 乘以2 就是尾巴加個0，跟十進位一樣，乘以10也是尾巴加個0
#也就是說舉個例子，數字9，8是4的兩倍，所以1的數量會跟4一樣
#9是8+1，所以9的1的數量會比8多1
class Solution:
    dp = [0]
    def countBits(self, n: int) -> List[int]:
        if n < len(self.dp):
            return self.dp[:n+1]
        for i in range(len(self.dp), n+1):
            self.dp.append(self.dp[i >> 1] + i % 2)
        return self.dp