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

每日刷题(翻转+二分+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)

食用指南&#xff1a;本文为作者刷题中认为有必要记录的题目 ♈️今日夜电波&#xff1a;凄美地—郭顶 1:10 ━━━━━━️&#x1f49f;──────── 4:10 &#x1f504; ◀️ ⏸ ▶️ ☰…...

系统卡死问题分析

CPU模式 CPU Frequency Scaling (CPUFREQ) Introduction CPU频率调节设备驱动程序的功能。该驱动程序允许在运行过程中更改CPU的时钟频率。一旦CPU频率被更改,必要的电源供应电压也会根据设备树脚本(DTS)中定义的电压值进行变化。通过降低时钟速度,这种方法可以减少功耗…...

中大许少辉博士中国建筑出版传媒八一新书《乡村振兴战略下传统村落文化旅游设计》百度百科新闻

中大许少辉博士中国建筑出版传媒八一新书《乡村振兴战略下传统村落文化旅游设计》百度百科新闻&#xff1a; 乡村振兴战略下传统村落文化旅游设计 - 百度百科 https://baike.baidu.com/item/乡村振兴战略下传统村落文化旅游设计/62588677 概览 《乡村振兴战略下传统村落文化旅游…...

int和Integer的不同

一个奇怪的事情&#xff0c;在int[]用 Arrays.asList 转List 的时候&#xff0c;转过去的是List<int[]>。而不是List<int>类型的。于是试了String和Integer类型。发现只有Int[]有问题。 package com.test.lc;import java.util.ArrayList; import java.util.Arrays…...

eslintignore无效解决办法

项目的根目录下新建.eslintignore&#xff0c;但是无论怎么配置&#xff0c;该文件总是无法生效。本想解决不生效的问题&#xff0c;但是一直无法解决&#xff0c;于是换了一种解决问题的思路。 方法一&#xff1a; 在需要进行忽略的文件顶部加上 /* eslint-disable */这样e…...

C# 学习笔记

此笔记极水~ &#xff0c;来自两年前的库存。 是来自 B站 刘铁猛大佬 的视频&#xff0c;因为 好奇学了学。 其他 c# 变量的 内联赋值 vs. 构造函数内赋值 (引用自&#xff1a;https://www.iteye.com/blog/roomfourteen224-2208838) 上下文&#xff1a;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…...

深入理解分布式架构,构建高效可靠系统的关键

深入探讨分布式架构的核心概念、优势、挑战以及构建过程中的关键考虑因素。 引言什么是分布式架构&#xff1f;分布式架构的重要性 分布式系统的核心概念节点和通信数据分区与复制一致性与一致性模型负载均衡与容错性 常见的分布式架构模式客户端-服务器架构微服务架构事件驱动…...

为什么选择elasticsearch分布式搜索引擎

文章目录 &#x1f52d;什么是elasticsearch&#x1f320;ELK技术栈&#x1f320;elasticsearch和lucene&#x1f320;为什么不是其他搜索技术&#xff1f; &#x1f52d;总结 &#x1f52d;什么是elasticsearch elasticsearch是一款非常强大的开源搜索引擎&#xff0c;具备非常…...

一百五十九、Kettle——Kettle9.2通过配置Hadoop clusters连接Hadoop3.1.3(踩坑亲测、附流程截图)

一、目的 由于kettle的任务需要用到Hadoop&#xff08;HDFS&#xff09;&#xff0c;所以就要连接Hadoop服务。 之前使用的是kettle9.3&#xff0c;由于在kettle新官网以及博客百度等渠道实在找不到shims的驱动包&#xff0c;无奈换成了kettle9.2&#xff0c;kettle9.2的安装…...

渗透测试之逻辑漏洞

文章目录 一、支付漏洞1.修改附属值2.多重替换支付3.重复支付4.最小额支付5.最大值支付6.越权支付7.无限制试用8.多线程并发9.支付漏洞思路 二、密码找回漏洞1.本地验证绕过2.利用session重新绑定客户3.去掉验证参数绕过4.总结 三、短信验证码绕过1.短信验证码生命期限内可暴力…...

HTML class 中 CSS名称的顺序并不重要

的确是这样&#xff01;我可以证明。让我们先来看一些CSS代码: .a {color: red; }.b {color: blue; }现在让我们看一些标记: <div class"a b">Here’s some text</div>文本会是蓝色的&#xff0c;因为.b 在CSS中是最后定义的&#xff0c;对吧&#xff…...

设计模式8:代理模式-静态代理

我尝试在JDK、Android SDK和一些出名的库中&#xff0c;寻找静态代理的源码&#xff0c;没能找到。如果有读者发现&#xff0c;欢迎评论或者私信我。 本文目录 静态代理的实例1. 售票代理2. 明星代理 静态代理的实例 1. 售票代理 售票服务 public interface TicketService {…...

运动耳机哪款好用、适合运动的耳机推荐

如今&#xff0c;蓝牙耳机不仅是手机的最佳伴侣&#xff0c;也成为了运动爱好者的必备装备。但是&#xff0c;在如此众多的蓝牙耳机中&#xff0c;你是否对选购感到困惑呢&#xff1f;实际上&#xff0c;选择适合运动的蓝牙耳机需要考虑许多因素&#xff0c;如舒适度、稳固性、…...

页面滑动到可视区域加载更多内容思维流程

页面滑动到可视区域加载更多内容思维流程...

Java Word转PDF(直接转和以图片形式转)、PDF转图片、图片转PDF

在淘宝上找了一家写代码的店铺写了一个工具类&#xff0c;再参考网上的代码&#xff0c;改了改 用到的类库&#xff1a; <!-- https://mvnrepository.com/artifact/org.apache.pdfbox/fontbox --><!--word转pdf--><dependency><groupId>com.documents4…...

dockerfile编写LNMP

目录 1. 项目环境 2. 服务器环境 二、部署nginx&#xff08;容器IP为192.168.158.26&#xff09; 1、整个Dockerfile文件内容 ​编辑 2、配置nginx.conf文件 3、构建镜像 三、部署mysql 1、整个Docker文件内容 3、生成镜像 4、启动镜像容器 5、验证mysql 四、PHP部署 1…...

websocket + stomp + sockjs学习

文章目录 学习链接后台代码引入依赖application.ymlWebSocketConfigPrivateControllerWebSocketService WebSocketEventListenerCorsFilter 前端代码Room.vue 学习链接 WebSocket入门教程示例代码&#xff0c;代码地址已fork至本地gitee&#xff0c;原github代码地址&#xff…...

ApplicationListener , @EventListener 和 CommandLineRunner 启动顺序验证

一. 背景 排查线上问题, 发现一个重要功能的全局锁线程启动延迟很高. 服务启动40分钟之后, 才能拿到锁. 排查之后发现原因是因为代码引入了高优先级的ApplicationListener代码, 导致全局锁线程启动延迟. 二. 结论 启动顺序从高到底依次为: ApplicationListener , EventListe…...

网络编程基础(1)

目录 网络编程解决是跨主机的进程间通讯 1、网络 2、互联网 3、ip地址 &#xff08;1&#xff09;ipv4: &#xff08;2&#xff09;ipV6:1 &#xff08;3&#xff09;IP地址的组成&#xff1a; (4)Linux查看IP地址&#xff1a;ifconfig 4、mac地址 5、ping Ip地址 6…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...