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.length1 <= 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 <= 201 <= p.length <= 30s只包含从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
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 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 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用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 ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入:nums [3,2,3] 输出࿱…...
Clickhouse学习:MergeTree
MergeTree一、MergeTree逻辑存储结构二、MergeTree物理存储结构三、总结一、MergeTree逻辑存储结构 如上图所示,在排序键(CountrID、Date)上做索引,数据会按照这两个字段先后排序ClickHouse是稀疏索引,每隔8192行做一个索引,如(a,1),(a,2),比如想查a,要读取[0,3)之间的内容,稀疏…...
【java基础】包装类,自动装箱和自动拆箱
文章目录基本介绍包装类自动装箱自动拆箱包装类注意事项包装类比较包装器内容不可变基本介绍 有时,需要将int这样的基本类型转换为对象。所有的基本类型都有一个与之对应的类。 例如,Integer类对应基本类型int。通常,这些类称为包装器&#…...
Android笔记(二十五):两种sdk热更插件资源加载方案
背景 在研究sdk插件化热更新方式的过程中总结出了两套插件资源加载方案,在此记录下 资源热更方式 方式一:合并所有插件资源 需要解决资源id冲突问题 资源ID值一共4个字段,由三部分组成: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(Aspect Oriented Programming) 10.AOP 实现分类 11.A…...
2023年CDGA考试模拟题库(401-500)
2023年CDGA考试模拟题库(401-500) 401.数据管理战略的SMART原则指的是哪项? [1分] A.具体 、高质量、可操作 、现实、有时间限制 B.具体、可衡量、可检验、现实、有时间限制 C.具体、可衡量、可操作、现实、有时间限制 D.具体、高质量、可检验、现实12-24个月的目标 答…...
软件设计师备考文档
cpu 计算机的基本硬件系统:运算器、控制器、存储器、输入设备、输出设备 cpu负责获取程序指令,对指令进行译码并加以执行 * cpu的功能控制器(保证程序正常执行,处理异常事件) 程序控制操作控制运算器(只能…...
Javascript的API基本内容(一)
一、获取DOM对象 querySelector 满足条件的第一个元素 querySelectorAll 满足条件的元素集合 返回伪数组 document.getElementById 专门获取元素类型节点,根据标签的 id 属性查找 二、操作元素内容 通过修改 DOM 的文本内容,动态改变网页的内容。 inn…...
10、最小公倍数
法一: #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; }法二:a*i%b0成立 #include &…...
【vue】vue2.x项目中使用md文件
一、Vue项目展示md文件的三种方式 1、将md文件 导入为 html 生成的标题标签自带具有id属性,值为标题内容; <h2 id"测试">测试</h2> # 处理md为html字符串 yarn add markdown-loader # 处理字符串,用于导出显示 yarn a…...
操作系统权限提升(十三)之绕过UAC提权-MSF和CS绕过UAC提权
系列文章 操作系统权限提升(十二)之绕过UAC提权-Windows UAC概述 注:阅读本编文章前,请先阅读系列文章,以免造成看不懂的情况!! MSF和CS绕过UAC提权 CS绕过UAC提权 拿到一个普通管理员的SHELL,在CS中没有*号代表有…...
快速排序+快速定位
快速排序算法采用了分治法以及递归作为解决问题的思想。在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以…...
nginx http rewrite module 详解
大家好,我是 17。 今天和大家聊聊 nginx http rewrite module 。 简单来说, ngx_http_rewrite_module module 用正则匹配请求,改写请求,然后做跳转。可以是内部跳转,也可以是外部跳转。 学习这个模块的时候…...
机器学习可解释性一(LIME)
随着深度学习的发展,越来越多的模型诞生,并且在训练集和测试集上的表现甚至于高于人类,但是深度学习一直被认为是一个黑盒模型,我们通俗的认为,经过训练后,机器学习到了数据中的特征,进而可以正…...
CV学习笔记-MobileNet
MobileNet 文章目录MobileNet1. MobileNet概述2. 深度可分离卷积(depthwise separable convolution)2.1 深度可分离卷积通俗理解2.2 深度可分离卷积对于参数的优化3. MobileNet网络结构4. 代码实现4.1 卷积块4.2 深度可分离卷积块4.3 MobileNet定义4.4 完…...
C++进阶——继承
C进阶——继承 1.继承的概念及定义 面向对象三大特性:封装、继承、多态。 概念: 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段,它允许程序员在保持原有类特 性的基础上进行扩展,增加功能,这…...
数据结构---单链表
专栏:数据结构 个人主页:HaiFan. 专栏简介:从零开始,数据结构!! 单链表前言顺序表的缺陷链表的概念以及结构链表接口实现打印链表中的元素SLTPrintphead->next!NULL和phead!NULL的区别开辟空间SLTNewNod…...
redis数据结构的底层实现
文章目录一.引言二.redis的特点三.Redis的数据结构a.字符串b.hashc.listd.sete.zset(有序集合)一.引言 redis是一个开源的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、key-value的NoSQL数据库。 通常使用redis作为缓存中间件来降低数据库的压力,除此…...
【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 开始,通过 java.util.logging 提供日志功能。虽然是官方自带的log lib,JUL的使用确不广泛。 JUL从JDK1.4 才开始加入(2002年),当时各种第三方log lib已经被广泛使用了JUL早期存在性能问题&#x…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
