【数据结构与算法】解题20240312

本文主要是介绍【数据结构与算法】解题20240312，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

这里写目录标题

一、字符串转换整数 (atoi)
二、1. 两数之和
三、128. 最长连续序列
四、73. 矩阵置零

一、字符串转换整数 (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 。

class S8:def func(self, s):i = 0n = len(s)while i < n and s[i] == ' ':i += 1if i == n or n == 0:  # 如果找不到字符串，返回0return 0# 判断正负数flag = 1if s[i] == '-':flag = -1# 判断符号位，如果存在符号位，i向后移动1位if s[i] in ('-', '+'):i += 1ans = 0i_min = -2 ** 31i_max = 2 ** 31 - 1# 当s[i]大于等于'0' and  小于等于'9'while i < n and '0' <= s[i] <= '9':ans = int(s[i]) + ans * 10i += 1if ans > i_max:breakans = flag * ansif ans > i_max:return i_maxelif ans < i_min:return i_minelse:return ansr = S8()
s = "42"
print(r.func(s))

二、1. 两数之和

简单
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

def func3(nums,target):n=len(nums)for i in range(n):value=target-nums[i]if value in nums:j=nums.index(value)if i==j:continueelse:return [i,j]else:continuenums = [2, 7, 11, 15]
target = 9
res=func3(nums,target)
print(res)

三、128. 最长连续序列

中等
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

class S128:def func(self, nums):ret = 0  # 初始值nums_set = set(nums)for num in nums_set:if (num - 1) not in nums_set:  # 如果当前值是一个连续序列的起点，统计这个连续序列的长度seq_len = 1  # 连续序列 的长度初始为1while (num + 1) in nums_set:  # 如果下一个值在集合中，连续序列的长度+1seq_len += 1num += 1  # num+1后继续遍历ret = max(ret, seq_len)  # 判断最大值return retr = S128()
nums = [100, 4, 200, 1, 3, 2]
print(r.func(nums))

四、73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。
在这里插入图片描述
思路：
用两个标记数组分别记录每一行和每一列是否出现0
首先遍历该数组一次，如果某个元素为0，那么就将该元素所在的行和列
所对应的标记数组置为true，最后我们再次遍历数组，用标记数组更新原数组即可。

class S73:def func(self,nums11):m,n=len(nums11),len(nums11[0])row,col=[False]*m,[False]*nfor i in range(m):for j in range(n):if nums11[i][j]==0:row[i]=col[j]=Truefor i in range(m):for j in range(n):if row[i] or col[j]:nums11[i][j]=0return nums11
r=S73()
nums11 = [[1,1,1],[1,0,1],[1,1,1]]
print(r.func(nums11))