个人刷Leetcode的一点解法，欢迎批评讨论，每日更新
GitHub:
https://github.com/seventheli/LeetCode-PracticesingleNumber
Core: A XOR B XOR A XOR C XOR B = C
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ result = 0 for each in range(len(nums)): result ^= nums[each] return result
reverseString
Core: Serializing String Value, then descending the list
class Solution(object): def reverseString(self, s): lst = [] for i in range(len(s)): lst.append(s[-(i + 1)]) lst = ''.join(lst) return lst
Nim GAME
Core: Second player only win when total accoumt % 4 = 0
class Solution(object): def canWinNim(self, n): val = n % 4 if val != 0: return True else: return False
Counting Bits
Core:
Each time the value is 2^n
The different between the the first half and second half is only the first digit
Example with 7
0 to 7 is
000
----
001
----
010
011
----
100
101
110
111
The Second half is always "1+Second Half
class Solution(object): def countBits(self, num): val = [0] while len(val) <= num: val += [i + 1 for i in val] return val[:num + 1]
Sum of two integers
Core: Implementation of an array of Full Adder
class Solution(object): def half_adder(self, a, b): s = a ^ b cin = a & b return s, cin def full_adder(self, a, b, cin): s1, c1 = self.half_adder(a, b) s2, c2 = self.half_adder(cin, s1) c_out = c1 | c2 return s2, c_out def getSum(self, a, b): mask = 1 ci = 0 sum_total = 0 while mask <= 0x080000000: a1 = a & mask b1 = b & mask (s, ci) = self.full_adder(a1, b1, ci) sum_total = sum_total | s ci <<= 1 mask <<= 1 print "s: " + str(s) + " ci: " + str(ci) maximum = 0x7FFFFFFF mask = 0xFFFFFFFF if sum_total > maximum: sum_total = ~(sum_total ^ mask) return sum_total
Add Digits
Core:
Dr(n) = n -9floor((n-1)/9)
Reference: https://en.wikipedia.org/wiki/Floor_and_ceiling_functions
class Solution(object): def addDigits(self, num): """ :type num: int :rtype: int """ if num == 0: return 0 else: return num - 9 * int((num - 1) / 9)
Maximum Depth of Binary Tree
Core:
Recursion
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ return self.search(root, 0) def search(self, node, i): if node is None: return i else: i += 1 a = self.search(node.left, i) b = self.search(node.right, i) if a > b: return a else: return b
Two Sum II
Core:
Binary Search, Ignoring repeat value
Remain: Squeeze is not suitable for this kind of scenes
class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ if not numbers: return [] for i in xrange(len(numbers)): if i > 0 and numbers[i-1] == numbers[i]: continue ind1 = i ind2 = len(numbers) - i -1 while ind1 <= ind2: sumv = numbers[ind1] + numbers[ind2] if sumv == target: return [ind1+1, ind2+1] elif sumv > target: ind2 -= 1 else: ind1 += 1
Find the Difference
Core: Sort,Serializing String Value
class Solution(object): def findTheDifference(self, s, t): """ :type s: str :type t: str :rtype: str """ s = list(s) s.sort() t = list(t) t.sort() for i in range(len(s)): if s[i] != t[i]: return t[i] return t[len(t)-1]
Invert Binary Tree
Core: Recursion
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ self.invert(root) return root def invert(self, node): if node is not None: template = node.left node.left = node.right node.right = template self.invert(node.left) self.invert(node.right)
singleNumber
Core: A XOR B XOR A XOR C XOR B = C, Use Bit with different value in the two single value to regist each value in list(otherwise, divide list with the regist bit)
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: List[int] """ result = [0, 0] x = 0 for each in nums: x ^= each # x = result_1 XOR result_2 x &= -x for each in nums: if each & x == 0: result[0] ^= each else: result[1] ^= each return result
Move Zeroes
class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ real_i = 0 for each in xrange(0,len(nums)): nums[real_i] = nums[each] if nums[real_i] != 0: real_i += 1 for each in xrange(real_i, len(nums)): nums[each] = 0
Linked List Random Node
Core: Recursion, for elements in an unknow list, fisrt of all, get 1 elements as output, for the following recursion, use 1/n(current recursion deep +1) probablity to repeat output, in the end of the recursion, the probability that each elements saved in output value is 1/(recursion deep +1),otherwise, the probablity developing with the recursion deep developing.
from random import random class Solution(object): def __init__(self, head): """ @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. :type head: ListNode """ self.header = head def getRandom(self): """ Returns a random node's value. :rtype: int """ head = self.header index = 1 while head: if random() * index <= 1: value = head.val index += 1 head = head.next return value
Product of Array Except Self
Core: Divide the multplication into two part( before self and after self)
class Solution(object): def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ output = [1] * len(nums) n = len(nums) template = 1 for i in range(1, n): template = template * nums[i - 1] output[i] *= template template = 1 for i in range(n - 2, -1, -1): template = template * nums[i + 1] output[i] *= template return output
Delete Node in a Linked List
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): 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
Ransom Note
Core: Hash two string
class Solution(object): def canConstruct(self, ransomNote, magazine): """ :type ransomNote: str :type magazine: str :rtype: bool """ magazine_dir = {} for each in list(magazine): if magazine_dir.get(each) is not None: magazine_dir[each] += 1 else: magazine_dir[each] = 1 for each in list(ransomNote): if magazine_dir.get(each) is not None: magazine_dir[each] -= 1 if magazine_dir[each] < 0: return False else: return False return True
Intersection of two arrays
Core: data structure convertion
class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ set1 = set(nums1) set2 = set(nums2) return list(set1 & set2)
Same True
Core: Use Stack to save the node order
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p and not q: return True if not p or not q: return False stack_p = [p] stack_q = [q] while stack_p and stack_q: node_p = stack_p.pop() node_q = stack_q.pop() if node_p.val != node_q.val: return False if node_p.left and node_q.left: stack_p.append(node_p.left) stack_q.append(node_q.left) elif not node_p.left and not node_q.left: pass else: return False if node_p.right and node_q.right: stack_p.append(node_p.right) stack_q.append(node_q.right) elif not node_p.right and not node_q.right: pass else: return False return True
is Sub sequence
Core: Two Pointer, Serializing String Value
class Solution(object): def isSubsequence(self, s, t): """ :type s: str :type t: str :rtype: bool """ list_s = list(s) list_t = list(t) list_s.sort() list_t.sort() i = 0 j = 0 while i < len(list_s): if j >= len(list_t): return False if list_s[i] == list_t[j]: i += 1 j += 1 return True
Top K Frequent Element
Core: Map the frequent and sort the map
class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ dir_nums = {} for each in nums: if each in dir_nums: dir_nums[each] += 1 else: dir_nums[each] = 1 return sorted(dir_nums, key=dir_nums.get, reverse=True)[:k]
已为社区贡献9条内容
所有评论(0)