【Day23】力扣：LeetCode算法刷题 [927. 三等分 ] [415. 字符串相加]

参赛话题：

⚽来刷题⚽ 记录每日LeetCode

题目一、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. 字符串相加

原题链接：

题目描述：

给定两个字符串形式的非负整数 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
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~