小奥的学习笔记

  • 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日 993点热度 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:一种基于深度滤波的全频带音频低复杂度语音增强框架
算一下暑假还没做完的事情 创作共用许可协议介绍 小花豆生活第12~14天:南京青奥会之旅[Nanjing2014] 关于更新github、微信公众号和博客周期的说明 iNove新春2010主题[本博客2010新年主题] 小奥の专属领地手机版二维码访问上线
标签聚合
Python linux 生活 Java 高中 leetcode 算法 鸟哥的linux私房菜 python学习 学习
最近评论
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号