小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

leetcode题目解析(191024)

2019年10月24日 986点热度 2人点赞 0条评论

昨天晚上有事情,导致都没有做题,所以计划的做题只能每次拖后一天,但是今天不能再拖了。

Leetcode 406:根据身高重建队列

题目描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意:
总人数少于1100人。

示例

输入:

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题思路

其实这道题我看到之后,第一想到的就是排序,当然怎么排序还是一个问题。后来经过思考之后我想到在排完序之后我可以这样做:根据第2个元素的大小,插入相应的位置,这样,只要我先插入的是第一个元素大的item,后续有item插入同一位置的时候,就可以保证第一个元素小的item前面比它小的item个数是第二个元素大小,第一个元素大的item前面比它小的item个数也是第二个元素所表示的大小。

所以这就要求我们,首先要对第一个元素从大到小排列,第二个元素从小到大排列。具体见代码。

代码示例

    static bool cmp(vector<int> a,vector<int> b)
    {
        if(a[0]>b[0])
            return true;
        if (a[0] == b[0] && a[1] < b[1])
            return true;
        return false;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>>result;
        for(auto p:people)
        {
            result.insert(result.begin()+p[1],p);
        }
        return result;
    }

代码性能

排序复杂度:O(nlogn)
插入复杂度 O(n^2)
总的来说复杂度O(n^2)
复杂度配图

Leetcode 416:分割等和子集

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200

示例

示例1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11]。

示例2:
输入:[1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

解题思路

其实这个题是Leetcode494的简化版本。首先我们可以把本题的题意重写为下面这段话,意思不变:

给定一个非负整数数组,a1, a2, ..., an,。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。返回是否可以使最终数组和为目标数 0 。

由于目标数是0,实际上这个数组所有元素之和sum应该是我们所认为的和的两倍,所以如果sum为奇数,则直接返回false,其它参考494来做即可。

但是目前在leetcode上第74个用例总是出错,问题尚待研究。

代码实现

    bool canPartition(vector<int>& nums) {
    if (nums.empty())
        return false;
    int sum = 0;
    for (auto n : nums)
    {
        sum += n;
    }
    cout << sum << endl;
    if (sum % 2 == 1)
        return false;
    sum /= 2;
    vector<int> dp(sum + 1, INT_MIN);
    dp[0] = 0;
    for (int i = 0; i < nums.size(); i++) {
        int n = nums[i];
        for (int j = sum; j >= n; j--)
        {
            dp[j] = max(dp[j], dp[j - n] + n);
            if (dp[j] < 0)
                dp[j] = INT_MIN;
        }
    }
    return dp.back()==sum;

}
};
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年10月24日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
全国首条市内高铁济莱高铁开工建设 Python网络爬虫与信息提取(第4周)知识点整理 Java语言程序设计【学堂在线】(第三章)整理 新建济南至莱芜高速铁路工程(不含先期开工段)站前工程施工招标中标候选人公示 已修:Python网络爬虫与信息提取【北京理工大学】[2018-08-21] S.V Beijing Travel 4:Very angry day
标签聚合
学习 leetcode linux 高中 Python python学习 算法 鸟哥的linux私房菜 Java 生活
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号