字符串相乘与反转(15)
字符串相乘与反转(15)
字符串相乘与反转(15)
0.前言1.字符串相乘2.反转字符串3.作者的话
0.前言
周五到了，我们LeetCode刷题继续。
首先来共勉一句话：Use the utility in the API is recommended in the project. But if you use it in an interview, you will definitely fail .来自老表!
LeetCode终于坚持下来了，第15篇！
今日讨论：字符串相乘 与 反转字符串
在这里我们一起坚持，点击公众号右下角->联系我可以进入leetcode微信群哦！备注：刷题
1.字符串相乘
问题
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1和num2的长度小于110。num1和num2只包含数字0-9。num1和num2均不以零开头，除非是数字 0 本身。- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
思路与代码结合
（1）首先计算两个数的长度分别用常量存储；
（2）若当前两个数字有一个为0或者为空字符，直接返回字符'0'；
（3）开辟一个数组空间，用于存放两个数相乘的结果；
我们知道两个数相乘，数字的长度不大于两数长度之和！
（4）两重for循环，用于乘法的核心操作；
假设现在有两个数，num1="48",num2='"17"
4 8
1 7
---------
0 0 0 0
0 0 5 6
0 3 3 6
--------
0 0 8 0
0 4 8 0
--------
0 8 1 6
如上表：就是我们乘法的基本运算过程：
s1_len-i-1与s2_len-j-1目的是从后面往前运算。
而low与hight分别代表低位与高位，这里的低位指的是被保留的数，高位指的是进位数！
然后不断更新对应位置的值，最终得到了一个[0,8,1,6]的数组，然后我们需要进一步做的就是后续处理！
后续处理：后面两层for循环，实现去除0以及转字符串，最终返回结果！
class Solution:
def multiply(self, num1, num2):
s1_len = len(num1)
s2_len = len(num2)
if s1_len == 0 or s2_len == 0 or num1 == '0' or num2 == '0':
return '0'
res_list = [0 for i in range(s1_len+s2_len)]
for i in range(s1_len):
for j in range(s2_len):
muti_num = int(num1[s1_len-i-1])*int(num2[s2_len-j-1])
low = s1_len+s2_len-i-j-1
print("----")
print(low)
high = s1_len+s2_len-i-j-2
print(high)
muti_num += res_list[low]
res_list[low]=muti_num%10
res_list[high]+=muti_num//10
print(res_list)
str_res = ''
for i in range(len(res_list)):
if res_list[i] != 0:
for j in res_list[i:]:
str_res += str(j)
return str_res
运行
2.反转字符串
问题
编写一个函数，其作用是将输入的字符串反转过来。
示例 1:
输入: "hello"
输出: "olleh"
示例 2:
输入: "A man, a plan, a canal: Panama"
输出: "amanaP :lanac a ,nalp a ,nam A"
这里给出三种方法！
第一种：直接法
class Solution:
def reverseString(self, s):
return s[::-1]
第二种：插补法(自己起的名字)
一层循环，倒着取出字符，记得从index=1开始，最后在加第一位字符！
class Solution:
def reverseString(self, s):
if not s:
return s
new_str = ''
for i in range(1,len(s)):
new_str+=s[-i]
new_str += s[0]
return new_str
第三种：头尾颠倒法(自己起的名字)
class Solution:
def reverseString(self, s):
t = list(s)
i=0
j=len(s)-1
while i<j:
temp = t[i]
t[i]=t[j]
t[j]=temp
i+=1
j-=1
return ''.join(t)