LeetCode 43字符串相乘&44通配符匹配

华为云博客 技术博客 12497 21

原创公众号：bigsai，回复进群加入力扣打卡群。

字符串相乘

题目描述：

给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。

不允许我们使用BigInteger，肯定无法使用常规类型去解决问题了。对应也要使用其他方法去解决问题。

怎么处理我们需要分析这个乘法的底层逻辑到底是怎么样的。
在这里插入图片描述

这样看这张图，其算法逻辑应该很清晰了，所以我们在具体处理的时候就用一个int数组用来表示对应位数乘积的值，最后从个位向上进位只保留各位就可以。

你可能会疑问，如果两个数组的长度分别为a和b这个数组到底该开多大呢？

  • a+b大小就够了，怎么分析呢？其中一个a不变。另一个b变成最小b+1数字即十的倍数，那么这样在相乘的时候也不过是a+b长度，所以这里a+b长度就够了。

ac的代码为：

public String multiply(String num1, String num2) { if("0".equals(num1)||"0".equals(num2))return "0"; char a[]=num1.toCharArray();
		char b[]=num2.toCharArray(); int value[]=new int[a.length+b.length]; for(int i=a.length-1;i>=0;i--)
		{ for(int j=b.length-1;j>=0;j--) { int index=a.length-1-i+b.length-1-j; value[index]+=(a[i]-'0')*(b[j]-'0'); }
		} //System.out.println(Arrays.toString(a)+""+Arrays.toString(b)+" "+Arrays.toString(value));
		for(int i=0;i<value.length-1;i++)
		{ value[i+1]+=value[i]/10; value[i]=value[i]%10;
		}
		int index=value.length-1;
		while(value[index]==0)
		{index--;}
		StringBuilder sBuilder=new StringBuilder();
		while (index>=0) { sBuilder.append(value[index--]);
		}
		return sBuilder.toString(); }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

在这里插入图片描述

通配符匹配

在这里插入图片描述
在这里插入图片描述

这题的话其实和前面的正则表达式很像，但是又略有区别。如果dp[i][j]表示匹配串前i个和模式串j个匹配情况(boolean类型)。核心的状态转移方程为：

dp[i][j]=dp[i-1][j-1] (s[i]==p[j]||p[j]=='?')
dp[i][j]=dp[i][j-1]||dp[i-1][j] (p[j]=='*');
  • 1
  • 2

在这里插入图片描述

public boolean isMatch(String s, String p) { int slen=s.length();
		int plen=p.length();
		char p1[]=p.toCharArray();
		char s1[]=s.toCharArray();
		boolean dp[][]=new boolean[slen+1][plen+1];
		dp[0][0]=true; for(int i=0;i<plen;i++) { if(p1[i]=='*') { dp[0][i+1]=true; } else break; } for(int j=1;j<=plen;j++)//遍历模式串
		{ for(int i=1;i<=slen;i++)//遍历匹配串 { //相等可以匹配 if(p1[j-1]=='?'||s1[i-1]==p1[j-1])//当前单词可以匹配 { dp[i][j]=dp[i-1][j-1]; } else if(p1[j-1]=='*')//可以匹配任意多个 { dp[i][j]=dp[i][j-1]||dp[i-1][j]; } }
		}
		//System.out.println(dp[s.length()][p.length()]);
		return dp[slen][plen]; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

在这里插入图片描述
至于还有贪心算法和其他优化方案，今天就不更了，下次可能会补更。

本次就到这里啦，感觉不错记得点赞或一键三连哦，个人公众号：bigsai 回复 bigsai 更多精彩和资源与你分享。
在这里插入图片描述

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/109247418

（完）