正文

算法通关手册刷题笔记1数组基础(代码片段)

临风而眠  临风而眠  2022-12-23  172

关键词：

算法通关手册刷题笔记1 数组基础

持续更新中

文章目录

算法通关手册刷题笔记1 数组基础
数组操作题目
二维数组题目
参考资料

数组操作题目

题号	标题	题解	标签	难度
0189	轮转数组	Python	数组	中等
0066	加一	Python	数组	简单
0724	寻找数组的中心下标	Python	数组	简单
0485	最大连续 1 的个数	Python	数组	简单
0238	除自身以外数组的乘积	Python	数组	中等

0189 轮转数组

AC

自己的解法

一开始犯了错误：注意python中数组的赋值

两个列表list1和list2，直接用等号赋值，list2修改后，list1也会被修改
- 想要不改变原列表，使用[:]或者.copy()
参考:python把一个数组赋值给另一个数组

一开始的错误代码

def rotate2( nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        nums2 = nums
        for i in range(len(nums)):
            nums2[i] =  nums[(i+k+1)%len(nums)]

        return nums2
rotate2([1,2,3,4,5,6,7],3)

[5, 6, 7, 5, 6, 7, 5]

来分析一下： nums2[0] = nums[4] , 这时候 nums2[0]和nums[0]都变成了5 ,所以nums2[3] = nums[0] = 5…

改了改，以为自己做对了，但是没AC

def rotate(nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # nums2 = num
        nums2 = []
        for i in range(len(nums)):
            nums2.append(0)
        for i in range(len(nums)):
        #下面这俩应该都可以
**            nums2[i] = nums[(i+k+1) % len(nums)]
            # nums2[(i+k)%len(nums)] =  nums[i]**
        return nums2
rotate([1,2,3,4,5,6,7],3)

[5, 6, 7, 1, 2, 3, 4]

难绷，审题！去掉return就行了

其他解法

算法通关手册上的python解法

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        self.reverse(nums, 0, n-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, n-1)
    
    def reverse(self, nums: List[int], left: int , right: int) -> None:
        while left < right:
            tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp
            left += 1
            right -=1

力扣题解区上面看到切片的解法，感觉very smart

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]

知识点查漏补缺

关于python中的数组赋值

python中对象的引用

试了下整数变量会不会和那个数组也是一样的情况，不是的
于是去查了查
- Python可变对象和不可变对象

0066 加一

AC

自己的解法

一开始写的代码

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        k = len(digits)
        sum = 0
        m = 1
        while k >= 1:
            sum += m*digits[k-1]
            m *= 10
            k -= 1
        newlis = []
        sum += 1
        j = 0
        while sum > 0:

            # newlis.append(sum % 10)
            newlis.insert(j, sum % 10)
            sum //=10
        return newlis

其他解法

看《算法通关手册》的题解

感觉思路很清晰

有可能有进位，先在前面放个0，末位加个1，啥时候会有进位呢，那个位置上的数字为10的时候，如果低位都没碰到10，那么高位肯定不会碰到10，直接break，返回原来的列表，即现在的digits[1:]

哪一位有进位，就把那一位变成0，然后它的前一位+1

如果会一直进位到最高位，那么就返回digits

def plusOne(self, digits: List[int]) -> List[int]:
    digits = [0] + digits
    digits[len(digits)-1] += 1
    for i in range(len(digits)-1,0,-1):
        if digits[i] != 10:
            break
        else:
            digits[i] = 0
            digits[i-1] += 1
        
    if digits[0] == 0:
        return digits[1:] 
    else:
        return digits

注意 [0] + digits的顺序是有影响的

力扣官方题解妙啊
- 思路
  - 找出最长的后缀9
    - 如果 $\\textitdigits $的末尾没有 999，例如 [1,2,3]，那么我们直接将末尾的数加一，得到 [1, 2, 4]并返回；
    - 如果 $\\textitdigits$ 的末尾有若干个 9，例如 [1,2,3,9,9]那么我们只需要找出从末尾开始的第一个不为 999的元素，即 333，将该元素加一，得到 [1,2,4,9,9]]。随后将末尾的 999 全部置零，得到 [1,2,4,0,0]并返回。
    - 如果 $\\textitdigits$ 的所有元素都是 999，例如 [9,9,9,9,9]，那么答案为 $[1, 0, 0, 0, 0, 0]$ 。我们只需要构造一个长度比 $\\textitdigits$ 多 111 的新数组，将首元素置为 111，其余元素置为 000 即可。
- 算法
  - 只需要对数组 $\\textitdigits$ 进行一次逆序遍历，找出第一个不为 999 的元素，将其加一并将后续所有元素置零即可。如果 $\\textitdigits$ 中所有的元素均为 999，那么对应着「思路」部分的第三种情况，我们需要返回一个新的数组。
```
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n -1, -1, -1):
            if digits[i] != 9:
                digits[i] += 1
                for j in range(i + 1, n):
                    digits[j] = 0
                return digits

        return [1] + [0] * n
```

知识点查漏补缺

在前面自己的解法那个代码里面
- 放到vscode里面会有这个问题
  - 需要from typing import List
- 那一步用append顺序会反双边队列里面才有appendleft
  - 用insert比较好
  - 另外别记混了那个appendleft是双边队列才有的之前在头歌学过👇
  - 2-4 Python入门之collections模块
  - 不过这题确实可以试试双边队列
    - Deque in Python - GeeksforGeeks
- python里面的//和/ 两种除法的区别
  - //是向下取整

0724 寻找数组的中心下标

AC

自己的解法

一开始的错误代码

    - 一开始的代码
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        suml = 0 # 从左往右的和
        sumr = 0 # 从右往左的和
        # l = len(nums)
        lisl = []
        lisr = []
        for i in range(len(nums)):
            suml += nums[i]
            lisl.append(suml)
        for i in range(len(nums)-1,-1,-1):
            sumr += nums[i]
            lisr.append(sumr)   
        # flag = 0
        if lisl[0] == lisl[len(nums)-1]:
            return 0
        elif lisr[0] == lisr[len(nums)-1]:
            return len(nums)-1
        else:
            for j in range(len(nums)):
                
                if lisl[j] == lisr[j]:
                    return j
    
        return -1

lisl=[1,8,11,17,22,28]

lisr=[6,11,17,20,21,28]

返回5是不正确的，突然发现自己这个代码只适合中心点两边元素个数相等的情况…

按照那个思路，在左和数组and 右和数组相同位置的话，那只能是元素个数相同了

改了改，还是有问题

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        suml = 0 # 从左往右的和
        sumr = 0 # 从右往左的和
        # l = len(nums)
        lisl = []
        lisr = []
        for i in range(len(nums)):
            suml += nums[i]
            lisl.append(suml)
        for i in range(len(nums)-1,-1,-1):
            sumr += nums[i]
            lisr.append(sumr)   
        # flag = 0
        if lisl[0] == lisl[len(nums)-1]:
            return 0
        elif lisr[0] == lisr[len(nums)-1]:
            return len(nums)-1
        else:
            for j in range(len(nums)):
                if lisl[j] == lisr[len(nums)-1-j]:
                    return j

    
        return -1

一开始感觉自己把两种特殊情况提出来很聪明，结果发现好像题目中这个条件的限制

如果数组有多个中心下标，应该返回 最靠近左边 的那一个

那么当左边的和为0的话，右边如果很多0，就会返回最右边的0

AC了
- 总结一下自己的思路
  - 设立一个数组，每一位依次存储原数组nums从左到右的和
- 再设立一个数组，每一位一次存储原数组nums从右到左的和
  - 然后由于题目要求返回靠左的中心点，那下标就从0到 len(nums)-1 从小到大遍历
- 遇到相等的就返回j

代码如下

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        suml = 0 # 从左往右的和
        sumr = 0 # 从右往左的和
        # l = len(nums)
        lisl = []
        lisr = []
        for i in range(len(nums)):
            suml += nums[i]
            lisl.append(suml)
        for i in range(len(nums)-1,-1,-1):
            sumr += nums[i]

        for j in range(len(nums)):
                if lisl[j] == lisr[len(nums)-1-j]:
                    return j

    
        return -1

但时空复杂度大了些

其他做法

官方题解：前缀和
- 思路
  - 记数组的和为 $t o t a l$ ,当遍历到第 $i$ 个元素时，左侧元素之和为 $s u m$ ,那么右侧元素的和为 $total-nums_i-sum$ ,左右侧元素相等即为 $sum=total-nums_i-sum$ ，即 $2\\times sum + nums_i=total$
  - 当中心索引左侧或右侧没有元素时，即为零个项相加，这在数学上称作「空和」（ $\\textempty sum$ ）。在程序设计中我们约定「空和是零」

题解没给python的，自己AC

对着题解的文字解释，自己写了一个…但是不全对

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = 0
        sum = 0
        for i in range(len(nums)):
            total += nums[i]
        for i in range(1,len(nums)):
            sum +=nums[i-1]
            if 2查看详情  
                
学习笔记在刷题前(代码片段)
刷题前知识目录刷题前知识复杂度1.算法的时间复杂度2.算法的空间复杂度数据结构1.数组Array2.链表LinkedList3.队列Queue/Deque4.栈stack5.哈希表HashTable6.集合Set6.树Tree概念性质遍历7.堆Heap概念8.图Graph概念总结关于字符和字符串；关于for...  查看详情  
                
leetcode通关：数组十七连，真是不简单(代码片段)
分门别类刷算法，坚持，进步！刷题路线参考：https://github.com/chefyuan/algorithm-base      https://github.com/youngyangyang04/leetcode-master/大家好，我是老三，一个刷题困难户，接下来我们开始数组类型算法...  查看详情  
                
leetcode通关：数组十七连，真是不简单(代码片段)
分门别类刷算法，坚持，进步！刷题路线参考：https://github.com/chefyuan/algorithm-base      https://github.com/youngyangyang04/leetcode-master/大家好，我是老三，一个刷题困难户，接下来我们开始数组类型算法...  查看详情  
                
leetcode刷题笔记-动态规划-day6(代码片段)
...数组1.题目原题链接：152.乘积最大子数组2.解题思路算法：动态规划+滚动数组优化f[i]表示所有从0到i并且选用a[i]获得的最大乘  查看详情  
                
leetcode刷题笔记-动态规划-day6(代码片段)
...数组1.题目原题链接：152.乘积最大子数组2.解题思路算法：动态规划+滚动数组优化f[i]表示所有从0到i并且选用a[i]获得的最大乘  查看详情  
                
leetcode刷题笔记-动态规划-day5(代码片段)
...子数组和1.题目原题链接：53.最大子数组和2.解题思路算法：前缀和我们用一个sum变量表示遍历到当前位置数组的前缀和用minn变量表示遍历到当前位置，  查看详情  
                
javascript数据结构与算法基础笔记(代码片段)
...的方式是按照定义>javascript实现方式>对应的方法>算法实现的结构去写的后面有想法在继续补充1.2数组1.2.1数组定义js数组其实就是API的调用是一种最简单的内存数据结构数组存储一系列同一种数据类型的值注：javascript...  查看详情  
                
javascript数据结构与算法基础笔记(代码片段)
...的方式是按照定义>javascript实现方式>对应的方法>算法实现的结构去写的后面有想法在继续补充1.2数组1.2.1数组定义js数组其实就是API的调用是一种最简单的内存数据结构数组存储一系列同一种数据类型的值注：javascript...  查看详情  
                
力扣刷题算法笔记（javascript版）下(代码片段)
上篇链接：力扣刷题算法笔记（javascript版）上视频链接：人人都能看得懂的Leetcode力扣刷题教程合集在笔记上中一共学习了31道算法题，剩下大概20到算法题在花两天的学习和总结一下1、打家劫舍题目描述࿱...  查看详情  
                
java基础知识点笔记总结(代码片段)
...值10.二维数组的内存解析11.数组赋值12.数组的复制13.数组算法线性查找14.数组算法二分法查找15.排序算法的优劣16.冒泡排序17.快速排序18.Arrays数组工具类1.eclips  查看详情  
                
leetcode刷题笔记-动态规划-day5(代码片段)
...子数组和1.题目原题链接：53.最大子数组和2.解题思路算法：前缀和我们用一个sum变量表示遍历到当前位置数组的前缀和用minn变量表示遍历到当前位置，前面所有位置前缀和的最小值遍历过程中答案需要更新，应...  查看详情  
                
leetcode刷题笔记-动态规划-day2(代码片段)
...划-day270.爬楼梯1.题目原题链接：70.爬楼梯2.解题思路算法：递推定义数组f[i]表示到第i级台阶的总方案数，走到第i级台阶的前一步可能走了1级台阶，也可能  查看详情  
                
leetcode刷题笔记-动态规划-day2(代码片段)
...划-day270.爬楼梯1.题目原题链接：70.爬楼梯2.解题思路算法：递推定义数组f[i]表示到第i级台阶的总方案数，走到第i级台阶的前一步可能走了1级台阶，也可能  查看详情  
                
leetcode刷题笔记-动态规划-day4(代码片段)
...ay455.跳跃游戏1.题目原题链接：55.跳跃游戏2.解题思路算法：贪心我们用变量j表示从前i-1个位置跳能跳到的最远位置，遍历数组：如果当前位置i大于了j  查看详情  
                
leetcode刷题笔记-动态规划-day4(代码片段)
...ay455.跳跃游戏1.题目原题链接：55.跳跃游戏2.解题思路算法：贪心我们用变量j表示从前i-1个位置跳能跳到的最远位置，遍历数组：如果当前位置i大于了j  查看详情  
                
阿里二面：什么是mmap？（不是mmp）(代码片段)
...Linux速查备忘手册.pdf我的浏览器收藏夹大公开数据结构和算法刷题笔记.pdf下载LeetCode算法刷题C/C++版答案pdf下载LeetCode算法刷题Java版答案pdf下载找工作简历模板集(word格式)下载Java基础核心知识大总结.pdf下载C/C++常见...  查看详情  
                
leetcode刷题笔记-数据结构-day15(代码片段)
文章目录LeetCode刷题笔记-数据结构-day15108.将有序数组转换为二叉搜索树1.题目描述2.解题思路3.代码105.从前序与中序遍历序列构造二叉树1.题目描述2.解题思路3.代码103.二叉树的锯齿形层序遍历1.题目描述2.解题思路3.代码LeetCode刷...  查看详情

正文

算法通关手册刷题笔记1数组基础(代码片段)

算法通关手册 刷题笔记1 数组基础

文章目录

数组操作题目

0189 轮转数组

AC

自己的解法

其他解法

知识点查漏补缺

关于python中的数组赋值

python中对象的引用

0066 加一

AC

自己的解法

其他解法

知识点查漏补缺

0724 寻找数组的中心下标

AC

自己的解法

其他做法

学习笔记在刷题前(代码片段)

leetcode通关：数组十七连，真是不简单(代码片段)

leetcode通关：数组十七连，真是不简单(代码片段)

leetcode刷题笔记-动态规划-day6(代码片段)

leetcode刷题笔记-动态规划-day6(代码片段)

leetcode刷题笔记-动态规划-day5(代码片段)

javascript数据结构与算法基础笔记(代码片段)

javascript数据结构与算法基础笔记(代码片段)

力扣刷题算法笔记（javascript版）下(代码片段)

java基础知识点笔记总结(代码片段)

leetcode刷题笔记-动态规划-day5(代码片段)

leetcode刷题笔记-动态规划-day2(代码片段)

leetcode刷题笔记-动态规划-day2(代码片段)

leetcode刷题笔记-动态规划-day4(代码片段)

leetcode刷题笔记-动态规划-day4(代码片段)

阿里二面：什么是mmap？（不是mmp）(代码片段)

leetcode刷题笔记-数据结构-day15(代码片段)

算法通关手册刷题笔记1 数组基础