LeetCode-初级算法之数组

python3

初学python 小白有些地方不是很熟练所以写的地方有些啰嗦😝 请大家轻点喷有错误的地方请大家帮我指正

删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
            max = -999999999999
            index = 0
          
            for x in nums:
                
                if max < x:
                    max = x
                    nums[index] = x
                    index += 1
    
            return index

买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
       
        sum = 0
        index = 0
        length = len(prices)
        while index < len(prices):
                newIndex = index
                flag = 0
                while newIndex < len(prices):
                    x = prices[newIndex]
                    length = len(prices)
                    count = length - 1 if newIndex + 1 >= length - 1 else newIndex + 1
                    behind = prices[count]
                    if x < behind:
                        flag += 1
                    else:
                      break
                    newIndex += 1
                x = prices[index]
                if flag > 0:
                    count = index + flag
                    sum += prices[count] - x
                    index = count
                    index += 1
                else:
                    count = length - 1 if index + 1 >= length - 1 else index + 1
                    if x - prices[count] < 0:
                        sum += prices[count] - x
                        index += 2 #跳过卖出股票那天
                    else:
                        index += 1
        return sum

旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

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

存在重复元素

给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
输入: [1,2,3,1]
输出: true
利用map特性来判断是否有重复的数字

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        
            dict = {}
            for x in nums:
                str1 = str(x)
                dict[str1] = x
            if len(dict) == len(nums):
                return False
            else:
                return True

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
输入: [2,2,1]
输出: 1

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
            length = len(nums)
            index = 0
            only = 0
            if length == 1:
                return nums[0]
            nums.sort()
            while index < length:

                    x = nums[index]
                    count = length - 1 if index + 1 >= length - 1 else index + 1
                    x2 = nums[count]

                    if x != x2:
                        if count == length - 1:
                            only = x2
                        else:
                            only = x
                        index += 1
                    else:
                        index += 2
                        if length - index == 1:
                             index -= 1

            return only

两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
            newNumsDict = {}
            littleNewNumsDict = {}
            newNums = []
            lengthOne = len(nums1)
            lengthTwo = len(nums2)
            flag = 0 #标记从那个数组里获取数组（这里感觉没有必要有点啰嗦😆）
            if lengthOne < lengthTwo:
                length = lengthOne
                flag = 1
            else:
                length = lengthTwo
                flag = 2

            index = 0
            while index < length:
                x = 0
                littleLength = 0
                littleIndex = 0
                if flag == 1:
                    x = nums1[index]
                    littleLength = lengthTwo
                else:
                    x = nums2[index]
                    littleLength = lengthOne
                while littleIndex < littleLength:
                    littleNumber = 0
                    if flag == 1:
                        littleNumber = nums2[littleIndex]
                    else:
                        littleNumber = nums1[littleIndex]
            
                    if x == littleNumber:
                        # 这里是这个算法主要比较的地方根据map key 来判断这个数字是否已经存在 
                        big = newNumsDict.get(str(index))
                        little = littleNewNumsDict.get(str(littleIndex))

                        if little is None and big is None:
                            newNumsDict[str(index)] = x
                            littleNewNumsDict[str(littleIndex)] = x

                            newNums.append(x)

                    littleIndex += 1
                index += 1
            
            return newNums

加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
这个题一开始没有看懂什么意思😝 其实是叫数组转换成整型进行加一计算这样一想还是蛮简单的
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

def plusOne(digits: List[int]) -> List[int]:
    # 进行转换
    number = "".join(map(str, digits))
    # 进行 加1 
    number = int(number) + 1
     # 在转换回去😝
    return list(map(int, list(str(number))))

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
             
            index = 0             
            length = len(nums)    
            while index < length: 
                x = nums[index]   
                if x == 0: 
                #我用数组方式把数据加到后面在进行删除对应位置下标0（我觉得效率要比进行交换要高 但给的时间相比较慢。 添加 和删除 对于数组就是O(1)复杂度）        
                    nums.append(x)
                    del nums[index]   
                    index = 0    
                    # 这个长度也需要进行相应的调正 
                    length -= 1   
                else:             
                    index += 1

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
这个也是利用map key 进行判断

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
                index = 0
                length = len(nums)
                map = {}
                while index < length:
                    x = nums[index]
                    if map.get(target - x) is not None:
                        return [map.get(target - x),index ]
                    map[x] = index
                    index += 1

# 这个和上面差不多 主要思想利用差值进行对比 到达遍历一次（不过这个我把数组进行了排序 下标位置进行改变了 这个提交不成功 但我觉得也是一种方法 故而记录保存一下吧）
class Solution:
def twoSum(nums: List[int], target: int) -> List[int]:
    index = 0
    length = len(nums)
    newNums = []
    oneNumber = nums[0]
    poorNumber = abs(target - oneNumber)
    newNums.append(0)
    while index < length:
        x = nums[index]
        if x == poorNumber:
            newNums.append(index)
        index += 1
    return newNums