使用Python3实现，以下题目均已AC
442. Find All Duplicats in an Array
Description
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Solution (使用array本身作为hash table)
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = []
for x in nums:
if nums[abs(x)-1] < 0:
res.append(abs(x))
else:
nums[abs(x)-1] *= -1
print(nums[abs(x)-1])
return res
141. Linked List Cycle
Description
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
Solution(Floyd Cycle Detection Algorithm)
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = fast = head
while fast and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
557. Reverse Words in a String III
Description
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Solution
Slice notation “[a,b,c]” means “count in increments of c starting at a inclusive, up to b exclusive”. If c is negative you count backwards, if omitted it is 1. If a is omitted then you start as far as possible in the direction you’re counting from (so that’s the start if c is positive and the end if negative). If b is omitted then you end as far as possible in the direction you’re counting to (so that’s the end if c is positive and the start if negative). If a or b is negative it’s an offset from the end (-1 being the last character) instead of the start.
class Solution(object):
def reverseWords(self, s):
return ' '.join(s.split()[::-1])[::-1]
575. Distribute Candies
Description
Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Solution(Hast set to remove duplicates)
class Solution(object):
def distributeCandies(self, candies):
"""
three operations of set: & | -
"""
return min(len(candies/2),len(set(candies)))
#3 滑动窗口
def lengthOfLongestSubstring(self, s):
"""
3. 无重复字符的最长子串
"""
left, right = 0, 0
win = []
map = dict()
res = 0
while right < len(s):
cur = s[right]
win.append(s[right])
if s[right] in map:
map[s[right]] += 1
else:
map[s[right]] = 1
right += 1
# 如果map中存在重复字符，则缩小左边界，直到当前cur字符在map中仅出现一次
while map[cur] > 1:
map[s[left]] -= 1
win.pop(0)
left += 1
res = max(res, right - left)
return res
