1. The number of combinations in which the sum of two elements in the array is less than or equal to M
For an integer array, how many combinations are there when any two elements are added and less than or equal to M;
If yes, output the combined logarithm;
No, output 0.
code:
nums = list(map(int, input().split())) M = int(input()) n = len(nums) ans = 0 for i in range(n - 1): for j in range(i + 1, n): if nums[i] + nums[j] <= M: ans += 1 print(ans)
2. Calculate K-bit
Give you two positive integers n and k, where 1 = < n < = 26, and the formation rules of string Sn are as follows:
Li stands for 26 letters a-z, which are:
L1 = "a"
L2 = "b"
L3 = "c"
...
L26="z"
S1 = "a"
When I > 1, Si = Si-1 +Li + reverse(invert(Si-1))
Where + represents the connection operation of the string, reverse(x) returns the string obtained by reversing x, and convert (x) will flip each bit in X (for example, 'a' to 'z', 'b' to 'y',... And 'z' to 'a').
For example, the first four strings of the sequence according to the above description are:
S1="a"
S2="abz"
S3="abzcayz"
S4="abzcayzdabzxayz"
Please return the k-th character of Sn. The title data must ensure that K is within the length range of Sn.
Example 1 input and output examples are only for debugging, and the background judgment data generally does not contain examples
code:
# The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly
#
# Returns the k-th character of Sn
# @N of param n int integer Sn
# @param k int integer needs to return the character subscript
# @return char character type
#
class Solution:
def findKthBit(self, n, k):
# write code here
def invert(s) -> str:
inv_s = ''
for ch in s:
inv_s += chr(122 - ord(ch) + 97)
return inv_s
S = {}
for i in range(1, n + 1):
if i == 1:
S[i] = 'a'
else:
S[i] = S[i - 1] + chr(96 + i) + invert(S[i - 1])[::-1]
return S[n][k - 1]
n, k = 3, 1
print(Solution().findKthBit(n, k))
3. Paper distribution problem
A group of children gathered in a circle to start painting. Now the teacher needs to give these children paper;
The rule is that if a child is older than the child next to him, the child must be given more paper than the child next to him;
All children should have at least one piece of paper. Please help the teacher design an algorithm to calculate the minimum number of sheets of paper.
remarks:
It is assumed that the total number of children will not exceed 100;
Each child is required to have at least one piece of paper;
If and only if the age is older than the adjacent children, more paper will be required (less than or equal to is allowed if the age is equal).
Solution: take the local minimum value by dichotomy, judge the height of the left and right sides, and discuss the situation
code:
from collections import defaultdict
ages = list(map(int, input().split()))
papers = defaultdict(int)
n = len(ages)
def get_paper(left, right):
if left >= right:
return
part_ages = ages[left: right]
min_age = min(part_ages)
idx = part_ages.index(min_age) + left
if ages[idx - 1] >= ages[idx] and ages[(idx + 1) % n] >= ages[idx]:
papers[idx] = 1
elif ages[idx - 1] < ages[idx] and ages[(idx + 1) % n] < ages[idx]:
papers[idx] = max(papers[idx - 1], papers[(idx + 1) % n]) + 1
elif ages[idx - 1] < ages[idx]:
papers[idx] = papers[idx - 1] + 1
else:
papers[idx] = papers[(idx + 1) % n] + 1
get_paper(left, idx)
get_paper(idx + 1, right)
get_paper(0, n)
print(sum(papers.values()))
4. Nautical exploration
Give you a two-dimensional grid composed of '0' (water), '1' (land) and '2' (obstacles), and then give you an amphibious vehicle. The land cost is 1 and the waterway cost is 2. The obstacles are impassable. Please calculate the minimum cost from the starting position of the grid to the final position.
Note: you can only drive horizontally and vertically. If the destination cannot be reached, - 1 is returned
In addition, the first starting location is not counted, and the cost is determined according to the attribute of the arrival location.
Example 1 input and output examples are only for debugging, and the background judgment data generally does not contain examples.
Solution:
Backtracking (time consuming, timeout)
#
# The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly
#
# Calculate the minimum sailing cost
# @param input int integer 2D array 2D mesh
# @return int integer
#
class Solution:
ans = 99999
def minSailCost(self, input):
# write code here
m, n = len(input), len(input[0])
flag = [[False] * n for _ in range(m)]
cost_dict = {0: 2, 1: 1, 2: 0}
def travel(x, y, cost):
if x < 0 or x >= m or y < 0 or y >= n:
return
if flag[x][y] or input[x][y] == 2:
return
if x != 0 or y != 0:
cost += cost_dict[input[x][y]]
if x == m - 1 and y == n - 1:
if cost < self.ans:
self.ans = cost
return
flag[x][y] = True
travel(x - 1, y, cost)
travel(x + 1, y, cost)
travel(x, y - 1, cost)
travel(x, y + 1, cost)
flag[x][y] = False
travel(0, 0, 0)
return self.ans if self.ans != 99999 else -1
input = [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
print(Solution().minSailCost(input))
Dynamic planning paper cutting (snake walking is not considered)
#
# The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly
#
# Calculate the minimum sailing cost
# @param input int integer 2D array 2D mesh
# @return int integer
#
class Solution:
def minSailCost(self, input):
# write code here
m, n = len(input), len(input[0])
cost_dict = {0: 2, 1: 1}
inf = 99999
# Record the minimum cost from a point of departure to the end
dp = [[inf] * n for _ in range(m)]
def travel(x, y):
if x < 0 or x >= m or y < 0 or y >= n or input[x][y] == 2:
return inf
if dp[x][y] != inf:
return dp[x][y]
cur_cost = 0 if x == 0 and y == 0 else cost_dict[input[x][y]]
if x == m - 1 and y == n - 1:
dp[x][y] = cur_cost
else:
part_cost1 = travel(x + 1, y)
part_cost2 = travel(x, y + 1)
dp[x][y] = min((part_cost1, part_cost2)) + cur_cost
return dp[x][y]
ans = travel(0, 0)
return ans if ans < inf else -1
input = [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
print(Solution().minSailCost(input))
Priority queue (positive solution, PRIM algorithm idea)
#
# The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly
#
# Calculate the minimum sailing cost
# @param input int integer 2D array 2D mesh
# @return int integer
#
from queue import PriorityQueue
class Node:
def __init__(self, x, y, cost):
self.x = x
self.y = y
self.cost = cost
def __lt__(self, other):
return self.cost < other.cost
class Solution:
def minSailCost(self, input):
# write code here
m, n = len(input), len(input[0])
cost_dict = {0: 2, 1: 1}
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
vis = [[0] * n for _ in range(m)]
q = PriorityQueue()
q.put(Node(0, 0, 0))
vis[0][0] = 1
while not q.empty():
node = q.get()
if node.x == m - 1 and node.y == n - 1:
return node.cost
for i in range(4):
dx = node.x + directions[i][0]
dy = node.y + directions[i][1]
if dx < 0 or dx >= m or dy < 0 or dy >= n or input[dx][dy] == 2 or vis[dx][dy] == 1:
continue
vis[dx][dy] = 1
cur_cost = node.cost + cost_dict[input[dx][dy]]
q.put(Node(dx, dy, cur_cost))
return -1
input = [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
print(Solution().minSailCost(input))