当前位置: 首页 > 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…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...