音乐播放器
R1yhtp的blog
 
文章 标签
4

Powered by Gridea | Theme: Fog
载入天数...
载入时分秒...

从零开始的算法之路(数组篇)

寄了。。。Gridea把我图片吞了,伤心。。。最近好倒霉qaq

算法1

复杂度分析:
时间复杂度:O(n * k),其中 n 是字符串的长度,k 是子字符串的长度。

空间复杂度:O(1),只使用了常数空间。

等下试试能不能优化(待补充)

算法2

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,
使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,
并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

(后面的题干没看懂喵)

def delete():
    nums = [1,2,3,5,6,7,88,9,88,7,4,5,6,2,2,1,13,10,0,8]
    s = len(nums)
    news = []
    for i in range(s):
        if nums[i] not in news:
            news.append(nums[i])
    print(news)
    print(f"数组的唯一元素个数是:{len(news)}")
delete()

那些能够坚持每天刷题,并最终学会一整套「基础算法知识」和「基础数据结构知识」的人,总是少数人。

希望我也是那部分少数人
(今天才想起来有博客,,,早知道上传这里来了)

算法3

今天写这个题的时候想到了贪心算法,但是下笔却不知道怎么写,后来才发现是因为自己想复杂了,其实只需要前一天值小于后一天的就行了
最后就是标记的地方:
因为return当时放到了for循环里面导致函数在第一次计算利润后直接返回结果。
应该将 return maxprofit 放在 for 循环外面,确保遍历完所有价格后才返回最终结果

其次类方法的调用:
如果 maxProfit 是类方法,调用时应该使用 Solution.maxProfit

留到以后复习总结吧(记得补档)

学的我大脑缺氧//

代码:

def plusOne(digits):
    carry = 1  # 初始进位为1,即加一
    n = len(digits)
    for i in range(n - 1, -1, -1):
        total = digits[i] + carry
        digits[i] = total % 10  # 当前位的新值
        carry = total // 10     # 计算新的进位
        if carry == 0:
            break  # 没有进位,提前终止循环
    if carry > 0:
        digits.insert(0, carry)  # 处理最高位的进位
    return digits

算法4

做了一个bool的简单题:
出错了(qaq)

错误:
内层循环的起始索引错误:内层循环的变量j应从i+1开始,而非i。原代码中j从i开始会导致元素与自身比较,错误地判定为重复。(i+1不是i)

提前返回False的逻辑错误:在内层循环中,当元素不相等时立即检查x是否为0并返回False,导致未遍历完所有元素对就提前终止。

下面画红框即是修改部分

但但但是,因为两个for,时间复杂度高了超出了时间限制,优化代码如下:

return len(nums) != len(set(nums))

该方案直接比较原列表和集合的长度差异,但会遍历整个数组创建集合。当数组很大且重复元素在末尾时,前一种方案更优。

算法5

算法题:给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。

第一次就出错了喵~()
错误代码:

def intersect(nums1,nums2):
    nums3 =[]
    for i in range(len(nums1)):
        for j in range(len(nums2)):
            if nums1[i]==nums2[j]:
                nums3.append(nums1[i])
                nums1.pop[i]
                nums2.pop[j]
    return nums3
n1 = [1,2,3,4,5,6]
n2 = [1,3,5]
print(intersect(n1,n2))

错误分析:!!!(以后不准犯pop的错误)
1.语法错误:pop[i] 应为 pop(i)

2.索引偏移:在循环中直接 pop 元素会导致:
列表长度变化引发索引越界
后续元素位置改变导致漏检

3.逻辑错误:当元素匹配时同时删除两个列表中的元素,这会破坏原始数据结构

下面是改进方案:

算法6

给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。

感觉要多练练range的顺序之类的以及余数

算法7

今日算法:双指针的讲解

代码错误:
remove(0)的问题:每次调用remove(0)会删除第一个出现的0,但循环遍历时数组长度变化会导致跳过元素或越界。

==的误用:n[j] == 0是比较而非赋值,应改为n[j] = 0。

逻辑混乱:尝试在中间过程删除并补0的方式不高效且容易出错。

双指针的应用:
双指针遍历:使用指针j记录下一个非零元素的位置。遍历时,每当遇到非零元素就将其放到j的位置,并移动j。

末尾补零:遍历结束后,从j到数组末尾的所有位置填充0。采用双指针法能在O(n)时间完成操作,且保证原地修改。

总结
双指针的核心思想:通过两个指针的协同遍历,将原本需要双重循环的问题优化为单次遍历。它特别适合处理需要 原地修改数组 或 减少时间复杂度 的场景。理解指针移动的条件和边界情况是关键