# 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]))
