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

LeetCode 热题 C++ 169. 多数元素 10. 正则表达式匹配 155. 最小栈

力扣169

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入:nums = [3,2,3]
输出:3

示例 2:

输入:nums = [2,2,1,1,1,2,2]
输出:2

提示:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路:

摩尔投票法。

因为最多的数字一定是大于n/2。所以不存在诸如3 3 2 4或者2 2 3 3这样的情况。也就是说,符合题目要求的情况都类似于 2 1 2,1 1 1 1 2 2这样子。

那么我们只要把相同数量的数字互相抵消,最后留下的就一定是最多的数字。

用ans记录当前哪个数字最多,count用来投票,遇到相同的+1,遇到不同的-1,当count=0的时候,更换ans,并重置count=1。

代码:

class Solution {
public:int majorityElement(vector<int>& nums) {int ans=nums[0];int count=1;for(int i=0;i<nums.size();i++){if(ans==nums[i])count++;else if(--count==0){ans=nums[i];count=1;}}return ans;}
};

力扣10

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

示例 1:

输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa", p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:s = "ab", p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。

提示:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 30
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母,以及字符 . 和 *
  • 保证每次出现字符 * 时,前面都匹配到有效的字符

思路:

xx题目,真的无语,题目意思表达地乱七八糟,全靠解答错误的答案去判断到底是什么意思。

代码:

class Solution {
public:bool isMatch(string s, string p) {//if(p.length()>s.length())return 0;bool dp[35][35];memset(dp,0,sizeof(dp));dp[0][0] = true;//if(p[p.length()-1]!='.'&&p[p.length()-1]!='*'&&p[p[p.length()-1]!=s[s.length()-1]])return 0;for (int j = 1; j < p.length() + 1; j++) {if (p[j - 1] == '*') dp[0][j] = dp[0][j - 2];}for(int i=1;i<=s.length();i++){for(int j=1;j<=p.length();j++){   if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {dp[i][j] = dp[i - 1][j - 1];} else if (p[j - 1] == '*') {if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];} else {dp[i][j] = dp[i][j - 2];}}/*if(p[j-1]=='*'&&p[j-2]=='.')dp[i][j]=dp[i-1][j-1]+1;else if(p[j-1]=='*'&&p[j-2]==s[i-1])dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]+1);else if(p[j-1]=='.'||p[j-1]==s[i-1])dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j-1]);else dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]);*///cout<<dp[i][j]<<" ";}//cout<<endl;}//cout<<dp[s.length()][p.length()]<<" "<<s.length()<<endl;return dp[s.length()][p.length()];}
};

力扣115

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出:
[null,null,null,null,-3,null,0,-2]解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

  • -231 <= val <= 231 - 1
  • poptopgetMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

思路:

用栈每次存取一个pair结构,pair的first是当前存入值,pair的second每次更新当前最小值。因为是栈的原因,每次存进来都在栈顶,所以很好去更新最小值。就是在一个元素出栈的时候,把总最小值变更为当前栈顶的second就好了。

代码:

class MinStack {
public:stack<pair<int,int> > s;int mmin=INT_MAX;MinStack() {}void push(int val) {if(val<mmin)mmin=val;s.push(pair<int,int>(val,mmin));}void pop() {s.pop();if(s.size()==0)mmin=INT_MAX;else mmin=s.top().second;}int top() {return s.top().first;}int getMin() {return s.top().second;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

 

相关文章:

LeetCode 热题 C++ 169. 多数元素 10. 正则表达式匹配 155. 最小栈

力扣169 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a;nums [3,2,3] 输出&#xff1…...

Clickhouse学习:MergeTree

MergeTree一、MergeTree逻辑存储结构二、MergeTree物理存储结构三、总结一、MergeTree逻辑存储结构 如上图所示,在排序键(CountrID、Date)上做索引,数据会按照这两个字段先后排序ClickHouse是稀疏索引,每隔8192行做一个索引,如(a,1),(a,2),比如想查a,要读取[0,3)之间的内容,稀疏…...

【java基础】包装类,自动装箱和自动拆箱

文章目录基本介绍包装类自动装箱自动拆箱包装类注意事项包装类比较包装器内容不可变基本介绍 有时&#xff0c;需要将int这样的基本类型转换为对象。所有的基本类型都有一个与之对应的类。 例如&#xff0c;Integer类对应基本类型int。通常&#xff0c;这些类称为包装器&#…...

Android笔记(二十五):两种sdk热更插件资源加载方案

背景 在研究sdk插件化热更新方式的过程中总结出了两套插件资源加载方案&#xff0c;在此记录下 资源热更方式 方式一&#xff1a;合并所有插件资源 需要解决资源id冲突问题 资源ID值一共4个字段&#xff0c;由三部分组成&#xff1a;PackageIdTypeIdEntryId PackageId&…...

spring框架--全面详解(学习笔记)

目录 1.Spring是什么 2.Spring 框架特点 3.Spring体系结构 4.Spring开发环境搭建 5.spring中IOC和DI 6.Spring中bean的生命周期 7.Spring Bean作用域 8.spring注解开发 9.Spring框架中AOP&#xff08;Aspect Oriented Programming&#xff09; 10.AOP 实现分类 11.A…...

2023年CDGA考试模拟题库(401-500)

2023年CDGA考试模拟题库(401-500) 401.数据管理战略的SMART原则指的是哪项? [1分] A.具体 、高质量、可操作 、现实、有时间限制 B.具体、可衡量、可检验、现实、有时间限制 C.具体、可衡量、可操作、现实、有时间限制 D.具体、高质量、可检验、现实12-24个月的目标 答…...

软件设计师备考文档

cpu 计算机的基本硬件系统&#xff1a;运算器、控制器、存储器、输入设备、输出设备 cpu负责获取程序指令&#xff0c;对指令进行译码并加以执行 * cpu的功能控制器&#xff08;保证程序正常执行&#xff0c;处理异常事件&#xff09; 程序控制操作控制运算器&#xff08;只能…...

Javascript的API基本内容(一)

一、获取DOM对象 querySelector 满足条件的第一个元素 querySelectorAll 满足条件的元素集合 返回伪数组 document.getElementById 专门获取元素类型节点&#xff0c;根据标签的 id 属性查找 二、操作元素内容 通过修改 DOM 的文本内容&#xff0c;动态改变网页的内容。 inn…...

10、最小公倍数

法一&#xff1a; #include <stdio.h>int main(){int a,b;scanf("%d%d",&a,&b);int m a>b?a:b;//m表示a,b之间的较大值while(1){if(m%a0&&m%b0){break;}m;}printf("%d",m);return 0; }法二&#xff1a;a*i%b0成立 #include &…...

【vue】vue2.x项目中使用md文件

一、Vue项目展示md文件的三种方式 1、将md文件 导入为 html 生成的标题标签自带具有id属性&#xff0c;值为标题内容&#xff1b; <h2 id"测试">测试</h2> # 处理md为html字符串 yarn add markdown-loader # 处理字符串&#xff0c;用于导出显示 yarn a…...

操作系统权限提升(十三)之绕过UAC提权-MSF和CS绕过UAC提权

系列文章 操作系统权限提升(十二)之绕过UAC提权-Windows UAC概述 注&#xff1a;阅读本编文章前&#xff0c;请先阅读系列文章&#xff0c;以免造成看不懂的情况&#xff01;&#xff01; MSF和CS绕过UAC提权 CS绕过UAC提权 拿到一个普通管理员的SHELL,在CS中没有*号代表有…...

快速排序+快速定位

快速排序算法采用了分治法以及递归作为解决问题的思想。在计算机科学中&#xff0c;分治法是一种很重要的算法。字面上的解释是“分而治之”&#xff0c;就是把一个复杂的问题分成两个或更多的相同或相似的子问题&#xff0c;再把子问题分成更小的子问题……直到最后子问题可以…...

nginx http rewrite module 详解

大家好&#xff0c;我是 17。 今天和大家聊聊 nginx http rewrite module 。 简单来说&#xff0c; ngx_http_rewrite_module module 用正则匹配请求&#xff0c;改写请求&#xff0c;然后做跳转。可以是内部跳转&#xff0c;也可以是外部跳转。 学习这个模块的时候&#xf…...

机器学习可解释性一(LIME)

随着深度学习的发展&#xff0c;越来越多的模型诞生&#xff0c;并且在训练集和测试集上的表现甚至于高于人类&#xff0c;但是深度学习一直被认为是一个黑盒模型&#xff0c;我们通俗的认为&#xff0c;经过训练后&#xff0c;机器学习到了数据中的特征&#xff0c;进而可以正…...

CV学习笔记-MobileNet

MobileNet 文章目录MobileNet1. MobileNet概述2. 深度可分离卷积&#xff08;depthwise separable convolution&#xff09;2.1 深度可分离卷积通俗理解2.2 深度可分离卷积对于参数的优化3. MobileNet网络结构4. 代码实现4.1 卷积块4.2 深度可分离卷积块4.3 MobileNet定义4.4 完…...

C++进阶——继承

C进阶——继承 1.继承的概念及定义 面向对象三大特性&#xff1a;封装、继承、多态。 概念&#xff1a; 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特 性的基础上进行扩展&#xff0c;增加功能&#xff0c;这…...

数据结构---单链表

专栏&#xff1a;数据结构 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;从零开始&#xff0c;数据结构&#xff01;&#xff01; 单链表前言顺序表的缺陷链表的概念以及结构链表接口实现打印链表中的元素SLTPrintphead->next!NULL和phead!NULL的区别开辟空间SLTNewNod…...

redis数据结构的底层实现

文章目录一.引言二.redis的特点三.Redis的数据结构a.字符串b.hashc.listd.sete.zset(有序集合)一.引言 redis是一个开源的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、key-value的NoSQL数据库。 通常使用redis作为缓存中间件来降低数据库的压力&#xff0c;除此…...

【JavaSE】复习(进阶)

文章目录1.final关键字2.常量3.抽象类3.1概括3.2 抽象方法4. 接口4.1 接口在开发中的作用4.2类型和类型之间的关系4.3抽象类和接口的区别5.包机制和import5.1 包机制5.2 import6.访问控制权限7.Object7.1 toString()7.2 equals()7.3 String类重写了toString和equals8.内部类8.1…...

Java 主流日志工具库

日志系统 java.util.logging (JUL) JDK1.4 开始&#xff0c;通过 java.util.logging 提供日志功能。虽然是官方自带的log lib&#xff0c;JUL的使用确不广泛。 JUL从JDK1.4 才开始加入(2002年)&#xff0c;当时各种第三方log lib已经被广泛使用了JUL早期存在性能问题&#x…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...