首页 / 算法 / 每日算法17_2020-11-23
每日算法17_2020-11-23
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了每日算法17_2020-11-23，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6484字，纯文字阅读大概需要10分钟。
内容图文
题目一
452. 用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
示例 4：
输入：points = [[1,2]]
输出：1
示例 5：
输入：points = [[2,3],[2,3]]
输出：1
提示：
0 <= points.length <= 104
points[i].length == 2
-231 <= xstart < xend <= 231 - 1
我没做出来，看的官方答案
class Solution {
public int findMinArrowShots(int[][] points) {
if(points == null || points.length == 0) return 0;
if(points.length == 1) return 1;
// 先排序 定制排序 按右边界来排序
Arrays.sort(points, new Comparator<int[]>() {
@Override
public int compare(int[] pLeft, int[] pRight) {
return Integer.compare(pLeft[1], pRight[1]);
}
});
// lambda表达式写法
// Arrays.sort(points, (p1, p2) -> Integer.compare(p1[1], p2[1]));
int position = points[0][1]; // 先把第一支箭指向排序后第一个气球的右边界
int result = 1; // 气球为0的情况在最顶上已经有了，这里肯定是有气球，所以最少为1
for(int[] ballon : points){
// 遍历每个气球
if(ballon[0] > position){
// 当气球的左边距大于右边界说明要多射一支箭
// 同时由于是排过序的，后续的x轴肯定也是大于第一支箭的
// 因此，第二只箭的位置为放在满足当前判断条件的气球的右边界处,后续的气球的右边界肯定是大于这个气球的
position = ballon[1];
result++;
}
}
return result;
}
}
复杂度分析
-
时间复杂度：O(n\log n)，其中 n是数组 points 的长度。排序的时间复杂度为 O(n \log n)，对所有气球进行遍历并计算答案的时间复杂度为 O(n)，其在渐进意义下小于前者，因此可以忽略。
-
空间复杂度：O(log n)，即为排序需要使用的栈空间。
题目二
117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
树中的节点数小于 6000
-100 <= node.val <= 100
我的答案，层序遍历
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root == null || (root.left == null && root.right == null)) return root;
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
Node last = new Node(); // 用于记录同层上一个元素
int queueSize = queue.size(); // 这一层有多少个元素
for(int i = 0; i < queueSize; i++){
// 遍历每一层的元素，先从队列中取出当前的节点
Node node = queue.poll();
// System.out.print(node.val + ",");
if (i-1 >= 0) last.next = node; // 同层后续的进来的元素为前一个元素的next
last = node; // 让当前的node变为上一个元素
if(node.left != null){
queue.offer(node.left); // 左节点不为空，左节点入队
}
if(node.right != null){
queue.offer(node.right);
}
}
}
return root;
}
}
复杂度分析
记树上的点的个数为 N。
- 时间复杂度：O(N)。我们需要遍历这棵树上所有的点，时间复杂度为 O(N)。
- 空间复杂度：O(N)。即队列的空间代价。
方法二：使用已建立的 next 指针
// next指针链表的方法
public static Node connext2(Node root){
if(root == null) return root;
// 把每一层看做是链表
Node current = root; // 表示当前链表的节点
while(current != null){ // 直到最后一个元素
// 先在准备next连接的链表（层）前加一个哑节点
// 同时可以方便串联下一层
Node dummy = new Node(0); // 哑节点只为指明链表起点
// pre节点用于指明哪个节点 准备 连接next
Node pre = dummy;
// 开始遍历当前层的链表
while(current != null){
if(current.left != null){
// 先从左子树开始
// 对于一开始，pre节点在哑节点上，哑节点在当前层链表的前面
// 那么可以先将哑节点与第一个节点链接在一起
pre.next = current.left;
// 然后让pre移动到当前层链表第一个节点上
pre = pre.next;
}
if(current.right != null){
// 右子树同左子树一样
// pre连接完左子树，该量级右子树了
pre.next = current.right;
pre = pre.next;
}
// 如果current是root几点那么其next为null，这里赋值后就会跳出循环
// 但是上面的代码，已经让root节点下的左右节点通过next连接在一起了
current = current.next;
// 如果不是root节点，而是root下面的已经连接了next的节点
// 如果是第二层，上面一次循环将root.left的左右子树通过next连接起来了
// 那么就要去连接root.right的左右子树
}
// 当前层的节点的左右子树都通过next连接起来后
// 去下一层（即当前层的左右子树的层）准备next连接再下一层的左右子树了
// 由于哑节点在当前层的链表（即下一层）的前面
// 那么哑节点的next就是下一层的起点
current = dummy.next;
}
return root;
}
复杂度分析
- 时间复杂度：O(N)。分析同「方法一」。
- 空间复杂度：O(1)。
题目三
1512. 好数对的数目
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对
示例 3：
输入：nums = [1,2,3]
输出：0
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
我的答案 暴力法
class Solution {
public int numIdenticalPairs(int[] nums) {
int n = 0;
for(int i = 0; i < nums.length; i++){
for(int j = i; j < nums.length; j++){
if(i < j && nums[i] == nums[j])
n++;
}
}
return n;
}
}
复杂度分析
- 时间复杂度：O(n^2)。
- 空间复杂度：O(1)。
官方组合计数法
class Solution {
public int numIdenticalPairs(int[] nums) {
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int num : nums) {
m.put(num, m.getOrDefault(num, 0) + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
int v = entry.getValue();
ans += v * (v - 1) / 2;
}
return ans;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)，即哈希表使用到的辅助空间的空间代价。
内容总结
以上是互联网集市为您收集整理的每日算法17_2020-11-23全部内容，希望文章能够帮你解决每日算法17_2020-11-23所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。