https://blog.csdn.net/qq_42364307/article/details/119257678
Plan to put LeetCode All the above questions are realized once , Two questions a day
LeetCode Catalog
1. Sum of two numbers
2. Addition of two numbers
11. Container for the most water
15. Sum of three numbers
33. Search rotation sort array
34. Find the first and last positions of the elements in the sort array
35. Search insert location
53. Maximum subarray and
64. Minimum path sum
70. climb stairs
74. Search for a two-dimensional matrix
82. Delete duplicate elements from the sort list II
88. Merge two ordered arrays
153. Look for the minimum value in the rotation sort array
162. Looking for peaks
167. Sum of two numbers II - Input an ordered array
189. Rotation array
217. There are duplicate elements
278. First wrong version
283. Move zero
344. Reverse string
557. Invert the words in the string III
704. Two points search
844. Compare strings with backspace
977. The square of an ordered array
986. Intersection of interval list
The finger of the sword Offer 05. Replace blank space
The finger of the sword Offer 06. Print linked list from end to end
The finger of the sword Offer 09. Queues are implemented with two stacks
The finger of the sword Offer 24. Reverse a linked list
The finger of the sword Offer 30. contain min Function of the stack
1. Sum of two numbers
Given an array of integers nums And an integer target value target, Please find the sum in the array as the target value target The two integers of , And return their array subscripts .
You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .
You can return the answers in any order
Example
Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .
Input ：nums = [3,2,4], target = 6
Output ：[1,2]
Input ：nums = [3,3], target = 6
Output ：[0,1]Ideas ： Use dictionary structure skillfully
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dist={}
for d,ind in enumerate(nums):
dist[ind] = d
for i, j in enumerate(nums):
f = dist.get(target - j)
if f is not None and f != i:
return [i, f]2. Addition of two numbers
Here are two for you Non empty The linked list of , Represents two nonnegative integers . Each of them is based on The reverse Stored in , And each node can only store a Numbers .
Please add up the two numbers , And returns a linked list representing sum in the same form .
You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .
Ideas
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
re = ListNode(0)
r=re
carry=0
while(l1 or l2):
x= l1.val if l1 else 0
y= l2.val if l2 else 0
s=carry+x+y
carry=s//10
r.next=ListNode(s%10)
r=r.next
if(l1!=None):l1=l1.next
if(l2!=None):l2=l2.next
if(carry>0):
r.next=ListNode(1)
return re.next11. Container for the most water
Given a length of n Array of integers for height . Yes n Vertical line , The first i The two ends of the line are (i, 0) and (i, height[i]) .
Find two of them , Make them x A container of shafts can hold the most water .
Return the maximum amount of water that the container can store .
explain ： You can't tilt the container .
Example 1：
Input ：[1,8,6,2,5,4,8,3,7]
Output ：49
explain ： The vertical line in the figure represents the input array [1,8,6,2,5,4,8,3,7]. In this case , The container can hold water （ In blue ） The maximum value of is 49.
Example 2：
Input ：height = [1,1]
Output ：1
1
2
3
4
5
6
7
Ideas
Use double pointer Be careful ！ We just move the side with the smaller height each time , Because moving the smaller side may increase , But moving the larger side will definitely reduce
Code
class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height) - 1
res = 0
while(i < j):
if(height[i] < height[j]):
res = max(res,height[i]*(j-i))
i += 1
else:
res = max(res,height[j]*(j-i))
j -= 1
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
15. Sum of three numbers
Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .
Be careful ： Answer cannot contain duplicate triples .
Example 1：
Input ：nums = [-1,0,1,2,-1,-4]
Output ：[[-1,-1,2],[-1,0,1]]
Example 2：
Input ：nums = []
Output ：[]
Example 3：
Input ：nums = [0]
Output ：[]
1
2
3
4
5
6
7
8
9
Ideas
You can use two pointers , Prioritize （ Time complexity nlogn）, Then make L = i+1 ,R = n - 1, We traverse i, If the value is big, we will R–, When you're young, you're young L++
Code
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n=len(nums)
res=[]
if(not nums or n<3):
return []
nums.sort()
res=[]
for i in range(n):
if(nums[i]>0):
return res
if(i>0 and nums[i]==nums[i-1]):
continue
L=i+1
R=n-1
while(L<R):
if(nums[i]+nums[L]+nums[R]==0):
res.append([nums[i],nums[L],nums[R]])
while(L<R and nums[L]==nums[L+1]):
L=L+1
while(L<R and nums[R]==nums[R-1]):
R=R-1
L=L+1
R=R-1
elif(nums[i]+nums[L]+nums[R]>0):
R=R-1
else:
L=L+1
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
33. Search rotation sort array
An array of integers nums In ascending order , The values in the array Different from each other .
Before passing it to a function ,nums In some unknown subscript k（0 <= k < nums.length） On the rotate , Make array [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（ Subscript from 0 Start Count ）. for example , [0,1,2,4,5,6,7] In subscript 3 It may turn into [4,5,6,7,0,1,2] .
Here you are. After rotation Array of nums And an integer target , If nums There is a target value in target , Returns its subscript , Otherwise return to -1 .
Example 1：
Input ：nums = [4,5,6,7,0,1,2], target = 0
Output ：4
Example 2：
Input ：nums = [4,5,6,7,0,1,2], target = 3
Output ：-1
Example 3：
Input ：nums = [1], target = 0
Output ：-1
1
2
3
4
5
6
7
8
9
Ideas
Binary search question , First use binary search to find k, Then find the target value
Code
class Solution:
def search(self, nums: List[int], target: int) -> int:
if(len(nums) == 0):
return -1
n = len(nums)
r = n-1
l = 0
# find k
while(l<r):
m = int(l + (r -l)/2)
if(nums[m] < nums[r]):
r = m
else:
l = m+1
k = l
l = 0
r = k-1
while(l<r):
m = int(l + (r -l)/2)
if(nums[m] >= target):
r = m
else:
l = m+1
if(nums[l]==target):
return l
l = k
r = n -1
while(l<r):
m = int(l + (r -l)/2)
if(nums[m] >= target):
r = m
else:
l = m+1
if(nums[l]==target):
return l
else:
return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
34. Find the first and last positions of the elements in the sort array
Given an array of integers in ascending order nums, And a target value target. Find the start and end position of the given target value in the array .
If the target value does not exist in the array target, return [-1, -1].
Advanced ：
You can design and implement time complexity of O(log n) Does the algorithm solve this problem ？
Example 1：
Input ：nums = [5,7,7,8,8,10], target = 8
Output ：[3,4]
Example 2：
Input ：nums = [5,7,7,8,8,10], target = 6
Output ：[-1,-1]
Example 3：
Input ：nums = [], target = 0
Output ：[-1,-1]
1
2
3
4
5
6
7
8
9
Ideas
Binary search , Find the starting position first , Looking for the end .
Code
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = [-1,-1]
if(len(nums) == 0):
return res
n = len(nums)
l = 0
r = n-1
while(l < r):
m = int(l + (r - l)/2)
if(nums[m] >= target):
r = m
else:
l = m+1
if(nums[l] != target):
return res
res[0] = l
r = n
while(l < r):
m = int(l + (r - l)/2)
if(nums[m] <= target):
l = m+1
else:
r = m
res[1] = l-1
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
35. Search insert location
Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .
Please use a time complexity of O(log n) The algorithm of .
Example 1:
Input : nums = [1,3,5,6], target = 5
Output : 2
Example 2:
Input : nums = [1,3,5,6], target = 2
Output : 1
Example 3:
Input : nums = [1,3,5,6], target = 7
Output : 4
Example 4:
Input : nums = [1,3,5,6], target = 0
Output : 0
Example 5:
Input : nums = [1], target = 0
Output : 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Ideas
Code
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while(left <= right):
mid = int(left + (right - left )/ 2)
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
1
2
3
4
5
6
7
8
9
10
11
53. Maximum subarray and
Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .
Subarray Is a continuous part of the array .
Example 1：
Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .
Example 2：
Input ：nums = [1]
Output ：1
Example 3：
Input ：nums = [5,4,-1,7,8]
Output ：23
1
2
3
4
5
6
7
8
9
10
Ideas
Dynamic programming can be used , The following code ,f_n Before presentation n The maximum sum of the two
Code
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = -10000
f_n = -1
for i in range(len(nums)):
f_n = max(nums[i],f_n + nums[i])
res = max(f_n,res)
return res
1
2
3
4
5
6
7
8
64. Minimum path sum
Given a... That contains a nonnegative integer m x n grid grid , Please find a path from the top left corner to the bottom right corner , Make the sum of the numbers on the path the smallest .
explain ： You can only move down or right one step at a time .
Ideas
Code
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
if(m<=0 or n<=0):
return 0
dp = []
for i in range(m):
dp.append([])
for j in range(n):
dp[i].append(0)
dp[0][0] = grid[0][0]
for i in range(1,m):
dp[i][0] = grid[i][0] + dp[i-1][0]
for i in range(1,n):
dp[0][i] = grid[0][i] + dp[0][i-1]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
70. climb stairs
Suppose you're climbing the stairs . need n You can reach the top of the building .
Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？
Be careful ： Given n Is a positive integer .
Example 1：
Input ： 2
Output ： 2
explain ： There are two ways to climb to the top .
1. 1 rank + 1 rank
2. 2 rank
Example 2：
Input ： 3
Output ： 3
explain ： There are three ways to climb to the top .
1. 1 rank + 1 rank + 1 rank
2. 1 rank + 2 rank
3. 2 rank + 1 rank
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Ideas
Code
class Solution:
def climbStairs(self, n: int) -> int:
A = []
if(n<=2):
return n
A.append(0)
A.append(1)
A.append(2)
for i in range(3,n+1):
A.append(A[i-1] + A[i-2])
return int(A[i])
1
2
3
4
5
6
7
8
9
10
11
74. Search for a two-dimensional matrix
Write an efficient algorithm to judge m x n Matrix , Is there a target value . The matrix has the following characteristics ：
The integers in each row are arranged in ascending order from left to right .
The first integer in each row is greater than the last integer in the previous row .
Ideas
Sort two dimensions into one , Continue to use binary search
Code
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
n = len(matrix)
m = len(matrix[0])
l = 0
r = n*m-1
while(l<r):
mid = int(l + (r - l)/2)
mid1 = mid/m
mid2 = mid%m
if(matrix[mid1][mid2] >= target):
r = mid
else:
l = mid + 1
ma1 = l/m
ma2 = l%m
if(matrix[ma1][ma2] == target):
return True
else:
return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
82. Delete duplicate elements from the sort list II
Given the header of a sorted linked list head , Delete all nodes with duplicate numbers in the original linked list , Leave only different numbers . return Sorted linked list .
Ideas
An easy question , It is mainly about how to delete the first value , We can build a new next Is the header of the list head
Code
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if(not head):
return head
tem = ListNode(0,head)
cur = tem
while(cur.next and cur.next.next):
if(cur.next.val == cur.next.next.val):
x = cur.next.val
while(cur.next and cur.next.val == x):
cur.next = cur.next.next
else:
cur = cur.next
return tem.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
88. Merge two ordered arrays
Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .
Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array .
Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are 0 , It should be ignored .nums2 The length of is n .
Example 1：
Input ：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output ：[1,2,2,3,5,6]
explain ： Need merger [1,2,3] and [2,5,6] .
The combined result is [1,2,2,3,5,6] , In which, bold italics indicates nums1 The elements in .
Example 2：
Input ：nums1 = [1], m = 1, nums2 = [], n = 0
Output ：[1]
explain ： Need merger [1] and [] .
The combined result is [1] .
Example 3：
Input ：nums1 = [0], m = 0, nums2 = [1], n = 1
Output ：[1]
explain ： The array to be merged is [] and [1] .
The combined result is [1] .
Be careful , because m = 0 , therefore nums1 No elements in .nums1 The only remaining 0 Just to ensure that the merged results can be successfully stored in nums1 in .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Ideas
We use it skillfully nums1 Structure , Put in the order from big to small
Code
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1, p2 = m - 1, n - 1
tail = len(nums1) - 1
while p2 >= 0:
if p1 < 0 or nums1[p1] <= nums2[p2]:
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1
else:
nums1[tail] = nums1[p1]
p1 -= 1
tail -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
153. Look for the minimum value in the rotation sort array
We know a length of n Array of , In ascending order in advance , Through 1 To n Time rotate after , Get the input array . for example , Original array nums = [0,1,2,4,5,6,7] After the change may get ：
If you rotate 4 Time , You can get [4,5,6,7,0,1,2]
If you rotate 7 Time , You can get [0,1,2,4,5,6,7]
Be careful , Array [a[0], a[1], a[2], …, a[n-1]] Rotate once The result is an array [a[n-1], a[0], a[1], a[2], …, a[n-2]] .
Give you an element value Different from each other Array of nums , It turns out to be an ascending array , According to the above situation, we have made many rotations . Please find and return the The smallest element .
You have to design a time complexity of O(log n) The algorithm to solve this problem .
Example 1：
Input ：nums = [3,4,5,1,2]
Output ：1
explain ： The original array is [1,2,3,4,5] , rotate 3 Get the input array for the first time .
Example 2：
Input ：nums = [4,5,6,7,0,1,2]
Output ：0
explain ： The original array is [0,1,2,4,5,6,7] , rotate 4 Get the input array for the first time .
Example 3：
Input ：nums = [11,13,15,17]
Output ：11
explain ： The original array is [11,13,15,17] , rotate 4 Get the input array for the first time .
1
2
3
4
5
6
7
8
9
10
11
12
Ideas
Just find the number of rotations
Code
class Solution:
def findMin(self, nums: List[int]) -> int:
if(len(nums) == 0):
return -1
n = len(nums)
r = n-1
l = 0
# find k
while(l<r):
m = int(l + (r -l)/2)
if(nums[m] < nums[r]):
r = m
else:
l = m+1
return nums[l]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
162. Looking for peaks
The peak element refers to the element whose value is strictly greater than the left and right adjacent values .
Give you an array of integers nums, Find the peak element and return its index . The array may contain multiple peaks , under these circumstances , return Any peak Just where you are .
You can assume nums[-1] = nums[n] = -∞ .
You must achieve a time complexity of O(log n) Algorithm to solve this problem .
Example 1：
Input ：nums = [1,2,3,1]
Output ：2
explain ：3 Is the peak element , Your function should return its index 2.
Example 2：
Input ：nums = [1,2,1,3,5,6,4]
Output ：1 or 5
explain ： Your function can return the index 1, Its peak element is 2;
Or return index 5, Its peak element is 6.
1
2
3
4
5
6
7
8
9
Ideas
Dichotomy , Just judge nums[m] > nums[m+1], Because a large value must have a solution
Code
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
n = len(nums)
l = 0
r = n - 1
while(l < r):
mid = int(l + (r - l)/2)
if(nums[mid] > nums[mid + 1]):
r = mid
else:
l = mid + 1
return l
1
2
3
4
5
6
7
8
9
10
11
12
167. Sum of two numbers II - Input an ordered array
Given a has been according to Non decreasing order Array of integers for numbers , Please find out two numbers from the array, and the sum of them is equal to the target number target .
Functions should be length based 2 Returns the subscript values of the two numbers in the form of an array of integers .numbers The subscript from 1 Start counting , So the answer array should satisfy 1 <= answer[0] < answer[1] <= numbers.length .
You can assume that each input Only corresponding to the only answer , And you Can not be Reuse the same elements .
Example 1：
Input ：numbers = [2,7,11,15], target = 9
Output ：[1,2]
explain ：2 And 7 The sum is equal to the number of targets 9 . therefore index1 = 1, index2 = 2 .
Example 2：
Input ：numbers = [2,3,4], target = 6
Output ：[1,3]
Example 3：
Input ：numbers = [-1,0], target = -1
Output ：[1,2]
1
2
3
4
5
6
7
8
9
10
11
12
Ideas
Code
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l = 0
r = len(numbers)-1
while(l<r):
if(numbers[l]+numbers[r]>target):
r= r - 1
elif(numbers[l]+numbers[r]<target):
l= l + 1
else:
return [l+1,r+1]
return [l+1,r+1]
1
2
3
4
5
6
7
8
9
10
11
12
189. Rotation array
Give you an array , Rotate the elements in the array to the right k A place , among k It is a non negative number .
Example 1:
Input : nums = [1,2,3,4,5,6,7], k = 3
Output : [5,6,7,1,2,3,4]
explain :
Rotate right 1 Step : [7,1,2,3,4,5,6]
Rotate right 2 Step : [6,7,1,2,3,4,5]
Rotate right 3 Step : [5,6,7,1,2,3,4]
Example 2:
Input ：nums = [-1,-100,3,99], k = 2
Output ：[3,99,-1,-100]
explain :
Rotate right 1 Step : [99,-1,-100,3]
Rotate right 2 Step : [3,99,-1,-100]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Ideas
Code
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums[: ] = nums[-k % len(nums) :] + nums[: -k % len(nums)]
1
2
3
4
5
6
217. There are duplicate elements
Give you an array of integers nums . If any value appears in the array At least twice , return true ; If each element in the array is different from each other , return false .
Example 1：
Input ：nums = [1,2,3,1]
Output ：true
Example 2：
Input ：nums = [1,2,3,4]
Output ：false
Example 3：
Input ：nums = [1,1,1,3,3,4,3,2,4,2]
Output ：true
1
2
3
4
5
6
7
8
9
10
Ideas
Use the uniqueness of the set to do .（ The complexity of violent exhaustion algorithm is too large O ( n 2 ) O(n^2)O(n
2
)）
Code
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
numsset = set(nums)
if(len(nums) == len(numsset)):
return False
else:
return True
1
2
3
4
5
6
7
278. First wrong version
You are the product manager , Currently leading a team to develop new products . Unfortunately , The latest version of your product doesn't pass the quality test . Because each version is based on the previous version , So all versions after the wrong version are wrong .
Suppose you have n A version [1, 2, …, n], You want to find out the first wrong version that caused all subsequent versions to go wrong .
You can call bool isBadVersion(version) Interface to determine version number version If there is an error in unit test . Implement a function to find the first wrong version . You should try to minimize calls to API The number of times .
Example 1：
Input ：n = 5, bad = 4
Output ：4
explain ：
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
therefore ,4 It's the first wrong version .
Example 2：
Input ：n = 1, bad = 1
Output ：1
1
2
3
4
5
6
7
8
9
10
11
12
Ideas
Code
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
left = 1
right = n
while(left<right):
mid = int(left + (right - left)/2)
if(isBadVersion(mid)):
right = mid
else:
left = mid + 1
return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
283. Move zero
Given an array nums, Write a function that will 0 Move to end of array , While maintaining the relative order of non-zero elements .
Example :
Input : [0,1,0,3,12]
Output : [1,3,12,0,0]
1
2
3
Ideas
Code
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort(key=bool, reverse=True)
1
2
3
4
5
6
344. Reverse string
Write a function , Its function is to invert the input string . Input string as character array s Given in the form of .
Do not allocate extra space to another array , You have to modify the input array in place 、 Use O(1) To solve this problem .
Example 1：
Input ：s = ["h","e","l","l","o"]
Output ：["o","l","l","e","h"]
Example 2：
Input ：s = ["H","a","n","n","a","h"]
Output ：["h","a","n","n","a","H"]
1
2
3
4
5
6
7
Ideas
Code
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
r = len(s)
l = r
for i in range(int(r/2)):
l = l - 1
tmp = s[i]
s[i] = s[l]
s[l] = tmp
return s
1
2
3
4
5
6
7
8
9
10
11
12
13
In one line
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s.reverse()
1
2
3
4
5
6
557. Invert the words in the string III
Given a string , You need to reverse the character order of each word in the string , Keep the initial order of spaces and words .
Example ：
Input ："Let's take LeetCode contest"
Output ："s'teL ekat edoCteeL tsetnoc"
1
2
3
Ideas
Code
One line of code
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join([w[::-1] for w in s.split()])
1
2
3
704. Two points search
Given a n The elements are ordered （ Ascending ） integer array nums And a target value target , Write a function search nums Medium target, If the target value has a return subscript , Otherwise return to -1.
Example 1:
Input : nums = [-1,0,3,5,9,12], target = 9
Output : 4
explain : 9 Appear in the nums And the subscript is 4
Example 2:
Input : nums = [-1,0,3,5,9,12], target = 2
Output : -1
explain : 2 non-existent nums So back to -1
1
2
3
4
5
6
7
8
9
Ideas
Code
class Solution:
def search(self, nums: List[int], target: int) -> int:
right = len(nums)-1
left = 0
while(left <= right):
mid = int(left + (right - left)/2)
if(target < nums[mid]):
right = mid - 1
elif(target > nums[mid]):
left = mid + 1
else:
return mid
return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
844. Compare strings with backspace
Given s and t Two strings , When they are entered into a blank text editor , If the two are equal , return true .# For backspace characters .
Be careful ： If you enter backspace characters for empty text , Text continues to be empty .
Example 1：
Input ：s = "ab#c", t = "ad#c"
Output ：true
explain ：s and t Will become "ac".
Example 2：
Input ：s = "ab##", t = "c#d#"
Output ：true
explain ：s and t Will become "".
Example 3：
Input ：s = "a#c", t = "b"
Output ：false
explain ：s Will become "c", but t Still "b".
1
2
3
4
5
6
7
8
9
10
11
12
Ideas
If there is violence, it will not work , To occupy new memory , And compare . We can use double pointers , Read from back to front , Compare each character . There is no sign to return flase
Code
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i = len(s) - 1
j = len(t) - 1
skipi = 0
skipj = 0
while(i >= 0 or j >= 0):
while(i >= 0):
if(s[i] == '#'):
skipi += 1
i -= 1
elif(skipi > 0):
skipi -= 1
i -= 1
else:
break
while(j >= 0):
if(t[j] == '#'):
skipj += 1
j -= 1
elif(skipj > 0):
skipj -= 1
j -= 1
else:
break
if(i >= 0 and j >= 0):
if(s[i] != t[j]):
return False
elif(i >= 0 or j >= 0):
return False
i -= 1
j -= 1
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
977. The square of an ordered array
Here's a button Non decreasing order Sorted array of integers nums, Return the square of each number A new array of , Requirements are also sorted in non decreasing order .
Example 1：
Input ：nums = [-4,-1,0,3,10]
Output ：[0,1,9,16,100]
explain ： After square , The array becomes [16,1,0,9,100]
After ordering , The array becomes [0,1,9,16,100]
Example 2：
Input ：nums = [-7,-3,2,3,11]
Output ：[4,9,9,49,121]
Tips ：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums Pressed Non decreasing order Sort
Advanced ：
Please design with a time complexity of O(n) The algorithm solves this problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Ideas
Code
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
B = sorted([num*num for num in nums])
return B
1
2
3
4
986. Intersection of interval list
Given two by some Closed interval A list of components ,firstList and secondList , among firstList[i] = [starti, endi] and secondList[j] = [startj, endj] . Each interval list is paired Disjoint Of , also It's sorted .
Back here The intersection of two interval lists .
Formally , Closed interval [a, b]（ among a <= b） For real numbers x Set , and a <= x <= b .
Of two closed intervals intersection Is a set of real numbers , Or it's an empty set , Either it's a closed interval . for example ,[1, 3] and [2, 4] The intersection of is [2, 3] .
Example 1：
Input ：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output ：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2：
Input ：firstList = [[1,3],[5,9]], secondList = []
Output ：[]
Example 3：
Input ：firstList = [], secondList = [[4,8],[10,12]]
Output ：[]
Example 4：
Input ：firstList = [[1,7]], secondList = [[3,10]]
Output ：[[3,7]]
1
2
3
4
5
6
7
8
9
10
11
12
Ideas
Use double pointer , One points to one of the arrays , Compare each internal array .
Code
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
res = []
i = 0
j = 0
while(i < len(firstList) and j<len(secondList)):
start = max(firstList[i][0],secondList[j][0])
end = min(firstList[i][1],secondList[j][1])
if(start <= end):
res.append([start,end])
if(firstList[i][1]<secondList[j][1]):
i += 1
else:
j += 1
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
The finger of the sword Offer 05. Replace blank space
Please implement a function , Put the string s Replace each space in with "%20".
Example 1：
Input ：s = "We are happy."
Output ："We%20are%20happy."
1
2
3
Ideas
Code
class Solution:
def replaceSpace(self, s: str) -> str:
return s.replace(" ","%20")
1
2
3
The finger of the sword Offer 06. Print linked list from end to end
Enter the head node of a linked list , Return the value of each node from the end to the end （ Return with array ）.
Example 1：
Input ：head = [1,3,2]
Output ：[2,3,1]
1
2
3
Ideas
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
A = []
while(head):
A.append(head.val)
head = head.next
return A[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
The finger of the sword Offer 09. Queues are implemented with two stacks
Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions appendTail and deleteHead , The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .( If there are no elements in the queue ,deleteHead Operation return -1 )
Ideas
Code
class CQueue:
def __init__(self):
self.s1 = []
self.s2 = []
def appendTail(self, value: int) -> None:
self.s1.append(value)
def deleteHead(self) -> int:
if(len(self.s1)==0 and len(self.s2) == 0):
return -1
if(len(self.s1)!=0 and len(self.s2) == 0):
while(len(self.s1)!=0):
self.s2.append(self.s1.pop())
return self.s2.pop()
if(len(self.s2) != 0):
return self.s2.pop()
return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
The finger of the sword Offer 24. Reverse a linked list
Define a function , Enter the head node of a linked list , Invert the linked list and output the head node of the inverted linked list .
Example :
Input : 1->2->3->4->5->NULL
Output : 5->4->3->2->1->NULL
1
2
3
Ideas
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
preNode = None
currNode = head
while(currNode):
nextNode = currNode.next
currNode.next = preNode
preNode = currNode
currNode = nextNode
return preNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
The finger of the sword Offer 30. contain min Function of the stack
Defines the data structure of the stack , Please implement a in this type that can get the minimum elements of the stack min The function is in the stack , call min、push And pop The time complexity of O(1).
Ideas
Code
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.MS = []
self.Min = inf
def push(self, x: int) -> None:
self.MS.append(self.Min)
if(x<self.Min):
self.Min = x
self.MS.append(x)
def pop(self) -> None:
self.MS.pop(-1)
self.Min = self.MS.pop(-1)
def top(self) -> int:
return self.MS[-1]
def min(self) -> int:
return self.Min
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()
