45. 扑克牌顺子
# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if not numbers:
return False
count = 0
for i in numbers:
if i == 0:
count+=1
numbers.sort()
if numbers[-1] -numbers[count] == 4 or count == 4:
return True
return False
46. 孩子们的游戏（圆圈中最后剩下的数）
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
n = [i for i in range(n)]
if not n:
return -1
while n:
i = (m-1)%len(n)
res = n.pop(i)
n = n[i:]+n[:i]
```
i = 0
while n:
i = (m+i-1)%len(res)
res = n.pop(i)
```
return res
47. 求1+2+3+……+n
不能用循环就用递归，不能用判断条件就用短路
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here
return n and n + self.Sum_Solution(n-1)
48. 不用加减乘除做加法
位运算虽然有sum()
- 深坑！！！python没有无符号右移操作，需要越界检查
# -*- coding:utf-8 -*-
class Solution:
def Add(self, a, b):
while(b):
a,b = (a^b) & 0xFFFFFFFF,((a&b)<<1) & 0xFFFFFFFF
return a if a<=0x7FFFFFFF else ~(a^0xFFFFFFFF)
49. 把字符串转换成整数
# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
if not s:
return 0
str2num={'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'0':0}
flag2num={'-':-1,'+':1}
first=s[0]
if first in ['+','-']:
flag=flag2num[first]
x=0
for i in s[1:]:
if i not in str2num:
return 0
x=x*10+str2num[i]
return flag*x
else:
x=0
for i in s:
if i not in str2num:
return 0
x=x*10+str2num[i]
return x
50. 数组中重复的数字
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
res = {}
for i in numbers:
res[i] = res.get(i,0)+1
if res[i] == 2:
duplication[0] = i
return True
else:
return False
51. 构建乘积数组
如果A[0]=0的话这道题的结果不就是应该求1到 n-1的值然后赋值给B[0]嘛？◔ ‸◔?
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
B=A[:]
number=0
for m in range(len(A)):
sum=1
number=m
for n in range(len(A)):
if n!=number:
sum=sum*A[n]
B[number]=sum
return B
嵌套for循环时间复杂度为O(n^2)
B[0]=1
for i in range(1,n):
B[i] = B[i-1] * A[i-1]
temp = 1
for j in range(n-2,-1,-1):
temp*= A[j+1]
B[j] *= temp
return B
52. 正则表达式匹配
本题的主要思路有两个关键点：
- 判断匹配字符的下个字符是不是
*
如果是*则判断*后面的字符和？*中的?是否相同，相同的话?*该匹配几位
# -*- coding:utf-8 -*-
class Solution:
def match(self, s, pattern):
if (len(s) == 0 and len(pattern) == 0):
return True
if (len(s) > 0 and len(pattern) == 0):
return False
if (len(pattern) > 1 and pattern[1] == '*'):
if (len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.')):
return (self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern))
else:
return self.match(s, pattern[2:])
if (len(s) > 0 and (pattern[0] == '.' or pattern[0] == s[0])):
return self.match(s[1:], pattern[1:])
return False
53. 表示数值的字符串
字符串相关问题还是用正则表达式做比较好
# -*- coding:utf-8 -*-
import re
class Solution:
def isNumeric(self, s):
return re.match(r"^[\+\-]?[0-9]*(\.[0-9]*)?([eE][\+\-]?[0-9]+)?$",s)
54. 字符流中第一个不重复的字符
可以说又是词频统计问题了
# -*- coding:utf-8 -*-
class Solution:
# 返回对应char
def __init__(self):
self.l=[]
self.d={}
def FirstAppearingOnce(self):
# write code here
for char in self.l:
if self.d[char]==1:
return char
return '#'
def Insert(self, char):
# write code here
if char in self.l:
self.d[char]+=1
else:
self.d[char]=1
if self.d[char]==1:
self.l.append(char)
55. 链表中环的入口结点
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
l=[]
while pHead:
if pHead in l:
return pHead
else:
l.append(pHead)
pHead = pHead.next
