【Day23】力扣：LeetCode算法刷题 [927. 三等分 ] [415. 字符串相加]
CSDN话题挑战赛第2期
参赛话题：学习笔记
刷题打卡，第 二十三 天
- 题目一、927. 三等分
- 题目二、415. 字符串相加
⚽
来刷题⚽ 记录每日LeetCode✔刷题专栏✔
题目一、927. 三等分
原题链接：927. 三等分
题目描述：
给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分 ，使得所有这些部分表示相同的二进制值。
如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来：
- arr[0], arr[1], …, arr[i] 为第一部分；
- arr[i + 1], arr[i + 2], …, arr[j - 1] 为第二部分；
- arr[j], arr[j + 1], …, arr[arr.length - 1] 为第三部分。
- 这三个部分所表示的二进制值相等。
如果无法做到，就返回 [-1, -1]。
注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 [0,1,1] 和 [1,1] 表示相同的值。
/
示例 1：
输入：arr = [1,0,1,0,1]
输出：[0,3]
/
示例 2：
输入：arr = [1,1,0,1,1]
输出：[-1,-1]
/
示例 3:
输入：arr = [1,1,0,0,1]
输出：[0,2]
/
提示：
3 <= arr.length <= 3 * 104
arr[i] 是 0 或 1
解题思路：
为了解决问题，我们需要将二进制数组分成三份，让它们非空且可以表示一样的值。
为了达到目的，需要不断地将不符合要求的情况排除：
我们知道，二进制值表示的数主要与当中的数字1挂钩，那么我们可以先从这个方面入手，遍历二进制数组，记录数组中数字1出现的次数，即为sum。如果sum不能被平均分成三等份，可以证明此二进制数组没办法分成三份表示相同值得二进制数,可以直接返回数组{-1，-1}；
当数组中没有出现数字1,也就是sum = 0,无论我们如何分配，都能获取到三份非空的，表示相同值的二进制数，随意返回符合题目要求的两个下标即可；注意：题目提示我们二进制数长度至少为3,那我们返回{0，2}出错的可能性极小，所以返回数组{0，2}即可。
接下来，为了判断出二进制数能否分为等值的三份，我们从平均分成三份的数字1当中，获取每份首次出现的数字1的下标，记作first second 和third，进而同时向后遍历，以此判断三份二进制数是否能表示相同值。
因为题目允许二进制数中存在前置的0，因此，我们唯一能确定长度的是第三部分，只需要计算第三份数字1的首个数字‘1’的下标third到原始二进制数组尾部的距离即可。
如果遍历过程中发现遍历到的三个数字不完全相同，说明无法将二进制数组分成三个表示相同值的部分，返回{-1，-1}；
如果我们能顺利遍历完三个部分的二进制数，说明一切顺利，就可以返回对应下标了。
提交代码：
class Solution {
public int[] threeEqualParts(int[] arr) {
int sum = 0;
for(int a : arr) sum += a; //记录二进制数中 1 出现的次数
if(sum % 3 != 0) return new int[]{-1,-1}; //1不能平均分成三等分，返回{-1，-1}
if(sum == 0) return new int[]{0,2}; //全为0，怎么分都相等，返回合理的下标即可
//接下来需要获取三等分中，每等分第一个1的位置
int first = 0,second = 0,third = 0;//分别代表每个等分第一个1的下标
int temp = sum / 3; //获取每个等分的长度
int curr = 0; //记录遇到的1的个数
for(int i = 0;i < arr.length;++i){ //遍历二进制数
if(arr[i] == 1){ //遇到1
if(curr == 0){ //如果是第一个遇到的1
first = i; //那么也是第一等分的第一个1，记录下标位置
}else if(curr == temp){ //如果第一等分中的1已经记录完
second = i; //那么现在遇到的1就是第二等分的第一个1
}else if(curr == temp*2){ //如果第一二等分的1已经记录完
third = i; //那么现在遇到的1是第三等分的首个1
}
++curr; //记录1出现的次数
}
}
int len = arr.length - third; //获取固定的第三等分的长
//我们要求前两等分的长度不小于第三代等分
if(first+len <= second && second+len <= third){
len = 0; //从每个等分开头开始遍历
while(third+len < arr.length){//知道第三等分遍历完
//当遍历到的三个数不完全相同，说明三个等分无法表示相同的二进制值
if(arr[first+len] != arr[second+len] || arr[third+len] != arr[second+len])
//返回-1
return new int[]{-1,-1};
++len;
}
//三个等分都遍历完了，我们获取题目要求的i和j对应的位置，（当前len比固定长度大一个长度）
return new int[]{first+len-1,second+len};
}
//一二等分中有长度小于的三等分的情况，返回-1
return new int[]{-1,-1};
}
}
提交结果：
题目二、415. 字符串相加
原题链接：415. 字符串相加
题目描述：
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
/
示例 1：
输入：num1 = “11”, num2 = “123”
输出：“134”
/
示例 2：
输入：num1 = “456”, num2 = “77”
输出：“533”
/
示例 3：
输入：num1 = “0”, num2 = “0”
输出：“0”
解题思路：
字符串相加，却不可以将字符直接转化为整形来运算，而且需要输出的依旧是字符串，那么为了得到每个位置上的数字，我们可以利用ASCII码值的加减来获取。
我们首先获取字符串的长度num.length();，然后也就可以确定个位数数字的下标：num.length() - 1;
我们从最末尾数字开始遍历，当前位置的数字通过当前位置的字符减去符号’0‘获取：
'0' - '0' = 0;
'1' - '0' = 1;
'2' - '0' = 2;
…
'9' - '0' = 9;
知道获取到当前位置数字的方法后，我们依次将两个字符串相同位置上的数字相加，同时设置一个add参数，记录满十进一的数位。
那么我们每次就将两数字之和的个位数连接进结果的字符串中，十位数则累加进下一次的两数之和中，最终也就得到了我们需要的字符串。
还需要注意的是，我们从个位数开始遍历，所以得到的字符串是从最小位数字开始的，还需要将字符串反转一下，才算完成。
提交代码：
class Solution {
public String addStrings(String num1, String num2) {
StringBuffer sb = new StringBuffer();
//从最小位数字下标
int index_1 = num1.length() - 1;
int index_2 = num2.length() - 1;
int add = 0; //满十进一
while(index_1 >= 0 || index_2 >=0 || add != 0){ //从最低位数字开始遍历
//该数位存在数字，记录下来
int n1 = index_1 >= 0?num1.charAt(index_1)-'0':0;
int n2 = index_2 >= 0?num2.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();//输出字符串
}
}
提交结果：
⚽
求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
