CONY的世界

523. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

 Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
   
   

Success:

56 ms, beats 67.24 % of python submissions

這題用到的觀念我不會，用到prefix sum，我本來只想到dynamic programming那個三角形的，想說是不是用那個不斷累積去看，不過當然這種方式就是很慢
以下是這邊對於prefix sum應用的解說

Since we are interested in quantities of the form A[L] + A[L+1] + ... + A[R], let's use a standard technique of keeping a prefix sum P[i] = sum(A[:i]), so that we can quickly query A[L] + A[L+1] + ... + A[R] = P[R+1] - P[L].

Now, we would like to know if P[R+1] - P[L] = 0 (mod k) is solvable with 0 <= L < R < len(A). This means: For any 0 <= L < len(A), we would like to know if there is some L + 2 <= X < len(A) with P[X] = P[L].

This can be solved in linear time: at decreasing time i, we've now seen in total all elements in P[i+2:], and we want to know if P[i] is something we've seen before. If we have, then indeed P[i] = P[j] for j >= i + 2 as desired.

基本上就是要找到第二個餘數相同的prefix sum 就可以達成 P(R+1) - P(L)  ＝＝0，也就等於有找到一個 sum(A[L:R]) == 0  
相加過程可以不斷用%k來整理，把倍數去掉

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        seen, psum = {0:-1}, 0
        for index, value in enumerate(nums):
            psum = (psum + value) % k if k else psum + value
            if psum not in seen:
                seen[psum] = index
            if index - seen[psum] > 1:
                return True
        return False

Fail:

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if len(nums) < 2:
            return False
        if k < 0:
            k = abs(k)
        if k == 0: 
            for x in nums: 
                if x > 0:
                    return False
            return True
        dic = {}
        for length in range(1,len(nums)):
            for index in range(len(nums)):
                value = 0
                if index + length > len(nums) -1:
                    break
                if dic.has_key((index, index+length-1)):
                    value = dic[(index, index+length-1)] + nums[index+length]
                else:
                    for j in range(length+1):
                        value += nums[index + j] 
                if (value % k == 0) or value == 0:
                    return True
                else:
                    dic[(index, index+length)] = value
        return False

464. Can I Win

In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins. 

What if we change the game so that players cannot re-use integers? 

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally. 

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:
maxChoosableInteger = 10
desiredTotal = 11

Output:
false

Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

Success:

722 ms, beats 90.78 % of python submissions

這題看到題目就放棄，一開始是有想到worst case是N! 的算法啦
之前演算法作業遊戲那題跟這概念很像，就是邊走邊消掉 fail 的結果
但這邊消去的rule 我想不太到，沒想到真的幾乎是硬做.....
每次做DP都有種把程式放下去給他跑，然後經過龐大運算後答案就出來了，有點無法控制的感覺
列一下這題用到的注意點
1. 用 cur 來表示實際用掉哪些數字，一個bit 一個值 7 就是第7個bit
2. 結果用d的dictionary 裡面
3. if not self.canWin(maxChoosableInteger, desiredTotal-(i+1), cur+(1<<i), d):  這句話的意思是
    我這輪結束換對方，如果對方回傳結果對方輸了（=沒有贏）就是我方贏，是這題的重點概念
4. 最後maxChoosableInteger 都跑完後，沒有跑出贏的結果表示沒有贏的可能，所以以輸回傳

class Solution(object):
    def canWin(self, maxChoosableInteger, desiredTotal, cur, d):
        if cur in d: return d[cur]
        if desiredTotal <=0:
            d[cur] = False
            return d[cur]
        for i in range(maxChoosableInteger):
            if (cur>>i) & 1 == 0:
                if not self.canWin(maxChoosableInteger, desiredTotal-(i+1), cur+(1<<i), d):
                    d[cur] = True
                    return d[cur]
        d[cur] = False
        return d[cur]
    
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        if desiredTotal <=0:
            return True
        if maxChoosableInteger*(maxChoosableInteger+1) / 2 < desiredTotal:
            return False
        return self.canWin(maxChoosableInteger, desiredTotal, 0, {})