首页 软件代码

LeetCode-数据结构-数组-第1天


217. 存在重复元素

给定一个整数数组,判断是否存在重复元素。
如果存在一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false 。
具体题目链接

Python

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        #通过集合进行排除重复值,之后进行长度判断。
        return len(nums)!=len(set(nums))

思路:通过集合进行排除重复值,之后进行长度判断。来自python的碾压。

GO

func containsDuplicate(nums []int) bool {
    nums_map := make(map[int]int)
    for _, num := range nums {
        if _, ok := nums_map[num]; ok {
            return true
        } else {
            nums_map[num] = 1
        }
    }
    return false
}

思路:通过创建map字典(哈希表),若字符第二次出现,则ok会为true,则会返回true。

53. 最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
具体题目链接

Python(参考leetcode答案)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i]=max(nums[i-1],0)+nums[i]     
        return max(nums)

思路:举个例子nums = [-2,1,-3,4,-1,2,1,-5,4],首先循环下标从1开始的,当nums[1]开始时首先要判断nums[0]是否大于0,若不大于,则无需与nums[0]构成子串,大于则构成,并将nums[1]的值改为num[1]+nums[0]。同样当nums[2]进行时,也要让nums[1]与0比较,大于则相加并更新nums[2],否则不变。直到结束,最后再选出最大的num即可。

GO(参考leetcode答案)

func maxSubArray(nums []int) int {
    max:=nums[0]
    for i:=1;i<len(nums);i++{
        if nums[i]+nums[i-1]>nums[i]{
            nums[i]+=nums[i-1]
        }
        if max<nums[i]{
            max=nums[i]
        }
    }
    return max
}

思路:同python

func maxSubArray(nums []int) int {
    length:=len(nums)
    sums:=make([]int, 0, length)
    sums=append(sums,nums[0])
    ans:=sums[0]
    for i:=1;i<length;i++{
        sums=append(sums,nums[i]+max(sums[i-1],0))
        if sums[i]>ans{
            ans=sums[i]
        }
    }
    return ans
}
func max(a,b int) int {
    if a>b{
        return a
    }
    return b
}

思路:此思路时第一开始我的思路,具体形式和官网一样,但我才用新的数组进行储存结果。





文章评论

    Oxygen 访客ChromeAndroid
    2021-07-30 21:57   回复

    Python确实有很多牛逼的api和第三方包,不过刷算法题建议还是要少用,站在巨人的肩膀上编程,很多东西学不到,如果是学习算法的话,建议抛开api,一些东西亲手去实现一遍,可以学到很多 ,实际开发或者写自用的小软件就怎么方便高效怎么来,该调包就调包。另外最大子序和这个题是典型的DP问题,可以借这个题学一下动态规划

      布衣者 站长ChromeWindows
      2021-07-30 23:39   回复

      对,刷题时确实不能用,要不然选练不出来思维。碰到python能够轻松解决的问题,我会选择python简单的写,而用go来完善自己基础的训练。(因为有很多时候我思路只能想起来一个,导致python和go代码相同。)我刚开始训练有些许盲目,只刷题感觉自己不太行,所以现在就按照别人整理好的思路来循循渐进的刷题和学习。

目录