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;
}
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;
}
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;
}