栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

力扣记录:贪心算法2中等(3)两个维度权衡问题——135 分发糖果,406 根据身高重建队列

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

力扣记录:贪心算法2中等(3)两个维度权衡问题——135 分发糖果,406 根据身高重建队列

本次题目
  • 135 分发糖果
  • 406 根据身高重建队列
135 分发糖果
  • 局部最优:分别讨论左右相邻孩子。从前向后遍历,只要右边评分比左边高,则右边孩子糖果加1,否则为1;从后向前遍历,只要左边评分比右边高,则左边孩子糖果加1。此时针对每个孩子都有两个选择(比左边大1或比右边大1),选择两者中最大的才满足条件。
  • 注意:数组求和先转为stream后(Arrays.stream())再求和(sum())。
class Solution {
    public int candy(int[] ratings) {
        //分别讨论左右相邻孩子
        int[] resFromLeft = new int[ratings.length];
        int[] resFromRight = new int[ratings.length];
        //初始化
        resFromLeft[0] = 1;
        resFromRight[resFromRight.length - 1] = 1;
        //从前向后遍历
        for(int i = 1; i < ratings.length; i++){
            //只要右边评分比左边高,则右边孩子糖果加1,否则为1
            if(ratings[i] > ratings[i - 1]){
                resFromLeft[i] = resFromLeft[i - 1] + 1;
            }else{
                resFromLeft[i] = 1;
            }
        }
        //从后向前遍历
        for(int j = ratings.length - 1; j > 0; j--){
            //只要左边评分比右边高,则左边孩子糖果加1
            if(ratings[j - 1] > ratings[j]){
                resFromRight[j - 1] = resFromRight[j] + 1;
            }else{
                resFromRight[j - 1] = 1;
            }
        }
        //针对每个孩子选择两者中最大的才满足条件
        for(int i = 0; i < resFromRight.length; i++){
            if(resFromRight[i] < resFromLeft[i]) resFromRight[i] = resFromLeft[i];
        }
        //返回结果
        return Arrays.stream(resFromRight).sum();
    }
}
406 根据身高重建队列
  • 局部最优:分别考虑身高和前面更高的人个数。先按身高从高到低排序(身高相同前面更高的人个数小的放前面),定义队列(LinkedList),然后按照前面更高的人个数插入。
  • 注意:构造器升序o1-o2;降序o2-o1(o1为右边元素,返回值小于0时交换两者位置)。按下标插入LinkedList中add(index, element)。将LinkedList转为二维数组toArray(new int[二维数组的行][可省略])。
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //分别考虑身高和前面更高的人个数
        //先按身高从高到低排序(身高相同前面更高的人个数小的放前面)
        Arrays.sort(people, (a, b) -> {
            if(a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        //定义队列(LinkedList)
        LinkedList queue = new LinkedList<>();
        //然后按照前面更高的人个数插入
        for(int[] p : people){
            queue.add(p[1], p);
        }
        //返回结果
        return queue.toArray(new int[people.length][]);
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/941083.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号