【题型总结】模拟运算-阿里云开发者社区

模拟运算

两数相加【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();
    }
}

【题型总结】模拟运算