21-04-06刷题记录35

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路

刚拿到手受到之前的题目的影响。还是想着交换。
但是对于这个题,只要求返回符合要求的大小,也就是前半段,后面的相当于丢弃,对这一点清楚就很好做了
其次在判断是否重复的时候,只要判断当前元素和前面的第二个是否相等即可

完整代码

public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int slow = 0;
        for(int i = 0; i < n; i++){
            if(slow < 2 || nums[i] != nums[slow - 2]){
                nums[slow] = nums[i];
                slow++;
            }
        }
        return slow;

    }

21-04-06刷题记录35

781. 森林中的兔子

森林中,每个兔子都有颜色。其中一些兔子(可能是全部)告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

思路

这个题用hash表很简单
我们存放所有有相同答案的key,同时注意,有相同答案的兔子是否超过了本身答案数量+1
key:兔子的答案
value:有相同兔子的答案

完整代码

public int numRabbits(int[] answers) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int sum = 0;
        for(int i = 0; i < answers.length; i++){
            if(!map.containsKey(answers[i])){
                map.put(answers[i], 1);
            }else{
                if(map.get(answers[i]) == answers[i] + 1){
                    sum += map.get(answers[i]);
                    map.put(answers[i], 1);
                }else{
                    map.put(answers[i], map.get(answers[i]) + 1);
                }
            }
        }
        for(int e : map.keySet()){
            sum += (e + 1);
        }
        return sum;


    }

21-04-06刷题记录35

102. 二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

思路

这个题的重点是每一层都需要单独输出
那么我们需要记下每一层对应的结点。
这里用当前大小记录是真的精妙哇~

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> que = new ArrayDeque<>();
        if(root == null){
            return ans;
        }
        que.add(root);
        TreeNode temp = null;
        while(!que.isEmpty()){
            int curSize = que.size();
            List<Integer> list = new ArrayList<>();
            while(!que.isEmpty() && curSize != 0){
                temp = que.poll();
                list.add(temp.val);
                curSize--;
                if(temp.left != null){
                    que.add(temp.left);
                }
                if(temp.right != null){
                    que.add(temp.right);
                }
            }
            ans.add(list);
        }
        return ans;

    }

21-04-06刷题记录35

上一篇:12、SEO工程师指南 - 软件项目角色指南系列文章


下一篇:swig编译GDAL的C#库时遇到的代码安全问题及解决方法