力扣随机题

二叉树中的第K大层和

题目

2583. 二叉树中的第 K 大层和 - 力扣（LeetCode）

思路

递归计算每层的和，然后排序获得第k个最大和

代码

public long kthLargestLevelSum(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }
        List<Long> list = new ArrayList<>();
        fun(list, root, 0);
        list.sort(Comparator.reverseOrder());
        if (list.size() < k) {
            return -1;
        }
        return list.get(k - 1);
    }

    private void fun(List<Long> list, TreeNode node, int k) {
        if (node == null) {
            return;
        }
        if (k >= list.size()) {
            list.add((long) node.val);
        } else {
            list.set(k, list.get(k) + node.val);
        }
        fun(list, node.left, k + 1);
        fun(list, node.right, k + 1);
    }

最大或值

题目

2680. 最大或值 - 力扣（LeetCode）

思路

• leftOr 和 rightOr 数组：用于分别存储从左到右和从右到左的累积按位或结果。
  • leftOr[i] 表示从数组开头到 i 的所有元素的按位或。
  • rightOr[i] 表示从数组结尾到 i 的所有元素的按位或。
• 计算新的按位或：
  • 对于每个元素 nums[i]，它的左侧按位或结果是 left[i - 1]，右侧按位或结果是 right[i + 1]。
  • 然后将 nums[i] 乘以 2 的 k 次方，得到新的数 t。
  • 将 left[i - 1]、t和 right[i + 1] 进行按位或，得到更新后的按位或结果。
• 最大化按位或结果：
  • 对于每个元素进行操作后，更新最大的按位或结果。

代码

public long maximumOr(int[] nums, int k) {
        if(nums.length==0){
            return 0;
        }
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        left[0]=nums[0];
        for(int i=1;i< nums.length;i++){
            left[i]=left[i-1]|nums[i];
        }
        right[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length- 2; i >= 0; i--) {
            right[i] = right[i + 1] | nums[i];
        }
        long max = 0;
        for (int i=0;i< nums.length;i++) {
            long t = nums[i] * (1L << k);
            long l = i > 0 ? left[i - 1] : 0;
            long r = i < nums.length - 1 ? right[i + 1] : 0;
            long cur = l|t|r;
            max = Math.max(max, cur);
        }
        return max;
    }

美丽下标对的数目

题目

2748. 美丽下标对的数目 - 力扣（LeetCode）

思路

模拟，首先是双重遍历数组

每次遍历获取nums[i]的第一个数字，nums[j]的最后一个数字

判断是否互质，互质则sum++

代码

public int countBeautifulPairs(int[] nums) {
        int sum = 0,n = nums.length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int a = nums[i];
                while(a>10){
                    a=a/10;
                }
                int b = nums[j]%10;
                if(gcd(a,b)){
                    sum++;
                }
            }
        }
        return sum;
    }

    private boolean gcd(int x,int y){
        for(int i=2;i<=Math.min(x,y);i++){
            if(x%i==0&&y%i==0){
                return false;
            }
        }
        return true;
    }

移除字符串中的尾随零

题目

2710. 移除字符串中的尾随零 - 力扣（LeetCode）

思路

从尾部开始遍历字符串，遇到0就删除，遇到其他的直接跳出

代码

public String removeTrailingZeros(String num) {
        int n = num.length();
        StringBuilder sb = new StringBuilder(num);
        for(int i=n-1;i>=0;i--){
            if(num.charAt(i)=='0'){
                sb.deleteCharAt(i);
            }else{
                break;
            }
        }
        return sb.toString();
    }