力扣大厂热门面试算法题 6-8

news/2024/4/21 14:21:25/文章来源:https://blog.csdn.net/qq_52213943/article/details/136566371

        6. Z 字形变换,7. 整数反转,8. 字符串转换整数 (atoi),每题做详细思路梳理,配套Python&Java双语代码, 2024.03.08 可通过leetcode所有测试用例。

目录

6. Z 字形变换

解题思路

边界条件

完整代码

Python

Java

7. 整数反转

解题思路

边界条件

完整代码

Python

Java

8. 字符串转换整数 (atoi)

解题思路

边界条件

完整代码

Python

Java


6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

P   A   H   N
A P L S I I G
Y   I   R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);
 

示例 1:

输入:s = "PAYPALISHIRING", numRows = 3
输出:"PAHNAPLSIIGYIR"
示例 2:
输入:s = "PAYPALISHIRING", numRows = 4
输出:"PINALSIGYAHRPI"
解释:
P     I    N
A   L S  I G
Y A   H R
P     I
示例 3:

输入:s = "A", numRows = 1
输出:"A"
 

提示:

1 <= s.length <= 1000
s 由英文字母(小写和大写)、',' 和 '.' 组成
1 <= numRows <= 1000

解题思路

这个问题可以通过模拟Z字形排列的过程来解决。具体思路如下:

  1. 初始化:创建一个列表(或者列表的列表),用于存储每一行的字符。行数由numRows指定。

  2. 字符遍历:遍历字符串s中的每个字符,并将其添加到正确的行中。

  3. 行的变化:使用一个变量来表示当前字符应该放在哪一行,以及一个方向变量,用于表示行的移动方向(向下或向上)。当我们向下移动到最底行时,改变方向向上移动;当向上移动到最顶行时,改变方向向下移动。

  4. 输出结果:遍历存储行的列表,将每行的字符连接起来形成最终的字符串。

边界条件

  • numRows为1时,不需要进行Z字形变换,直接返回原字符串。
  • numRows大于等于字符串长度时,同样不需要进行变换,直接返回原字符串。

完整代码

Python
class Solution:def convert(self, s: str, numRows: int) -> str:if numRows == 1 or numRows >= len(s):return srows = [''] * min(numRows, len(s))  # 初始化行curRow = 0  # 当前行goingDown = False  # 方向# 遍历字符串,模拟Z字形排列for c in s:rows[curRow] += cif curRow == 0 or curRow == numRows - 1:goingDown = not goingDowncurRow += 1 if goingDown else -1# 合并所有行,形成最终字符串return ''.join(rows)
Java
class Solution {public String convert(String s, int numRows) {if (numRows == 1 || numRows >= s.length()) {return s;}StringBuilder[] rows = new StringBuilder[numRows];for (int i = 0; i < numRows; i++) {rows[i] = new StringBuilder();}int curRow = 0;boolean goingDown = false;for (char c : s.toCharArray()) {rows[curRow].append(c);if (curRow == 0 || curRow == numRows - 1) {goingDown = !goingDown;}curRow += goingDown ? 1 : -1;}StringBuilder ret = new StringBuilder();for (StringBuilder row : rows) {ret.append(row);}return ret.toString();}   
}

7. 整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。
 

示例 1:

输入:x = 123
输出:321
示例 2:

输入:x = -123
输出:-321
示例 3:

输入:x = 120
输出:21
示例 4:

输入:x = 0
输出:0

解题思路

        这个问题的关键在于如何反转一个整数的数字,并且在反转的过程中需要检查结果是否会超出32位有符号整数的范围(即是否会溢出)。

  1. 处理符号:首先,我们需要处理整数的符号。我们可以通过取绝对值的方式忽略掉整数的符号,然后在最后根据原始整数的符号来确定最终结果的符号。

  2. 数字反转:对于数字反转的部分,我们可以通过不断地取整数的最后一位数字,并将其添加到结果整数的末尾,同时将原整数除以10(向下取整)来去掉已经处理过的最后一位。

  3. 检查溢出:在每次添加新数字之前,我们需要检查结果是否会超出32位有符号整数的范围。对于正数,检查是否大于Integer.MAX_VALUE/10;对于负数,检查是否小于Integer.MIN_VALUE/10

  4. 返回结果:根据原始整数的符号返回最终的反转结果。

边界条件

  • 如果整数为0,则直接返回0。
  • 需要注意的是,整数反转后可能会出现前导0,但这对最终结果没有影响,因为在数学上,前导0被忽略。

完整代码

Python
class Solution:def reverse(self, x: int) -> int:INT_MAX, INT_MIN = 2**31 - 1, -2**31rev = 0sign = -1 if x < 0 else 1x *= sign  # 使x为正数,便于处理while x != 0:digit = x % 10x = x // 10  # 更新x# 检查反转后是否溢出if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and digit > INT_MAX % 10):return 0rev = rev * 10 + digitreturn rev * sign
Java
class Solution {public int reverse(int x) {int res = 0;while (x != 0) {// 取最后一位int digit = x % 10;x /= 10;// 检查溢出if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > 7)) return 0;if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && digit < -8)) return 0;res = res * 10 + digit;}return res;
}}

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。

函数 myAtoi(string s) 的算法如下:

读入字符串并丢弃无用的前导空格
检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意:

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
 

示例 1:

输入:s = "42"
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:"42"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"42"(读入 "42")
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。
示例 2:

输入:s = "   -42"
输出:-42
解释:
第 1 步:"   -42"(读入前导空格,但忽视掉)
            ^
第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)
             ^
第 3 步:"   -42"(读入 "42")
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。
示例 3:

输入:s = "4193 with words"
输出:4193
解释:
第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。

解题思路

  1. 去除前导空格:遍历字符串,跳过所有前导空格。
  2. 处理正负号:如果遇到正号+或负号-,记录下符号,并处理下一个字符。如果没有符号,默认为正数。
  3. 读取数字:继续遍历字符串,直到遇到非数字字符或字符串结束。将每个数字字符转换为数字,并加到结果中。在每次添加数字之前,检查是否会溢出。
  4. 溢出处理:如果在任何时候计算的结果超出32位有符号整数的范围,则根据正负号返回INT_MAX或INT_MIN。
  5. 返回结果:返回计算的结果,根据步骤2中记录的正负号调整正负。

边界条件

  • 字符串为空或仅包含空白字符时,返回0。
  • 读取的数字之后还有其他字符,忽略这些字符。

完整代码

Python
class Solution:def myAtoi(self, s: str) -> int:INT_MAX, INT_MIN = 2**31 - 1, -2**31i, n, sign = 0, len(s), 1result = 0# 跳过前导空格while i < n and s[i] == ' ':i += 1# 处理正负号if i < n and (s[i] == '+' or s[i] == '-'):sign = -1 if s[i] == '-' else 1i += 1# 读取数字while i < n and s[i].isdigit():digit = int(s[i])# 检查溢出if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > INT_MAX % 10):return INT_MIN if sign == -1 else INT_MAXresult = result * 10 + digiti += 1return result * sign
Java
class Solution {public int myAtoi(String s) {int index = 0, sign = 1, total = 0;// 1. Empty stringif(s.length() == 0) return 0;// 2. Remove Spaceswhile(index < s.length() && s.charAt(index) == ' ')index++;// 3. Handle signsif(index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')){sign = s.charAt(index) == '+' ? 1 : -1;index++;}// 4. Convert number and avoid overflowwhile(index < s.length()){int digit = s.charAt(index) - '0';if(digit < 0 || digit > 9) break;// Check if total will be overflow after 10 times and add digitif(Integer.MAX_VALUE/10 < total || Integer.MAX_VALUE/10 == total && Integer.MAX_VALUE %10 < digit)return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;total = 10 * total + digit;index ++;}return total * sign;}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_998185.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

express接受请求参数

传参问题 1. get方式接受请求参数 get方式请求的参数会拼接在地址栏的后面&#xff0c;参数的格式是?namevalue&namevalue...express针对前端get方式发送的数据可以通过req.query来获取后端代码 // cart.js router.get(/getList, (req,res)>{const param {username…

中霖教育:注册安全工程师考是科目有哪些?

注册安全工程师的类型是职业资格证书&#xff0c;需要满足报名条件才能参加考试&#xff0c;考试通过就能发放证书。报名时间一般在八月份&#xff0c;考试时间在十月底左右。 考试科目&#xff1a; 《安全生产法律法规》 《安全生产管理》 《安全生产技术基础》 《安全生…

【算法训练营】:期末考试

清华大学驭风计划课程链接 学堂在线 - 精品在线课程学习平台 (xuetangx.com) 如果需要答案代码可以私聊博主 有任何疑问或者问题&#xff0c;也欢迎私信博主&#xff0c;大家可以相互讨论交流哟~~ 考题12-1 题目描述 输入格式 输出格式 输出到标准输出。 输出一行一个整数…

在表格中循环插入表单

<template><div class"key">{{ruleForm.casesRange}}<el-form label-position"top" :model"ruleForm" refruleForm><el-form-item label"这个表格怎么写"><el-table :data"tableData" border>…

42、网络编程/多点通信和域套接字通信模型20240304

一、多点通信之广播的收发端实现 1.广播发送端代码&#xff1a; #include<myhead.h>int main(int argc, const char *argv[]) {int sfdsocket(AF_INET,SOCK_DGRAM,0);//创建套接字if(sfd-1){perror("socket,error");return -1;}int broadcast1;//设置套接字广…

力扣--滑动窗口438.找到字符串中所有字母异位词

思路分析&#xff1a; 使用两个数组snum和pnum分别记录字符串s和p中各字符出现的次数。遍历字符串p&#xff0c;统计其中各字符的出现次数&#xff0c;存储在pnum数组中。初始化snum数组&#xff0c;统计s的前m-1个字符的出现次数。从第m个字符开始遍历s&#xff0c;通过滑动窗…

liunx操作系统 环境变量

环境变量 main函数参数 命令行参数环境变量 环境变量的查看环境变量的获取 main函数参数 命令行参数 main函数是有参数的&#xff0c;只是我们一般不适用 这是main函数从bash中读取进程数据使用的一个基本入口。 下面进行简单演示。 o 好oo都是我们输入的命令行参数。其实&a…

韦东山嵌入式Liunx入门驱动开发五

文章目录 一、驱动程序基石1-1 休眠与唤醒1-2 POLL机制1-3 异步通知(1) 异步通知程序解析(2) 异步通知机制内核代码详解 1-4 阻塞与非阻塞1-5 定时器(1) 内核函数(2) 定时器时间单位 1-6 中断下半部 tasklet1-7 工作队列1-8 中断的线程化处理1-9 mmap 本人学习完韦老师的视频&a…

springboot244基于SpringBoot和VUE技术的智慧生活商城系统设计与实现

智慧生活商城系统的设计与实现 摘 要 计算机网络发展到现在已经好几十年了&#xff0c;在理论上面已经有了很丰富的基础&#xff0c;并且在现实生活中也到处都在使用&#xff0c;可以说&#xff0c;经过几十年的发展&#xff0c;互联网技术已经把地域信息的隔阂给消除了&…

MySQL--MHA高可用方案

MHA高可用方案实行 1.1MHA简介 MHA 在监控到 master 节点故障时&#xff0c;会提升其中拥有最新数据的 slave 节点成为新的master 节点&#xff0c;在此期间&#xff0c;MHA 会通过于其它从节点获取额外信息来避免一致性方面的问题。MHA 还提供了 master 节点的在线切换功能&a…

通过测试自动化转移安全关键软件测试

我们正面临安全关键软件的成本危机&#xff0c;这意味着所需增加的功能已经超出了支付其开发费用的能力。例如&#xff0c;波音 787 项目需要 650 万行代码&#xff0c;设计、开发和测试成本达 40 亿美元。波音777X项目的成本数字并未公开披露&#xff0c;波音737 MAX最初估计为…

python异常机制

当代码出现异常后底下代码都不会被执行了&#xff0c;也就是程序崩溃了。当然能避免异常的话尽量避免但是有的时候这个是没有办法避免的。 异常处理 &#xff08;注&#xff1a;异常处理是从上往下处理&#xff0c;所以编写代码时要注意&#xff09; 语法 try:可能出现异常…

昇腾芯片解析:华为自主研发的人工智能处理器全面分析

在当今科技发展的浪潮中&#xff0c;昇腾芯片作为一种新兴的处理器&#xff0c;正引起广泛的关注和讨论。升腾芯片究竟是由哪家公司生产的&#xff1f;这个问题一直困扰着许多人。下面小编将全面介绍、分析升腾芯片的生产商及各类参数、应用&#xff0c;以便读者对其有更全面的…

GitHub登不上:修改hosts文件来解决(GitHub520,window)

参考链接&#xff1a;GitHub520: 本项目无需安装任何程序&#xff0c;通过修改本地 hosts 文件&#xff0c;试图解决&#xff1a; GitHub 访问速度慢的问题 GitHub 项目中的图片显示不出的问题 花 5 分钟时间&#xff0c;让你"爱"上 GitHub。 (gitee.com) GitHub网站…

C++ Qt开发:QFileSystemWatcher文件监视组件

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QFileSystemWatcher组件实现对文件或…

利用redis实现秒杀功能

6、秒杀优化 这个是 图灵 的redis实战里面的一个案例 6.1 秒杀优化-异步秒杀思路 我们来回顾一下下单流程 当用户发起请求&#xff0c;此时会请求nginx&#xff0c;nginx会访问到tomcat&#xff0c;而tomcat中的程序&#xff0c;会进行串行操作&#xff0c;分成如下几个步骤…

python coding with ChatGPT 打卡第22天| 二叉搜索树的操作:插入、删除、修剪、转换

相关推荐 python coding with ChatGPT 打卡第12天| 二叉树&#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树&#xff1a;翻转…

django中URL配置和视图渲染

前提&#xff1a; 使用django-admin startproject XXX创建了一个django项目【项目目录为project】 django-admin startproject project 一&#xff1a;控制器配置 在项目的根目录创建一个Controller目录&#xff0c;后续所有的控制器方法都放在此目录下 这里我们在Control…

迅速上手:CentOS 系统下 SSH 服务配置指南

前言 掌握 SSH 服务&#xff0c;就像拥有了一把解锁网络世界的钥匙。本文深入浅出地介绍了如何使用 SSH&#xff08;Secure Shell&#xff09;服务&#xff0c;从连接远程服务器到安全文件传输&#xff0c;让你轻松驾驭远程管理与数据传输&#xff0c;提高工作效率&#xff0c…

[密码学]入门篇——加密方式

一、概述 加密方法主要分为两大类&#xff1a; 单钥加密&#xff08;private key cryptography&#xff09;&#xff1a;加密和解密过程都用同一套密码双钥加密&#xff08;public key cryptography&#xff09;&#xff1a;加密和解密过程用的是两套密码 历史上&#xff0c…