上海做网站公司做网站的公司有哪些深圳住房和城乡建设局网站首页

当前位置： 首页 > news >正文

上海做网站公司做网站的公司有哪些,深圳住房和城乡建设局网站首页,企业网站的基本内容以及营销功能,庆阳市住房和城乡建设局网站135. 分发糖果 问题描述 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求#xff0c;给这些孩子分发糖果#xff1a; 每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果#x…135. 分发糖果 问题描述 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求给这些孩子分发糖果 每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 示例 1 输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2 输入ratings [1,2,2] 输出4 解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。提示 n ratings.length1 n 2 * 1040 ratings[i] 2 * 104 解题思路与代码实现 class Solution {public int candy(int[] ratings) {// 糖果数组int[] candies new int[ratings.length];Arrays.fill(candies, 1); // 每个孩子最后分发一颗糖果// 顺序构建糖果数组for (int i 1; i ratings.length; i) {if (ratings[i] ratings[i - 1]) {// 贪心策略求最少故只多发1棵糖果candies[i] candies[i - 1] 1;}}// 逆序构建糖果数组for (int i ratings.length - 2; i 0; i–) {if (ratings[i] ratings[i 1]) {// 判断是否符合题目要求candies[i] Math.max(candies[i], candies[i 1] 1);}}// 糖果数组求和并返回return Arrays.stream(candies).sum();} }踩坑点 如何处理区间问题

1. 根据身高重建队列 问题描述 假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性不一定按顺序。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue 其中 queue[j] [hj, kj] 是队列中第 j 个人的属性queue[0] 是排在队列前面的人。 示例 1 输入people [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释 编号为 0 的人身高为 5 没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 有 2 个身高更高或者相同的人排在他前面即编号为 0 和 1 的人。 编号为 3 的人身高为 6 有 1 个身高更高或者相同的人排在他前面即编号为 1 的人。 编号为 4 的人身高为 4 有 4 个身高更高或者相同的人排在他前面即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 有 1 个身高更高或者相同的人排在他前面即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。示例 2 输入people [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]提示 n ratings.length1 n 2 * 1040 ratings[i] 2 * 104 解题思路与代码实现 class Solution {public int[][] reconstructQueue(int[][] people) {// people数组按照h降序k升序规则排序Arrays.sort(people, (p1, p2) - p1[0] ! p2[0] ? p2[0] - p1[0] : p1[1] - p2[1]);LinkedListint[] resList new LinkedList();for (int i 0; i people.length; i) {resList.add(people[i][1], people[i]);}// 根据身高排名k更新people数组for (int i 0; i people.length; i) {people[i] resList.get(i);}return people;} }452. 用最少数量的箭引爆气球 问题描述 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后可以无限地前进。 给你一个数组 points 返回引爆所有气球所必须射出的 最小 弓箭数 。 示例 1 输入points [[10,16],[2,8],[1,6],[7,12]] 输出2 解释气球可以用2支箭来爆破: -在x 6处射出箭击破气球[2,8]和[1,6]。 -在x 11处发射箭击破气球[10,16]和[7,12]。示例 2 输入points [[1,2],[3,4],[5,6],[7,8]] 输出4 解释每个气球需要射出一支箭总共需要4支箭。示例 3 输入points [[1,2],[2,3],[3,4],[4,5]] 输出2 解释气球可以用2支箭来爆破:

• 在x 2处发射箭击破气球[1,2]和[2,3]。
• 在x 4处射出箭击破气球[3,4]和[4,5]。提示: 1 points.length 105points[i].length 2-231 xstart xend 231 - 1 解题思路与代码实现 class Solution {public int findMinArrowShots(int[][] intervals) {// 按照开始区间升序排序Arrays.sort(intervals, Comparator.comparingInt(o - o[0]));int res 1; // 记录最终结果for (int i 1; i intervals.length; i) {if (intervals[i][0] intervals[i - 1][1]) { // 没有重叠区间res; // 需要再来一只箭} else {// 更新最小结束区间intervals[i][1] Math.min(intervals[i][1], intervals[i - 1][1]);}}return res;} }踩坑点 将问题转化为求非交叉区间数量的问题非交叉区间如[1,3],[2,4]算1个非交叉区间如[1,2],[3,4]算2个非交叉区间

1. 无重叠区间 问题描述 给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。 示例 1: 输入: intervals [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后剩下的区间没有重叠。示例 2: 输入: intervals [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3: 输入: intervals [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间因为它们已经是无重叠的了。提示: 1 intervals.length 105intervals[i].length 2-5 * 104 starti endi 5 * 104 解题思路与代码实现 class Solution {public int eraseOverlapIntervals(int[][] intervals) {// 按照开始区间升序排序Arrays.sort(intervals, Comparator.comparingInt(o - o[0]));// 贪心策略移除区间的数量 intervals数组元素个数 - 非交叉区间数量int res 1; // 记录非交叉区间数量for (int i 1; i intervals.length; i) {if (intervals[i][0] intervals[i - 1][1]) { // 没有交叉区间设定[0,1]和[1,2]非交叉res;} else {// 更新最小结束区间intervals[i][1] Math.min(intervals[i][1], intervals[i - 1][1]);}}return intervals.length - res;} }踩坑点 问题转换移除区间的数量 intervals数组元素个数 - 非交叉区间数量
2. 合并区间 问题描述 以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。 示例 1 输入intervals [[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2 输入intervals [[1,4],[4,5]] 输出[[1,5]] 解释区间 [1,4] 和 [4,5] 可被视为重叠区间。提示 1 intervals.length 104intervals[i].length 20 starti endi 104 解题思路与代码实现 class Solution {public int[][] merge(int[][] intervals) {if (intervals.length 1)return intervals;// 按照开始区间升序排序Arrays.sort(intervals, (o1, o2) - Integer.compare(o1[0], o2[0]));LinkedListint[] resList new LinkedList();resList.addLast(intervals[0]);for (int i 1; i intervals.length; i) {int[] item resList.getLast();// 贪心策略碰到交叉区间就进行合并if (intervals[i][0] item[1]) { // 区间重叠resList.removeLast(); // 合并区间resList.addLast(new int[] { Math.min(item[0], intervals[i][0]), Math.max(item[1], intervals[i][1]) });} else {resList.addLast(intervals[i]);}}// 列表转数组return resList.toArray(new int[resList.size()][]);} } 踩坑点 采用贪心策略先将intervals按开始下标升序排序然后遍历数组相邻的两个区间能合并则进行合并
3. 划分字母区间 问题描述 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。 注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 示例 1 输入s ababcbacadefegdehijhklij 输出[9,7,8] 解释 划分结果为 ababcbaca、defegde、hijhklij 。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。 示例 2 输入s eccbbbbdec 输出[10]提示 1 s.length 500s 仅由小写英文字母组成 解题思路与代码实现 class Solution {public ListInteger partitionLabels(String s) {// 统计各个字符开始和结束位置map的key为字符value为长度为2的数组包含出现开始下标和结束下标MapCharacter, int[] map new HashMap();for (int i 0; i s.length(); i) {char c s.charAt(i);if (!map.containsKey©) { // 首次出现map.put(c, new int[] { i, i });} else { // 再次出现// 更新结束下标map.put(c, new int[] { map.get©[0], i });}}// 转为数组int[][] intervals map.values().toArray(new int[map.size()][]);// 数组按照开始下标升序排序Arrays.sort(intervals, Comparator.comparingInt(o - o[0]));LinkedListint[] resList new LinkedList(); // 记录最终结果区间resList.addLast(intervals[0]);for (int i 1; i intervals.length; i) {int[] item resList.getLast();// 贪心策略碰到交叉区间就进行合并if (intervals[i][0] item[1]) { // 重叠区间// 合并区间resList.removeLast();resList.addLast(new int[] { Math.min(intervals[i][0], item[0]), Math.max(intervals[i][1], item[1]) });} else { // 非重叠区间resList.addLast(intervals[i]);}}// 转换并返回return resList.stream().map(o - o[1] - o[0] 1).collect(Collectors.toList());} }踩坑点 如何进行问题转换这里是先统计各个字符的开始下标和结束下表然后转换为合并区间问题