算法刷题-插入区间、杨辉三角、移除链表元素

插入区间

给你一个无重叠的，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

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

本文内容到此结束了， 如有收获欢迎点赞

标签：newInterval,ListNode,val,示例,int,链表,intervals,移除,杨辉三角
From： https://blog.51cto.com/zhanjq/6051775