第一题:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
最先想到的办法,暴力枚举。
很简单,两层循环找出合适的解即可。
var twoSum = function(nums, target) {
let len = nums.length
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
开始思考其他的解决方法,一开始想通过一次循环把数组中所有的元素和target之间的差值存到Object里,然后再遍历一次数组,找出满足差值的元素。又因为题目要求所有数组元素只能利用一次所以要想办法把两次循环合并到一起。
var twoSum = function(nums, target) {
let len = nums.length
let diffMap = {};
for (let i = 0; i < len; i++) {
let diff = target - nums[i];
if (diff in diffMap) {
return [diffMap[diff], i];
} else {
diffMap[nums[i]] = i;
}
}
};
第二题:
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
理解题目意思以后,想到了第一种方法,将链表中的所有值转换成字符串,然后再把两个字符串转换成数字相加,之后再把数字转换成字符串,再把字符串转换成链表。虽然过程复杂,效率也差,但是这是我一开始能想到的办法。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = (l1, l2) => {
let tempOne = analysisNumbers(l1);
let tempTwo = analysisNumbers(l2);
tempOne = Number(tempOne);
tempTwo = Number(tempTwo);
let result = tempOne + tempTwo;
return decodeStringToList(BigInt(result).toString());
};
var analysisNumbers = (node) => {
let resultNum = '';
resultNum = node.val ? node.val.toString() : '0' + resultNum;
if (node.next != null) {
return resultNum = analysisNumbers(node.next) + resultNum;
} else {
return resultNum;
}
};
var decodeStringToList = (str) => {
let tempNode = new ListNode(null);
let head = tempNode;
for(let i = str.length - 1; i >= 0 ; i--) {
tempNode.next = new ListNode(Number(str.charAt(i) == '0' ? 0 : Number(str.charAt(i))));
tempNode = tempNode.next;
}
return head.next;
};
尝试之后,发现题目给的例子是可以行的通的,果断提交。结果解答错误,分析错误时的测试用例,发现是链表过长时,数字被转换成了科学计数法,转字符串时出了问题,修改代码用BigInt发现还是存不下,所以该方法行不通,明天再尝试其他的解法。
网友评论