3 不限于leecode了，其他一些代码的实践也准备加进来
三短代码让你知道什么是yield
原始的不递归fib写法
def fib(n):
ans = []
i = 0
a, b = 0, 1
while (i < n):
a, b = b , a + b
ans.append(a)
i +=1
print(ans)
手动实现fib的写法
class Fab():
def __init__(self, n):
self.a = 0
self.b = 1
self.max = n
self.iter = 0
def next(self):
if(self.iter<self.max):
self.a, self.b = self.b, self.a + self.b
self.iter += 1
return self.a
raise StopIteration()
利用Python yield的写法，优点，可以节省内存, 只是生成一个迭代器
def fib(n):
r,a,b = 0,0,1
while(r<n):
a,b=b,a+b
r+=1
yield a
a = fib(10)
print(next(a))
5. 牛客网设计LRU缓存结构
联想python中有什么先进先出的结构
# lru design
# @param operators int整型二维数组 the ops
# @param k int整型 the k
# @return int整型一维数组
# def LRU(self , operators , k ):
import collections
import sys
class Solution:
def __init__(self, k):
self.dic = collections.OrderedDict()
# 关于orderdict的牛逼之处可以看博客 https://blog.csdn.net/qq_41648043/article/details/82878812
#当然这里简要说一下：
# 1. 按照插入的顺序排列，不是key本身排序
# 2. popitem方法默认参数last=True,删除最后一个，如果想删除第一个设置为False
self.capacity = k
def set(self, key, value):
if key in self.dic:
self.dic.pop(key) #先pop再加入保证永远都是最新的，优先级最高
else:
if self.capacity > 0:
self.capacity -= 1
else:
self.dic.popitem(False) #达到容量时，先进先出（删除）
self.dic[key] = value
def get(self, key):
if key not in self.dic:
return -1
val = self.dic.pop(key)
self.dic[key] = val
return val
for line in sys.stdin.readlines():
line = line.strip()
line = line.replace(' ', '')
a = line.split(']],')
k = int(a[1])
res = []
s = Solution(k)
for item in a[0][2:].split('],['):
m = item.split(',')
if m[0] == '1':
s.set(int(m[1]), int(m[2]))
else:
res.append(s.get(int(m[1])))
print(str(res).replace(' ', ''))
5. 这里记录一个面试遇到的问题
https://blog.csdn.net/qq_34342154/article/details/77388913
面试官还问了一个升级版本：
如果给定的数组是无序的，多次要查询某个字符串所在的位置，有什么办法？
通过哈希分桶，把哈希相同的放到一个桶中，记录在哈希表中，每次去查哈希表就可以
6. 这里是在寻找5的过程中碰到一个很好的博客，可以跟着做程序员代码指南的部分
https://blog.csdn.net/qq_34342154/article/details/77918297
不能停~~总结下最近面试被问到的一些算法题目
1 百度面试官自己YY出来的题目
百度问到：
比较简单第一个
N+1 个数中一定包含1-N中所有元素外加一个在 1-N之间（包含）的重复元素
求出这个重复元素
题目加强：
N+1 个数中一定包含1-N中所有元素外加两个在 1-N之间（包含）的重复元素
求出这两个重复元素
沿用第一个思路可以得到这两个数的和
然后只要再得出两个数的其他关系，就可以求出这两个数
这里想到乘法，但是乘法容易溢出，所以我答了乘法后取对数的思路
相当于知道了 a+b 和 log(a) + log(b)， 后面就是数学上的事情了
5 15. 三数之和
个人的第一个版本, 有问题的地方注释了
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
res = []
nums.sort()
print(nums)
for i in range(len(nums)):
#这里要想一下如何去掉重复的情况
low, high = i+1, len(nums) - 1
while(low < high):
if nums[low] + nums[high] + nums[i] > 0 :
high -= 1
elif nums[low] + nums[high] + nums[i] < 0 :
low += 1
else:
res.append([nums[i],nums[low],nums[high]])
low += 1
high -= 1
break # 这里显然是不对的，第一次满足后，在low high 内部可能依然存在满足条件的组合
return res
改进之后发现还是报错，错误case : 输入为 [-2,0,0,2,2] 发现是没有考虑当 0 2 和 0 2 重复的情况 所以要再做一次判断 , 最终改正的代码如下：
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
res = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
low, high = i+1, len(nums) - 1
while(low < high):
if nums[low] + nums[high] + nums[i] > 0 :
high -= 1
elif nums[low] + nums[high] + nums[i] < 0 :
low += 1
else:
res.append([nums[i],nums[low],nums[high]])
low += 1
high -= 1
#这里加入重复判断
while low < high and nums[low] == nums[low-1]:
low += 1
while low < high and nums[high] == nums[high+1]:
high -= 1
return res
6 18. 四数之和
还是稍微看了下思路，三数会了四个的还是不会，智商堪忧啊。。。
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4 :
return []
nums.sort()
res = []
for i in range(len(nums)-3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1,len(nums)-2):
if j > i + 1 and nums[j] == nums[j-1]:
continue
low, high = j+1, len(nums)-1
while(low < high):
sum_value = nums[i] + nums[j] + nums[low] + nums[high]
if sum_value == target:
res.append([nums[i],nums[j],nums[low],nums[high]])
low += 1
high -= 1
while low < high and nums[low] == nums[low-1]:
low += 1
while low < high and nums[high] == nums[high+1]:
high -= 1
elif sum_value > target:
high -= 1
else:
low += 1
return res
