字符串相加(力扣第415题)
题目要求：给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例：
输入：num1 = "11", num2 = "123" 输出："134" 输入：num1 = "456", num2 = "77" 输出："533" 输入：num1 = "0", num2 = "0" 输出："0"
解题思路：
这道题目其实就是把字符串的数字进行加法运算，但是不可以直接转成int来进行操作。
那么怎么把它间接转成int呢，这就用到char的特性了，对于char类型如果相减，那么就可以得到int值，例如: int a = '5'-'0'; a的值为5。
这里我们就按照正常的加法运算来做，从右往左每一位相加，保留相加的个位数，然后 /10 得到的数作为下一次相加的数参与进去，直到所有位数加完。如果说两个数长度不一样，那么就往短的前面加0
public static String addStrings(String num1, String num2) { //构建一个结果，方便后面拼接 StringBuffer result = new StringBuffer(); //定义两个数的最后一位 int i = num1.length() - 1; int j = num2.length() - 1; //定义两个数同一个位置相加 /10 的结果 int carry = 0; //这里开始循环，当所有位置相加完毕之后，并且最后一次相加没有大于10将退出循环 while (i >= 0 || j >= 0 || carry != 0) { //当大于等于0当时候取当前当数，否则就是位数不够了用0来补充 int x = i >= 0 ? num1.charAt(i) - '0' : 0; int y = j >= 0 ? num2.charAt(j) - '0' : 0; //结果就是相加 int sum = x + y + carry; //大于十的部分记录一下，只保留个位 result.append(sum % 10); carry = sum / 10; i--; j--; } return result.reverse().toString(); }
字符串相乘(力扣第43题)
题目要求：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例：
输入: num1 = "2", num2 = "3" 输出: "6" 输入: num1 = "123", num2 = "456" 输出: "56088"
解题思路：
这道题目其实就是字符串进行乘法，也是不能直接转成int类型，还是需要用char类型来中转一下。
当然本题也可以像上题一样，直接暴力的按照算术方式进行计算，但是代码量非常大，并且不容易记忆。那么这里我们采用数组的方式来进行计算。
这里需要定义一个用来存储结果的数组，长度为两个数长度相加，毕竟99*999=98901
我们把第一个数作为外层循环，第二个数作为内层循环，然后两两相乘，这里要注意到内层循环每循环一次结果的存放下标要左移。
public String multiply(String num1, String num2) { //1.如果两个数都为0，直接返回 if (num1.equals("0") || num2.equals("0")) { return "0"; } //2。定义结果数组 int[] resultArr = new int[num1.length() + num2.length()]; //3。遍历第一个数每一个字符 for (int i = num1.length() - 1; i >= 0; i--) { int x = num1.charAt(i) - '0'; //遍历第二个数每一个字符 for (int j = num2.length() - 1; j >= 0; j--) { int y = num2.charAt(j) - '0'; //对两个字符进行相乘 int product = x * y; /** * 临时数为：相乘结果当前最后一位对应的下标位置的数+相乘结果 * 然后在把临时数从新进行保存 * 这里i+j+1为关键 */ int temp = resultArr[i + j + 1] + product; resultArr[i + j + 1] = temp % 10; resultArr[i + j] += temp / 10; } } //如果当前结果数组第一位是0，那么就取1到length-1，如果是1，那么就取0到length-1 StringBuffer result = new StringBuffer(); int start = resultArr[0] == 0 ? 1 : 0; for (int i = start; i < resultArr.length; i++) { result.append(resultArr[i]); } return result.toString(); }
去除重复字母(力扣第316题)
题目要求：给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对
位置）。
示例：
输入：s = "bcabc" 输出："abc" 输入：s = "cbacdcbc" 输出："acdb"
数组递归法
解题思路：
首先我们要保证最左边的字母是最小的，但是也不完全一定就是a，bacad就不可以，因为b在后面没出现过一次，所以我们有两个条件挑选最左侧值。数值越小越好，但是如果后面没有值重复了，无论多大也都作为最左值。
这里我们先定义一个数组，用来存储26个字母出现的次数
然后我们遍历字符串，然后找到最小的字符，在找的过程中，如果有的值在后面的字符中没出现过(也就是在数组中-1为0)，那么就退出循环。
然后获取到这个字符后，截取这个字符后面的字符串进行递归，不过要把重复值去掉。
public String removeDuplicateLetters(String s) { if (s.length() == 0) { return ""; } //定义一个用来记录最小字母的指针 int position = 0; //定义26个字母次数的数组 int[] count = new int[26]; for (int i = 0; i < s.length(); i++) { count[s.charAt(i) - 'a']++; } //遍历字符串 for (int i = 0; i < s.length(); i++) { //当前位置字符如果小于最小字母指针时，指针移动到该最小字母的位置 if (s.charAt(i) < s.charAt(position)) { position = i; } //当前位置-1为0的时候，代表后面不会出现该字母了，所以该字母必须作为最左侧字母了 if (--count[s.charAt(i) - 'a'] == 0) { break; } } //递归获取每次最小的字母，并且在递归传递参数的时候，要把当前位置前的字符全部删除，当前位置后的字符和当前位置的字符相同的也删掉 return s.charAt(position) + removeDuplicateLetters(s.substring(position + 1).replaceAll("" + s.charAt(position), "")); }
使用栈
解题思路：
遇到一个新字符，如果比栈顶小，并且在新字符后面还有和栈顶一样的 就把栈顶的字符抛弃
public String removeDuplicateLetters(String s) { //定义一个栈 Stack<Character> stack = new Stack<>(); //循环字符串 for (int i = 0; i < s.length(); i++) { Character current = s.charAt(i); //如果栈中包含这个数直接继续下次循环 if (stack.contains(current)) { continue; } // 如果栈顶的数大于当前数，并且字符串后边的值不是唯一的 while (!stack.isEmpty() && stack.peek() > current && s.indexOf(stack.peek(), i) != -1) { stack.pop(); } //入栈 stack.push(current); } //取栈的值进行拼接 char chars[] = new char[stack.size()]; for (int i = 0; i < stack.size(); i++) { chars[i] = stack.get(i); } return new String(chars); }
