【アルゴリズム】【leetcode】2数の和、2数加算
20945 ワード
/*
1. , , , 。
2. , , ( )
*/
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
var addTwoNumbers_2 = function (l1, l2) {
let nums = [];
let carry = 0;
while (l1 != null || l2 != null || carry != 0) {
let val1 = l1 ? l1.val : 0;
let val2 = l2 ? l2.val : 0;
let sum = val1 + val2 + carry;
carry = Math.floor(sum / 10);
l1 = l1 ? l1.next : null;
l2 = l2 ? l2.next : null;
}
console.log(nums);
let root = new ListNode(-1, null);
let pointer = root;
while (nums.length != 0) {
pointer.next = new ListNode(nums.shift(), null);
pointer = pointer.next;
}
return root.next;
};
var addTwoNumbers = function (l1, l2) {
let tempRoot = new ListNode(0, null);
let pointer = tempRoot;
let carry = 0;
while (l1 != null || l2 != null || carry != 0) {
let val1 = l1.val || 0;
let val2 = l2.val || 0;
let sum = val1 + val2 + carry;
carry = Math.floor(sum / 10);
pointer.next = new ListNode(sum % 10, null);
pointer = pointer.next;
l1 = l1 ? l1.next : null;
l2 = l2 ? l2.next : null;
}
return tempRoot.next;
};
let ln1 = new ListNode(3, null);
let ln2 = new ListNode(4, ln1);
let ln3 = new ListNode(2, ln2);
let ln4 = new ListNode(4, null);
let ln5 = new ListNode(6, ln4);
let ln6 = new ListNode(5, ln5);
// console.log(addTwoNumbers_2(ln3, ln6));
// console.log(addTwoNumbers(ln3, ln6));
//====================================================================================================
/*
1. map
2. ,
3.
*/
var twoSum3 = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i == j) continue;
if (nums[i] + nums[j] == target) return [i, j];
}
}
};
var twoSum2 = function (nums, target) {
nums.sort((a, b) => a - b);
let head = 0;
let tail = nums.length - 1;
while (nums[head] + nums[tail] != target) {
let val = nums[head] + nums[tail];
if (val > target) tail -= 1;
else head += 1;
}
return [head, tail];
};
var twoSum = function (nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
/*
, key, value 。
map ( , value )
*/
if (map.has(nums[i])) {
return [map.get(nums[i]), i];
} else {
map.set(target - nums[i], i);
}
}
};
// console.log(twoSum3([2, 11, 7, 15], 9));