算法练习--leetcode 数组

这篇具有很好参考价值的文章主要介绍了算法练习--leetcode 数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

爬楼梯问题

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

示例1:输入2, 输出2
一次爬2阶;
一次爬1阶;
故两种方法。

示例2:
输入3, 输出3
三个1;
一个1 + 一个 2;
一个2 + 一个1;

思路分析:
采用递归求解
算法练习--leetcode 数组,算法与数据结构(python),算法,leetcode

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

裴波那契数列

算法练习--leetcode 数组,算法与数据结构(python),算法,leetcode
类似爬楼梯问题。
 

两数之和 [数组]

给定一个整数数组 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(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 ) {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]] = 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实现:
算法练习--leetcode 数组,算法与数据结构(python),算法,leetcode

移动零

给定一个数组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:
            continue
        k = i # 记录当前0的位置
        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

# 双指针
# 双指针同时从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开始的元素 全部赋值0
    while j < n:             # 时间复杂度 O(2n)
        arr[j] = 0
        j += 1
    print("result:", arr)
    return arr

java实现:双指针移动0
算法练习--leetcode 数组,算法与数据结构(python),算法,leetcode

 

找到所有数组中消失的数字

给定一个n个整数的数组array,每个元素值在【1,n】之间,找出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, n+1):  # 时间复杂度 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 * n

    temp = []  # 存储最终结果的空间不算 额外空间
    for i in range(n):
        if arr[i] <= n:
            temp.append(i + 1)

    print("result:", temp)
    return temp

java实现
算法练习--leetcode 数组,算法与数据结构(python),算法,leetcode

 

三数之和

给一个整数数组 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(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]]
    # 会产生重复的三元组
    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 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

java实现
pass

 

最大上升子序列

Redraiment是走梅花桩的高手,可以选择任意一个起点,只能从低处往高处的桩子走。他希望走的步数最多,试研究他最多走的步数?

输入描述:
第1行输入数组的长度;
第2行输入每个梅花桩的高度

输出描述:
输出一个结果

示例1
输入:
6
2 5 1 5 4 5
输出:
3

说明:
6个点的高度各为 2 5 1 5 4 5
从第1格开始走,最多为3步, 2 4 5 ,下标分别是 1 5 6
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5, 下标分别是 3 5 6
从第5格开始走最多有2步,4 5, 下标分别是 5 6
所以这个结果是3。

python实现:,最大上升子序列 问题

  • 每个元素的最大上升子序列 ,长度最小为1,初始化 o r i g i n [ 1 , 1 , . . . . ] {origin [1, 1, ....]} origin[1,1,....]
  • 遍历数组元素,计算以每个元素结尾的数组的最大上升子序列长度;
  • 结尾元素依次与前面的元素比较大小,若大于前面元素,则 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

 
 
[下一篇]:算法练习–leetcode 链表文章来源地址https://www.toymoban.com/news/detail-631589.html

到了这里,关于算法练习--leetcode 数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】算法的时间复杂度和空间复杂度(下)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 空间复杂度也是一个数学表达式,是对一个算法在运行过程中 临时占用的额外的存储空间大小的量度 。 空间复杂度不是程序占用

    2023年04月19日
    浏览(82)
  • 【数据结构】算法的时间复杂度和空间复杂度 (上)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何

    2023年04月22日
    浏览(60)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(48)
  • 数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

    数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此

    2024年02月07日
    浏览(48)
  • 【python与数据结构】(leetcode算法预备知识)

    笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ 1.数字类型: 整数(int):表示整数值,例如 1、-5、100。 浮点数(float):表示带有小数部分的数字,例如 3.14、-0.5、2.0。 复数(complex):表示实部和虚部的复数,例如 2+3j。 2.布尔类型(bool): 表示真(True)或假(

    2024年02月08日
    浏览(38)
  • 力扣(LeetCode)数据结构练习题(2)

    今天又写了两道关于链表的练习题,来给大家分享一下。巩固一下上一篇学到的链表知识,题目可以然我们更清楚的认识链表。 目录 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表 给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中

    2024年02月21日
    浏览(52)
  • 【数据结构】顺序表详解(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺

    2023年04月27日
    浏览(47)
  • LeetCode 刷题 数据结构 数组 485 最大连续1的个数

    给定一个二进制数组  nums  , 计算其中最大连续  1  的个数。 示例 1: 示例 2: 提示: 1 = nums.length = 105 nums[i]  不是  0  就是  1.   参看bilibli视频-up主 爱学习的饲养员,讲解的很清晰。 手把手带你刷Leetcode力扣|各个击破数据结构和算法|大厂面试必备技能【已完结】-

    2024年02月15日
    浏览(44)
  • 数据结构算法练习 插入排序 冒泡排序

    插入排序 代码如下  package main import \\\"fmt\\\" func main() {     a := []int{4, 5, 6, 1, 3, 2}         b := insert(a)     for i := 0; i len(b); i++ {         fmt.Println(b[i])     } } func insert(a []int) []int {     if len(a) = 1 {                   如果数组长度小于等于1 不用排序直接返回          retur

    2024年02月08日
    浏览(55)
  • 数据结构与算法系列之习题练习

    💗 💗 博客:小怡同学 💗 💗 个人简介:编程小萌新 💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞 括号匹配问题。 用队列实现栈。 用栈实现队列。 设计循环队列。 有效的括号 //用栈来实现 //左括号进栈 右括号出栈并销毁如果不匹配则return //设置两个队列,入栈

    2024年02月11日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包