第一题：https://leetcode-cn.com/problems/special-array-with-x-elements-greater-than-or-equal-x/
第二题：https://leetcode-cn.com/problems/even-odd-tree/
第三题：https://leetcode-cn.com/problems/maximum-number-of-visible-points/
第四题：https://leetcode-cn.com/problems/minimum-one-bit-operations-to-make-integers-zero/
一、特殊数组的特征值
给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
class Solution:
def specialArray(self, nums: List[int]) -> int:
nums.sort()
n=len(nums)
for x in range(nums[-1]+1): # 特征值的遍历
if x==(n-bisect_left(nums,x)):
return x
return -1
# nums.sort(reverse=True)
# sorted(nums,reverse=True)
# 今天bisect对递减的数组出错了，未知原因
二、奇偶树
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
class Solution:
def isEvenOddTree(self, root: TreeNode) -> bool:
ans=[]
def dfs(node,depth):
if node:
if len(ans)==depth: ans.append([])
ans[depth].append(node.val)
dfs(node.left,depth+1)
dfs(node.right,depth+1)
dfs(root,0)
for depth,nums in enumerate(ans):
flag=depth%2
for num in nums:
if (depth+num)%2==0: return False
if flag: #奇数
if sorted(nums,reverse=True)!=nums: return False
if len(list(set(nums)))!= len(nums): return False
else: #偶数
if sorted(nums)!=nums: return False
if len(list(set(nums)))!= len(nums): return False
return True
三、可见点的最大数目
给你一个点数组 points 和一个表示角度的整数 angle ，你的位置是 location ，其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。
最开始，你面向东方进行观测。你 不能 进行移动改变位置，但可以通过 自转 调整观测角度。换句话说，posx 和 posy 不能改变。你的视野范围的角度用 angle 表示， 这决定了你观测任意方向时可以多宽。设 d 为逆时针旋转的度数，那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。
class Solution:
def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
ret, n = 0, len(points)
a = []
for x in points:
if x == location:
ret += 1
else:
a.append(atan2(x[1]-location[1], x[0]-location[0]))
a.append(atan2(x[1]-location[1], x[0]-location[0])+2*pi)
a.sort()
j, ans = 0, 0
for i in range(len(a)//2):
while j < i+len(a)//2 and a[j]-a[i] <= angle/180*pi:
j += 1
ans = max(ans, j-i)
return ret+ans
#copy
四、使整数变为 0 的最少操作次数
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
- 翻转
n的二进制表示中最右侧位（第0位）。 - 如果第
(i-1)位为1且从第(i-2)位到第0位都为0，则翻转n的二进制表示中的第i位。
返回将 n 转换为 0 的最小操作次数。
# 格雷码：一种二进制编码方式，相邻码只有一位二进制数不同
# 0001->0001,0010->0011,0011->0010,0100->0110
# 弄清编码方式，总结规律即可。
#方法一：格雷码的解码
# eg:n=1110
# 1. n的左边第二位：1，与前一位已经解码：1，进行异或，1^1=0，所以数字变成10xx
# 2. n的左边第三位：1，与前一位已经解码：0，进行异或，1^0=1，所以数字变成101x
# 3. n的左边第四位：0，与前一位已经解码：1，进行异或，0^1=1，所以数字变成1011
# 所以答案就是1011B=11D
class Solution:
def minimumOneBitOperations(self, n: int) -> int:
nums=[int(i) for i in bin(n)[2:]]
pre=nums[0]
for i in range(1,len(nums)):
nums[i]^=pre
pre=nums[i]
return eval('0b'+''.join([str(i) for i in nums]))
#方法二：
class Solution:
def minimumOneBitOperations(self, p: int) -> int:
dp = {}
def helper(k):
if k in dp:
return dp[k]
if k <= 1:
res = k
else:
m = 1
while m * 2 <= k:
m *= 2
n = m // 2
#print(k, m, n)
if k >= m + n:
res = m + helper(k - m - n)
else:
res = m + helper(k - n)
dp[k] = res
return res
return helper(p)
# copy
小结
考察数学。。。
复习了math, bisect，角度问题
那个树，hhh，做题还是有好处
