Python解力扣算法题4（基础）

# 1.求斐波那契数列下标为n的数 （从零开始）
# def fib(n):
#     if n < 2:
#         return n
#
#     p, q, r = 0, 0, 1
#     for i in range(2, n + 1):
#         p, q = q, r
#         r = p + q
#
#     return r#2. 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
# 现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
# 在这段代码中，Counter(nums)会返回一个字典，其中的键是数组中的数，值是这个数在数组中出现的次数。
# 然后，对于字典中的每个数，我们检查x + 1是否在字典中，如果在，那么就更新最长的和谐子序列的长度。
# def findLHS(nums):
#     from collections import Counter
#     count = Counter(nums)
#     # print(count) Counter({2: 3, 3: 2, 1: 1, 5: 1, 7: 1})
#     ans = 0
#     for x in count:
#         if x + 1 in count:
#             ans = max(ans, count[x] + count[x+1])
#     return ans
# print(findLHS([1,3,2,2,5,2,3,7]))# 3.假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
# 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？
# 能则返回 true ，不能则返回 false 。
# def canPlaceFlowers(flowerbed, n):
#     # count用来检测当前种了几朵花
#     count = 0
#     flowerbed = [0] + flowerbed + [0]
#     # len(flowerbed) - 1是为了后面遍历flowerbed[i + 1]防止越界
#     for i in range(1, len(flowerbed) - 1):
#         if flowerbed[i - 1] == 0 and flowerbed[i] == 0 and flowerbed[i + 1] == 0:
#             flowerbed[i] = 1
#             count += 1
#         if count >= n:
#             return True
#     return False
# print(canPlaceFlowers([1,0,0,0,1],1))# 4.给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
# 法1 超时
# def maximumProduct(nums):
#     max=nums[0]*nums[1]*nums[2]
#     for i in range(0,len(nums)):
#         for j in range(i+1,len(nums)):
#             for k in range(j+1,len(nums)):
#                 if nums[i]*nums[j]*nums[k]>max:
#                     max=nums[i]*nums[j]*nums[k]
#     return max# 法2
# def maximumProduct(nums):
#     nums.sort()
#     # 两个最小的数和最大的数的乘积
#     min_product = nums[0] * nums[1] * nums[-1]
#     # 三个最大的数的乘积
#     max_product = nums[-1] * nums[-2] * nums[-3]
#     return max(min_product, max_product)
# print(maximumProduct([-1,-2,-3]))# 5.给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
# 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
# 任何误差小于 10-5 的答案都将被视为正确答案。
# def findMaxAverage(nums, k):
#     maxtotal = total = sum(nums[:k])
#     n = len(nums)
#     for i in range(k, n):
#         total = total - nums[i - k] + nums[i]
#         maxtotal = max(total, maxtotal)
#     return maxtotal / k
# print(findMaxAverage([1,12,-5,-6,50,3],4))# 6.集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
# 给定一个数组 nums 代表了集合 S 发生错误后的结果。
# 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
# def findErrorNums(nums):
#     total = sum(range(1, len(nums) + 1))
#     num = total - sum(set(nums))
#     diff = total - sum(nums)
# 我（错误的）离正确的（3）少了一个，所以我（错误的）是2
#     return [num - diff, num]# 7.给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
# def reverseWords(s):
#    s=s.split(" ")
#    for i in range(len(s)):
#       s[i]=s[i][::-1]
#    #  用空格连接s中的每个元素并返回连接后的字符串
#    return " ".join(s)
#
# print(reverseWords("Let's take LeetCode contest"))# 8.给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
# 返回该 最大总和 。
# 容易想到答案就是将列表排序后，每隔一个取一个数，这些数相加就是满足题意的最大总和
# def arrayPairSum(nums):
#    nums.sort()
#    return sum(nums[::2])
# print(arrayPairSum([6,2,6,5,1,2]))# 9.在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
# 移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。
# 如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
# def judgeCircle(moves):
#     num = 0
#     num1 = 0
#     for i in moves:
#         if i == "U":
#             num += 1
#         if i == "D":
#             num -= 1
#         if i == "R":
#             num1 += 2
#         if i == "L":
#             num1 -= 2
#     return num == 0 and num1 == 0#print(judgeCircle("UDDUURLRLLRRUDUDLLRLURLRLRLUUDLULRULRLDDDUDDDDLRRDDRDRLRLURRLLRUDURULULRDRDLURLUDRRLRLDDLUUULUDUUUUL"))# 10.给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度
# def findLengthOfLCIS(nums):
#     count=1
#     max=0
#     if len(nums)==1:
#         return 1
#     for i in range(len(nums)-1):
#         if nums[i+1]>nums[i]:
#             count+=1
#         else:
#             count=1
#         if count>max:
#             max=count
#     return max
#
# print(findLengthOfLCIS([1,3,5,4,7]))# 11.给你一个字符串 s，最多 可以从中删除一个字符。
# def validPalindrome(self, s):
#     isPalindrome = lambda x : x == x[::-1]
#     left, right = 0, len(s) - 1
#     while left <= right:
#         if s[left] == s[right]:
#             left += 1
#             right -= 1
#         else:
#             return isPalindrome(s[left + 1 : right + 1]) or isPalindrome(s[left: right])
#     return True
# print(validPalindrome("abca"))# 12.你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
# 比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
# 整数 x - 表示本回合新获得分数 x
# "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
# "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
# "C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
# 请你返回记录中所有得分的总和。
# def calPoints(ops):
#     ans = 0
#     points = []
#     for op in ops:
#         if op == '+':
#             pt = points[-1] + points[-2]
#         elif op == 'D':
#             pt = points[-1] * 2
#         elif op == 'C':
#             ans -= points.pop()
#             continue
#         else:
#             pt = int(op)
#         ans += pt
#         points.append(pt)
#     return ans
# print(calPoints(["5","2","C","D","+"]))# 13.给你一个整数数组 nums ，请计算数组的 中心下标 。
# 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
# 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
# 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。# 这题要求某个区间的元素之和，立马想到 preSum 这个方法。
# 它的计算方法是从左向右遍历数组，当遍历到数组的 i 位置时，preSum表示 i 位置左边的元素之和。
# 我们提前计算出所有元素之和 sums_，那么 sums_ - preSum - nums[i] 就是 i 位置右边元素之和。
# 如果 preSum == sums_ - preSum - nums[i]，那么 i 就是满足题目含义的「中心索引」位置。
# 如果遍历完数组，都没有发现满足题意的「中心索引」，那么返回 -1 .# def pivotIndex(nums):
#     N = len(nums)
#     sums_ = sum(nums)
#     preSum = 0
#     for i in range(N):
#         if preSum == sums_ - preSum - nums[i]:
#             return i
#         preSum += nums[i]
#     return -1
#
# print(pivotIndex([1, 7, 3, 6, 5, 6]))# 14.自除数 是指可以被它包含的每一位数整除的数。
# 例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
# 自除数 不允许包含 0 。
# 给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right]（包括两个端点）内所有的 自除数 。
# def selfDividingNumbers(left, right):
#    list1=[]
#    for i in range(left,right+1):
#        if i==0:
#            continue
#        digits = []
#        list2=[int(j) for j in str(i)]
#        n=len(list2)
#        count=0
#        for j in list2:
#           if j==0:
#               continue
#           if i % j==0:
#               count+=1
#        if count==n:
#           list1.append(i)
#    return list1
#
# print(selfDividingNumbers(1,22))# 15.Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
# 医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。
# 给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。
# def distributeCandies(candyType):
#     num=len(candyType)
#     num=num//2
#     candy=set(candyType)
#     if len(candy)==num:
#         return num
#     elif len(candy)>num:
#         return num
#     else:
#         return len(candy)
#
#
# print(distributeCandies([6,6,6,6]))