每日一算法-基础1

开始刷题啦！

今天刷的是基础中数组部分的两道简单题，一是删除有序数组的重复项，一个是经典的杨辉三角打印问题。

1.删除有序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

示例 1：

解题思路：

要原地删除数组，所以不能另外新声明一个数组；数组是有序的，那就比较好办，定义一个变量来表示删除重复数字后的当前插入位置，遍历，比较它和遍历数组的位置的数字大小，相同则继续遍历，否则写入数组:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k =0
        lens = len(nums)
        
        for i in range(1, lens):
            if nums[i] == nums[k]:
                continue
            else:
                k = k+1
                nums[k] = nums[i]
        return k+1

看了一下讨论，有用到python里的数组的计数函数count的，试了一下能通过，但是用时远远超过上一个方法，因为每个位置都要经过一次遍历来进行计数，比较耗时，代码如下

 class Solution:
     def removeDuplicates(self, nums: List[int]) -> int:
       for i in nums[:]:
         if nums.count(i) ==1:
           continue
         else:
           nums.remove(i)
       return len(nums)

用时比较：

2.杨辉三角

题目：

示例  

解题思路

经典问题，杨辉三角，每个数是它左上方和右上方的数的和，主要是要在计算本行的数的时候怎样读取上一行的数，我的思路是将所有行的数组都存在一个allList中，这样上一行的数就可以根据数组index来得到，看讨论里有人定义了一个pre变量来保存上一行的数。我的代码及结果：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        allList = []
        for i in range(numRows):
            tmp = [1] *  (i+1)
            if numRows >=2:
                for j in range(i):
                    tmp[j] = allList[i][j-1] + allList[i][j]
                allList.append(tmp)
            return allList

以上是今天的刷题内容，有什么问题可以加群询问哦