python練習(十六)
31675 ワード
注意して、答えはただ他人が書いたコードを代表して、正しいですが、テスト(例えばタイムアウト)に合格するとは限らない.列挙するのはただそれらが独特なところを持っているだけで、大部分は確かに私より良いですが.
Permutation in String
タイトル
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.
考え方と解答
pythonはどんなに便利なことか...配列を含めていればいいのに、inは使えない.じゃ、辞書を使います.
class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
d = collections.defaultdict(int)
for s in s1:
d[s] -= 1
l = len(s1)
for k,v in enumerate(s2):
if k < l:
d[v] += 1
if not d[v]:del d[v]
else:
d[v] += 1
d[s2[k-l]] -= 1
if not d[v]: del d[v]
if not d[s2[k-l]] : del d[s2[k-l]]
if not d: return True
return False
答え
def checkInclusion(self, s1, s2):
A = [ord(x) - ord('a') for x in s1]
B = [ord(x) - ord('a') for x in s2]
target = [0] * 26
for x in A:
target[x] += 1
window = [0] * 26
for i, x in enumerate(B):
window[x] += 1
if i >= len(A):
window[B[i - len(A)]] -= 1
if window == target:
return True
return Falseこれは私にはないと思います(やはり私より遅いです)
class Solution(object):
def checkInclusion(self, s1, s2):
return len(self.minWindow(s2, s1)) == len(s1)
# Copied&pasted old problem's solution
def minWindow(self, s, t):
need, missing = collections.Counter(t), len(t)
i = I = J = 0
for j, c in enumerate(s, 1):
missing -= need[c] > 0
need[c] -= 1
if not missing:
while i < j and need[s[i]] < 0:
need[s[i]] += 1
i += 1
if not J or j - i <= J - I:
I, J = i, j
return s[I:J]
私はこれに行くのが私の倍遅いですが、考えが面白いです.
Flatten Nested List Iterator
タイトル
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
Example 1: Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2: Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
考え方と解答
頭の中に騒ぎがあるのか?テーマは死んで、騒ぐわけにはいかない...もともとyieldを使いたかったのですが、後で使いにくいことに気づきました.
やっと補助関数を与えたことに気づきました....mmp、補助関数はどうして呼び出せませんか???
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
self.l = nestedList[::-1]
def next(self):
"""
:rtype: int
"""
return self.l.pop().getInteger()
def hasNext(self):
"""
:rtype: bool
"""
while True:
if self.l[-1].isInetger():
return True
else:
self.l += self.l.pop().getList()[::-1]
if not self.l:
return FalseisInteger()この関数は名前をコピーするときにエラーが発生しました?!マウスの問題に違いない
class NestedIterator(object):
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
self.l = nestedList[::-1]
def next(self):
"""
:rtype: int
"""
return self.l.pop().getInteger()
def hasNext(self):
"""
:rtype: bool
"""
while True:
if not self.l:
return False
if self.l[-1].isInteger():
return True
else:
self.l += self.l.pop().getList()[::-1]
空だと判断したら一番前に出して判断しなければなりません.そうしないと数列を超えます.
答え
class NestedIterator(object):
def __init__(self, nestedList):
"""
Initialize your data structure here.
:type nestedList: List[NestedInteger]
"""
self.stack = nestedList[::-1]
def next(self):
"""
:rtype: int
"""
return self.stack.pop().getInteger()
def hasNext(self):
"""
:rtype: bool
"""
while self.stack:
top = self.stack[-1]
if top.isInteger():
return True
self.stack = self.stack[:-1] + top.getList()[::-1]
return Falseうん.どこまでも
class NestedIterator(object):
def __init__(self, nestedList):
self.stack = [[nestedList, 0]]
def next(self):
self.hasNext()
nestedList, i = self.stack[-1]
self.stack[-1][1] += 1
return nestedList[i].getInteger()
def hasNext(self):
s = self.stack
while s:
nestedList, i = s[-1]
if i == len(nestedList):
s.pop()
else:
x = nestedList[i]
if x.isInteger():
return True
s[-1][1] += 1
s.append([x.getList(), 0])
return Falseうん....
def __init__(self, nestedList):
def gen(nestedList):
for x in nestedList:
if x.isInteger():
yield x.getInteger()
else:
for y in gen(x.getList()):
yield y
self.gen = gen(nestedList)
def next(self):
return self.value
def hasNext(self):
try:
self.value = next(self.gen)
return True
except StopIteration:
return Falseジェネレータ案、私ももともとこの考えを考えていましたが、書けません...
Count and Say
タイトル
The count-and-say sequence is the sequence of integers with the first five terms as following:
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1 Output: “1” Example 2:
Input: 4 Output: “1211”
考え方と解答
?????? どういう意味か探してみましたが、この問題は面白いです.のでも本当にeasyなの?
class Solution(object):
def countAndSay(self, n):
s = ['1']
result = '1'
for i in range(n-1):
start = 0
temp = []
while start < len(s):
count = 1
next = start + 1
while next < len(s) and s[start] == s[next]:
next += 1
count += 1
temp.append(str(count))
temp.append(s[start])
start = next
result = ''.join(temp)
s = temp
return result
答え
1 ...
def countAndSay(self, n):
s = '1'
for _ in range(n - 1):
s = re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1), s)
return s
2 ...
def countAndSay(self, n):
s = '1'
for _ in range(n - 1):
s = ''.join(str(len(group)) + digit
for group, digit in re.findall(r'((.)\2*)', s))
return s
3 ... groupby
def countAndSay(self, n):
s = '1'
for _ in range(n - 1):
s = ''.join(str(len(list(group))) + digit
for digit, group in itertools.groupby(s))
return s……
Majority Element
タイトル
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Credits: Special thanks to @ts for adding this problem and creating all test cases.
考え方と解答
…
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
d,l = collections.defaultdict(int),len(nums)/2
for num in nums:
d[num] += 1
if d[num] > l:
return num答え
return sorted(num)[len(num)/2]
速くなくても
# two pass + dictionary
def majorityElement1(self, nums):
dic = {}
for num in nums:
dic[num] = dic.get(num, 0) + 1
for num in nums:
if dic[num] > len(nums)//2:
return num
# one pass + dictionary
def majorityElement2(self, nums):
dic = {}
for num in nums:
if num not in dic:
dic[num] = 1
if dic[num] > len(nums)//2:
return num
else:
dic[num] += 1
# TLE
def majorityElement3(self, nums):
for i in xrange(len(nums)):
count = 0
for j in xrange(len(nums)):
if nums[j] == nums[i]:
count += 1
if count > len(nums)//2:
return nums[i]
# Sotring
def majorityElement4(self, nums):
nums.sort()
return nums[len(nums)//2]
# Bit manipulation
def majorityElement5(self, nums):
bit = [0]*32
for num in nums:
for j in xrange(32):
bit[j] += num >> j & 1
res = 0
for i, val in enumerate(bit):
if val > len(nums)//2:
# if the 31th bit if 1,
# it means it's a negative number
if i == 31:
res = -((1<<31)-res)
else:
res |= 1 << i
return res
# Divide and Conquer
def majorityElement6(self, nums):
if not nums:
return None
if len(nums) == 1:
return nums[0]
a = self.majorityElement(nums[:len(nums)//2])
b = self.majorityElement(nums[len(nums)//2:])
if a == b:
return a
return [b, a][nums.count(a) > len(nums)//2]
# the idea here is if a pair of elements from the
# list is not the same, then delete both, the last
# remaining element is the majority number
def majorityElement(self, nums):
count, cand = 0, 0
for num in nums:
if num == cand:
count += 1
elif count == 0:
cand, count = num, 1
else:
count -= 1
return candこの問題を解くには1万の方法がある.
Count Primes
タイトル
Count the number of prime numbers less than a non-negative number, n.
考え方と解答
タイトルがよくわかりませんねprime numbersは質量数ですね.いいでしょう.の
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 3:return 0
res = 1
for i in xrange(3,n):
for x in xrange(2,i):
if not i%x:
break
else:
res += 1
return res
タイムアウトしました.何か速い方法があるのではないでしょうか.
if n < 3:return 0
res = 1
l =[2]
for i in xrange(3,n):
for x in l:
if not i%x:
break
else:
l.append(i)
res += 1
return res修正して、依然としてタイムアウトしてどのように最適化することを知りません
答え
def countPrimes(self, n):
if n <= 2:
return 0
res = [True] * n
res[0] = res[1] = False
for i in xrange(2, n):
if res[i] == True:
for j in xrange(i, (n-1)/i+1):
res[i*j] = False
return sum(res)900+ms版
if n < 3:
return 0
arr = [True] * n
arr[0] = arr[1] = False
for i in range(2, int(n ** 0.5) + 1):
if arr[i]:
arr[i*i:n:i] = [False] * ((n - 1) // i - i + 1)
return arr.count(True) 200+ms版!こんな騒々しい操作はありますか?エラトスターニふるい法により証明:反証法を利用する:このようにふるい出したNが合数であり、その平方根以下のすべての素数で除去できないと仮定すると、Nは必ずその平方根よりもその平方根よりも自身のある素数で除去することができる.この素数をMとすると√N
しばらくは更けない