算法刷题-插入区间、杨辉三角、移除链表元素
算法刷题-插入区间、杨辉三角、移除链表元素
共饮一杯无
发布于 2023-02-10 09:59:00
发布于 2023-02-10 09:59:00
文章目录
插入区间
给你一个** 无重叠的**_ ，_按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]提示：
- 0 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= intervals[i][0] <= intervals[i][1] <= 105
- intervals 根据 intervals[i][0] 按 升序 排列
- newInterval.length == 2
- 0 <= newInterval[0] <= newInterval[1] <= 105
public class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
}
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] newIntervals = new int[intervals.length + 1][];
System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
newIntervals[intervals.length] = newInterval;
Arrays.sort(newIntervals, (a, b) -> a[0] - b[0]);
Stack<int[]> stack = new Stack<>();
for (int[] num : newIntervals) {
if (stack.isEmpty()) {
stack.push(num);
continue;
}
int[] arr = stack.peek();
if (arr[1] >= num[0]) {
int[] combine = { arr[0], Math.max(arr[1], num[1]) };
stack.pop();
stack.push(combine);
} else {
stack.push(num);
}
}
return stack.toArray(new int[0][]);
}
}杨辉三角
给定一个非负整数 _numRows，_生成「杨辉三角」的前 _numRows _行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 输入: numRows = 1 输出: [[1]]
提示:
- 1 <= numRows <= 30
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (numRows == 0) {
return res;
}
for (int i = 0; i < numRows; ++i) {
List<Integer> temp = new ArrayList<Integer>();
for (int j = 0; j <= i; ++j) {
temp.add(numberget(i, j));
}
res.add(temp);
}
return res;
}
public int numberget(int i, int j) {
if (j == 0 || i == j) {
return 1;
} else {
return (numberget(i - 1, j - 1) + numberget(i - 1, j));
}
}
}移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
在这里插入图片描述
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5] 示例 2： 输入：head = [], val = 1 输出：[] 示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]
提示：
- 列表中的节点数目在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode top = new ListNode(0);
top.next = head;
ListNode pre = top;
ListNode temp = head;
while (temp != null) {
if (temp.val == val)
pre.next = temp.next;
else
pre = temp;
temp = temp.next;
}
return top.next;
}
}本文内容到此结束了， 如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问💬欢迎各位指出。 主页：共饮一杯无的博客汇总👨💻 保持热爱，奔赴下一场山海。🏃🏃🏃
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-02-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录