''' 解题思路： 公司首先将这 2N2N 个人全都安排飞往 BB 市，再选出 NN 个人改变它们的行程，让他们飞往 AA 市。 如果选择改变一个人的行程，那么公司将会额外付出 price_A - price_B 的费用，这个费用可正可负 最优的方案是，选出 price_A - price_B 最小的 NN 个人，让他们飞往 A 市，其余人飞往 B 市。 ''' class Solution: def twoCitySchedCost(self, costs: List[List[int]]) -> int: n = len(costs) #p...

''' 解题思路： 二分查找：左边界为数组最大值，右边界为数组元素的和，寻找船的最低运载能力 ''' class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: W = weights n = len(weights) #print(W) wMin = max(W) wMax = sum(W) # 最低运载能力为w时，是否可在days天内完成 def ...

''' 1、双指针，先对tokens从小到大排序，当power足够时从小到大换取得分(S++)，power不够时由大到小兑换一次(S--)，过程中取得分最大值 2、本题边界及退出条件相对复杂 ''' class Solution: def bagOfTokensScore(self, tokens: List[int], power: int) -> int: T = tokens n = len(T) p = power T = sorted(T) print(T...

''' 解题思路： 双指针移动判断即可 ''' class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: P = people n = len(P) P = sorted(P) print(P) i = 0 j = n-1 k = 0 while i<=j: if i==j: ...

''' 解题思路： 如有 x 只兔子都回答 y，则至少有 ceil(x/(y+1))*(y+1) 只兔子 ''' class Solution: def numRabbits(self, answers: List[int]) -> int: if not answers: return 0 A = answers n = len(answers) print(A) Dic = {} for i in range(n): ...

''' 解题思路： 区间不断合并，没有交集时，需要一支箭 ''' class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: P = points n = len(points) P = sorted(P,key=lambda x:x[0]) print(P) S = P[0] k = 0 for i in range(1,n): N = P[i]...

''' 解题思路： 维护一个长度为2的上升子序列up，和当前为止的序列最小值minv，根据规则更新即可 ''' # [20,100,10,12,5,13] from typing import re class Solution: def increasingTriplet(self, nums): L = nums print(L) n = len(nums) minv = L[0] up = [minv] for i in range(1,n): ...

''' 解题思路： 1、输出out为最小字典排列的字符串，如新字符已在out中，则直接跳过 2、如新字符si不在out中，但小于out[-1]（不是字典序），检查后面是否还有out[-1]，如有则删除当前out[-1]； 该过程通过while循环一直向前，直到while条件不满足 ''' class Solution: def removeDuplicateLetters(self, s): s = list(s) print('s=',s) n = len(s) out = [s[0]] fo...

''' 解题思路： 1、sum(gas)<sum(cost)无解 2、行驶过程中，如gas[k]-cost[k]的累积值小于0，跳过k 3、在终点，如gas[k]-cost[k]的累积值大于等于0，即是解 ''' class Solution: def canCompleteCircuit(self, gas, cost): #print(gas) #print(cost) n = len(gas) pos = list(range(n))+list(range(n-1)) #print(pos...

''' 解题思路 核心就一句话：就是把第一个小数和它后面最大的大数进行交换 理由如下： 要让一个数变大，要尽可能的让其高位变大 比如说 2736 ， 让最高位2变大成3，也比让3那位变成9来的大， 3736 >>>> 2796 所以，本题的核心要义就是 让最高位的小数和后面的大数交换 小数我们找到了，那那个大数怎么找呢？大数需要满足以下特点 比小数靠后(废话) 值比小数大(废话) 尽可能的后(因为，该大数位交换后，来的是个小数，所以要把这个小数尽可能放到后面去) 比如 12344 ，是42341 大还是 42314 大呢？显而易见嘛 ''' class Solution...

''' https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=196&&tqId=37055&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking ''' # -*- coding:utf-8 -*- class TreeNode: def __init__(self, x): self.val = x self.left = None sel...

''' 6.7 二叉树重建 #============================================================================================= https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=196&&tqId=37109&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking 解题思路： 前序遍历：先根节点，再左子...

2、 recursive / fibonacci 2.1 蛙跳 mem = {} def fun(n): global mem if n in mem: return mem[n] else: if n==1: mem[n] = 1 return 1 elif n==2: mem[n] = 2 return 2 else: t = fun(n-1)+fun(n-2) ...

8、 point 8.1 两数之和等于指定值 class Solution: def twoSum(self , numbers , target ): # write code here n = len(numbers) if n<2: return [] L = sorted(numbers) i = 0 j = n-1 while i<j: if L[i]+L[j]==target: ...