判断字符串是否是互为置换，类似 替换字符串之类的遍历就行了。。
class Solution: # @param {string} A a string # @param {string} B a string # @return {boolean} a boolean def stringPermutation(self, A, B): # Write your code here if len(A) !=len(B):return False lb=[] for b in B:， lb.append(b) for a in A: if a in lb: lb.remove(a) else: return False return True
取滑动窗口的中位数，如果窗口是偶数取中间两个比较小的那个，这个做起来有点复杂，一开始上来直接遍历加排序，总是提示超时，后来优化排序除第一次用全排，后边直接用插入排序，直接用插入排序还是慢，因为上次的序列是一个有序序列可以用二分法优化
插入排序，这么做以后每次构造新的序列移除一个元素还是耗时多，因为本身上次序列是有序的，也可以直接通过索引知道要移除的值，再用二分查找，得出索引，直接移除该索引对应的值
class Solution: """ @param nums: A list of integers. @return: The median of element inside the window at each moving. """ def medianSlidingWindow(self, nums, k): # write your code here le = len(nums) res = [] a = [] def sort(b,first=True): if len(b) < 2:return b if first: return sortq(b)#快速排序，只运行第一次 else:#二分插入 insert = b[len(b) - 1] low=0 high=len(b)-2 while low<=high: mid=(low+high)//2; if insert>b[mid]: low=mid+1 else: high=mid-1 b.insert(low,insert) b.pop() return b def sortq(b): if len(b)<2: return b else: q=b[0] less=[i for i in b[1:] if i<=q] greator=[i for i in b[1:] if i>q] return sortq(less)+[q]+sortq(greator) for i in range(le): if i + k > le: break if i == 0: a = nums[i:i + k] b = sort(a) else: n=len(b) l = 0 r = n - 1 target = nums[i - 1] while l <= r:#二分查找 mid = (l + r) // 2 if b[mid] > target: r = mid-1 elif b[mid]<target: l = mid+1 else: b.pop(mid) break b.append(nums[i+k-1]) b=sort(b,first=False) l=len(b) if l % 2 == 0: res.append (b[l / 2] if b[l / 2 - 1] > b[l / 2] else b[l / 2 - 1]) else: res.append(b[l // 2]) return res
接雨水二 ，一个二维的数组，每个位置有一个高度，问可以接多少水·
整了半天没整明白，网上查了下，从外围构造一个范围，用优先队列做存储，每次pop最小的一个高度然后判断其上下左右的位置是否比该值小，小就又水流入，然后把该点push队列，标记高度为高的哪一个，标记访问到的位置，循环直到队列没有为止
python 又自带的优先队列 heapd，但是这里需要自定义一个类型，看了一下heapd里面的实现代码做大小比较的时候是直接用的运算符，这里直接把自定义类型重载运算符就可以直接用了
class Solution: class bar(object): def __init__(self, x, y, h): self.x = x self.y = y self.h = h def __lt__(self, other): return self.h < other.h def __gt__(self,other): return self.h > other.h def __eq__(self, other): return self.h == other.h # @param heights: a matrix of integers # @return: an integer def trapRainWater(self, heights): # write your code here res=0 import heapq pq = [] heapq.heapify(pq) cols=len(heights[0]) rows=len(heights) visit=[None]*rows for i in range(rows): visit[i]=[False]*cols for i in range(cols): heapq.heappush(pq,self.bar(0,i,heights[0][i])) visit[0][i]=True heapq.heappush(pq, self.bar(rows-1, i, heights[rows-1][i])) visit[rows-1][i] = True for i in range(1,rows-1): heapq.heappush(pq, self.bar(i, 0, heights[i][0])) visit[i][0] = True heapq.heappush(pq, self.bar(i, cols-1, heights[i][cols-1])) visit[i][cols-1] = True dir=[[-1,0],[1,0],[0,-1],[0,1]] while len(pq)>0: b = heapq.heappop(pq) for i in dir: x=b.x+i[0] y=b.y+i[1] if x>=0 and x<rows and y>=0 and y<cols and not visit[x][y]: visit[x][y] = True res=res+max(0,b.h-heights[x][y]) if heights[x][y]>b.h:h=heights[x][y] else: h=b.h nb=self.bar(x,y,h) heapq.heappush(pq,nb) return res
链表求和问题,两个链表，每个节点都只有一位数字，表示一个多位数，输出相加以后的数字的链表形式，这里把两个链表都直接累加程字符串，然后转成数字相加，再转成字符串然后组装成链表输出
class Solution: # @param l1: the first list # @param l2: the second list # @return: the sum list of l1 and l2 def addLists2(self, l1, l2): # Write your code here strl1 = '' current = l1 while current is not None: strl1 = strl1+str(current.val) current = current.next intl1 = int(strl1) strl1 = '' current = l2 while current is not None: strl1 = strl1 + str(current.val) current = current.next intl2 = int(strl1) val = str(intl1+intl2) res = None last = None for s in val: v = int(s) if res is None: res = ListNode(v) last=res else: last.next = ListNode(v) last = last.next return res
回文数，转成字符串倒个序，然后再转成数字，判断相等就行了
class Solution: # @param {int} num a positive number # @return {boolean} true if it's a palindrome or false def palindromeNumber(self, num): # Write your code here strr = '' for s in str(num): strr = s + strr num2=int(strr) return num == num2
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
