1. The longest non-repeating substring
I don’t need to say the specific meaning of this topic. I will give two algorithms here.
1) Violent search
As long as the machine is fast enough, there is nothing that search can’t solve ^ ^ (just kidding
It’s very simple, we only need to traverse the length and follow the left boundary. There should be nothing to say about this
s = input()
n = len(s)
def solve(s): # Determine whether the string is repeated, return True to represent no repetition
charstr = set()
for ch in s:
if ch in charstr:
return False
charstr. add(ch)
return True
res = 1
for maxl in range(2,n + 1): # string length
for i in range(n - maxl + 1): # left boundary
s2 = s[i : i + maxl]
if solve(s2): res = maxl # Our maxl is incremental, no need to compare
2) Sliding window
We can clearly see that the violent search actually wastes a lot of resources. For example, if the subsequence from 1-5 has been repeated, there is no need to search for the subsequence 1-6. Therefore, the sliding window Ideas arise
We have two pointers, left and right. Right moves first. If the traversed element is not in the set, add it and lens + 1. Otherwise, we let left move, and left deletes the traversed element. Until the element pointed to by the right pointer is not in the set
The specific code is as follows
s = input()
n = len(s)
left, right, lens, maxlen = 0, 0, 0, 0
strset = set()
while right < n:
if s[right] not in strset:
strset. add(s[right])
right + = 1
lens + = 1
maxlen = max(lens,maxlen)
else:
while (s[right] in strset):
strset. remove(s[left])
left + = 1
lens -= 1
print(maxlen)
2. Quick row
The idea of quick sorting is very simple. It is to take a number, and then find the position where the number should be, so that the left side of the number is smaller than him, and the right side is larger than him, divide and conquer (whether this number should be changed to It doesn’t matter where he should be)
Specific code
n = int(input())
a = [int(x) for x in input(). split()]
def quicksort(a,l,r):
if l >= r : return
x = a[l]
i, j = l - 1, r + 1
while (i < j):
i + = 1
j -= 1
while (a[i] < x):
i + = 1
while (a[j] > x):
j -= 1
if (i < j): a[i], a[j] = a[j], a[i]
quicksort(a,l,j)
quicksort(a,j + 1,r)
quicksort(a,0,n - 1)
print(' '.join(map(str,a)))
3. Merge sort
It also adopts the idea of divide and conquer, and a picture can well show the sorting of divide and conquer
Local order –> Global order
The specific code is as follows
n = int(input())
a = [int(x) for x in input(). split()]
def merge_sort(a,l,r):
if l >= r : return
mid = (l + r) // 2
merge_sort(a, l, mid)
merge_sort(a, mid + 1, r)
temp = []
i,j = l,mid + 1
while (i <= mid and j <= r) :
if a[i] < a[j]:
temp.append(a[i])
i + = 1
else:
temp.append(a[j])
j + = 1
if i <= mid:
temp + = a[i : mid + 1]
else:
temp + = a[j : r + 1]
a[l : r + 1] = temp[:]
merge_sort(a, 0, n - 1)
print(' '.join(map(str,a)))
4. Integer dichotomy
This is actually two templates, and the specific problems will be covered in detail.
The first is mid = (l + r) // 2, at this time it depends on a[mid] >=k r = mid
The second is mid = (l + r + 1) // 2, at this time, look at a[mid] <=k l = mid
Else just need to pay attention, r is always l – 1
The specific code is as follows
## Integer binary, find the range of values in the list
# The first line number n and the number to be queried
# The second line is a monotonically increasing array
# The rest of the next few lines are the number of queries
# Floating point binary is not so complicated, no + 1 -1
n ,q = map(int, input(). split())
a = [int(x) for x in input(). split()]
for i in range(q):
l , r = 0, n - 1
k = int(input()) # number to be queried
# first template
while (l < r):
mid = (l + r) // 2
if (a[mid] >= k):
r = mid
else:
l = mid + 1
if a[l] != k : print('-1 1')
else:
print(l, end = ' ') # l is equivalent to the left border
print(r)
# The second template
l , r = 0, n - 1
while (l < r):
mid = (l + r + 1) // 2
if (a[mid] <= k):
l = mid
else:
r = mid - 1
print(l) # This l is equivalent to the right border
5. One-dimensional prefix sum
There is nothing to say about this, just to quickly find the sum of the array from l to r
# It is very convenient to find a[l] + … + a[r], the subscript starts from 1
n ,m = map(int,input().split())
a = [0] + [int(x) for x in input(). split()]
s = [0] * (n + 1)
for i in range(1,n + 1):
s[i] = s[i – 1] + a[i]
for i in range(m): # m queries
l, r = map(int, input(). split())
print(s[r] - s[l - 1])
—————Now it’s too slow to react one by one, I will directly transfer to graph theory and DP, and focus on these two parts
shortest path first
6.dijkstra
This is actually quite simple, it just needs to be proficient, and I have already struggled to write it in retrospect.
The principle of dijkstra is very simple. It is to repeat n (the number of points) times each time, find a point with the shortest distance from the origin each time, and use it to update the distance from the origin to other points. I will not elaborate on the specific proof here. , the time complexity is n^2, it seems that there is a heap optimization method that can achieve a complexity of mlogn
The specific code is as follows
N,null = 510,0x3f3f3f3f
def dijkstra():
dist[1] = 0
for _ in range(n): # update n times because there are n points, each time determine one
t = -1
# Find the closest point to the source point in the set of points without a confirmed shortest path
for j in range(1,n + 1):
if (not st[j] and (t == -1 or dist[t] > dist[j])): # He is the first point or the distance between the following points and the origin is smaller than him
t = j
st[t] = True
for j in range(1,n + 1): # Use t to update In fact, as long as the update is uncertain, but for the convenience of the code, all are updated together
dist[j] = min(dist[j],dist[t] + g[t][j])
if dist[n] == null : return -1
else: return dist[n]
if __name__ == '__main__':
g = [[null]*N for _ in range(N)] # adjacency matrix for dense graph
dist,st = [null]*N,[False]*N # dist is used to store the distance from each point to the starting point st is used to indicate that the current point has been determined to be the shortest
n,m = map(int,input().split())
for _ in range(m):
x,y,z = map(int,input().split())
g[x][y] = min(g[x][y],z) # There may be multiple sides, take the smallest
print(dijkstra())
7. Bellman-ford
This algorithm is to update multiple times according to the edge information, and finally update n (number of points) times to find the shortest path from 1 to n
The advantages of this algorithm are: 1. Negative edges are allowed, 2. He can limit how many edges can be passed from 1 to n at most (wait and see the question)
The specific code is as follows
N, null = 100010, 0x3f3f3f3f
import copy
def bellman_ford():
dist[1] = 0
for _ in range(k): # traverse k times, because there is a limit
last = copy.deepcopy(dist) # Copy it, it is only used when the number of sides is limited, for fear of concatenation
for j in range(m): # traversal updates all edges
a, b, c = edges[j]
dist[b] = min(dist[b], last[a] + c)
if dist[n] > null / 2: print('impossibile')
else: print(dist[n])
if __name__ == '__main__':
n, m, k = map(int, input(). split())
dist = [null] * N
edges = []
for _ in range(m):
x, y, z = map(int, input(). split())
edges. append((x, y, z))
bellman_ford()
8.spfa
This algorithm is actually an improvement on bellman-ford. In the worst case, it has the same time complexity as the bellman-ford algorithm (it seems that most games will get stuck on this). He introduced an idea that only the updated point can update other points. , look at the code specifically, I don’t really like to use linked lists for storage. If there are too many points, the adjacency matrix needs to be 100000*100000, which is obviously too large. You can consider using two lists to store the connection of points and the weight of points ( If you don’t use a linked list), it should be pretty easy to implement. I’ll just use the adjacency matrix here.
The specific code is as follows
##I still don't like to use the linked list to save, I feel a little troublesome
from collections import deque
def spfa():
dist[1] = 0
q = deque([1])
while q:
t = q.popleft() # Pop the element at the beginning
st[t] = False # he is not in the queue anymore
for i in range(1, n + 1): # This step is actually to find the nodes connected to t, but I have no good way, I can only traverse all
if g[t][i] == null: continue
if dist[i] > dist[t] + g[t][i]:
dist[i] = min(dist[i], dist[t] + g[t][i])
if not st[i]:
q.append(i)
st[i] = True
if dist[n] > null / 2: print('impossible')
else: print(dist[n])
N = 510
null = 0x3f3f3f3f
dist, st = [null] * N, [False] * N
g = [[null] * N for _ in range(N)]
n, m = map(int, input(). split())
for _ in range(m):
x, y, z = map(int, input(). split())
g[x][y] = min(g[x][y], z)
spfa()
9. spfa judges negative ring
His way of judging the negative ring is actually very simple. As long as there is an edge that has been updated more than n times, it means that there is a negative ring, so it only needs to be changed a little under the original code. It should be noted that we need to Add all the points to the queue, because point 1 may not reach the negative ring
The specific code is as follows
##I still don't like to use the linked list to save, I feel a little troublesome
from collections import deque
def spfa():
dist[1] = 0
q = deque([x for x in range(1,n + 1)]) # Because it may not be possible to reach the negative ring from point 1. So you need to go through all the points and try
while q:
t = q.popleft() # Pop the element at the beginning
st[t] = False # he is not in the queue anymore
for i in range(1, n + 1): # This step is actually to find the nodes connected to t, but I have no good way, I can only traverse all
if g[t][i] == null: continue
if dist[i] > dist[t] + g[t][i]:
dist[i] = min(dist[i], dist[t] + g[t][i])
cnt[i] = cnt[t] + 1
if cnt[i] >= n : return 'Yes'
if not st[i]:
q.append(i)
st[i] = True
return 'No'
if __name__ == '__main__':
N = 510
null = 0x3f3f3f3f
dist, st = [null] * N, [False] * N
cnt = [0] * N
g = [[null] * N for _ in range(N)]
n, m = map(int, input(). split())
for _ in range(m):
x, y, z = map(int, input(). split())
g[x][y] = min(g[x][y], z)
spfa()
10.flord
This kind of n^3 approach is quite violent. Haha, there is nothing to say about this. Three fors are enough.
The specific code is as follows
N, null= 210, 0x3f3f3f3f
def flord():
for k in range(n + 1):
for i in range(n + 1):
for j in range(n + 1):
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
if __name__ == '__main__':
n, m, k = map(int,input().split()) # k queries
g = [[null] * N for _ in range(N)]
for i in range(n + 1): # flord is updated on g, so do this step
g[i][i] = 0
for _ in range(m):
x, y, z = map(int, input(). split())
g[x][y] = min(g[x][y], z)
flord()
for _ in range(k):
x, y = map(int, input(). split())
if g[x][y] > null / 2: print('impossible')
else: print(g[x][y])