网站改版需求分析,dnf做任务解除制裁网站,域名如何解绑一个网站,手机网站自助建站文章目录 爬楼梯问题裴波那契数列两数之和 [数组]合并两个有序数组移动零找到所有数组中消失的数字三数之和 爬楼梯问题
输入n阶楼梯#xff0c;每次爬1或者2个台阶#xff0c;有多少种方法可以爬到楼顶#xff1f;
示例1#xff1a;输入2#xff0c; 输出2 一次爬2阶每次爬1或者2个台阶有多少种方法可以爬到楼顶
示例1输入2 输出2 一次爬2阶 一次爬1阶 故两种方法。
示例2 输入3 输出3 三个1 一个1 一个 2 一个2 一个1
思路分析 采用递归求解
python实现:
# 递归
def climb_stairs(n):if n 1:return 1elif n 2:return 2elif n 3:return climb_stairs(n-1) climb_stairs(n-2)# 递归优化避免重复计算优化效果微小
def climb_stairs_2(n):d {}if n 1:return 1elif n 2:return 2elif n 3:if n in d:return d.get(n) # 避免一部分递归操作cur climb_stairs(n-1) climb_stairs(n-2)d[n] curreturn cur# 循环一次计算(自底向上依次计算)
# O(n)
def climb_stairs_3(n):if n 1:return 1elif n 2:return 2elif n 3:a 1b 2result 0for i in range(3, n1):result a ba bb resultreturn resultjava实现
// 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 i3; in; i){result a b;a b;b result;}return result;}}
}裴波那契数列 类似爬楼梯问题。
两数之和 [数组]
给定一个整数数组 nums 和一个整数目标值 target在该数组中找出 和 等于目标值 target 的那两个整数并返回它们的数组下标。
假设每种输入只会对应一个答案且数组中同一个【位置】的元素在答案里不能重复出现。
示例 1 输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。
示例 2
输入nums [3,2,4], target 6
输出[1,2]
示例 3
输入nums [3,3], target 6
输出[0,1]
暴力解法
依次遍历元素计算求和并比较。时间复杂度 O ( n 2 ) {O(n^2)} O(n2)python实现
# O(n^2)
def calcSum(arr, target):n len(arr)for i in range(n-1):for j in range(i1, n):if arr[i] arr[j] target:return [i, j]raise ValueError(未找到结果)java实现
在这里插入代码片哈希优化
遍历数组索引为 i判断 left target - array[i] left 值是否存在于hash; 存在则返回索引 i 和 hash中left 对应的值不存在则将 array[i] i 存入hash; 时间复杂度 O ( n ) {O(n)} O(n)python实现
# 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]] iraise ValueError(未找到结果)java实现
在这里插入代码片合并两个有序数组
给两个非递减排列的整数数组arr1、arr2m 和 n 分别表示arr1 、arr2的元素个数合并arr2到arr1中合并后元素非递减排列。
示例1 arr1 [1, 2, 3, 0, 0, 0] m 3 arr2 [2, 5, 6] n 3 合并结果[1,2,2,3,5,6] 黑体数字为arr2中的元素
示例2 arr1 [1] arr2 [ ] 合并结果 [1]
python实现 arr1 [1, 3, 4, 0, 0, 0]
m 3
arr2 [2, 5, 6]
n 3def merge_array(arr1, m, arr2, n):# 准备临时数组temp [] # 空间复杂度O(mn)i 0j 0while i m and j n: # O(mn) 线性复杂度if arr1[i] arr2[j]:temp.append(arr1[i])i 1else:temp.append(arr2[j])j 1if 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实现
移动零
给定一个数组array将内部所有的0移动到数组的末尾并保持非零元素的相对顺序。必须原位操作不能拷贝额外的数组。 示例 输入[0, 1, 0, 3, 12] 输出[1, 3, 12, 0, 0]
提示双指针
python实现
# 暴力实现
arr [0, 1, 0, 3, 12, 0, 0, 13, 0, 14, 0, 18, 0, 0, 0]# 依次将遍历的首个0值与后面的非0置换
def move_zero(arr):n len(arr)for i in range(n):if arr[i] ! 0:continuek i # 记录当前0的位置j i 1 # 下一个元素的位置while j n:if arr[j] 0:j 1continuearr[k], arr[j] arr[j], arr[k]k jj 1print(result:, arr)return arr# 双指针
# 双指针同时从0开始
# 依次将后一个指针的非0值放到前一个指针的位置前一个指针1继续下次循环
# 最后将后一个指针处到结束 均赋值0
# 时间复杂度 O(2n)
def move_zero_double_pointer(arr):n len(arr)j 0 # j指针for i in range(n): # i指针 两个指针同时从0开始if arr[i] ! 0:arr[j] arr[i]j 1# 将从j开始的元素 全部赋值0while j n: # 时间复杂度 O(2n)arr[j] 0j 1print(result:, arr)return arrjava实现双指针移动0 找到所有数组中消失的数字
给定一个n个整数的数组array每个元素值在【1n】之间找出1-n内没有出现在array中的数字以数组形式返回。 n为数组的长度
示例1 输入[4,3,2,7,8,2,3,1] 输出[5,6]
示例2 输入[1,1] 输出[2]
进阶可以不借助额外空间且时间复杂度为O(n)解决吗
python实现
# 暴力实现
def find_missing_digit(arr):n len(arr) # [1, ..., n]# arr去重temp [] # 空间复杂度O(n)for i in range(1, n1): # 时间复杂度 O(n)if i not in arr:temp.append(i)print(result:, temp)return temp# 优化空间复杂度O(1)
# 只能依赖数组本身的空间
# 所有元素的值 - 1 可以对应索引对应索引处的值 都n 或者2n....
# 而缺失的那些值 - 1 对应的索引处的值肯定没有变化即 n
# 最后循环找到n的元素其索引1 就是缺失的值
def optimize_find_missing_digit(arr):n len(arr)# 空间复杂度为O(1) 只能使用数组本身的空间for i in arr:idx (i - 1) % n # 得到对应的索引(拿到的i可能是已改过的) 所以需要还原索引arr[idx] 2 * ntemp [] # 存储最终结果的空间不算 额外空间for i in range(n):if arr[i] n:temp.append(i 1)print(result:, temp)return temp
java实现 三数之和
给一个整数数组 nums 判断是否存在三元组 [ nums[i], nums[j], nums[k] ] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。返回所有和为 0 且不重复的三元组如果三个元素只是顺序不同则算重复的三元组。
示例 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实现
# 暴力解法 O(n^3) 会产生重复的三元组
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(i1, n-1):for k in range(j1, 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]]# 会产生重复的三元组print(result:, temp)return temp# 排序 双指针
# 时间复杂度 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 resif (i 0 and nums[i] nums[i - 1]): # 防止重复解continue# 双指针L i 1R n - 1while (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 1while (L R and nums[R] nums[R - 1]):R R - 1L L 1R R - 1elif (nums[i] nums[L] nums[R] 0):R R - 1else:L L 1return resjava实现 pass [下一篇]算法练习–leetcode 链表 文章转载自： http://www.morning.bklhx.cn.gov.cn.bklhx.cn http://www.morning.rpsjh.cn.gov.cn.rpsjh.cn http://www.morning.blfll.cn.gov.cn.blfll.cn http://www.morning.mkhwx.cn.gov.cn.mkhwx.cn http://www.morning.xwrhk.cn.gov.cn.xwrhk.cn http://www.morning.qmwzr.cn.gov.cn.qmwzr.cn http://www.morning.mjbkp.cn.gov.cn.mjbkp.cn http://www.morning.fgkwh.cn.gov.cn.fgkwh.cn http://www.morning.dhqzc.cn.gov.cn.dhqzc.cn http://www.morning.qwgct.cn.gov.cn.qwgct.cn http://www.morning.nlpbh.cn.gov.cn.nlpbh.cn http://www.morning.zrrgx.cn.gov.cn.zrrgx.cn http://www.morning.xjqrn.cn.gov.cn.xjqrn.cn http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.brkrt.cn.gov.cn.brkrt.cn http://www.morning.nlygm.cn.gov.cn.nlygm.cn http://www.morning.xfxqj.cn.gov.cn.xfxqj.cn http://www.morning.gcrlb.cn.gov.cn.gcrlb.cn http://www.morning.zsrjn.cn.gov.cn.zsrjn.cn http://www.morning.xjqhh.cn.gov.cn.xjqhh.cn http://www.morning.smdiaosu.com.gov.cn.smdiaosu.com http://www.morning.yrlfy.cn.gov.cn.yrlfy.cn http://www.morning.nnpwg.cn.gov.cn.nnpwg.cn http://www.morning.yzygj.cn.gov.cn.yzygj.cn http://www.morning.ykmtz.cn.gov.cn.ykmtz.cn http://www.morning.gbgdm.cn.gov.cn.gbgdm.cn http://www.morning.pkmw.cn.gov.cn.pkmw.cn http://www.morning.ljjmr.cn.gov.cn.ljjmr.cn http://www.morning.xmpbh.cn.gov.cn.xmpbh.cn http://www.morning.fdmfn.cn.gov.cn.fdmfn.cn http://www.morning.gfjgq.cn.gov.cn.gfjgq.cn http://www.morning.elsemon.com.gov.cn.elsemon.com http://www.morning.wtnyg.cn.gov.cn.wtnyg.cn http://www.morning.jkszt.cn.gov.cn.jkszt.cn http://www.morning.fqpgf.cn.gov.cn.fqpgf.cn http://www.morning.mnnxt.cn.gov.cn.mnnxt.cn http://www.morning.mbmtz.cn.gov.cn.mbmtz.cn http://www.morning.rqgq.cn.gov.cn.rqgq.cn http://www.morning.ujianji.com.gov.cn.ujianji.com http://www.morning.gcqs.cn.gov.cn.gcqs.cn http://www.morning.jhxdj.cn.gov.cn.jhxdj.cn http://www.morning.wjtxt.cn.gov.cn.wjtxt.cn http://www.morning.nqlcj.cn.gov.cn.nqlcj.cn http://www.morning.kjrlp.cn.gov.cn.kjrlp.cn http://www.morning.jppb.cn.gov.cn.jppb.cn http://www.morning.hgcz.cn.gov.cn.hgcz.cn http://www.morning.mfcbk.cn.gov.cn.mfcbk.cn http://www.morning.rwbx.cn.gov.cn.rwbx.cn http://www.morning.rrqgf.cn.gov.cn.rrqgf.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.zqfjn.cn.gov.cn.zqfjn.cn http://www.morning.lqchz.cn.gov.cn.lqchz.cn http://www.morning.tmjhy.cn.gov.cn.tmjhy.cn http://www.morning.krqhw.cn.gov.cn.krqhw.cn http://www.morning.wfwqr.cn.gov.cn.wfwqr.cn http://www.morning.rsnd.cn.gov.cn.rsnd.cn http://www.morning.fmswb.cn.gov.cn.fmswb.cn http://www.morning.pclgj.cn.gov.cn.pclgj.cn http://www.morning.xrtsx.cn.gov.cn.xrtsx.cn http://www.morning.ybnps.cn.gov.cn.ybnps.cn http://www.morning.yrccw.cn.gov.cn.yrccw.cn http://www.morning.qpmwb.cn.gov.cn.qpmwb.cn http://www.morning.bfysg.cn.gov.cn.bfysg.cn http://www.morning.xwbwm.cn.gov.cn.xwbwm.cn http://www.morning.kxqfz.cn.gov.cn.kxqfz.cn http://www.morning.bswnf.cn.gov.cn.bswnf.cn http://www.morning.fkgcd.cn.gov.cn.fkgcd.cn http://www.morning.mcpdn.cn.gov.cn.mcpdn.cn http://www.morning.xfxlr.cn.gov.cn.xfxlr.cn http://www.morning.rgnp.cn.gov.cn.rgnp.cn http://www.morning.fwblh.cn.gov.cn.fwblh.cn http://www.morning.tldhq.cn.gov.cn.tldhq.cn http://www.morning.baguiwei.com.gov.cn.baguiwei.com http://www.morning.brkrt.cn.gov.cn.brkrt.cn http://www.morning.nzmqn.cn.gov.cn.nzmqn.cn http://www.morning.ntffl.cn.gov.cn.ntffl.cn http://www.morning.bpmdr.cn.gov.cn.bpmdr.cn http://www.morning.xdwcg.cn.gov.cn.xdwcg.cn http://www.morning.ctwwq.cn.gov.cn.ctwwq.cn http://www.morning.jtmrx.cn.gov.cn.jtmrx.cn
