每日刷题(翻转+二分+BFS)
食用指南:本文为作者刷题中认为有必要记录的题目
♈️今日夜电波:凄美地—郭顶
1:10 ━━━━━━️💟──────── 4:10
🔄 ◀️ ⏸ ▶️ ☰
💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍
目录
一、局部翻转+整体翻转
二、二分查找
三、BFS—广度优先算法
一、局部翻转+整体翻转
题目链接:剑指 Offer 58 - II. 左旋转字符串
题目描述:
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1:
输入: s = "abcdefg", k = 2 输出: "cdefgab"
示例 2:
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
限制:
1 <= k < s.length <= 10000
本题思路:
使用 整体反转+局部反转 就可以实现「反转单词顺序」的目的。当然,你使用先整体还是先局部翻转得到的效果都是一样的!
这里使用先局部后整体的思路:(时间复杂度O(n),空间复杂度 O(1))
反转前 n 个字符
反转 n 到末尾的字符
反转整个字符串
char* reverse(char* s, int start, int end) {while (start < end) {char temp = s[start];s[start++] = s[end];s[end--] = temp;}return s;
}
char* reverseLeftWords(char* s, int n){int len = strlen(s);//反转前 n 个字符s = reverse(s, 0, n - 1);//反转 k 到末尾的字符s = reverse(s, n, len - 1);//反转整个字符串s = reverse(s, 0, len - 1);return s;
}
二、二分查找
题目链接:剑指 Offer 53 - I. 在排序数组中查找数字 I
题目描述:
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10]
, target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10]
, target = 6
输出: 0
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
本题思路:
一种是暴力,一种是二分法求边界
暴力法当然简单,一个for循环就搞定了。那为什么我还把这道简单题放到这里呢?因为我们需要做的是以简答题来体现我们思想递进的过程。
于是我们就想到了二分法,这里是使用了两次二分。一次找到x元素最左边位置,一次找到x元素最右边的位置,最终返回的是右边的位置减左边的位置 + 1。当数组大小为零时候特殊处理,返回0。
暴力法
int search(int* nums, int numsSize, int target){int cn=0;for(int i=0;i<numsSize;i++){if(nums[i]==target){cn++;}}return cn;
}
二分法
int L(int *nums, int x, int size)
{int l=0, r=size-1, mid=0;while( l < r ) {mid = l + (r-l)/2;if( nums[mid] >= x ) r = mid;else l = mid + 1;}return nums[l] == x?l:0;
}int R(int *nums, int x, int size)
{int l=0, r=size-1, mid=0;while( l < r ) {mid = l + (r-l)/2 + 1;if( nums[mid] <= x ) l = mid;else r = mid - 1;}return nums[l] == x?l:-1;
}int search(int* nums, int numsSize, int target){if( !numsSize ) return 0;return R(nums,target,numsSize) - L(nums,target,numsSize) + 1;
}
三、BFS—广度优先算法
题目链接:剑指 Offer 32 - I. 从上到下打印二叉树
题目描述:
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3/ \9 20/ \15 7
返回:
[3,9,20,15,7]
提示:
节点总数 <= 1000
本题思路:
运用队列来实现BFS。需要注意二叉树空的情况,返回NULL,这里有个*returnsize也是需要反回的,所以开始先设置其为0,然后后面再返回一次。这里队列遍历时也需要注意要用个中间的变量来存储之前遍历的节点,以此来模拟触发BFS进队列的功能。
#define MAX_SIZE 1001
int* levelOrder(struct TreeNode* root, int* returnSize)
{*returnSize=0;if(root==NULL)return NULL;//为空情况struct TreeNode* queue[MAX_SIZE];//初始化memset(queue,0,sizeof(struct TreeNode*));int *ren=(int*)malloc(sizeof(int)*MAX_SIZE);int ret=0,front=0,rear=0;queue[rear++]=root;//先进一个,保证进入循环while(front<rear)//BFS{struct TreeNode* tmp=queue[front++];ren[ret++]=tmp->val;if(tmp->left!=NULL)queue[rear++]=tmp->left;if(tmp->right!=NULL)queue[rear++]=tmp->right;}*returnSize=ret;return ren;
}
感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o!
给个三连再走嘛~
相关文章:
每日刷题(翻转+二分+BFS)
食用指南:本文为作者刷题中认为有必要记录的题目 ♈️今日夜电波:凄美地—郭顶 1:10 ━━━━━━️💟──────── 4:10 🔄 ◀️ ⏸ ▶️ ☰…...
系统卡死问题分析
CPU模式 CPU Frequency Scaling (CPUFREQ) Introduction CPU频率调节设备驱动程序的功能。该驱动程序允许在运行过程中更改CPU的时钟频率。一旦CPU频率被更改,必要的电源供应电压也会根据设备树脚本(DTS)中定义的电压值进行变化。通过降低时钟速度,这种方法可以减少功耗…...
中大许少辉博士中国建筑出版传媒八一新书《乡村振兴战略下传统村落文化旅游设计》百度百科新闻
中大许少辉博士中国建筑出版传媒八一新书《乡村振兴战略下传统村落文化旅游设计》百度百科新闻: 乡村振兴战略下传统村落文化旅游设计 - 百度百科 https://baike.baidu.com/item/乡村振兴战略下传统村落文化旅游设计/62588677 概览 《乡村振兴战略下传统村落文化旅游…...
int和Integer的不同
一个奇怪的事情,在int[]用 Arrays.asList 转List 的时候,转过去的是List<int[]>。而不是List<int>类型的。于是试了String和Integer类型。发现只有Int[]有问题。 package com.test.lc;import java.util.ArrayList; import java.util.Arrays…...
eslintignore无效解决办法
项目的根目录下新建.eslintignore,但是无论怎么配置,该文件总是无法生效。本想解决不生效的问题,但是一直无法解决,于是换了一种解决问题的思路。 方法一: 在需要进行忽略的文件顶部加上 /* eslint-disable */这样e…...
C# 学习笔记
此笔记极水~ ,来自两年前的库存。 是来自 B站 刘铁猛大佬 的视频,因为 好奇学了学。 其他 c# 变量的 内联赋值 vs. 构造函数内赋值 (引用自:https://www.iteye.com/blog/roomfourteen224-2208838) 上下文:c#中变量的内联赋值其…...
算法练习(8):牛客在线编程08 字符串
package jz.bm;import java.util.Arrays;public class bm8 {/*** BM83 字符串变形*/public String trans(String s, int n) {StringBuilder res new StringBuilder();//大小写转换for (int i 0; i < n; i) {if (s.charAt(i) > a && s.charAt(i) < z) {res.a…...
深入理解分布式架构,构建高效可靠系统的关键
深入探讨分布式架构的核心概念、优势、挑战以及构建过程中的关键考虑因素。 引言什么是分布式架构?分布式架构的重要性 分布式系统的核心概念节点和通信数据分区与复制一致性与一致性模型负载均衡与容错性 常见的分布式架构模式客户端-服务器架构微服务架构事件驱动…...
为什么选择elasticsearch分布式搜索引擎
文章目录 🔭什么是elasticsearch🌠ELK技术栈🌠elasticsearch和lucene🌠为什么不是其他搜索技术? 🔭总结 🔭什么是elasticsearch elasticsearch是一款非常强大的开源搜索引擎,具备非常…...
一百五十九、Kettle——Kettle9.2通过配置Hadoop clusters连接Hadoop3.1.3(踩坑亲测、附流程截图)
一、目的 由于kettle的任务需要用到Hadoop(HDFS),所以就要连接Hadoop服务。 之前使用的是kettle9.3,由于在kettle新官网以及博客百度等渠道实在找不到shims的驱动包,无奈换成了kettle9.2,kettle9.2的安装…...
渗透测试之逻辑漏洞
文章目录 一、支付漏洞1.修改附属值2.多重替换支付3.重复支付4.最小额支付5.最大值支付6.越权支付7.无限制试用8.多线程并发9.支付漏洞思路 二、密码找回漏洞1.本地验证绕过2.利用session重新绑定客户3.去掉验证参数绕过4.总结 三、短信验证码绕过1.短信验证码生命期限内可暴力…...
HTML class 中 CSS名称的顺序并不重要
的确是这样!我可以证明。让我们先来看一些CSS代码: .a {color: red; }.b {color: blue; }现在让我们看一些标记: <div class"a b">Here’s some text</div>文本会是蓝色的,因为.b 在CSS中是最后定义的,对吧ÿ…...
设计模式8:代理模式-静态代理
我尝试在JDK、Android SDK和一些出名的库中,寻找静态代理的源码,没能找到。如果有读者发现,欢迎评论或者私信我。 本文目录 静态代理的实例1. 售票代理2. 明星代理 静态代理的实例 1. 售票代理 售票服务 public interface TicketService {…...
运动耳机哪款好用、适合运动的耳机推荐
如今,蓝牙耳机不仅是手机的最佳伴侣,也成为了运动爱好者的必备装备。但是,在如此众多的蓝牙耳机中,你是否对选购感到困惑呢?实际上,选择适合运动的蓝牙耳机需要考虑许多因素,如舒适度、稳固性、…...
页面滑动到可视区域加载更多内容思维流程
页面滑动到可视区域加载更多内容思维流程...
Java Word转PDF(直接转和以图片形式转)、PDF转图片、图片转PDF
在淘宝上找了一家写代码的店铺写了一个工具类,再参考网上的代码,改了改 用到的类库: <!-- https://mvnrepository.com/artifact/org.apache.pdfbox/fontbox --><!--word转pdf--><dependency><groupId>com.documents4…...
dockerfile编写LNMP
目录 1. 项目环境 2. 服务器环境 二、部署nginx(容器IP为192.168.158.26) 1、整个Dockerfile文件内容 编辑 2、配置nginx.conf文件 3、构建镜像 三、部署mysql 1、整个Docker文件内容 3、生成镜像 4、启动镜像容器 5、验证mysql 四、PHP部署 1…...
websocket + stomp + sockjs学习
文章目录 学习链接后台代码引入依赖application.ymlWebSocketConfigPrivateControllerWebSocketService WebSocketEventListenerCorsFilter 前端代码Room.vue 学习链接 WebSocket入门教程示例代码,代码地址已fork至本地gitee,原github代码地址ÿ…...
ApplicationListener , @EventListener 和 CommandLineRunner 启动顺序验证
一. 背景 排查线上问题, 发现一个重要功能的全局锁线程启动延迟很高. 服务启动40分钟之后, 才能拿到锁. 排查之后发现原因是因为代码引入了高优先级的ApplicationListener代码, 导致全局锁线程启动延迟. 二. 结论 启动顺序从高到底依次为: ApplicationListener , EventListe…...
网络编程基础(1)
目录 网络编程解决是跨主机的进程间通讯 1、网络 2、互联网 3、ip地址 (1)ipv4: (2)ipV6:1 (3)IP地址的组成: (4)Linux查看IP地址:ifconfig 4、mac地址 5、ping Ip地址 6…...
Linux驱动开发(Day4)
思维导图: 字符设备驱动分步注册:...
LVS负载均衡群集部署(LVS-NAT模型实例)
一、集群 1.1集群的含义 Cluster,集群、群集,为解决某个特定问题将多台计算机组合起来形成的单个系统。 由多台主机构成,但对外只表现为一个整体。 1.2群集的三种类型 1.2.1负载均衡群集 LB: Load Balancing,负载均衡&#x…...
【仿写tomcat】五、响应静态资源(访问html页面)、路由支持以及多线程改进
访问html页面 如果我们想访问html页面其实就是将本地的html文件以流的方式响应给前端即可,下面我们对HttpResponseServlet这个类做一些改造 package com.tomcatServer.domain;import com.tomcatServer.utils.ScanUtil;import java.io.IOException; import java.io…...
stm32单片机/51单片机蜂鸣器不响(proteus模拟)
蜂鸣器不发生原因就1个:电压不够 所以需要提高蜂鸣器2端的电压:可以采用的方法有: 1提高蜂鸣器电阻,这样根据分压原理,可以提升蜂鸣器2段电压 2更改蜂鸣器的工作电压为更小的值,这个可以通过在proteus内…...
BERT、ERNIE、Grover、XLNet、GPT、MASS、UniLM、ELECTRA、RoBERTa、T5、C4
BERT、ERNIE、Grover、XLNet、GPT、MASS、UniLM、ELECTRA、RoBERTa、T5、C4 ELMOBERTERNIE![在这里插入图片描述](https://img-blog.csdnimg.cn/274e31d0f8274c748d05abe2ec65fc73.png)GroverXLNetGPTMASSUniLMELECTRARoBERTaT5C4ELMO BERT...
主机防护的重要性和方式
01 主机防护的重要性 主机防护是网络安全的重要组成部分。在互联网时代,网络攻击成为了一种常见的威胁,而主机防护则是保护计算机系统免受网络攻击的重要手段。 主机防护可以防范各种网络攻击,如病毒、木马、黑客攻击等,从而保…...
聚观早报 | 抢先体验阿维塔11座舱;本田和讴歌采用NACS充电标准
【聚观365】8月21日消息 抢先体验阿维塔11鸿蒙座舱 本田和讴歌采用特斯拉NACS充电标准 华为秋季新品发布会将于9月12日举行 iQOO Z8即将到来 三星Galaxy S24系列外观或更改 抢先体验阿维塔11鸿蒙座舱 当前,智能座舱成了各大巨头跑马圈地的重要领域。根据毕马威…...
思科计算机网络答案(包含第1~11章节)
第一章 1.在以下哪个场景中推荐使用 WISP? 选择一项: A.城市里的网吧 B.没有有线宽带接入的农村地区的农场 C.任何有多个无线设备的家庭 D.通过有线连接访问 Internet 的大厦公寓 2.一位员工希望以尽可能最安全的方式远程访问公司网络。 下列哪种网络特征将允许员工获得对…...
所见即所得,「Paraverse平行云」助力万间打造智能建造新图景
在城市建设行业中,数字化逐渐成为其主导力量。 新一代信息基础设施建设也迎来了新的里程碑。数据显示,截至今年,我国已全面推进城市信息模型(CIM)基础平台建设,为城市规划、建设管理提供了多场景应用的强大…...
AI图片处理功能演示
例如,这是一张不错的图片,但是有3只手。 我们可以选择有问题的区域,然后要求 niji 进行重新绘制。 根据我们选择的区域,我们可以以不同的方式修复结果。 创意修复 修复并不仅限于纠正错误。我们可以要求 niji 添加额外的元素&…...
工业产品设计工资/永州网站seo
案例:怎么看到电脑隐藏的文件? “有时候我在电脑找不到一些文件,听朋友说这些文夹可能是隐藏的,直接查找是找不到的。那怎么才能看到隐藏的文件呢?电脑怎么看隐藏的文件?有没有小伙伴知道具体的方法。” …...
wordpress标志/全面的seo网站优化排名
6、到这里我们就可以打开Win7本地连接属性了,在里边即可更高本地连接IP地址了,如下图所示,我们切换到网络一栏,然后选中“ Internet 协议版本4 ”,然后点击下边的属性,如下图所示1、2、3步骤:7…...
wordpress添加动态图标/搜索引擎营销的原理是什么
STL之deque容器1. deque容器基本概念2. deque容器实现原理3. deque常用API1. deque容器基本概念 vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,…...
可信网站认证不做/前端优化
积累些常用的方法, 都是随写的, 不好之处, 望指出。 getRandomItem(arr)函数如下: 1 var getRandomItem function () {2 var preItem null;3 4 return function (arr) {5 6 var index Math.floor(Math.random() * arr.leng…...
做园林景观的网站/seo技术优化
由于口令密码容易泄露,SSH公钥登录相比口令登录更加安全。SSH可以轻松使用非对称加密技术给两台机子订立契约,步骤如下: 第一步 本地机生成秘钥对 指令:ssh-keygen 功能:在本地(~/.ssh/)产生公钥…...
下列不属于网站建设规划/室内设计师培训班学费多少
在部署服务时,有一类服务是需要在每台node上都启动一个的(例如,日志收集,网络存储设置等基础服务,最典型的,搭建k8s集群master节点时,需要创建一个网络管理,例如,flannel…...