edit some solutions

Jack · Jack · commit 5ed5a1d06e5e · 2017-01-02T15:59:10.000+08:00
diff --git a/Python/add-digits.py b/Python/add-digits.py
@@ -17,9 +17,18 @@
 #
 # A naive implementation of the above process is trivial.
 # Could you come up with other methods? 
-#
+
+
 class Solution:
-    # @param {integer} num
-    # @return {integer}
+    """
+    :type num: int
+    :rtype: int
+    """
     def addDigits(self, num):
         return (num - 1) % 9 + 1 if num > 0 else 0
+
+
+if __name__ == '__main__':
+    s = Solution()
+    r = s.addDigits(12345)
+    print r
diff --git a/Python/battleships-in-a-board.py b/Python/battleships-in-a-board.py
@@ -24,6 +24,7 @@
 # This is not a valid board - as battleships will always have a cell separating between them.
 # Your algorithm should not modify the value of the board.
 
+
 class Solution(object):
     def countBattleships(self, board):
         """
diff --git a/Python/counting-bits.py b/Python/counting-bits.py
@@ -25,6 +25,7 @@
 # 3. Or does the odd/even status of the number help you in
 #    calculating the number of 1s?
 
+
 class Solution(object):
     def countBits(self, num):
         """
@@ -36,3 +37,19 @@ def countBits(self, num):
             # Number of 1's in i = (i & 1) + number of 1's in (i / 2).
             res.append((i & 1) + res[i >> 1])
         return res
+
+    def countBits2(self, num):
+        """
+        :type num: int
+        :rtype: List[int]
+        """
+        s = [0]
+        while len(s) <= num:
+            s.extend(map(lambda x: x + 1, s))
+        return s[:num + 1]
+
+
+if __name__ == '__main__':
+    s = Solution()
+    r = s.countBits2(5)
+    print r
diff --git a/Python/find-all-numbers-disappeared-in-an-array.py b/Python/find-all-numbers-disappeared-in-an-array.py
@@ -17,6 +17,7 @@
 # Output:
 # [5,6]
 
+
 class Solution(object):
     def findDisappearedNumbers(self, nums):
         """
@@ -34,3 +35,23 @@ def findDisappearedNumbers(self, nums):
             else:
                 nums[i] *= -1
         return result
+
+    def findDisappearedNumbers2(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: List[int]
+        """
+        return list(set(range(1, len(nums) + 1)) - set(nums))
+
+    def findDisappearedNumbers3(self, nums):
+        for i in range(len(nums)):
+            index = abs(nums[i]) - 1
+            nums[index] = - abs(nums[index])
+
+        return [i + 1 for i in range(len(nums)) if nums[i] > 0]
+
+
+if __name__ == '__main__':
+    s = Solution()
+    r = s.findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1])
+    print r
diff --git a/Python/find-the-difference.py b/Python/find-the-difference.py
@@ -20,7 +20,9 @@
 # Explanation:
 # 'e' is the letter that was added.
 
-from operator import xor
+import operator
+import collections
+
 
 class Solution(object):
     def findTheDifference(self, s, t):
@@ -29,4 +31,32 @@ def findTheDifference(self, s, t):
         :type t: str
         :rtype: str
         """
-        return chr(reduce(xor, map(ord, s), 0) ^ reduce(xor, map(ord, t), 0))
+        return chr(reduce(operator.xor, map(ord, s), 0) ^ reduce(operator.xor, map(ord, t), 0))
+
+    def findTheDifference2(self, s, t):
+        """
+        :type s: str
+        :type t: str
+        :rtype: str
+        """
+        t = list(t)
+        s = list(s)
+        for i in s:
+            t.remove(i)
+        return t[0]
+
+    def findTheDifference3(self, s, t):
+        return chr(reduce(operator.xor, map(ord, s + t)))
+
+    def findTheDifference4(self, s, t):
+        return list((collections.Counter(t) - collections.Counter(s)))[0]
+
+    def findTheDifference5(self, s, t):
+        s, t = sorted(s), sorted(t)
+        return t[-1] if s == t[:-1] else [x[1] for x in zip(s, t) if x[0] != x[1]][0]
+
+
+if __name__ == '__main__':
+    s = Solution()
+    r = s.findTheDifference2('abcd', 'abcde')
+    print r
diff --git a/Python/fizz-buzz.py b/Python/fizz-buzz.py
@@ -49,3 +49,26 @@ def fizzBuzz(self, n):
                 result.append(str(i))
 
         return result
+
+    def fizzBuzz2(self, n):
+        """
+        :type n: int
+        :rtype: List[str]
+        """
+        l = [str(x) for x in range(n + 1)]
+        l3 = range(0, n + 1, 3)
+        l5 = range(0, n + 1, 5)
+        for i in l3:
+            l[i] = 'Fizz'
+        for i in l5:
+            if l[i] == 'Fizz':
+                l[i] += 'Buzz'
+            else:
+                l[i] = 'Buzz'
+        return l[1:]
+
+    def fizzBuzz3(self, n):
+        return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n + 1)]
+
+    def fizzBuzz4(self, n):
+        return ['FizzBuzz'[i % -3 & -4:i % -5 & 8 ^ 12] or `i` for i in range(1, n + 1)]
diff --git a/Python/move-zeroes.py b/Python/move-zeroes.py
@@ -12,6 +12,7 @@
 # You must do this in-place without making a copy of the array.
 # Minimize the total number of operations.
 
+
 class Solution(object):
     def moveZeroes(self, nums):
         """
@@ -24,6 +25,13 @@ def moveZeroes(self, nums):
                 nums[i], nums[pos] = nums[pos], nums[i]
                 pos += 1
 
+    def moveZeroes2(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: void Do not return anything, modify nums in-place instead.
+        """
+        nums.sort(cmp=lambda a, b: 0 if b else -1)
+
 
 class Solution2(object):
     def moveZeroes(self, nums):
@@ -39,3 +47,9 @@ def moveZeroes(self, nums):
         
         for i in xrange(pos, len(nums)):
             nums[i] = 0 
+
+
+if __name__ == '__main__':
+    s = Solution()
+    r = s.moveZeroes([0, 1, 0, 3, 12])
+    print r
diff --git a/Python/nim-game.py b/Python/nim-game.py
@@ -16,6 +16,7 @@
 # the last stone will always be removed by your friend.
 #
 
+
 class Solution(object):
     def canWinNim(self, n):
         """
diff --git a/Python/reverse-integer.py b/Python/reverse-integer.py
@@ -18,7 +18,7 @@
 # 
 # Throw an exception? Good, but what if throwing an exception is not an option? 
 # You would then have to re-design the function (ie, add an extra parameter).
-#
+
 
 class Solution(object):
     def reverse(self, x):
diff --git a/Python/rotate-array.py b/Python/rotate-array.py
@@ -10,41 +10,58 @@
 #
 
 class Solution:
-    # @param nums, a list of integer
-    # @param k, num of steps
-    # @return nothing, please modify the nums list in-place.
+    """
+    :type nums: List[int]
+    :type k: int
+    :rtype: void Do not return anything, modify nums in-place instead.
+    """
+
     def rotate(self, nums, k):
         k %= len(nums)
         self.reverse(nums, 0, len(nums))
         self.reverse(nums, 0, k)
         self.reverse(nums, k, len(nums))
-    
+
     def reverse(self, nums, start, end):
         while start < end:
-            nums[start], nums[end-1] = nums[end-1], nums[start]
+            nums[start], nums[end - 1] = nums[end - 1], nums[start]
             start += 1
             end -= 1
 
+    def rotate2(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: void Do not return anything, modify nums in-place instead.
+        """
+        nums[:] = nums[len(nums) - k:] + nums[:len(nums) - k]
+
+
 from fractions import gcd
 
+
 class Solution2:
-    # @param nums, a list of integer
-    # @param k, num of steps
-    # @return nothing, please modify the nums list in-place.
+    """
+    :type nums: List[int]
+    :type k: int
+    :rtype: void Do not return anything, modify nums in-place instead.
+    """
+
     def rotate(self, nums, k):
         k %= len(nums)
         num_cycles = gcd(len(nums), k)
         cycle_len = len(nums) / num_cycles
         for i in xrange(num_cycles):
             self.apply_cycle_permutation(k, i, cycle_len, nums)
-    
+
     def apply_cycle_permutation(self, k, offset, cycle_len, nums):
         tmp = nums[offset]
         for i in xrange(1, cycle_len):
-            nums[(offset+i*k) % len(nums)], tmp = tmp, nums[(offset+i*k) % len(nums)]
+            nums[(offset + i * k) % len(nums)], tmp = tmp, nums[(offset + i * k) % len(nums)]
         nums[offset] = tmp
-          
+
+
 if __name__ == '__main__':
-    nums = [1,2,3,4,5,6,7]
+    nums = [1, 2, 3, 4, 5, 6, 7]
     Solution().rotate(nums, 3)
     print nums
diff --git a/Python/sum-of-two-integers.py b/Python/sum-of-two-integers.py
@@ -7,6 +7,7 @@
 # Example:
 # Given a = 1 and b = 2, return 3.
 
+
 class Solution(object):
     def getSum(self, a, b):
         """
@@ -28,3 +29,49 @@ def getSum(self, a, b):
             b = (b | ~mask) if (b & neg_bit) else (b & mask)
 
         return a
+
+    def getSum2(self, a, b):
+        """
+        :type a: int
+        :type b: int
+        :rtype: int
+        """
+        # 32 bits integer max
+        MAX = 0x7FFFFFFF
+        # 32 bits interger min
+        MIN = 0x80000000
+        # mask to get last 32 bits
+        mask = 0xFFFFFFFF
+        while b:
+            # ^ get different bits and & gets double 1s, << moves carry
+            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
+        # if a is negative, get a's 32 bits complement positive first
+        # then get 32-bit positive's Python complement negative
+        return a if a <= MAX else ~(a ^ mask)
+
+    def minus(self, a, b):
+        b = self.getSum(~b, 1)
+        return self.getSum(a, b)
+
+    def multiply(self, a, b):
+        isNeg = (a > 0) ^ (b > 0)
+        x = a if a > 0 else self.getSum(~a, 1)
+        y = b if b > 0 else self.getSum(~b, 1)
+        ans = 0
+        while y & 0x01:
+            ans = self.getSum(ans, x)
+            y >>= 1
+            x <<= 1
+        return self.getSum(~ans, 1) if isNeg else ans
+
+    def divide(self, a, b):
+        isNeg = (a > 0) ^ (b > 0)
+        x = a if a > 0 else self.getSum(~a, 1)
+        y = b if b > 0 else self.getSum(~b, 1)
+        ans = 0
+        for i in range(31, -1, -1):
+            if (x >> i) >= y:
+                x = self.minus(x, y << i)
+                ans = self.getSum(ans, 1 << i)
+        return self.getSum(~ans, 1) if isNeg else ans
+

Original file line number	Diff line number	Diff line change
`@@ -16,6 +16,7 @@`
`16`	`16`	`# the last stone will always be removed by your friend.`
`17`	`17`	`#`
`18`	`18`
	`19`	`+`
`19`	`20`	`class Solution(object):`
`20`	`21`	`def canWinNim(self, n):`
`21`	`22`	`"""`
Original file line number	Diff line number	Diff line change
`@@ -18,7 +18,7 @@`
`18`	`18`	`#`
`19`	`19`	`# Throw an exception? Good, but what if throwing an exception is not an option?`
`20`	`20`	`# You would then have to re-design the function (ie, add an extra parameter).`
`21`		`-#`
	`21`	`+`
`22`	`22`
`23`	`23`	`class Solution(object):`
`24`	`24`	`def reverse(self, x):`