您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

653. 两数之和 IV - 输入 BST / 856. 括号的分数 / 137. 只出现一次的数字 II

653. 两数之和 IV - 输入 BST【简单题】【每日一题】

思路:【二叉树中序遍历+哈希set】

  1. 先将二叉搜索树中序遍历存入哈希set。
  2. 遍历哈希set,如果存在表中同时存在num和k-num,且num和k-num不相等,那么返回true;如果遍历结束没有上述情况出现,返回false。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        dfs(set,root);
        for (int num : set) {
            if (set.contains(k-num) && k - num != num){
                return true;
            }
        }
        return false;

    }
    public void dfs(Set<Integer> set,TreeNode root){
        if(root == null){
            return;
        }
        dfs(set,root.left);
        set.add(root.val);
        dfs(set,root.right);
    }
}

856. 括号的分数【中等题】

思路:

  1. 所有的括号分为两种,一种是真的在贡献分数,属于生产者,一种是在增强分数,属于消费者。()属于生产者,其他属于消费者。
  2. 记录每一个生产者括号的深度depth,那么生产者括号对分数的贡献为2*depth。
  3. 将当前生产者生产的分数累加起来,就是最终的分数。

代码:

class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0,depth = 0,len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '('){
                depth++;
            }else {
                depth--;
                if (s.charAt(i-1) == '('){
                    ans += 1 << depth;
                }
            }
        }
        return ans;
    }
}

137. 只出现一次的数字 II【中等题】

思路:

  1. 这题我来不了O(n),我只想AC~
  2. 先对数组进行排序,然后遍历nums,如果nums[i+2]==nums[i],那么说明这个数不是唯一数,i+=3进行下一个数的判断,否则就说明这个数是唯一数,flag置为true表示遍历中找到唯一数,并将唯一数用ans存储,然后退出for循环。
  3. 如果flag为true,说明唯一数在遍历中找到,那么直接返回答案,如果flag为false,说明唯一数不在前面遍历的这些数里,那么现在的i必然是最后一位没被遍历到的,那么此时直接返回nums[i]即可。

代码:

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int i = 0,len = nums.length,ans = 0;
        boolean flag = false;
        while (i<len-2){
            if (nums[i] == nums[i+2]){
                i+=3;
            }else {
                ans = nums[i];
                flag = true;
                break;
            }
        }
        return flag ? ans : nums[i];
    }
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进