https://blog.csdn.net/qq_42364307/article/details/119257678
打算把LeetCode上面的題都實現一遍，每日兩題
LeetCode目錄
1. 兩數之和
2. 兩數相加
11. 盛最多水的容器
15.三數之和
33.搜索旋轉排序數組
34. 在排序數組中查找元素的第一個和最後一個位置
35.搜索插入位置
53.最大子數組和
64. 最小路徑和
70.爬樓梯
74.搜索二維矩陣
82. 刪除排序鏈表中的重復元素 II
88. 合並兩個有序數組
153. 尋找旋轉排序數組中的最小值
162. 尋找峰值
167. 兩數之和 II - 輸入有序數組
189.輪轉數組
217.存在重復元素
278.第一個錯誤的版本
283. 移動零
344. 反轉字符串
557. 反轉字符串中的單詞 III
704. 二分查找
844. 比較含退格的字符串
977. 有序數組的平方
986. 區間列表的交集
劍指 Offer 05. 替換空格
劍指 Offer 06. 從尾到頭打印鏈表
劍指 Offer 09.用兩個棧實現隊列
劍指 Offer 24. 反轉鏈表
劍指 Offer 30.包含min函數的棧
1. 兩數之和
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出和為目標值 target 的那兩個整數，並返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案裡不能重復出現。
你可以按任意順序返回答案
示例
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
輸入：nums = [3,3], target = 6
輸出：[0,1]思路：巧用字典結構
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. 兩數相加
給你兩個 非空 的鏈表，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的，並且每個節點只能存儲 一位 數字。
請你將兩個數相加，並以相同形式返回一個表示和的鏈表。
你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。
思路
# 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. 盛最多水的容器
給定一個長度為 n 的整數數組 height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
返回容器可以儲存的最大水量。
說明：你不能傾斜容器。
示例 1：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
示例 2：
輸入：height = [1,1]
輸出：1
1
2
3
4
5
6
7
思路
使用雙指針 注意！我們每次只要移動高度小的一邊，因為移動小的那一邊可能會增大，但是移動大的一邊一定會減小
代碼
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.三數之和
給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復的三元組。
注意：答案中不可以包含重復的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
示例 2：
輸入：nums = []
輸出：[]
示例 3：
輸入：nums = [0]
輸出：[]
1
2
3
4
5
6
7
8
9
思路
可以使用雙指針，先排序（時間復雜度nlogn），然後令L = i+1 ，R = n - 1，我們遍歷i，如果值大了我們就R–，小了就L++
代碼
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.搜索旋轉排序數組
整數數組 nums 按升序排列，數組中的值 互不相同 。
在傳遞給函數之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉，使數組變為 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下標 從 0 開始 計數）。例如， [0,1,2,4,5,6,7] 在下標 3 處經旋轉後可能變為 [4,5,6,7,0,1,2] 。
給你 旋轉後 的數組 nums 和一個整數 target ，如果 nums 中存在這個目標值 target ，則返回它的下標，否則返回 -1 。
示例 1：
輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4
示例 2：
輸入：nums = [4,5,6,7,0,1,2], target = 3
輸出：-1
示例 3：
輸入：nums = [1], target = 0
輸出：-1
1
2
3
4
5
6
7
8
9
思路
二分查找題，先用二分查找找到k，然後找到目標值
代碼
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. 在排序數組中查找元素的第一個和最後一個位置
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
如果數組中不存在目標值 target，返回 [-1, -1]。
進階：
你可以設計並實現時間復雜度為 O(log n) 的算法解決此問題嗎？
示例 1：
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
示例 2：
輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]
示例 3：
輸入：nums = [], target = 0
輸出：[-1,-1]
1
2
3
4
5
6
7
8
9
思路
兩分查找，先找開始的位置，在找結束的位置。
代碼
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.搜索插入位置
給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為 O(log n) 的算法。
示例 1:
輸入: nums = [1,3,5,6], target = 5
輸出: 2
示例 2:
輸入: nums = [1,3,5,6], target = 2
輸出: 1
示例 3:
輸入: nums = [1,3,5,6], target = 7
輸出: 4
示例 4:
輸入: nums = [1,3,5,6], target = 0
輸出: 0
示例 5:
輸入: nums = [1], target = 0
輸出: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
思路
代碼
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.最大子數組和
給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
子數組 是數組中的一個連續部分。
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。
示例 2：
輸入：nums = [1]
輸出：1
示例 3：
輸入：nums = [5,4,-1,7,8]
輸出：23
1
2
3
4
5
6
7
8
9
10
思路
可以使用動態規劃的方法，如下代碼，f_n表示前n個之和最大值
代碼
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. 最小路徑和
給定一個包含非負整數的 m x n 網格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。
說明：每次只能向下或者向右移動一步。
思路
代碼
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.爬樓梯
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
1
2
3
4
5
6
7
8
9
10
11
12
13
14
思路
代碼
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.搜索二維矩陣
編寫一個高效的算法來判斷 m x n 矩陣中，是否存在一個目標值。該矩陣具有如下特性：
每行中的整數從左到右按升序排列。
每行的第一個整數大於前一行的最後一個整數。
思路
將二維排序成一維來做，繼續用二分查找
代碼
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. 刪除排序鏈表中的重復元素 II
給定一個已排序的鏈表的頭 head ， 刪除原始鏈表中所有重復數字的節點，只留下不同的數字 。返回 已排序的鏈表 。
思路
很容易的題，主要是第一個值的話怎麼刪，我們可以新建一個next 為列表的頭head
代碼
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. 合並兩個有序數組
給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2 中的元素數目。
請你 合並 nums2 到 nums1 中，使合並後的數組同樣按 非遞減順序 排列。
注意：最終，合並後數組不應由函數返回，而是存儲在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合並的元素，後 n 個元素為 0 ，應忽略。nums2 的長度為 n 。
示例 1：
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合並 [1,2,3] 和 [2,5,6] 。
合並結果是 [1,2,2,3,5,6] ，其中斜體加粗標注的為 nums1 中的元素。
示例 2：
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合並 [1] 和 [] 。
合並結果是 [1] 。
示例 3：
輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合並的數組是 [] 和 [1] 。
合並結果是 [1] 。
注意，因為 m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合並結果可以順利存放到 nums1 中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
思路
我們巧用nums1的結構，把從大到小排序放進去
代碼
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. 尋找旋轉排序數組中的最小值
已知一個長度為 n 的數組，預先按照升序排列，經由 1 到 n 次 旋轉 後，得到輸入數組。例如，原數組 nums = [0,1,2,4,5,6,7] 在變化後可能得到：
若旋轉 4 次，則可以得到 [4,5,6,7,0,1,2]
若旋轉 7 次，則可以得到 [0,1,2,4,5,6,7]
注意，數組 [a[0], a[1], a[2], …, a[n-1]] 旋轉一次 的結果為數組 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
給你一個元素值 互不相同 的數組 nums ，它原來是一個升序排列的數組，並按上述情形進行了多次旋轉。請你找出並返回數組中的 最小元素 。
你必須設計一個時間復雜度為 O(log n) 的算法解決此問題。
示例 1：
輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數組為 [1,2,3,4,5] ，旋轉 3 次得到輸入數組。
示例 2：
輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原數組為 [0,1,2,4,5,6,7] ，旋轉 4 次得到輸入數組。
示例 3：
輸入：nums = [11,13,15,17]
輸出：11
解釋：原數組為 [11,13,15,17] ，旋轉 4 次得到輸入數組。
1
2
3
4
5
6
7
8
9
10
11
12
思路
查找旋轉次數就好了
代碼
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. 尋找峰值
峰值元素是指其值嚴格大於左右相鄰值的元素。
給你一個整數數組 nums，找到峰值元素並返回其索引。數組可能包含多個峰值，在這種情況下，返回 任何一個峰值 所在位置即可。
你可以假設 nums[-1] = nums[n] = -∞ 。
你必須實現時間復雜度為 O(log n) 的算法來解決此問題。
示例 1：
輸入：nums = [1,2,3,1]
輸出：2
解釋：3 是峰值元素，你的函數應該返回其索引 2。
示例 2：
輸入：nums = [1,2,1,3,5,6,4]
輸出：1 或 5
解釋：你的函數可以返回索引 1，其峰值元素為 2；
或者返回索引 5， 其峰值元素為 6。
1
2
3
4
5
6
7
8
9
思路
二分法，只需要判斷nums[m] > nums[m+1]，因為大的值一定有解
代碼
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. 兩數之和 II - 輸入有序數組
給定一個已按照 非遞減順序排列 的整數數組 numbers ，請你從數組中找出兩個數滿足相加之和等於目標數 target 。
函數應該以長度為 2 的整數數組的形式返回這兩個數的下標值。numbers 的下標 從 1 開始計數 ，所以答案數組應當滿足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假設每個輸入 只對應唯一的答案 ，而且你 不可以 重復使用相同的元素。
示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等於目標數 9 。因此 index1 = 1, index2 = 2 。
示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
1
2
3
4
5
6
7
8
9
10
11
12
思路
代碼
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.輪轉數組
給你一個數組，將數組中的元素向右輪轉 k 個位置，其中 k 是非負數。
示例 1:
輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋:
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
思路
代碼
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.存在重復元素
給你一個整數數組 nums 。如果任一值在數組中出現 至少兩次 ，返回 true ；如果數組中每個元素互不相同，返回 false 。
示例 1：
輸入：nums = [1,2,3,1]
輸出：true
示例 2：
輸入：nums = [1,2,3,4]
輸出：false
示例 3：
輸入：nums = [1,1,1,3,3,4,3,2,4,2]
輸出：true
1
2
3
4
5
6
7
8
9
10
思路
利用集合的唯一性來做。（暴力窮舉算法復雜度太大了O ( n 2 ) O(n^2)O(n
2
)）
代碼
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.第一個錯誤的版本
你是產品經理，目前正在帶領一個團隊開發新的產品。不幸的是，你的產品的最新版本沒有通過質量檢測。由於每個版本都是基於之前的版本開發的，所以錯誤的版本之後的所有版本都是錯的。
假設你有 n 個版本 [1, 2, …, n]，你想找出導致之後所有版本出錯的第一個錯誤的版本。
你可以通過調用 bool isBadVersion(version) 接口來判斷版本號 version 是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。
示例 1：
輸入：n = 5, bad = 4
輸出：4
解釋：
調用 isBadVersion(3) -> false
調用 isBadVersion(5) -> true
調用 isBadVersion(4) -> true
所以，4 是第一個錯誤的版本。
示例 2：
輸入：n = 1, bad = 1
輸出：1
1
2
3
4
5
6
7
8
9
10
11
12
思路
代碼
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. 移動零
給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
1
2
3
思路
代碼
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. 反轉字符串
編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 s 的形式給出。
不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。
示例 1：
輸入：s = ["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
示例 2：
輸入：s = ["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
1
2
3
4
5
6
7
思路
代碼
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
一行實現
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. 反轉字符串中的單詞 III
給定一個字符串，你需要反轉字符串中每個單詞的字符順序，同時仍保留空格和單詞的初始順序。
示例：
輸入："Let's take LeetCode contest"
輸出："s'teL ekat edoCteeL tsetnoc"
1
2
3
思路
代碼
一行代碼
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join([w[::-1] for w in s.split()])
1
2
3
704. 二分查找
給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中並且下標為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1
1
2
3
4
5
6
7
8
9
思路
代碼
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. 比較含退格的字符串
給定 s 和 t 兩個字符串，當它們分別被輸入到空白的文本編輯器後，如果兩者相等，返回 true 。# 代表退格字符。
注意：如果對空文本輸入退格字符，文本繼續為空。
示例 1：
輸入：s = "ab#c", t = "ad#c"
輸出：true
解釋：s 和 t 都會變成 "ac"。
示例 2：
輸入：s = "ab##", t = "c#d#"
輸出：true
解釋：s 和 t 都會變成 ""。
示例 3：
輸入：s = "a#c", t = "b"
輸出：false
解釋：s 會變成 "c"，但 t 仍然是 "b"。
1
2
3
4
5
6
7
8
9
10
11
12
思路
如果暴力的話肯定不行的，要占用新的內存，且要比較。我們可以使用雙指針，從後往前讀，比較每一個字符。有不符號返回flase
代碼
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. 有序數組的平方
給你一個按 非遞減順序 排序的整數數組 nums，返回每個數字的平方 組成的新數組，要求也按非遞減順序排序。
示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方後，數組變為 [16,1,0,9,100]
排序後，數組變為 [0,1,9,16,100]
示例 2：
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非遞減順序 排序
進階：
請你設計時間復雜度為 O(n) 的算法解決本問題
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
思路
代碼
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. 區間列表的交集
給定兩個由一些 閉區間 組成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每個區間列表都是成對 不相交 的，並且 已經排序 。
返回這 兩個區間列表的交集 。
形式上，閉區間 [a, b]（其中 a <= b）表示實數 x 的集合，而 a <= x <= b 。
兩個閉區間的 交集 是一組實數，要麼為空集，要麼為閉區間。例如，[1, 3] 和 [2, 4] 的交集為 [2, 3] 。
示例 1：
輸入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
輸出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
示例 2：
輸入：firstList = [[1,3],[5,9]], secondList = []
輸出：[]
示例 3：
輸入：firstList = [], secondList = [[4,8],[10,12]]
輸出：[]
示例 4：
輸入：firstList = [[1,7]], secondList = [[3,10]]
輸出：[[3,7]]
1
2
3
4
5
6
7
8
9
10
11
12
思路
使用雙指針，一個指向其中一個數組，對每一個內部數組進行比較。
代碼
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
劍指 Offer 05. 替換空格
請實現一個函數，把字符串 s 中的每個空格替換成"%20"。
示例 1：
輸入：s = "We are happy."
輸出："We%20are%20happy."
1
2
3
思路
代碼
class Solution:
def replaceSpace(self, s: str) -> str:
return s.replace(" ","%20")
1
2
3
劍指 Offer 06. 從尾到頭打印鏈表
輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值（用數組返回）。
示例 1：
輸入：head = [1,3,2]
輸出：[2,3,1]
1
2
3
思路
代碼
# 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
劍指 Offer 09.用兩個棧實現隊列
用兩個棧實現一個隊列。隊列的聲明如下，請實現它的兩個函數 appendTail 和 deleteHead ，分別完成在隊列尾部插入整數和在隊列頭部刪除整數的功能。(若隊列中沒有元素，deleteHead 操作返回 -1 )
思路
代碼
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
劍指 Offer 24. 反轉鏈表
定義一個函數，輸入一個鏈表的頭節點，反轉該鏈表並輸出反轉後鏈表的頭節點。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
1
2
3
思路
代碼
# 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
劍指 Offer 30.包含min函數的棧
定義棧的數據結構，請在該類型中實現一個能夠得到棧的最小元素的 min 函數在該棧中，調用 min、push 及 pop 的時間復雜度都是 O(1)。
思路
代碼
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()
