注意，答案只是代表是他人写的代码，正确，但不一定能通过测试（比如超时），列举出来只是它们拥有着独到之处，虽然大部分确实比我的好
551. Student Attendance Record I
题目
You are given a string representing an attendance record for a student. The record only contains the following three characters:
‘A’ : Absent.
‘L’ : Late.
‘P’ : Present.
A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).
You need to return whether the student could be rewarded according to his attendance record.
Example 1:
Input: “PPALLP”
Output: True
Example 2:
Input: “PPALLL”
Output: False
思路与解答
判断字符串内某字符的数量以及连续字符，话说能直接用counter吗？话说其它字符数量也不需要统计吧
d = {'A':0,'L':0}
for w in s:
if w == 'A':
d[w] += 1
if d[w] > 1:
return False
if w == 'L':
d[w] += 1
if d[w] >= 3:
return False
else:
d['L']=0
return True太慢了，感觉也不需要字典，又没有进行查询
a = 0
for w in s:
if w == 'A':
a += 1
if a > 1:
return False
return 'LLL' not in s 这样子反而快了不少
答案
果然有一个count方法
return (False if s.count('A') > 1 or 'LLL' in s else True)正则匹配
return not re.search('A.*A|LLL', s)581. Shortest Unsorted Continuous Subarray
题目
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.
思路与解答
感觉easy难度的题不应该用滑动窗口做啊
我刚才好像理解错题目了。。。
好像用sorted就够了，找出第一个不同的数，最后一个不同的数
居然还能是0的
n = sorted(nums)
l = len(nums)
if n == nums:return 0
for i in range(l):
if n[i] != nums[i]:
smin = i
break
for i in range(l-1,0,-1):
if n[i] != nums[i]:
return i-smin+1好像也可以把不同的数组成一个list然后len？不过可能会出问题。。。
答案
def findUnsortedSubarray(self, nums):
is_same = [a == b for a, b in zip(nums, sorted(nums))]
return 0 if all(is_same) else len(nums) - is_same.index(False) - is_same[::-1].index(False)return len(''.join(('.', ' ')[m==n] for m, n in zip(sorted(nums), nums)).strip())和我一个想法的
n, sorts = len(nums), sorted(nums)
if nums == sorts: return 0
l, r = min(i for i in range(n) if nums[i] != sorts[i]), max(i for i in range(n) if nums[i] != sorts[i])
return r - l + 1572. Subtree of Another Tree
题目
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.
Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2Return false.
思路与解答
这道题让我想起之前返回元组的那种了
def stree(n):
return n and (n.val, stree(n.left), stree(n.right))
return stree(t) in stree(s) 不行，没研究出来哪错了，反正就是不行
那感觉做起来就复杂了啊
def dfs(r1,r2,r3):
if r1 == r2 :return True
if r1 == None or r2 == None : return False
if r1.val == r2.val:
return (dfs(r1.left,r2.left,r3) and dfs(r1.right,r2.right,r3)) or dfs(r3,r2.left,r3) or dfs(r3,r2.right,r3)
return dfs(r3,r2.left,r3) or dfs(r3,r2.right,r3)
return dfs(t,s,t)改版，超时，应该是对的
应该在哪方面优化呢
答案
话说我用的第一种怎么就不行呢
def convert(p):
return "^" + str(p.val) + "#" + convert(p.left) + convert(p.right) if p else "$"
return convert(t) in convert(s)404. Sum of Left Leaves
题目
Find the sum of all left leaves in a given binary tree.
Example:
3
/ \
9 20
/ \
15 7There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
思路与解答
看起来蛮简单
只包括叶子节点啊
if not root :return 0
self.s = 0
def dfs(r,f):
if r.left:
dfs(r.left,1)
if r.right:
dfs(r.right,0)
if f and not r.left and not r.right:
self.s += r.val
dfs(root,0)
return self.s
总是忘记有空的啊
答案
总是没有想起自身递归的方案
class Solution(object):
def sumOfLeftLeaves(self, root):
if not root: return 0
if root.left and not root.left.left and not root.left.right:
return root.left.val + self.sumOfLeftLeaves(root.right)
return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right) # isn't leave还能再短点
if not root: return 0
if not (root.left or root.right): return root.val * isLeft
return self.sumOfLeftLeaves(root.left, True) + self.sumOfLeftLeaves(root.right)633. Sum of Square Numbers
题目
Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.
Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3
Output: False
思路与解答
这种题目？？？
还没有给范围，暴力列举会超时的啊
摸不到头脑。。。
搜到这个
来源
但是到底是什么意思呢。。。
还是先试试暴力破解吧
if c%4 == 3:
return False
for i in range(int(math.sqrt(c))+1):
if int(math.sqrt(c-i*i))**2 == c-i*i:
return True
return False不算太慢216ms
但是我看到别人52ms的了
至于那个第一句判断，我研究了一会那个文章就能用上这么一句
答案
52ms的，虽然长了点，但是快啊
不过他写的都是啥啊。。。。
class Solution(object):
def judgeSquareSum(self, c):
"""
:type c: int
:rtype: bool
"""
primes = self.primes(c)
congruent={}
for n in primes:
if n%4==3:
congruent[n]=congruent.get(n,0)+1
for v in congruent.values():
if v%2!=0:
return False
return True
def primes(self,n):
primfac = []
d = 2
while d*d <= n:
while (n % d) == 0:
primfac.append(d) # supposing you want multiple factors repeated
n //= d
d += 1
if n > 1:
primfac.append(n)
return primfac
42ms虽然可读性上升，但是不懂其中的数学原理，并不懂他在做什么
limit = int(math.sqrt(c)) + 1
for i in xrange(2, limit):
if i * i > c:
break
if c % i == 0:
count = 0
while c % i == 0:
c /= i
count += 1
if i % 4 == 3 and count % 2 != 0:
return False
return c % 4 != 335ms，看起来和上面一个原理的，所以还是不懂。。。。
while c and not c%2:
c//=2
if c%4==3:
return False
pset=set()
i,count=3,0
while i*i<=c:
if i%4==3:
while not c%i:
c//=i
count+=1
if count%2:
return False
else:
while not c%i:
c//=i
i+=2
return c%4!=3126ms
方法很好懂，这样子可以？不会产生疏漏？
if(c<0):
return False
left =0
right = int(math.sqrt(c))
while(left<=right):
curr = left*left + right*right
if(curr < c):
left +=1
elif(curr>c):
right -=1
else:
return True
return False;200ms以内的差不多都是这种方案
对了，50ms的那种方案我找到解释了