爬楼梯问题

输入n阶楼梯，每次爬1或者2个台阶，有多少种方法可以爬到楼顶？

示例1：输入2，输出2
一次爬2阶；
一次爬1阶；
故两种方法。

示例2：
输入3，输出3
三个1；
一个1 + 一个 2；
一个2 + 一个1；

思路分析：
采用递归求解
在这里插入图片描述

python实现:

# 递归
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)

# 递归优化，避免重复计算（优化效果微小）
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

# 循环一次计算(自底向上依次计算)
# 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实现：

// 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;
		}
	}
}

裴波那契数列

在这里插入图片描述
类似爬楼梯问题。

两数之和 [数组]

给定一个整数数组 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)}$
python实现

# 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("未找到结果")

java实现

在这里插入代码片

哈希优化

遍历数组，索引为 i；
判断 left = target - array[i] ，left 值是否存在于hash;
- 存在，则返回索引 i 和 hash中left 对应的值；
- 不存在，则将 array[i] ：i 存入hash;
时间复杂度 ${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]] = i
    raise ValueError("未找到结果")

java实现

在这里插入代码片

合并两个有序数组

给两个非递减排列的整数数组arr1、arr2，m 和 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 = 3

def merge_array(arr1, m, arr2, n):
    # 准备临时数组
    temp = []   # 空间复杂度O(m+n)
    i = 0
    j = 0
    while i < m and j < n:  # O(m+n) 线性复杂度
        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实现：
在这里插入图片描述

移动零

给定一个数组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]


def move_zero(arr):
    n = len(arr)
    for i in range(n):
        if arr[i] != 0:
            continue
        k = i
        j = i + 1
        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