模拟运算
两数相加【LC2】
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
我的题解
- 2021/12/18
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode pre = dummyHead; int carryFlag = 0;//carryFlag为0表示无进位，为1表示有进位 while(l1!=null || l2!=null){ int val1 = l1==null ? 0 :l1.val; int val2 = l2==null ? 0 :l2.val; pre.next = new ListNode( (val1 + val2+ carryFlag) % 10 ); carryFlag = (val1 + val2 + carryFlag) / 10; l1 = l1==null ? null: l1.next ; l2 = l2==null ? null: l2.next ; pre = pre.next; } pre.next = carryFlag == 1 ? new ListNode(1) : null; return dummyHead.next; } }
- 时间复杂度：O(N+M)，其中 N和M分别是链表中的节点数。
- 空间复杂度：O(1)，返回值不计入空间复杂度
两数相加Ⅱ【LC445】
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
反转链表
2022/11/4
- 思路：将链表1、链表2反转后进行求和，并使用变量记录进位，最后将结果再进行反转后返回
- 实现
- 如果有一个链表为空链表，那么将另一个链表返回
- 将链表1、链表2反转得到新的头结点cur1、cur2
- 使用变量cnt记录低位节点相加后的进位结果，使用cur记录求和后的结果
- 当两个链表不都为空时，需要进行累加
(val1+val2+cnt)%10得到新节点 - 注意：需要处理空节点，空节点的值记为0
- 更新：cnt = (val1+val2+cnt)/10
- 最后判断是否存在进位，如果存在的话加在链表末尾
- 最后将结果进行反转
- 代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode cur1 = reverse(l1); ListNode cur2 = reverse(l2); int cnt = 0; ListNode dummyNode = new ListNode(0); ListNode cur = dummyNode; while (cur1 != null || cur2 != null){ int val1 = cur1 == null ? 0 : cur1.val; int val2 = cur2 == null ? 0 : cur2.val; cur.next = new ListNode((cnt + val1 + val2) % 10); cnt = (cnt + val1 + val2 ) / 10; cur1 = cur1 == null ? null : cur1.next ; cur2 = cur2 == null ? null : cur2.next ; cur = cur.next; } if (cnt != 0){ cur.next = new ListNode(cnt); } return reverse(dummyNode.next); } public ListNode reverse(ListNode head){ ListNode dummyNode = new ListNode(0,head); ListNode cur = dummyNode.next; while (cur != null && cur.next != null){ ListNode nextTemp = cur.next.next; cur.next.next = dummyNode.next; dummyNode.next = cur.next; cur.next = nextTemp; } return dummyNode.next; } }
- 复杂度分析
- 时间复杂度：O(N+M)，其中 N和M分别是链表中的节点数。
- 空间复杂度：O(1)，返回值不计入空间复杂度
前后双指针【太繁琐了】
2022/11/5思路：使用前后双指针将链表中的两数之后记录在数组中，然后倒序遍历数组，处理产生的进位，最后通过数组生成链表
实现
先将两个链表遍历一遍，统计其节点个数，记为n1,n2，使用数组nums记录数值
然后设置指针位于链表的起点，记为cur1，cur2
如果n1 > n2，那么将cur1先移动n1-n2步，并将数值记录在nums中
如果n2 > n1，那么将cur2先移动n1-n2步，并将数值记录在nums中
此时cur1和cur2位于相同位置，将链表中的两数进行相加操作，并将数值（val1+val2）记录在nums中
使用变量cnt记录低位的进行，然后倒序遍历数组处理进位
判断是否存在最高位进位，如果存在的话加在链表开头
最后通过nums数组构建链表
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode cur1 = l1; ListNode cur2 = l2; int n1 = 0, n2 = 0; // 统计个数 while (cur1 != null){ n1++; cur1 = cur1.next; } while (cur2 != null){ n2++; cur2 = cur2.next; } cur1 = l1; cur2 = l2; int i = 0; int[] nums; // 移动后指针 if (n1 > n2){ nums = new int[n1]; while (i < n1 - n2){ nums[i++] = cur1.val; cur1 = cur1.next; } }else { nums = new int[n2]; while (i < n2 - n1){ nums[i++]= cur2.val; cur2 = cur2.next; } } // 链表相加 while (cur1 != null && cur2 != null){ nums[i++] = cur1.val + cur2.val; cur1 = cur1.next; cur2 = cur2.next; } // 处理进位 int cnt = 0; for (i = nums.length - 1; i >= 0;i--){ int tmp = (nums[i] + cnt) / 10; nums[i] = (nums[i] + cnt) % 10; cnt = tmp; } // 构造链表 ListNode dummyNode = new ListNode(0); ListNode cur = dummyNode; if (cnt != 0){ cur.next = new ListNode(cnt); cur = cur.next; } for(i = 0; i < nums.length; i++){ cur.next = new ListNode(nums[i]); cur = cur.next; } return dummyNode.next; } }
复杂度分析
时间复杂度：O(N+M)，其中 N和M分别是链表中的节点数。
空间复杂度：O(N+M)，返回值不计入空间复杂度
栈
2022/11/5
思路：由于链表中数位的顺序与加法的顺序相反，为了逆序处理所有数位，可以使用栈，把所有数字压入栈中，再依次取出相加，计算过程中注意进位的情况
实现：倒序构建链表，注意使用变量记录当前节点的下一节点，完成链表的构建
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null){ return l2; } if (l2 == null){ return l1; } ListNode cur1 = l1; ListNode cur2 = l2; Deque<ListNode> st1 = new LinkedList<>(); Deque<ListNode> st2 = new LinkedList<>(); while (cur1 != null ){ st1.addFirst(cur1); cur1 = cur1.next; } while (cur2 != null){ st2.addFirst(cur2); cur2 = cur2.next; } int cnt = 0; ListNode nn = null; while (!st1.isEmpty() || !st2.isEmpty() || cnt != 0){ int val1 = st1.isEmpty() ? 0 :st1.pollFirst().val; int val2 = st2.isEmpty() ? 0 :st2.pollFirst().val; int val = (val1 + val2 + cnt) % 10; cnt = (val1 + val2 + cnt) / 10; ListNode ptr = new ListNode(val); ptr.next = nn; nn = ptr; } return nn; } }
字符串相加【LC415】
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
思路：使用双指针从整数的最低位模拟相加操作
- 使用两个指针从整数的低位开始定位字符，模拟相加操作
- 使用变量记录低位的进位，将每位的相加结果放入StringBuilder变量的开头中
- 每次相加后的结果为 ( v a l 1 + v a l 2 + c n t ) % 10
- 进位为( v a l 1 + v a l 2 + c n t ) / 10
实现
class Solution { public String addStrings(String num1, String num2) { StringBuilder sb = new StringBuilder(); int i = num1.length() - 1, j = num2.length() - 1; int cnt = 0; while (i >= 0 || j >= 0 || cnt != 0){ int val1 = i >= 0 ? num1.charAt(i) - '0' : 0; int val2 = j >= 0 ? num2.charAt(j) - '0' : 0; sb.insert(0,(val1+val2+cnt)%10); cnt = (val1+val2+cnt) / 10; i--; j--; } return new String(sb); } }
复杂度
时间复杂度：O ( n ) ,n为两个字符串的最大长度
空间复杂度：O ( 1 )
负二进制数相加【LC1073】
给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。
数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字(-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。
返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。
思路
从低位开始模拟负二进制相加的过程，负数加法每逢2进-1。记cnt进位，x=arr1[i]+arr2[j]+cnt
当x≥2时，我们需要将高位进位，但由于在负二进制数中高位永远小于低位，因此我们需要进-1，然后将x置为0
(−2)i+1−1=(−2)i
当x=−1时，由于−(−2)i=(−2)i+(−2)i+1因此可以将x置为1，cnt置为0
其他情况下x不变，cnt为0
最后由于需要将结果进行反转，因此需要去除反转后的前导0，也就是在末尾的后置0
- 实现
class Solution { public int[] addNegabinary(int[] arr1, int[] arr2) { // 负二进制数的性质 // 1 + 1 进位 -1 // 0 - 1 进位 1，当前位置1 List<Integer> res = new ArrayList<>(); int n = arr1.length, m = arr2.length; int i = n - 1, j = m - 1; int cnt = 0; while (i >= 0 || j >= 0 || cnt != 0){ int num1 = i >= 0 ? arr1[i] : 0; int num2 = j >= 0 ? arr2[j] : 0; int x = num1 + num2 + cnt; cnt = 0; if (x >= 2){ x -= 2; cnt -= 1; }else if (x == -1){ x = 1; cnt += 1; } res.add(x); i--; j--; } // 去除前导0 while (res.size() > 1 && res.get(res.size() - 1) == 0){ res.remove(res.size() - 1); } // 反转 Collections.reverse(res); return res.stream().mapToInt(x -> x).toArray(); } }
复杂度
- 时间复杂度：O(m+n)
- 空间复杂度：O(m+n)
字符串相乘【LC43】
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
2023/6/1 实现起来有点难
普通竖式
- 思路
将字符串num2的每一位与字符串num1相乘，然后最后将每一轮的结果通过字符串加法累加
实现
class Solution { /** * 计算形式 * num1 * x num2 * ------ * result */ public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) { return "0"; } // 保存计算结果 String res = "0"; // num2 逐位与 num1 相乘 for (int i = num2.length() - 1; i >= 0; i--) { int carry = 0; // 保存 num2 第i位数字与 num1 相乘的结果 StringBuilder temp = new StringBuilder(); // 补 0 for (int j = 0; j < num2.length() - 1 - i; j++) { temp.append(0); } int n2 = num2.charAt(i) - '0'; // num2 的第 i 位数字 n2 与 num1 相乘 for (int j = num1.length() - 1; j >= 0 || carry != 0; j--) { int n1 = j < 0 ? 0 : num1.charAt(j) - '0'; int product = (n1 * n2 + carry) % 10; temp.append(product); carry = (n1 * n2 + carry) / 10; } // 将当前结果与新计算的结果求和作为新的结果 res = addStrings(res, temp.reverse().toString()); } return res; } /** * 对两个字符串数字进行相加，返回字符串形式的和 */ public String addStrings(String num1, String num2) { StringBuilder builder = new StringBuilder(); int carry = 0; for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry != 0; i--, j--) { int x = i < 0 ? 0 : num1.charAt(i) - '0'; int y = j < 0 ? 0 : num2.charAt(j) - '0'; int sum = (x + y + carry) % 10; builder.append(sum); carry = (x + y + carry) / 10; } return builder.reverse().toString(); } } 作者：breezean 链接：https://leetcode.cn/problems/multiply-strings/solutions/29100/you-hua-ban-shu-shi-da-bai-994-by-breezean/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(mn)
- 空间复杂度：O(m+n)，用于存储结果
优化竖式
思路
乘数 num1 位数为 m，被乘数 num2 位数为n，num1∗num2 结果 res 最大总位数为M+N
num1[i]∗num2[j] 的结果为 tmp(位数为两位，“0x”,“xy” 的形式)，其第一位位于res[i+j]，第二位位于res[i+j+1]。
省略了字符串相加和字符串反转的时间复杂度
实现
class Solution { public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) { return "0"; } int[] res = new int[num1.length() + num2.length()]; for (int i = num1.length() - 1; i >= 0; i--) { int n1 = num1.charAt(i) - '0'; for (int j = num2.length() - 1; j >= 0; j--) { int n2 = num2.charAt(j) - '0'; int sum = (res[i + j + 1] + n1 * n2); res[i + j + 1] = sum % 10; res[i + j] += sum / 10; } } StringBuilder result = new StringBuilder(); for (int i = 0; i < res.length; i++) { if (i == 0 && res[i] == 0) continue; result.append(res[i]); } return result.toString(); } } 作者：breezean 链接：https://leetcode.cn/problems/multiply-strings/solutions/29100/you-hua-ban-shu-shi-da-bai-994-by-breezean/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(mn)
- 空间复杂度：O ( m + n )，用于存储结果
分数到小数【LC166】
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于 104 。
思路
模拟竖式除法，过程为
首先使用分子第一次除以分母，如果余数为0，那么直接返回结果，否则继续进行除法运算
如果余数不为0，不断对余数乘10补零，将余数除以除数，计算新余数
由于答案一定为有限小数或者无限循环小数，
有限小数：不断进行除法运算，余数等于0，返回答案
无限循环小数：如果余数重复出现那么证明出现了循环部分，因此可以使用哈希表记录余数及其答案出现的位置，当余数重复出现时，将[ 上一次出现的位置，本次位置 − 1 ] [上一次出现的位置，本次位置-1][上一次出现的位置，本次位置−1]进行循环
由于分子和分母存在负数，因此先根据乘积判断结果是否小于0，如果小于0，先在StringBuilder中添加负号
实现
观察数据范围，为了防止溢出，使用long类型变量记录被除数和除数
class Solution { public String fractionToDecimal(int numerator, int denominator) { // 转 long 计算，防止溢出 long a = numerator, b = denominator; // 如果本身能够整除，直接返回计算结果 if (a % b == 0) return String.valueOf(a / b); StringBuilder sb = new StringBuilder(); // 如果其一为负数，先追加负号 if (a * b < 0) sb.append('-'); a = Math.abs(a); b = Math.abs(b); // 计算小数点前的部分，并将余数赋值给 a sb.append(String.valueOf(a / b) + "."); a %= b; Map<Long, Integer> map = new HashMap<>(); while (a != 0) { // 记录当前余数所在答案的位置，并继续模拟除法运算 map.put(a, sb.length()); a *= 10; sb.append(a / b); a %= b; // 如果当前余数之前出现过，则将 [出现位置 到 当前位置] 的部分抠出来（循环小数部分） if (map.containsKey(a)) { int u = map.get(a); return String.format("%s(%s)", sb.substring(0, u), sb.substring(u)); } } return sb.toString(); } } 作者：宫水三叶 链接：https://leetcode.cn/problems/fraction-to-recurring-decimal/solutions/1028784/gong-shui-san-xie-mo-ni-shu-shi-ji-suan-kq8c4/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O ( M ) ，复杂度取决于最终答案的长度，题目规定了最大长度不会超过10^4
实现
2023/7/13
class Solution { public String fractionToDecimal(int numerator, int denominator) { long x = numerator, y = denominator; StringBuilder sb = new StringBuilder(); Map<Long, Integer> map = new HashMap<>(); if (x * y < 0){ sb.append("-"); } x = Math.abs(x); y = Math.abs(y); long tmp = x / y; x = x % y; sb.append(tmp); if (x == 0){ return sb.toString(); } x *= 10; sb.append("."); while (x != 0L){ if (map.containsKey(x)){ int l = map.get(x); String re = sb.substring(l, sb.length()); return sb.substring(0, l) + "(" + re + ")"; } map.put(x, sb.length()); tmp = x / y; sb.append(tmp); x = x % y; x *= 10; } return sb.toString(); } }
