1. (Leetcode665) non decreasing column: given an integer array of length N, your task is to judge whether the array can become a non decreasing column when at most one element is changed. We define a non decreasing column as follows: for all I (1 < = I < n) in the array, array [i] < = array [i + 1] is satisfied
Idea:
- Judge whether to modify the current number num [i] or the next number num [i + 1].
- If num [i + 1] > = num [I-1], modify the current number num [i] = num [i + 1];
- If num [i + 1] < num [I-1], modify the next number num [i + 1] = num [i];
- Also consider the 0 position. The 0 position can directly modify the current number, Num [i] = num [i + 1];
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
count = 0
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
if i == 0 or nums[i + 1] >= nums[i - 1]:
nums[i] == nums[i + 1]
count += 1
else:
nums[i + 1] = nums[i]
count += 1
if count <= 1:
return True
else:
return False
2. (Leetcode51) n Queens: place n queens in n × N's chessboard, and the Queens can't attack each other. That is, any two queens are not on the same straight line or slash.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ary = [0]*n
res = []
self.queen(n,ary,0,res)
return res
def queen(self,n,ary,p,res):
if p == n:
temp = []
for k in ary:
temp.append('.'*k + 'Q' + '.'*(n-k-1))
res.append(temp)
return
for i in range(n):
flag = True
for j in range(p):
if ary[j] == i or abs(ary[j]-i) == abs(j-p):
flag = False
break
if flag:
ary[p] = i
self.queen(n,ary,p+1,res)
3. (4.21Pony written test) maximum value of k-times exchange: the array stores non negative integers less than 10. After k-times array adjacent position element transformation (it must be K times), find the maximum number represented by the array.
For example,
int array ={0,1,3,2}
after K=1 transformation, the maximum value is 1032;
the maximum value represented by K=2 transformations is 3012;
Input:
the first line T represents the number of test cases entered;
the second line K represents the number of transformations;
the third line N represents the length of the array;
the fourth line is the value in the input array, separated by spaces;
followed by the alternation of K and N and array digital input.
Output:
array string after exchange
Example:
input:
4
2
5
4 2 1 3 5
3
5
4 2 1 3 5
4
5
4 2 1 3 5
5
5
4 2 1 3 5
output:
4 3 2 1 5
4 5 2 1 3
5 4 2 1 3
5 4 2 3 1
Idea:
- Traverse the array from beginning to end in order to change the maximum exchangeable value to the current position each time;
- Find the maximum value: search backward from the current position until it reaches the end of the array or the step size reaches K;
- Exchange the maximum value from back to front to the current position, update K, and subtract the number of exchanges with K;
- Until the traversal is completed or K is equal to 0, the array is returned
- Note that if K is not 0 after traversal, you need to judge the parity of K. if K is odd, exchange the last two elements. If K is even, return the array directly. (because the title requires K times of exchange. For example, after traversal, the array is 4231, but at this time k is an odd number. You need to exchange 3 and 1 to consume all k)
def change(ary,i,p):
maxnum = ary[p]
for j in range(p-i):
ary[p-j] = ary[p-j-1]
ary[i] = maxnum
def kmax(k,numl):
l = len(numl)
for i in range(l):
maxindex = i
p = i
while p < l and p-i <= k:
if numl[maxindex] < numl[p]:
maxindex = p
p += 1
if maxindex == i:
continue
else:
change(numl,i,maxindex)
k = k-(maxindex-i)
if k == 0:
break
if k == 0 or k%2 == 0:
print(numl)
else:
numl[-1],numl[-2] = numl[-2],numl[-1]
print(numl)
k = [2,3,4,5]
numl = [[4,2,1,3,5],[4,2,1,3,5],[4,2,1,3,5],[4,2,1,3,5]]
for i in range(5):
kmax(k[i], numl[i])
4. (wave question) for natural numbers greater than 1, n=x1y1=x2y2 =... = xiyi, define f(n)=max(yi); For example, 55 = 551, f(55)=max(1)=1, 64 = 641 = 82 = 43 = 26, f(64)=max(1,2,3,6)=6; unsigned long given interval [M,N]; Define g(M,N)=max(f(i)), m < = I < = n, such as g(63,65)=6, g(61,63)=1, g(26,28,)=3. The power() and log() functions can be used at will.
Idea:
- You can consider using the power() function for open root operation. The goal is to find the maximum power satisfying the condition, so you can traverse from the maximum 64 until you find the power satisfying the condition, and then output (why start from 64, because the long type is up to 64bit, that is, the maximum M and N can only be 264);
- Consider that a and b of two integers, a < b. if there is an integer x between a1/k and b1/k, there must be an integer equal to xk between a and b, and this k is the power satisfying the requirements;
- How to determine whether this integer x exists? a1/k is rounded up to index1 and b1/k is rounded down to index2. If index1 < = index2, it must exist;
import math
def get_max(M,N):
for i in range(64,0,-1):
start = pow(M,(1/i))
end = pow(N,(1/i))
index1 = math.ceil(start)
index2 = math.floor(end)
if index1<=index2:
return i
5. Given an integer, it is required to print out the rotated two-dimensional array as required.
For example:
input 1
output
[[1]]
input 2
output
[[3,4],
[2,1]]
input 3
output
[[3,4,5],
[2,1,6],
[9,8,7]]
input 4
output
[[13,14,15,16],
[12,3,4,5],
[11,2,1,6],
[10,9,8,7]]
My idea is:
Using recursion, when n is an odd number, add a row on the lower right side of the matrix, and when n is an even number, add a row on the upper left side of the matrix.
6. (8.3 ape tutoring 01) ape tutoring APP needs to distribute some publicity texts to students. The engineer uses a character compression algorithm. For simplicity, it is assumed that all the compressed characters are capital letter sequences. The rules are as follows:
- AAAB can be compressed to A3B (single character compression without parentheses)
- ABABA can be compressed to (AB)2A (parentheses are added for multi character compression)
- The input data shall ensure that there are no redundant parentheses, and the repeated numbers must be legal and greater than 1, that is: (A)2B, ((AB))2C, (A)B, A1B, (AB)1B will not appear
Note: the number may have multiple digits, i.e. A11B or (AB)10C or A02.
Example:
A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2
Output:
AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD
Ha ha ha, write it out, happy
def decode(string):
res = ''
u = 0
pre = [] #Used to save the position of the first parenthesis
while u < len(string):
if '0' <= string[u] <= '9' and 'A' <= string[u-1] <='Z': #Handle single character numbers without parentheses
num = 0
while u < len(string) and '0'<= string[u] <='9':
num = num*10 + int(string[u])
u += 1
res += res[-1]*(num-1)
elif string[u] == '(':
res += string[u] #Note that the brackets are pushed onto the stack
pre.append(u) #Save the position of the front bracket
u += 1
elif string[u] == ')':
index1 = pre.pop()
num = 0
u += 1
while u < len(string) and '0'<= string[u] <='9':
num += num*10 + int(string[u])
u += 1
res = res[:index1] + res[index1+1:]*num
else:
res += string[u]
u += 1
print(res)
7. (8.3.02) there is a maze matrix with the size of N*M, and each grid of the maze has a value (a [i] [J] < 10 ^ 9). The little ape found in the maze that it can only move towards the adjacent grid in the up, down, left and right directions, and can only enter the grid with a larger value than the current position. But the little ape has an emergency call button. He can press the button to forcibly enter the adjacent grid that does not meet the conditions. Unfortunately, the button can only be pressed K times. Please tell me how many steps the ape can take from any grid in the maze with the help of the emergency call button (the starting position is counted into the number of steps, that is, standing at the starting point is the number of steps is 1).
Example:
3 3 1(N,M,K)
1 3 3
2 4 6
8 9 2
Output:
6
Description: (0,0) (0,1) (0,0) (1,0) (2,0) (2,1)
def step(N,M,x,y,k,data):
res = 1
for i,j in [(0,1),(0,-1),(1,0),(-1,0)]:
nx = x + i
ny = y + j
if nx>=0 and nx<N and ny>=0 and ny<M:
if data[nx][ny]>data[x][y]:
res = max(res, step(N,M,nx,ny,k,data)+1)
elif data[nx][ny]<=data[x][y] and k>0:
res = max(res, step(N,M,nx,ny,k-1,data)+1)
return res
N = 3
M = 3
K = 1
data = [[1,3,3],[2,4,6],[8,9,2]]
res = 1
for i in range(N):
for j in range(M):
res = max(res, step(N,M,i,j,K,data))
print(res) #The output is 6
7. (8.3 ape tutoring 03) K (k > = 3) ape tutoring teachers are playing a little game of beating the drum and passing flowers. Each time they hit the drum, the teacher holding the flowers should give the flowers to others and can't leave them in his own hands. Before the game, the flower is in the hands of the ape. After beating the drum N times, the flower returns to the scheme number in the hands of the ape. Please output the modulus 1e9+7 of this number.
Example:
3 3(N,K)
Output:
2
Idea:
- When this round is not in hand, the last round may or may not be in hand; When the last round was in hand, there was a K-1 possibility (that is, pass the flowers in your hand to others); When the last round is not in hand, there are K-2 possibilities (that is, it is neither in their own hands nor in the hands of the person in the last round);
- When this round is in hand, the previous round must not be in hand, so it is equal to the situation that the previous round is not in hand;
- Use two arrays to save the current round in hand and not in hand;
- Pay attention to the initial conditions and spend it in your hand;
def flower(N,K):
f0 = [0]*(N+1) #Not in hand
f1 = [0]*(N+1) #In hand
for i in range(N+1):
if i == 0:
f0[i] = 0
f1[i] = 1
else:
#This round is not in hand: the previous round is not in hand * (K-2) + the previous round is in hand * (K-1)
f0[i] = f0[i-1]*(K-2)+f1[i-1]*(K-1)
#This round is in hand: the last round is not in hand
f1[i] = f0[i-1]
print(f1[-1])
flower(3,3)
#Output 2
#Verify f0 = [0, 2, 2, 6]
#Verify f1 = [1, 0, 2, 2]
8. Simulate the operation of window and mouse click in windows system, as follows:
- The screen resolution is 3840 * 2160, the upper left corner coordinate is (0,0), and the lower right corner coordinate is (38392159);
- The window is a holding shape, which is positioned by four numbers in the upper left corner (X,Y), width and height (W,H). The upper left corner must be within the scope of the screen, and some other parts may exceed the scope of the screen;
- The click and occlusion rules of the window are the same as those of windows, that is:
-If overlap occurs, the window opened later will be displayed on the window opened earlier;
-When the mouse clicks, you need to judge which window you clicked;
-If there are multiple windows in the same coordinate, click to the top one;
-When a window is clicked, it will float to the top layer;
Enter Description:
- The first line contains two integers N,M, N represents the number of open windows, M represents the number of mouse clicks, 0 < N,M < 1000;
- Next, N lines, 4 integers in each line, Xi Yi Wi Hi, represent the four positioning numbers of each window i. initially, the window opens in the order of input;
- Next M lines, each line has 2 integers, xj, yj, and non-standard represents the coordinates of the next mouse click;
Output Description:
- Each click will output the window ID of this click. If no window is clicked, output - 1
Example:
2 4
100 100 100 100
10 10 150 150
105 105
180 180
105 105
1 1
Output:
2
1
1
-1
Idea:
- Use the list to store in the order of the window. Each time you click, look for the first window that can be clicked in the list from the back to the front, and take out the window and put it at the end of the list, which is similar to the operation of stacking in and out of the stack;
- Pay attention to dealing with windows that exceed the range in advance;
def smallwin(x,y,w,h): #Window preprocessing
x2 = 3839 if x+w > 3839 else x+w
y2 = 2159 if y+h > 3839 else y+h
return [x,x2,y,y2]
def ccc(N,M,window,click):
win = []
for i in range(N):
x,y,w,h = window[i]
win.append(smallwin(x,y,w,h))
win[-1].append(i+1) #Add a one-dimensional window number after the window coordinates to facilitate output
for x,y in click:
cur = -1
for j in range(N-1,-1,-1):
x1,x2,y1,y2,num = win[j]
if x1<=x<=x2 and y1<=y<=y2:
cur = num
temp = win[j]
win.remove(win[j])
win.append(temp)
break
print(cur)
N,M = 2,4
window =[[100,100,100,100],[10,10,150,150]]
click = [[105,105],[180,180],[105,105],[1,1]]
ccc(N,M,window,click)
9. For a string composed of all uppercase letters, it is allowed to change up to 2 uppercase letters to make the length of the longest continuous N string contained in the string the longest.
Example:
3
NNTN
NNNNGGNNNN
NGNNNNGNNNNNNNNSNNNN
Output:
4
10
18
Idea:
- Record the position of non-N characters;
- If n < = 2, directly return the string length;
- Otherwise, consider changing the length of N string after two adjacent non-n characters, and the length calculation is calculated by the position difference of two non-n characters before and after the changed non-n characters;
- Note that since it is necessary to calculate the length by using the position, after the non-N character position is counted, a 0 element should be added in front of it and a total length element should be added after it;
def numN(string):
err = [0]
for i in range(len(string)):
if string[i] != 'N':
err.append(i)
if len(err)<=2:
return len(string)
else:
err.append(len(string))
num = 0
for i in range(len(err)-3):
temp = err[i+3]-err[i]-1
if temp>num:
num = temp
return num
data = ['NNTN','NNNNGGNNNN','NGNNNNGNNNNNNNNSNNNN']
for i in data:
print(numN(i))
10. For the swimming pool control device, the water supply pipe and drainage pipe are open at the beginning. The state of the water supply pipe will change every t1 minutes, and the state of the drainage pipe will change every t2 minutes; The water supply pipe will inject m1 liters of water every minute, and the drainage pipe will discharge m2 liters of water every minute; The water volume of the swimming pool cannot be negative and cannot exceed the maximum capacity of m liters. Then how many liters of water does the swimming pool have after t minutes.
Enter Description:
- Enter the first line T, indicating that there are t groups of data;
- Each group of data contains six integers, m,t,m1,m2,t1,t2;
Output Description:
- An integer is output for each group of data to represent the water volume after t minutes;
Example input:
5
10 2 1 5 2 5
10 2 10 5 2 5
10 2 3 5 2 5
100 100 3 4 4 3
10000 1000 10 5 5 3
output
0
10
0
3
2495
def water(m,t,m1,m2,t1,t2):
temp1 = True
temp2 = True
total = 0
for i in range(t):
total += (temp1*m1 - temp2*m2)
if total < 0:
total = 0
if total > m:
total = m
if (i+1)%t1 == 0:
temp1 = not temp1
if (i+1)%t2 == 0:
temp2 = not temp2
print(total)
data = [[10,2,1,5,2,5],
[10,2,10,5,2,5],
[10,2,3,5,2,5],
[100,100,3,4,4,3],
[10000,1000,10,5,5,3]]
for m,t,m1,m2,t1,t2 in data:
water(m,t,m1,m2,t1,t2)
11. (360-8.15 written test 1) calculate the surface area. The rectangular area with a length of N*M cm is divided into N rows and M columns (the width of each row and column is 1 cm). AI and j cubes with a side length of 1 cm (1 ≤ Ai,j ≤ 100) are stacked at the position of row i and column J. all cubes form a three-dimensional figure, and part of the six faces of each cube will be blocked by other cubes, The total area of the unobstructed part is the surface area of the three-dimensional figure. How many square centimeters is the surface area of the three-dimensional figure?
Enter Description:
- The first line contains two integers N and M, 1 ≤ N, M ≤ 1000;
- Next, N lines, each line contains M integers, and the j integer in line i represents Ai,j;
Example:
Input:
2 2
2 1
1 1
Output:
20
Idea:
- Count the occluded area at each position;
- Subtract the occluded area from the total surface area;
def area(N,M,matrix):
num = 0
cover = 0
for i in range(N):
for j in range(M):
num += matrix[i][j]
cover += (matrix[i][j]-1) * 2
if i>0: #upper
cover += min(matrix[i][j],matrix[i-1][j])
if i<N-1: #lower
cover += min(matrix[i][j],matrix[i+1][j])
if j>0: #Left
cover += min(matrix[i][j-1],matrix[i][j])
if j<M-1: #right
cover += min(matrix[i][j+1],matrix[i][j])
res = num*6 - cover
return res
matrix = [[2,1],[1,1]] area(2,2,matrix)
12. (360-8.15 written test 2) give two numbers containing N digits in M-ary. You can rearrange the numbers on each digit of the two numbers respectively, then add the two numbers corresponding to each digit and modulus m respectively. Obviously, you can get... 1 new n digits in M-ary (there may be leading 0), but the result is not unique. The problem comes. Follow this operation, What is the largest number in M-ary that can be obtained.
Enter Description:
- The first input line contains two positive integers n,m respectively indicates that the number contains n bits, and in M-ary;
- The second and third input lines contain n integers respectively, separated by spaces, and each integer is between 0 and m-1. The i-th number in each line represents the number in the i-th bit of the current number;
- The output contains n numbers separated by spaces, indicating the largest number obtained. It is output from high to low. For example, 6 outputs 3 bits in binary system, and the result is 1 0.
Example:
input
5 5
4 4 1 1 1
4 3 0 1 2
output
4 4 3 3 2
Explanation:
4 4 1 1 1 →1 4 1 4 1
4 3 0 1 2 → 3 0 2 4 1 (rearrange the sequence, the number after adding the digits is 4 4 3 8 2, and take the module of 5)
Idea:
- Greed, violence. Try to find a larger combination after taking the mold, such as m=5, give priority to 4 and put it in front, and then 3,2,1.
def eee(lis1,lis2,m,enum):
for i in lis1:
for j in lis2:
if (i+j)%m == enum:
lis1.remove(i)
lis2.remove(j)
print(enum,end = ' ')
return True
return False
def find(lis1,lis2,m,enum):
q = True
while lis1:
if q:
q = eee(lis1,lis2,m,enum)
else:
enum -= 1
q = eee(lis1,lis2,m,enum)
lis1 = [4,4,1,1,1] lis2 = [4,3,0,1,2] m = 5 find(lis1,lis2,m,m-1) #Output 4 4 3 2
13. () a small sweet potato won a certain value of potato coupons in the lucky draw in the activity of small sweet potato. These potato coupons can be used to buy a batch of goods. Ask how many kinds of purchase combinations there are. You can buy more than one item.
Input: voucher amount and commodity price respectively; Output: number of combinations
Example:
input
10 [2,3,5]
output
4 (the result set is 2,2,2,2,2; 5,5; 2,3,5; 2,2,3,3)
Idea: dynamic programming
- The number of possible combinations of current amount is equal to the accumulation of combinations after subtracting different commodity prices respectively;
- For example, the number of combinations of 10 is equal to the accumulation of the number of combinations of 10-2, 10-3 and 10-5;
- During implementation, you can consider the possible accumulation of each commodity price, so as to avoid repeated calculation. For example, 5 has only one combination number 2,3, but if subtraction is used, there will be two repeated cases of 5-2 = 3,5-3 = 2; However, if the amount is accumulated, only 2 + 3 = 5, because when 3 + 2, the combination number of 3 is 0.
money= 10
coins = [2,3,5]
dp = [0] * (money+ 1) #Construct an array with the length of coupon amount + 1 to store each possible amount
dp[0] = 1 #Pay attention to the first number and ask 1
for coin in coins:
for i in range(money- coin + 1):
if dp[i]:
dp[i + coin] += dp[i]
print(dp[amount])
14. () captain Shu wrote n notes, numbered from 1 to N, and each note received a lot of praise. Captain potato wants to select some notes from them and make a selection collection. There are two rules for selection:
- Consecutive numbered notes cannot appear.
- Maximum total likes
If there are multiple schemes that meet the conditions of 1 and 2, select the one with the least total number of notes.
Input:
the first line n indicates how many notes
n integers in the second line represent the number of likes obtained
Output:
two integers x,y
x represents the total number of likes, and y represents the total number of selected notes
Sample input:
4
1 2 3 1
sample output
4 2
Idea:
Dynamic programming (leetcode 198 is a deformation of house robbing, with the consideration of selecting the least total number of notes)
Give priority to those with more likes, and then consider those with the least total number of notes;
n = 4
data = [1,2,3,1]
res = [[0,0]]*n
res[0] = [data[0],1]
res[1] = [max(data[0],data[1]),1]
for i in range(2,n):
if res[i-1][0]>res[i-2][0]+data[i]:
res[i][0] = res[i-1][0]
res[i][1] = res[i-1][1]
elif res[i-1][0]<res[i-2][0]+data[i]:
res[i][0] = res[i-2][0]+data[i]
res[i][1] = res[i-2][1]+1
else: #If the two are equal, consider the case where the total number of notes is the least
res[i][0] = res[i-1][0]
if res[i-1][1]<res[i-2][1]+1:
res[i][1] = res[i-1][1]
else:
res[i][1] = res[i-2][1]+1
15. () N-value monster, Hi indicates the health of the ith monster. You need to defeat all monsters in t turn to win. You can choose to physically attack monsters every round, causing 1 point of damage; Or consume a little mana to cause fixed X points of damage, and initially have M points of mana. Ask X at least how big, in order to have a chance to win; If you can't win in the T round, you will output - 1.
Input:
first line N,T,M
the blood volume of N monsters in the second row
Output:
an integer X
Idea:
binary search + greed
- The range of fixed damage X must be between the minimum value (0) and the maximum value (maximum blood volume). Use binary search, and then judge whether X meets the conditions;
- Take the maximum value from all blood volume each time, and then judge how many spells this maximum value can consume. At the same time, consider m, i.e. min (maximum blood volume / X,m); Then add the remaining blood volume into the blood volume array again, m=m-min;
- If T < 0 occurs, that is, it has not been completely destroyed but cannot be attacked, if the conditions are not met, return False;
- When m=0, judge whether the total remaining blood volume is less than or equal to T. If yes, the conditions are met and return True; otherwise, return False;
- After judging x once, if it returns True, it will search again between the minimum value (0) and X; Otherwise, it will be split again between X and the maximum value (maximum blood volume).
def check(n,t,m,x,data,total):
while data:
if m:
data.sort()
mon = data.pop()
total -= mon
if mon>x:
n = min(mon//x,m)
remain = mon-n*x
if remain != 0:
data.append(remain)
m -= n
t -= n
else:
m -= 1
t -= 1
if t<0:
return False
else:
if total<=t:
return True
else:
return False
return True
n,t,m = 3,4,3
data = [5,2,1]
data.sort()
total = sum(data)
l = 0
r = data[-1]
while l < r:
mid = (l + r)//2
if check(n,t,m,mid,data,total):
r = mid
else:
l = mid + 1
print(l)
This problem can also consider using a large root heap to store blood volume, which can avoid sorting in each cycle.
class Myheap(object):
def __init__(self):
self.data = []
def push(self,item):
if item != 0:
heapq.heappush(self.data, item)
def pop(self):
return -heapq.heappop(self.data)
def not_empty(self):
if self.data:
return True
else:
return False
def check(n,t,m,x,bheapq,total):
while bheapq.not_empty():
if m:
mon = bheapq.pop()
total -= mon
if mon>x:
n = min(mon//x,m)
remain = mon - n*x
bheapq.push(-remain)
total += remain
m -= n
t -= n
else:
m -= 1
t -= 1
if t<0:
return False
else:
if total<=t:
return True
else:
return False
return True
n,t,m = 3,4,3
data = [5,2,1]
total = sum(data)
bheapq = Myheap()
for i in data:
bheapq.push(-i) #Because the headpq in python is used to build a small root heap, you only need to reverse it every time you get the meal, push and pop
l = 0
r = max(data)
while l < r:
mid = (l + r)//2
if check(n,t,m,mid,bheapq,total):
r = mid
else:
l = mid + 1
print(l)