小奥的学习笔记

  • 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题目解析(191113):169&198

2019年11月13日 695点热度 0人点赞 0条评论

Leetcode 169:求众数

题目描述

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。

示例

示例1:
输入: [3,2,3]
输出: 3

示例2:
输入: [2,2,1,1,1,2,2]
输出: 2

解题思路1

由于众数是出现次数大于n/2的数字,所以第n/2个数字已经是众数。故可以采用快速排序方法。

代码实现1

int partition(vector<int>& nums, int left, int right)
{
    int start = left, end = right;
    int povit = nums[start];
    while (start < end)
    {
        while ((start < end) && (nums[end] >= povit))
            --end;
        nums[start] = nums[end];
        while ((start < end) && (nums[start] < povit))
            ++start;
        nums[end] = nums[start];
        nums[start] = povit;
    }
    return start;
}

int majorityElement(vector<int>& nums) {
    int nlen = nums.size();
    int k = nlen / 2;
    int start = 0, end = nlen - 1;
    int target = 0;
    while (start <= end)
    {
        int mid = partition(nums, start, end);
        if (mid == k )
        {
            target = nums[mid];
            break;
        }
        else if (mid > k )
            end = mid;
        else
            start = mid + 1;
    }
    return target;

}

复杂度1

运行时间

时间复杂度:O(nlogn)。空间复杂度:O(1)。

解题思路2

参见:https://leetcode-cn.com/problems/majority-element/solution/du-le-le-bu-ru-zhong-le-le-ru-he-zhuang-bi-de-qiu-/

代码实现2


int majorityElement(vector<int>& nums) {     int can = nums[0], count = 1;     for (int i = 1; i < nums.size(); i++)     {         if (count == 0)         {             can = nums[i];             count = 1;         }         else if (nums[i] == can) {             ++count;         }         else { --count; }                  }     return can; }

复杂度2

运行时间

时间复杂度:O(n)总共只有一个循环,因此时间复杂度为 O(n)。
空间复杂度:O(1)只需要常数级别的额外空间,因此空间复杂度为 O(1)。

Leetcode 198:打家劫舍

题目描述

是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例

示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路

动态规划,状态转移方程为

dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])

代码实现


int rob(vector<int>& nums) {     vector<int>dp(nums.size() + 1, 0);     for (int i = 1; i <= nums.size(); i++)     {         if (i == 1) {             dp[i] = nums[i-1];         }else             dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);     }     return dp[nums.size()]; }

复杂度

运行时间

时间复杂度:O(n)。其中 n为房子的数量。空间复杂度:O(1)。

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

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
这几天很忙,很忙,很忙! Java语言程序设计【学堂在线】(第七章)整理 英语四六级写作25个加分句型 数据结构【浙江大学】(第9节)整理 2017考研最后33天复习计划 Java语言程序设计(进阶)(第七章)整理
标签聚合
算法 学习 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号