周赛笔记209


第一题: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 平面上的整数坐标。

最开始,你面向东方进行观测。你 不能 进行移动改变位置,但可以通过 自转 调整观测角度。换句话说,posxposy 不能改变。你的视野范围的角度用 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,做题还是有好处


文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录