leetcode 刷题记录，数组部分，代码随想录刷题顺序

leetcode 刷题记录，数组部分，代码随想录刷题顺序

     看了好多攻略，打算第一遍刷题顺序跟着 代码随想录 ：数组、链表、哈希表、字符串、双指针法、栈与队列、二叉树、回溯算法 、贪心算法、动态规划、单调栈

      题外话：小白一枚，打算刷题提高编程能力，由于现在在公司算法部门实习，所以使用python语言，打算明年秋招之前用java或者c++再刷一遍。下面纯记录个人刷题日记及代码。

代码随想录：代码随想录 (programmercarl.com)

DAY 1 704.二分查找

704. 二分查找 - 力扣（LeetCode）

class Solution1:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        
        while left <= right:
            middle = (left + right) // 2

            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                return middle
        return -1

emp1 = Solution1()
emp1.search([-1,3,5,7,9,14,55,48],55)
#输出：6

35.搜索插入位置

class Solution3:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        
        while left <= right:
            middle = (left + right) // 2

            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                return middle
        return right + 1

emp3 = Solution3()
emp3.search([-1,3,5,7,9],8)
#输出：4

34.在排序数组中查找元素的第一个和最后一个位置

class Solution4:
    def search(self, nums, target):
        def result(nums,target):
            left, right = 0, len(nums) - 1
            while left <= right:
                middle = (left + right) // 2
                if nums[middle] < target:
                    left = middle + 1
                elif nums[middle] > target:
                    right = middle - 1
                else:
                    return left
            return -1

        index = result(nums,target)
        if index==-1:return [-1,-1]
        left,right=index,index
        while left -1 >=0 and nums[left - 1] == target: left -=1
        while right+1 < len(nums) and nums[right + 1] == target:right +=1
        print([left,right])

emp4 = Solution4()
nums=[-1,3,5,6,7,9,9,9,9,9]
target=9
emp4.search(nums,target)
#输出：[5,9]

69.x 的平方根

方法一：

class Solution5:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r: #不能漏掉l=r的情况
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

emp5 = Solution5()
emp5.mySqrt(9)
#输出：3

方法二：

​
class Solution6:
    def mySqrt(self, x):
        if x == 0:
            return 0
        
        x0,C = float(x),float(x)
        while True:
            xi = 0.5 * (x0 + C/x0)
            if abs(x0 - xi) < 1e-7:
                break
            x0 = xi
        return int(x0)

emp6 = Solution6()
emp6.mySqrt(10)
#输出：3

​

DAY 2 27.移除元素

方法一：双指针法，快指针、慢指针

class Solution8:
    def removeElement(self, nums,val):
        fast = 0
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] == val:
                continue
            else:
                nums[slow] = nums[fast]
            slow  +=1
        return slow
          
emp8 = Solution8()
nums=[3,2,2,3]
val = 3
length=emp8.removeElement(nums,val)
for i in range(length):
    print(nums[i])
#输出：2
#      2

方法二：双指针法、左指针、右指针

class Solution9:
    def removeElement(self, nums,val):
        right = len(nums)-1
        left = 0
        while left <= right:
            if nums[left] == val:
                nums[left] = nums[right]
                right -= 1
            else:
                left  += 1
        return nums[0:left]

emp9 = Solution9()
nums=[3,2,2,2,3,6,7,5,3]
val = 2
emp9.removeElement(nums,val)
#输出：[3, 3, 5, 7, 3, 6]

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

class Solution10:
    def removeDuplicates(self, nums):
        fast = 1
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] == nums[slow]:
                fast +=1
            else:
                slow  +=1
                nums[slow] = nums[fast]
                
        return nums[0:slow]

emp10 = Solution10()
nums=[3,2,2,2,3,6,7,5,3] 
emp10.removeDuplicates(nums)
#输出：[3, 2, 3, 6, 7, 5]

283.移动零

class Solution11:
    def moveZeroes(self, nums):
        right = 0
        left = 0
        for right in range(len(nums)):
            if nums[right]:
                nums[left],nums[right] = nums[right],nums[left]
                left  += 1
            right +=1
        return nums
  
emp11 = Solution11()
nums=[3,0,2,0,3,6,0] 
emp11.moveZeroes(nums)
#输出：[3, 2, 3, 6, 0, 0, 0]

844.比较含退格的字符串

class Solution12:
    def backspaceCompare(self,s,t):
        def build(str):
            ret = list()
            for i in str:
                if i != '#':
                    ret.append(i)
                elif ret:
                    ret.pop() #保证ret里面有字符才能pop
            return ret
        
        return build(s) == build(t)

emp12 = Solution12()
s='a##c'
t='#a#c'
emp12.backspaceCompare(s,t)
#输出：True

977.有序数组的平方

方法一：直接排序

class Solution13:
    def sortedSquares(self, nums):
        return sorted(num * num for num in nums)

emp13 = Solution13()
nums=(2,3,4,7,8,-1,-3)
emp13.sortedSquares(nums)
#输出：[1, 4, 9, 9, 16, 49, 64]

方法二：双指针法，重点是有序数组，最大值是最右边或者最左边、左右指针 

class Solution14:
    def sortedSquares(self, nums):
        n = len(nums)
        result = [-1]*n
        i,j,k = 0,n-1,n-1
        while i <= j:
            lm = nums[i]**2
            rm = nums[j]**2
            if lm > rm:
                result[k] = lm
                i +=1
            else:
                result[k] = rm
                j -=1
            k -=1
        return result

emp14 = Solution14()
nums=(-3,-1,0,4,6,9)
emp14.sortedSquares(nums)
#输出：[0, 1, 9, 16, 36, 81]

DAY 3 209.长度最小的子数组

滑动窗口、双指针法

class Solution15:
    def minSubArrayLen(self, nums,target):
        res = float("inf") #设为无穷大
        sum = 0
        i = 0
        for j in range(len(nums)):
            sum += nums[j]
            while sum >= target:
                res = min(res,j-i+1)
                sum -= nums[i]
                i += 1
        if res == float("inf"):
            return 0
        else:
            return res

emp15 = Solution15()
nums = (2,3,1,2,4,3)
target = 7
emp15.minSubArrayLen(nums,target )
#输出：2

DAY 4 904.水果成篮

class Solution16:
    def totalFruit(self, fruits: List[int]) -> int:
        ans = i = 0
        count = collections.Counter()
        for j, x in enumerate(fruits):
            count[x] += 1
            while len(count) >= 3:
                count[fruits[i]] -= 1
                if count[fruits[i]] == 0:
                    del count[fruits[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

emp16 = Solution16()
fruits = (2,3,1,2,2,1,3)
emp16.totalFruit(fruits)
#输出：4

DAY 5