LeetCode初级算法的Python实现--排序和搜索、设计问题、数学及其他
1、排序和搜索
class Solution(object):
# 合并两个有序数组
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
nums1[m:m + n] = nums2[:n]# 合并数组
nums1.sort()
# 第一个错误的版本
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
minn=1
maxn=n
while True:
mid=int((minn+maxn)/2)# 二分
if isBadVersion(mid)==True and isBadVersion(mid+1)==True:
maxn=mid-1
elif isBadVersion(mid)==False and isBadVersion(mid+1)==False:
minn=mid+1
else:
return mid+1
2、设计问题
打乱一个没有重复元素的数组。
class Solution(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.numsR = nums[:]
self.nums = nums
def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
self.nums = self.numsR[:]
return self.nums
def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
random.shuffle(self.nums)
return self.nums
# 最小栈
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.nums = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.nums.append(x)
def pop(self):
"""
:rtype: void
"""
self.nums.pop(len(self.nums) - 1)
def top(self):
"""
:rtype: int
"""
return self.nums[(len(self.nums) - 1)]
def getMin(self):
"""
:rtype: int
"""
return min(self.nums)
3、数学
import random
class Solution(object):
# Fizz Buzz
def fizzBuzz(self, n):
"""
:type n: int
:rtype: List[str]
"""
strList = []
for i in range(1, n + 1):
if i % 3 == 0 and i % 5 == 0:
strList.append("FizzBuzz")
elif i % 3 == 0:
strList.append("Fizz")
elif i % 5 == 0:
strList.append("Buzz")
else:
strList.append(str(i))
return strList
# 计数质数，将当前该数的的倍数标记，则未被标记的位置为质数，因为当前该数不是前面的数的倍数
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
count = 0
flag = [False for i in range(n + 1)]
for i in range(2, n):
if flag[i] == False:
k = i
while k <= n:
flag[k] = True
k += i
count += 1
return count
# 3的幂
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
if n <= 0:
return False
while n > 1:
n = n / 3.0
if n != int(n):
return False
return True
# 罗马数字转整数
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
val = 0
data = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, }
for i in range(0, len(s)): # 如果遍历到最后一个字符或者当前字符代表的数大于后一个字符代表的数则加，反之减
if len(s) == i + 1 or data[s[i + 1]] <= data[s[i]]:
val += data[s[i]]
else:
val -= data[s[i]]
return val
4、其他
class Solution(object):
# 位1的个数
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
res = bin(n).count('1')
return res
# 汉明距离
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
xbin = bin(x)[2:]
ybin = bin(y)[2:]
count = 0
if len(xbin) > len(ybin): # 得到长度较短的
xbin, ybin = ybin, xbin
cha = len(ybin) - len(xbin)
for i in range(0, cha): # 将较短的用0补全
xbin = '0' + xbin
for i in range(0, len(ybin))[::-1]:
if xbin[i] != ybin[i]: # 判断
count += 1
return count
# 颠倒二进制位
def reverseBits(self, n):
nbin = bin(n)[2:]
for i in range(0, 32 - len(nbin)):
nbin = '0' + nbin
nbin = nbin[::-1]
result = int(nbin, 2) # 转十进制
return result
# 帕斯卡三角形
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows == 0:
return []
result = [[1]]
for i in range(1, numRows):
block = [1]
for j in range(0, i - 1):
block.append(result[i - 1][j] + result[i - 1][j + 1])
block.append(1)
result.append(block)
return result
# 有效的括号
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
while len(s) >= 0: #
flag = False # 标志如果下面三个都不存在 说明不是有效果括号，有的话则替换
if s.__contains__('()'):
s = s.replace('()', '')
flag = True
if s.__contains__('{}'):
s = s.replace('{}', '')
flag = True
if s.__contains__('[]'):
s = s.replace('[]', '')
flag = True
if len(s) == 0:
return True
if flag == False:
break
return False
# 缺失数字
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort() # 排序
for i in range(0, len(nums) - 1):
if (nums[i] + 1) != nums[i + 1]: # 如果当前值加一等于下一个
return nums[i] + 1
if nums[0] > 0:
return 0
return len(nums)