刷题打卡，第 二十四 天
题目一、43. 字符串相乘
题目二、1800. 最大升序子数组和
题目一、43. 字符串相乘
原题链接：43. 字符串相乘
题目描述：
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
/
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
/
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
/
提示：
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
解题思路：
我们需要获得两个字符串表示的正整数num1和num2的乘积，而且记过依旧以字符串形式输出。
首先我们可以通过Ascii码值获取到正整数每个位置上的数字。
接下来，我们模拟出乘法运算的步骤，用num2中每个位置上的数，依次与被乘数num1相乘得出结果，每次结果都里加起来就可以得到最终乘积。
每次相乘的时候还需要注意给乘数num2当中每个位置上的数补齐后面数位中的0。
而字符串的相加 与 相乘，我们都不可以使用任何内置的 BigInteger 库或直接将输入转换为整数，那么就需要借助可变的字符串序列StringBuffer()中的方法。
如果不理解代码中的 字符串相加的方法，我以看看这篇文章中这道题的讲解：[415. 字符串相加]
提交代码：
class Solution { public String multiply(String num1, String num2) { //其中一个数为0时，乘积也为0 if(num1.equals("0") || num2.equals("0")) return "0"; String answer = "0"; int n1 = num1.length(); //获取num1字符串的长度 int n2 = num2.length(); //获取num2字符串的长度 for(int i = n2-1;i >= 0; --i){ //从最小的数位开始遍历num2 StringBuffer sb = new StringBuffer(); int add = 0; //满十进一 //需要给每个位置上的数字补齐后面的0，十位补一个0，百位补两个0，依次类推 for(int j = n2-1;j > i;--j){ sb.append(0); } //获取num2字符串当前位置的数字 int y = num2.charAt(i)-'0'; //遍历num1各个位置上的数字 for(int k = n1-1;k >= 0;--k){ int x = num1.charAt(k)-'0'; //num1各位置上的数字依次与num2当前数字相乘，同时加上上次相乘的进位数 int num = x*y + add; //给字符序列后面补上结果个位位置上的数字 sb.append(num % 10); //记录进位数 add = num/10; } if(add != 0){ //补齐进位数 sb.append(add%10); } //将每次结果加起来，最终就是两个数相乘的结果 answer = plus(answer,sb.reverse().toString()); } return answer; } //不使用Integer相应API，将字符串类型的两个整数相加，返回字符串结果 public String plus(String str1,String str2){ StringBuffer sb = new StringBuffer(); int index_1 = str1.length() - 1; //str1末尾字符下标 int index_2 = str2.length() - 1; //str2末尾字符下标 int add = 0; //满十进一 while(index_1 >=0 || index_2 >= 0 || add != 0){ int n1 = index_1 >= 0 ? str1.charAt(index_1) - '0' : 0; int n2 = index_2 >= 0 ? str2.charAt(index_2) - '0' : 0; int sum = n1 + n2 + add; sb.append(sum % 10); add = sum / 10; index_1--; index_2--; } sb.reverse(); return sb.toString(); } }
提交结果：
题目二、1800. 最大升序子数组和
原题链接：1800. 最大升序子数组和
题目描述：
给你一个正整数组成的数组 nums ，返回 nums 中一个 升序 子数组的最大可能元素和。
子数组是数组中的一个连续数字序列。
已知子数组 [numsl, numsl+1, …, numsr-1, numsr] ，若对所有 i（l <= i < r），numsi < numsi+1 都成立，则称这一子数组为 升序 子数组。注意，大小为 1 的子数组也视作 升序 子数组。
/
示例 1：
输入：nums = [10,20,30,5,10,50]
输出：65
解释：[5,10,50] 是元素和最大的升序子数组，最大元素和为 65 。
/
示例 2：
输入：nums = [10,20,30,40,50]
输出：150
解释：[10,20,30,40,50] 是元素和最大的升序子数组，最大元素和为 150 。
/
示例 3：
输入：nums = [12,17,15,13,10,11,12]
输出：33
解释：[10,11,12] 是元素和最大的升序子数组，最大元素和为 33 。
/
示例 4：
输入：nums = [100,10,1]
输出：100
解题思路：
题目要求我i们获取到，数组所有升序序列中，最大的元素和。
那么我们可以通过遍历数组来实现，一边遍历数组，一边记录元素和，当检测到下一个元素值小于或等于当前元素，也就代表两者无法构成升序数组，我们将最大元素和记录下来，然后将元素和清零，重复操作。
当遍历完整个数组，我们也遍历完了所有升序序列的元素和，自然可以得到其中的最大元素和并返回…
提交代码：
class Solution { public int maxAscendingSum(int[] nums) { int curr = 0; //表示当前元素和 int max = 0; //表示最大元素和 int n = nums.length - 1; //数组最后一个元素的下标 for(int i = 0;i < n;++i){ //遍历数组 curr += nums[i]; //数字累加 if(nums[i] >= nums[i+1]){ //若与下一个元素无法组成升序数组 max = Math.max(max,curr); //记录当前最大元素和 curr = 0; //元素和清零 } } //我们只遍历到了数组的倒数第二位： //还需要在当前最大元素和 与 最后一个升序数组的元素和比较大小 return Math.max(max,curr + nums[n]); } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
