[数据结构与算法]算法题-day1

这里介绍LeetCode上初级算法题的记录和思考，学会总结！

1、数组

在python中使用list类型，关于list需要记住：

• list索引从0开始
• 可以使用赋值的方式直接修改元素值。list[0]=2
• 遍历list元素时，使用for i in range(start, stop, step): range函数从start开始，不包括stop结束，如果只有一个值:range(2)，指的是0,1
• 使用del list[x]可以删除索引为x的元素
• list.append(obj)可在末尾添加元素
• list.insert(index, obj)可以在指定位置插入一个元素
• len(list)可以输出list的长度
• list*N复制N个list元素：[0]*4: [0,0,0,0]
• 两个list相加，进行组合：[1,2,3]+[2,3,4]: [1,2,3,2,3,4]
• 运算符：
  • %取模，返回除法的余数
  • //取整，返回商的整数部分

7.加一

将一个整数存入数组中，每个元素只存入单一数字，除整数0外，整数不会以0开头。对此整数进行加一。

分析：

从最后一位开始，如果元素≠9，那么就不会出现进位，直接+1，如果元素=9，那么该位置0，前一位+1；

如果前一位≠9，直接+1，如果=9，那么置零，前一位+1

也就是说，遍历元素，只要元素出现≠9，那么直接+1,；出现=9，直接置零。但是需要考虑全为9的情况，因为全为9已经被全部置零，那么只需在第一位插入1。正常情况下只需要在≠9的条件下，返回list，特殊情况在插入1后返回。

class Solution:
    
    def plusOne(self, digits: List[int]) -> List[int]:
        z = 0
        L = len(digits)
        for i in range(L-1, -1, -1):
            if digits[i] != 9:
                digits[i] += 1
                return digits
            else:
                digits[i] = 0
        digits.insert(0, 1)
        return digits

8.移动0

将数组中含0元素移到最后，非零元素顺序不变，不可以使用额外的数组

分析：可以遍历循环每个元素，如果!=0，那么将元素移到前面，计算=0元素个数，将最后几位的元素置零。

看到答案中说双指针可以使用元素的交换，只要!=0就交换两数组

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        L = len(nums)
        j = 0
        a = 0
        for i in range(L):
            if nums[i]!=0:
                nums[j] = nums[i]
                j += 1
            else:
                a += 1
        for a in range(1, a+1, 1):
            nums[L-a] = 0
#交换两数组
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        L = len(nums)
        j = 0
        a = 0
        for i in range(L):
            if nums[i] != 0:
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                j += 1