爬樓梯問題
輸入n階樓梯，每次爬1或者2個(gè)臺(tái)階，有多少種方法可以爬到樓頂？
示例1：輸入2， 輸出2
一次爬2階；
一次爬1階；
故兩種方法。
示例2：
輸入3， 輸出3
三個(gè)1；
一個(gè)1 + 一個(gè) 2；
一個(gè)2 + 一個(gè)1；
思路分析：
采用遞歸求解
python實(shí)現(xiàn):
# 遞歸
def climb_stairs(n):
if n == 1:
return 1
elif n == 2:
return 2
elif n >= 3:
return climb_stairs(n-1) + climb_stairs(n-2)
# 遞歸優(yōu)化，避免重復(fù)計(jì)算（優(yōu)化效果微?。?/span>
def climb_stairs_2(n):
d = {}
if n == 1:
return 1
elif n == 2:
return 2
elif n >= 3:
if n in d:
return d.get(n) # 避免一部分遞歸操作
cur = climb_stairs(n-1) + climb_stairs(n-2)
d[n] = cur
return cur
# 循環(huán)一次計(jì)算(自底向上依次計(jì)算)
# O(n)
def climb_stairs_3(n):
if n == 1:
return 1
elif n == 2:
return 2
elif n >= 3:
a = 1
b = 2
result = 0
for i in range(3, n+1):
result = a + b
a = b
b = result
return result
java實(shí)現(xiàn)：
// O(n)
class Solution{
public int climbStairs(int n){
if(n == 1) return 1;
else if(n == 2) return 2;
else if(n >= 3){
int result = 0;
int a = 1;
int b = 2;
for(int i=3; i<=n; i++){
result = a + b;
a = b;
b = result;
}
return result;
}
}
}
裴波那契數(shù)列
類似爬樓梯問題。
?
兩數(shù)之和 [數(shù)組]
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，在該數(shù)組中找出 和 等于目標(biāo)值 target 的那兩個(gè)整數(shù)，并返回它們的數(shù)組下標(biāo)。
假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案，且數(shù)組中同一個(gè)【位置】的元素在答案里不能重復(fù)出現(xiàn)。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]
暴力解法：
- 依次遍歷元素，計(jì)算求和，并比較。
- 時(shí)間復(fù)雜度 O ( n 2 ) {O(n^2)} O(n2)
- python實(shí)現(xiàn)
# O(n^2)
def calcSum(arr, target):
n = len(arr)
for i in range(n-1):
for j in range(i+1, n):
if arr[i] + arr[j] == target:
return [i, j]
raise ValueError("未找到結(jié)果")
- java實(shí)現(xiàn)
在這里插入代碼片
哈希優(yōu)化
- 遍歷數(shù)組，索引為 i；
- 判斷 left = target - array[i] ，left 值是否存在于hash;
- 存在，則返回索引 i 和 hash中l(wèi)eft 對(duì)應(yīng)的值；
- 不存在，則將 array[i] ：i 存入hash;
- 時(shí)間復(fù)雜度 O ( n ) {O(n)} O(n)
- python實(shí)現(xiàn)
# python
def optimize_calc_sum(alist, target):
dict_ = {}
n = len(alist)
for i in range(n):
if target - alist[i] in dict_:
return [i, dict_.get(target - alist[i])]
dict_[alist[i]] = i
raise ValueError("未找到結(jié)果")
- java實(shí)現(xiàn)
在這里插入代碼片
?
合并兩個(gè)有序數(shù)組
給兩個(gè)非遞減排列的整數(shù)數(shù)組arr1、arr2，m 和 n 分別表示arr1 、arr2的元素個(gè)數(shù)；合并arr2到arr1中，合并后元素非遞減排列。
示例1：
arr1 = [1, 2, 3, 0, 0, 0] m = 3
arr2 = [2, 5, 6] n = 3
合并結(jié)果：[1,2,2,3,5,6] 黑體數(shù)字為arr2中的元素
示例2：
arr1 = [1]
arr2 = [ ]
合并結(jié)果： [1]
python實(shí)現(xiàn)：
arr1 = [1, 3, 4, 0, 0, 0]
m = 3
arr2 = [2, 5, 6]
n = 3
def merge_array(arr1, m, arr2, n):
# 準(zhǔn)備臨時(shí)數(shù)組
temp = [] # 空間復(fù)雜度O(m+n)
i = 0
j = 0
while i < m and j < n: # O(m+n) 線性復(fù)雜度
if arr1[i] <= arr2[j]:
temp.append(arr1[i])
i += 1
else:
temp.append(arr2[j])
j += 1
if i == m:
temp.extend(arr2[j:n])
elif j == n:
temp.extend(arr1[i:m])
for i in range(m + n):
arr1[i] = temp[i]
print("arr1:", arr1)
return arr1
java實(shí)現(xiàn)：
移動(dòng)零
給定一個(gè)數(shù)組array，將內(nèi)部所有的0移動(dòng)到數(shù)組的末尾，并保持非零元素的相對(duì)順序。必須原位操作，不能拷貝額外的數(shù)組。
示例：
輸入，[0, 1, 0, 3, 12]
輸出，[1, 3, 12, 0, 0]
提示：雙指針
python實(shí)現(xiàn)：
# 暴力實(shí)現(xiàn)
arr = [0, 1, 0, 3, 12, 0, 0, 13, 0, 14, 0, 18, 0, 0, 0]
# 依次將遍歷的首個(gè)0值與后面的非0置換
def move_zero(arr):
n = len(arr)
for i in range(n):
if arr[i] != 0:
continue
k = i # 記錄當(dāng)前0的位置
j = i + 1 # 下一個(gè)元素的位置
while j < n:
if arr[j] == 0:
j += 1
continue
arr[k], arr[j] = arr[j], arr[k]
k = j
j += 1
print("result:", arr)
return arr
# 雙指針
# 雙指針同時(shí)從0開始
# 依次將后一個(gè)指針的非0值，放到前一個(gè)指針的位置，前一個(gè)指針+1，繼續(xù)下次循環(huán)
# 最后將后一個(gè)指針處到結(jié)束 均賦值0
# 時(shí)間復(fù)雜度 O(2n)
def move_zero_double_pointer(arr):
n = len(arr)
j = 0 # j指針
for i in range(n): # i指針 兩個(gè)指針同時(shí)從0開始
if arr[i] != 0:
arr[j] = arr[i]
j += 1
# 將從j開始的元素 全部賦值0
while j < n: # 時(shí)間復(fù)雜度 O(2n)
arr[j] = 0
j += 1
print("result:", arr)
return arr
java實(shí)現(xiàn)：雙指針移動(dòng)0
?
找到所有數(shù)組中消失的數(shù)字
給定一個(gè)n個(gè)整數(shù)的數(shù)組array，每個(gè)元素值在【1，n】之間，找出1-n內(nèi)沒有出現(xiàn)在array中的數(shù)字，以數(shù)組形式返回。
n為數(shù)組的長(zhǎng)度；
示例1：
輸入：[4,3,2,7,8,2,3,1]
輸出：[5,6]
示例2：
輸入：[1,1]
輸出：[2]
進(jìn)階：可以不借助額外空間且時(shí)間復(fù)雜度為O(n)，解決嗎？
python實(shí)現(xiàn)：
# 暴力實(shí)現(xiàn)
def find_missing_digit(arr):
n = len(arr) # [1, ..., n]
# arr去重
temp = [] # 空間復(fù)雜度O(n)
for i in range(1, n+1): # 時(shí)間復(fù)雜度 O(n)
if i not in arr:
temp.append(i)
print("result:", temp)
return temp
# 優(yōu)化空間復(fù)雜度O(1)
# 只能依賴數(shù)組本身的空間
# 所有元素的值 - 1 可以對(duì)應(yīng)索引，對(duì)應(yīng)索引處的值 都+n 或者2n....
# 而缺失的那些值 - 1 對(duì)應(yīng)的索引處的值肯定沒有變化，即 <= n
# 最后循環(huán)找到<=n的元素，其索引+1 就是缺失的值
def optimize_find_missing_digit(arr):
n = len(arr)
# 空間復(fù)雜度為O(1) 只能使用數(shù)組本身的空間
for i in arr:
idx = (i - 1) % n # 得到對(duì)應(yīng)的索引(拿到的i可能是已改過的) 所以需要還原索引
arr[idx] += 2 * n
temp = [] # 存儲(chǔ)最終結(jié)果的空間不算 額外空間
for i in range(n):
if arr[i] <= n:
temp.append(i + 1)
print("result:", temp)
return temp
java實(shí)現(xiàn)：
?
三數(shù)之和
給一個(gè)整數(shù)數(shù)組 nums ，判斷是否存在三元組 [ nums[i], nums[j], nums[k] ] 滿足 i != j、i != k 且 j != k ，同時(shí)還滿足 nums[i] + nums[j] + nums[k] == 0 。返回所有和為 0 且不重復(fù)的三元組，如果三個(gè)元素只是順序不同，則算重復(fù)的三元組。
示例 1：
輸入：[-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。
示例 2：
輸入：[0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。
示例 3：
輸入：[0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
python實(shí)現(xiàn)：
# 暴力解法 O(n^3) 會(huì)產(chǎn)生重復(fù)的三元組
arr = [-1,0,1,2,-1,-4]
def three_nums_sum(arr: List[int]) -> List[List[int]]:
n = len(arr)
temp = []
for i in range(n-2):
for j in range(i+1, n-1):
for k in range(j+1, n):
if arr[i] + arr[j] + arr[k] == 0:
temp.append([arr[i], arr[j], arr[k]])
# result: [[-1, 0, 1], [-1, 2, -1], [0, 1, -1]]
# 會(huì)產(chǎn)生重復(fù)的三元組
print("result:", temp)
return temp
# 排序 + 雙指針
# 時(shí)間復(fù)雜度 O(n^2)
def optimize_three_nums_sum(nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
if n < 3:
return []
nums.sort() # 排序 快排 O(nlogn)
res = []
for i in range(n): O(n^2)
if (nums[i] > 0):
return res
if (i > 0 and nums[i] == nums[i - 1]): # 防止重復(fù)解
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]])
# 去除重復(fù)
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
java實(shí)現(xiàn)：
pass
?
最大上升子序列
Redraiment是走梅花樁的高手，可以選擇任意一個(gè)起點(diǎn)，只能從低處往高處的樁子走。他希望走的步數(shù)最多，試研究他最多走的步數(shù)？
輸入描述：
第1行輸入數(shù)組的長(zhǎng)度；
第2行輸入每個(gè)梅花樁的高度
輸出描述：
輸出一個(gè)結(jié)果
示例1
輸入：
6
2 5 1 5 4 5
輸出：
3
說明：
6個(gè)點(diǎn)的高度各為 2 5 1 5 4 5
從第1格開始走,最多為3步, 2 4 5 ，下標(biāo)分別是 1 5 6
從第2格開始走,最多只有1步,5
而從第3格開始走最多有3步,1 4 5， 下標(biāo)分別是 3 5 6
從第5格開始走最多有2步,4 5， 下標(biāo)分別是 5 6
所以這個(gè)結(jié)果是3。
python實(shí)現(xiàn)：，最大上升子序列 問題文章來源：http://www.zghlxwxcb.cn/news/detail-631589.html
- 每個(gè)元素的最大上升子序列 ，長(zhǎng)度最小為1，初始化 o r i g i n [ 1 , 1 , . . . . ] {origin [1, 1, ....]} origin[1,1,....]
- 遍歷數(shù)組元素，計(jì)算以每個(gè)元素結(jié)尾的數(shù)組的最大上升子序列長(zhǎng)度；
- 結(jié)尾元素依次與前面的元素比較大小，若大于前面元素，則 o r i g i n [ i ] = m a x ( o r i g i n [ i ] , o r i g i n [ p r e ] + 1 ) {origin[i] = max(origin[i], origin[pre] + 1)} origin[i]=max(origin[i],origin[pre]+1)
- 最終求origin的最大值即可。
while True:
try:
n = int(input().strip())
alist = list(map(int, input().strip().split()))
origin = [1 for i in range(n)]
for i in range(n):
for j in range(i):
if alist[i] > alist[j]:
origin[i] = max(origin[i], origin[j] + 1)
max_ = max(origin)
print(max_)
except:
break
?
?
[下一篇]：算法練習(xí)–leetcode 鏈表文章來源地址http://www.zghlxwxcb.cn/news/detail-631589.html
到了這里，關(guān)于算法練習(xí)--leetcode 數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
