二分
左闭右闭区间
while <=
l, r = m+1，m-1
==return mid
return left
def lower_bound(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1 # 闭区间 [left, right]
while left <= right: # 区间不为空
# 循环不变量：
# nums[left-1] < target
# nums[right+1] >= target
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # 范围缩小到 [mid+1, right]
else:
right = mid - 1 # 范围缩小到 [left, mid-1]
return left # 或者 right+1
=x => bin(x)
x => bin(x+1)
<=x => bin(x+1)-1 # 小于等于x对应大于x的那个index-1
<x => bin(x)-1
图论
floyd O(n^3)
枚举所有点，从中间计算
Distance[i][j] = minimum (Distance[i][j], (Distance from i to A) + (Distance from A to j ))
for p in range(n):
for i in range(n):
for j in range(n):
dp[i][j]=min(dp[i][j],dp[i][p]+dp[p][j])
Dijkstra O(n^2)
def dijkstra(u: int) -> int:
dist = [inf] * n
dist[u] = 0
vis = [False] * n
for _ in range(n):
k = -1
for j in range(n):
if not vis[j] and (k == -1 or dist[k] > dist[j]):
k = j
vis[k] = True
for j in gg[k]:
dist[j] = min(dist[j], dist[k] + g[k][j])
return sum(d <= distanceThreshold for d in dist)
下一个排列
思路：
- 先找出最大的索引
k满足nums[k] < nums[k+1]，如果不存在，就翻转整个数组； - 再找出另一个最大索引
l满足nums[l] > nums[k]； - 交换
nums[l]和nums[k]； - 最后翻转
nums[k+1:]。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
firstIndex = -1
n = len(nums)
def reverse(nums, i, j):
while i < j:
nums[i],nums[j] = nums[j], nums[i]
i += 1
j -= 1
for i in range(n-2, -1, -1):
if nums[i] < nums[i+1]:
firstIndex = i
break
#print(firstIndex)
if firstIndex == -1:
reverse(nums, 0, n-1)
return
secondIndex = -1
for i in range(n-1, firstIndex, -1):
if nums[i] > nums[firstIndex]:
secondIndex = i
break
nums[firstIndex],nums[secondIndex] = nums[secondIndex], nums[firstIndex]
reverse(nums, firstIndex+1, n-1)
作者：powcai
链接：https://leetcode.cn/problems/next-permutation/solutions/3830/xia-yi-ge-pai-lie-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
二叉树迭代遍历
s = [root]
res = []
while s:
tmp = s.pop()
if isinstance(tmp,TreeNode):
#注意栈是先进先出，所以right在left前边
s.extend([tmp.right,tmp.left,tmp.val])#前序
s.extend([tmp.right,tmp.val,tmp.left])#中序
s.extend([tmp.val,tmp.right,tmp.left])#后序
elif isinstance(tmp,int):
res.append(tmp)
return res
另一种：
def inorderTraversal(root):
if not root: return []
return inorderTraversal(root.left)+[root.val]+inorderTraversal(root.right)
KMP
#构造next数组，类似单调栈
j=0
next=[0]*len(needle)
for i in range(1,len(needle)):
while j>0 and needle[i]!=needle[j]:
j=next[j-1]
if needle[i]==needle[j]:
j+=1
next[i]=j
if len(needle)==0:
return 0
j=0
ans=0
for i in range(len(haystack)):
while j>0 and haystack[i]!=needle[j]:
j = next[j-1]
if haystack[i]==needle[j]:
j+=1
if j==len(needle):
######求子串出现的位置
return i-j+1
return -1
######
######求字串出现的次数
ans+=1
j=next[j-1]
return ans
######
//python 二分
def search(nums, target):
l,r=0,len(nums)-1
while l<=r:
mid=l+(r-l)//2
if target==nums[mid]:
return mid
if nums[mid]>target:
r=mid-1
else:
l=mid+1
return -1
//优先队列定义
priority_queue<int,vector<int>,greater<int>> q;
//并查集
//最大公约数gcd
int gcd(int a,int b) {
if(b==0) return a;
else
return gcd(b,a%b);
}
//最大公倍数lcm
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
//int字符串互转
include <iostream>
using namespace std;
int main() {
int a;
char aa[425]="12345678900";
//注意有&符号!!!
sscanf(aa,"%lld",&a);//注意有&符号!!!
sprintf(aa,"%d",a);
cout<<a;
}
//质数欧拉筛
int prime[100005], total=0;
bool check[100005];
void get_primes(int n){//筛出[1,n]之间的素数
for (int i = 2; i <= n; ++i) {
if (!check[i]) prime[total++] = i;
for (int j = 0; j < total && i * prime[j] <= n; ++j) {
check[i*prime[j]] = 1;
if (i % prime[j] == 0) break;//保证每个数被他最小的质因数约去
}
}
}
n=int(input())
primes=[]
checks=[False]2+[True]n
for i in range(2,n+1):
if checks[i]==True:
primes.append(i)
checks[i]=False
for k in primes:
if ik>=len(checks):
break
checks[ik]=False
if i%k==0:
break
//计算n！中有多少个质因子p
int cal(int n,int p){
if(n<p) return 0;
return n/p+cal(n/p,p);
}
网友评论