记录leetcode上的一些题
此篇文章最先发布在我的博客mbinary上
记录OJ上的一些题，基本上是leetcode上的题，其他的我会标注出来，用的语言目前是python,写的代码很庸俗，请大神不要见笑(>_<)
# 2017-8-20
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
罗马数字的规则如下：
罗马数字共有7个，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、Ⅽ（100）、Ⅾ（500）和Ⅿ（1000）。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”，与进位制无关。一般认为罗马数字只用来记数，而不作演算。
- 重复数次：一个罗马数字重复几次，就表示这个数的几倍。
右加左减：
- 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
- 在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
- 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
- 左减时不可跨越一个位值。比如，99不可以用IC（ 100-1）表示，而是用XCIX（[100-10]+[10-1]）表示。（等同于阿拉伯数字每位数字分别表示。）
- 左减数字必须为一位，比如8写成VIII，而非IIX。
- 右加数字不可连续超过三位，比如14写成XIV，而非XIIII。（见下方“数码限制”一项。）
- 加线乘千：
在罗马数字的上方加上一条横线或者加上下标的Ⅿ，表示将这个数乘以1000，即是原数的1000倍。同理，如果上方有两条横线，即是原数的1000000（ {displaystyle 1000^{2}} 1000^{{2}}）倍。 - 数码限制：
同一数码最多只能连续出现三次，如40不可表示为XXXX，而要表示为XL。例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替IV。
思路
这道题还是蛮有意思的，同样用递归的方法，在了解拼写规则后，要从数值范围来判断罗马数字的结构，即取哪个字母？哪种组合？左或是右？
孪生题是Roman to Interger比较简单
代码
#python
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
dic = {0:'',1:'I',5:'V',10:'X',50:'L',100:'C',500:'D',1000:'M'}
ks = [1,5,10,50,100,500,1000]
def convert(num):
if num in dic.keys():
return dic[num]
if num > 1000:
n = int(num/1000)
num -= n * 1000
return 'M'*n + convert(num)
n = 1000
for i in ks:
if i > num :
n = i
break
exp = 1
flag = False
while exp <= n: # judge if n is 10 exp k
if exp == n:
flag = True
break
exp *= 10
if flag:
small = n / 10
if num >= 9 * small:
return dic[small] + dic[n] + convert(small -(n-num))
else:
return dic[n/2] + convert(num - n/2)
else:
small = n / 5
if n - small <= num :
return dic[small] + dic[n] + convert(small - (n-num))
else:
n2 = int(num / small)
num -= n2 * small
return dic[small] * n2 + convert(num)
return convert(num)word search
题目
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example, Given board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.
思路
这道题可以用递归函数来解决，注意到，eg从“a” 中判断是否有“aa” ，如果直接递归是返回true的，这不对，要就是说在一次判断中，已判断过的字母不能再判断，所以参数应该还有一个board，记录当前的字母状态，考虑到python是用的引用，传递参数时没有复制，我又不想额外再去复制board，就在函数中记下当前位置的字母，在函数调用结束再改回来的。哈哈！
代码
#python
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
row = len(board)
col = len(board[0])
num = len(word)
def find(r,c,n):
if n == num-1 and board[r][c] == word[n]:
return True
if board[r][c] != word[n] or n == num-1:
return False
tmp = board[r][c] #save the val
board[r][c] = 0
if r < row-1 and find(r+1,c,n+1):
return True
if r > 0 and find(r-1,c,n+1):
return True
if c 0 and find(r,c-1,n+1):
return True
board[r][c] = tmp
return False
for i in range(row):
for j in range(col):
if find(i,j,0):
return True
return False# 2017-8-19
3 sum
题目
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
思路
最开始我想的就直接3重循环，再加判重的循环，暴力求解，当然超时了，要高于O(n3)。后来想到可以将正负数，0，分成三组来组合，然而最后两个数据过不了，在网上搜了一下，可以固定一个数，头尾双指针来移动，这是O(n2)。哎，折腾了一晚上，我好菜啊。 这是前几次的结果[站外图片上传中……(1)]
代码 (分成正负0三组，写了很多判断语句，唉，庸俗的代码。 )
#python
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
rst = []
zero = [] #zeros
neg = [] #negative
pos = [] #positive
for i in (nums):
if i < 0:
neg.append(i)
elif i > 0:
pos.append(i)
else:
zero.append(i)
if len(zero) > 2:
rst.append([0,0,0])
if neg == [] or pos == []:
return rst
if zero != []:
if len(neg) > len(pos):
for i in pos:
if -i in neg:
rst.append([-i,0,i])
else:
for i in neg:
if -i in pos:
rst.append([i,0,-i])
pos.sort()
neg.sort()
if len(pos) == 1 and len(neg) == 1:
return rst
elif len(pos) == 1 :
tmp = len(neg) - 1
while tmp > 0:
sum = neg[tmp] + neg[tmp-1]
if sum == - pos[0]:
rst.append([neg[tmp-1],neg[tmp],pos[0]])
break
elif sum < - pos[0]:
break
tmp -= 1
elif len(neg) == 1:
tmp = 0
while tmp < len(pos) - 1 :
sum = pos[tmp] + pos[tmp+1]
if sum == - neg[0]:
rst.append([neg[0],pos[tmp],pos[tmp+1]])
break
elif sum > - neg[0]:
break
tmp -= 1
sameI = [] #avoid test several same num
for i in range(len(pos)-1):
if i in sameI:
continue
sameI.append(i)
sameJ=[]
for j in range(i+1,len(pos)):
if j in sameJ:
continue
sameJ.append(j)
sum = pos[i] + pos[j]
for k in neg:
if sum > -k:
break
elif sum == -k:
rst.append([k,pos[i],pos[j]])
sameI = []
for i in range(len(neg)-1):
if i in sameI:
continue
sameI.append(i)
sameJ=[]
for j in range(i+1,len(neg)):
if j in sameJ:
continue
sameJ.append(j)
sum = neg[i] + neg[j]
for k in pos:
if sum > -k:
break
elif sum == -k:
rst.append([neg[i],neg[j],k])
fnl = []
for i in rst:
if i not in fnl:
fnl.append(i)
return fnl代码 (头尾双指针，过了，注意判重的方法，前一个用的if，后面在找到答案时用while)
#python
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
rst=[]
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
head = i+1
tail = len(nums) - 1
while head < tail:
if nums[i] + nums[head] + nums[tail] == 0:
rst.append([nums[i],nums[head],nums[tail]])
head += 1
tail -= 1
while head< tail and nums[head] == nums[head -1]:
head = i+1
tail = len(nums) - 1
while head < tail:
if nums[i] + nums[head] + nums[tail] == 0:
rst.append([nums[i],nums[head],nums[tail]])
head += 1
tail -= 1
while head< tail and nums[head] == nums[head -1]:
head += 1
while head<tail and tail < len(nums)-1 and nums[tail]== nums[tail +1]:
tail -= 1
elif nums[i] + nums[head] + nums[tail] < 0:
head += 1
else:
tail -= 1
return rst2017-8-17
jump game
题目
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
思路
由于只有非负数，不能成功的点一定是当前位置为0，所以可以将列表中所以的0找出来，并记下位置（下标），然后从这个位置开始往前搜索，若存在能跳过此位置的点，则能跳过，去除这个0，一直跳过所有0
代码
#python
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) == 1:
return True
zeros = []
for i,j in enumerate(nums):
if j == 0:
zeros.append(i)
while zeros != []:
i = zeros[0]
tmp = i - 1
flag = 0
while tmp >= 0:
if nums[tmp] > i-tmp or nums[tmp]+tmp+1 >=len(nums):
flag = 1
break
tmp -= 1
if flag == 0 :
return False
del zeros[0]
return Truesuper pow
题目
Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:
a = 2
b = [3]
Result: 8
Example2:
a = 2
b = [1,0]
Result: 1024
思路
这道题显然不能直接计算，可以用欧拉定理
对任意正整数a,正整数m,(a,m) = 1,ƒ(m) 为比m小的与m互质的(注意不一定是质数)正整数的个数，
则 aƒ(m) ≡ 1 (mod m) 。
再利用性质： a ≡ b (mod m) ,c ≡ d (mod m) ,则ac ≡ bd (mod m)
证明就不写了，打数学符号太累了（T^T）,给个传送门吧--> 欧拉定理)
代码
#python
class Solution(object):
def superPow(self, a, b):
"""
:type a: int
:type b: List[int]
:rtype: int
"""
m = 1337
if a % m == 0:
return 0
sum = 0
for i in b:
sum = 10 * sum + i
phi = 0
for i in range(1,m):
if (i % 7 != 0) and (i % 191 != 0):
phi += 1
sum = sum % phi
return (a**sum) % 1337
# if m a prime num ,use the small law of Fermat
# else use the law of Euler