文章目录
一、字符串相乘
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）或直接将输入转换为整数来处理。
2、源代码
# -*- coding: utf-8 -*-
"""
Created on Mon Nov 22 13:33:07 2021
Function:
@author: 小梁aixj
"""
class solution(object):
def multiply(self, num1,num2):
if num1=='0' or num2=='0':
return '0'
res=''
ls1,ls2,=len(num1),len(num2)
ls=ls1+ls2
arr=[0]*ls
for i in reversed(range(ls1)):
for j in reversed(range(ls2)):
arr[i+j+1] += int(num1[i])*int(num2[j])
for i in reversed(range(1,ls)):
arr[i-1]+=arr[i]//10
arr[i]%=10
pos = 0
if arr[pos]==0:
pos += 1
while pos <ls:
res=res+str(arr[pos])
pos+=1
return res
if __name__=='__main__':
s=solution()
print(s.multiply('2', '3'))
3、运行结果
二、合并两个有序链表
1、程序简介
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2
输入：l1 = [], l2 = []
输出：[]
示例 3
输入：l1 = [], l2 = [0]
输出：[0]
提示
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
## 2、源代码
# -*- coding: utf-8 -*-
"""
Created on Mon Nov 22 11:13:43 2021
Function:
@author: 小梁aixj
"""
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkList:
def __init__(self):
self.head = None
def initList(self, data):
self.head = ListNode(data[0])
r = self.head
p = self.head
for i in data[1:]:
node = ListNode(i)
p.next = node
p = p.next
return r
def convert_list(self,head):
ret = []
if head == None:
return
node = head
while node != None:
ret.append(node.val)
node = node.next
return ret
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
h = ListNode(0, None)
p = h
while l1 and l2:
if l1.val < l2.val:
p.next = l1
p = l1
l1 = l1.next
else:
p.next = l2
p = l2
l2 = l2.next
if l1:
p.next = l1
else:
p.next = l2
return h.next
# %%
l = LinkList()
list1 = [1,2,4]
list2 = [1,3,4]
l1 = l.initList(list1)
l2 = l.initList(list2)
s = Solution()
print(l.convert_list(s.mergeTwoLists(l1, l2)))
3、运行结果
三、复原IP地址
1、程序简介
要求
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
示例 1
输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]
示例 2
输入：s = “0000”
输出：[“0.0.0.0”]
示例 3
输入：s = “1111”
输出：[“1.1.1.1”]
示例 4
输入：s = “010010”
输出：[“0.10.0.10”,“0.100.1.0”]
示例 5
输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]
2、源代码
# -*- coding: utf-8 -*-
"""
Created on Mon Nov 22 11:14:05 2021
Function:
@author: 小梁aixj
"""
class Solution(object):
def restoreIpAddresses(self, s):
ls=len(s)
if ls == 0 or ls > 12:
return []
res=[]
for i in range(1,4):
for j in range(1,4):
for k in range(1,4):
m=ls-i-j-k
if m>0 and m<=3:
add1 =s[0:i]
add2 = s[i:i+j]
add3=s[i+j:i+j+k]
add4=s[i+j+k:]
if self.isValid(add1) and self.isValid(add2) and \
self.isValid(add3) and self.isValid(add4):
res.append(add1+'.'+add2+'.'+add3+'.'+add4)
return res
def isValid(self, add):
if len(add) == 1:
return True
if add[0] == '0':
return False
if int(add) <= 255:
return True
return False
if __name__=='__main__':
s=Solution()
print(s.restoreIpAddresses('25525511135'))