LeetCode 两数相加算法题解 All In One

本文主要是介绍LeetCode 两数相加算法题解 All In One，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LeetCode 两数相加算法题解 All In One

js / ts 实现两数相加

两数相加原理图解

字符串相加 / 大数相加

// 字符串相加 / 大数相加
const addStrings = function(num1, num2) {
  let res = '';
  let temp = 0;
  const arr1 = num1.split('');
  const arr2 = num2.split('');
  while (arr1.length || arr2.length || temp) {
    // ~~ ??? bitwise not 双非位运算
    temp += ~~arr1.pop() + ~~arr2.pop();
    // 字符串相加，要注意先后顺序
    res = (temp % 10) + res;
    // 进位
    temp = temp > 9 ? 1 : 0;
  }
  // console.log('res =', res, typeof res);
  return res === "0" ? res : res.replace(/^0+/, '');
}

两数相加

// 2. Add Two Numbers


"use strict";

/**
 *
 * @author xgqfrms
 * @license MIT
 * @copyright xgqfrms
 * @created 2022-09-08
 * @modified
 *
 * @description 2. 两数相加
 * @description 2. Add Two Numbers
 * @difficulty Medium
 * @ime_complexity O(n)
 * @space_complexity O(n)
 * @augments
 * @example
 * @link https://leetcode.com/problems/add-two-numbers/
 * @link https://leetcode-cn.com/problems/add-two-numbers/
 * @solutions
 *
 * @best_solutions
 *
 */

// export {};

const log = console.log;

// // 节点
// function ListNode(val, next) {
//   this.val = 0 || val;
//   this.next = null || next;
// }

// // 链表
// function LinkedList(value) {
//   const node = new ListNode(value, ``);
//   let head;
//   if(!head) {
//     head = node;
//   } else {
//     let current = head;
//     while(current.next) {
//       current = current.next;
//     }
//     current.next = node;
//   }
// };

// function sumString(a1, a2) {
//   const s1 = a1.reverse();
//   const s2 = a2.reverse();
//   let result = [];
//   let upNum = 0;
//   if(s1.length > s2.length) {
//      result = s1;
//      for (let i = 0; i < s1.length; i++) {
//        let a = s1[s1.length - i - 1];
//        let b = s2[s2.length - i - 1] || 0;
//        result[s1.length - i - 1] = (a + b + upNum) % 10;
//        if((a + b + upNum) >= 10) {
//           upNum = 1;
//        } else {
//           upNum = 0;
//        }
//      }
//   } else {
//      result = s2;
//      for (let i = 0; i < s2.length; i++) {
//        let a = s2[s2.length - i - 1];
//        let b = s1[s1.length - i - 1] || 0;
//        result[s2.length - i - 1] = (a + b + upNum) % 10;
//        if((a + b + upNum) >= 10) {
//           upNum = 1;
//        } else {
//           upNum = 0;
//        }
//      }
//   }
//   if(upNum) {
//      result.unshift(upNum);
//   }
//   // return result.reverse();
//   return result;
// }

// singly-linked list
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
  }
  // add
  // remove
}

// 链表生成
const linkedListGenerator = (arr) => {
  let head;
  for (const item of arr) {
    const node = new ListNode(item);
    if(!head) {
      head = node;
    } else {
      let temp = head;
      // 关键：迭代 next
      while(temp.next) {
        temp = temp.next;
      }
      temp.next = node;
    }
  }
  return head;
}

// 字符串相加 / 大数相加
const addStrings = function(num1, num2) {
  let res = '';
  let temp = 0;
  const arr1 = num1.split('');
  const arr2 = num2.split('');
  while (arr1.length || arr2.length || temp) {
    // ~~ ??? bitwise not 双非位运算
    temp += ~~arr1.pop() + ~~arr2.pop();
    // 字符串相加，要注意先后顺序
    res = (temp % 10) + res;
    // 进位
    temp = temp > 9 ? 1 : 0;
  }
  // console.log('res =', res, typeof res);
  return res === "0" ? res : res.replace(/^0+/, '');
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  // 1. 暴力法
  // 遍历链表，获取原始正数，求和
  // 然后，逆序的生成一个新的链表
  let nums1: number[] = [];
  let nums2: number[] = [];
  while(l1?.val || l1?.val === 0) {
    nums1.push(l1.val);
    l1 = l1.next;
  }
  while(l2?.val || l2?.val === 0) {
    nums2.push(l2.val);
    l2 = l2.next;
  }
  let num1 = nums1.reverse().join('');
  let num2 = nums2.reverse().join('');
  // console.log(`num1 =`, num1)
  // console.log(`num2 =`, num2)
  // let sum = parseInt(num1) + parseInt(num2);
  let sum = addStrings(num1, num2);
  // let arr = [...`${sum}`.split('')].map(Number);
  let arr = [...`${sum}`.split('')].map(Number).reverse();
  // [8, 0, 7]
  // console.log(`arr =`, arr)
  return linkedListGenerator(arr);
};



// 测试用例 test cases
const testCases = [
  {
    inputs: [[2,4,3], [5,6,4]],
    result: [7,0,8],
    desc: 'value equal to [7,0,8]',
  },
  {
    inputs: [[0],[0]],
    result: [0],
    desc: 'value equal to [0]',
  },
  {
    inputs: [[9,9,9,9,9,9,9],[9,9,9,9]],
    result: [8,9,9,9,0,0,0,1],
    desc: 'value equal to [8,9,9,9,0,0,0,1]',
  },
  {
    inputs: [[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[5,6,4]],
    result: [6,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    desc: 'value equal to [6,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]',
  },
];
for (const [i, testCase] of testCases.entries()) {
  const [first,  second] = testCase.inputs;
  const l1 = linkedListGenerator(first);
  const l2 = linkedListGenerator(second);
  const testResult = linkedListGenerator(testCase.result);
  const result = addTwoNumbers(l1, l2);
  log(`test case i result: `, JSON.stringify(result) === JSON.stringify(testResult) ? `✅ passed` : `❌ failed`, JSON.stringify(result));
  // log(`test case i result: `, JSON.stringify(result) === JSON.stringify(testResult) ? `✅ passed` : `❌ failed`, result);
  // log(`test case i result: `, result === testCase.result ? `passed ✅` : `failed ❌`, result);
  // log(`test case i =`, testCase);
}

// npx ts-node ./002\ add-two-numbers.ts



/*

[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1].join('')

'1000000000000000000000000000001'
[5,6,4].join('')
'564'
[5,6,4].reverse().join('')
'465'
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1].reverse().join('')

'1000000000000000000000000000001'
parseInt('1000000000000000000000000000001');
1e+30
parseInt('1000000000000000000000000000001') +  parseInt('465')
1e+30
sum = parseInt('1000000000000000000000000000001') +  parseInt('465');

1e+30
`${sum}`.split('');
(5) ['1', 'e', '+', '3', '0']

科学计数法 ??? 字符串相加 ??? 进位

*/

https://leetcode.com/problems/add-two-numbers/
https://leetcode.cn/problems/add-two-numbers/

LeetCode 题解 / LeetCode Solutions

https://www.youtube.com/results?search_query=+Leetcode+2

https://www.youtube.com/playlist?list=PLamwFu9yMruCBtS2tHUD77oI_Wsce-syE

YouTube & LeetCode 力扣官方算法题解视频列表

https://github.com/xgqfrms/leetcode/issues/14

https://www.youtube.com/channel/UCftIXZeipv4MTVwmfFphtYw/videos

https://neetcode.io/

https://github.com/neetcode-gh/leetcode/blob/main/javascript/2-Add-Two-Numbers.js

https://github.com/neetcode-gh/leetcode/blob/main/typescript/2-Add-Two-Numbers.ts

类似问题

LeetCode 445. Add Two Numbers II / 两数相加 II

https://leetcode.com/problems/add-two-numbers-ii/

LeetCode 415. Add Strings / 字符串相加 (大数相加)

https://leetcode.com/problems/add-strings/

LeetCode 43. Multiply Strings / 字符串相乘

https://leetcode.com/problems/multiply-strings/

refs

©xgqfrms 2012-2020
www.cnblogs.com/xgqfrms 发布文章使用：只允许注册用户才可以访问！

原创文章，版权所有©️xgqfrms, 禁止转载

这篇关于LeetCode 两数相加算法题解 All In One的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程