字符串相乘与反转(15)
- 2019 年 10 月 5 日
- 筆記
字符串相乘与反转(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)
