LeetCode 刷题笔记——day 1
难度：简单
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
1
2
3
| 输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
|
示例 2：
1
2
| 输入：nums = [3,2,4], target = 6
输出：[1,2]
|
示例 3：
1
2
| 输入：nums = [3,3], target = 6
输出：[0,1]
|
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
我的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
for(int i = 0; i < len - 1; i++) {
for(int j = i + 1; j < len; j++){
if(nums[i] + nums[j] == target) {
vector<int> num = {i, j};
return num;
}
}
}
vector<int> num;
return num;
}
};
|
官方答案
哈希表法
看过题解之后，学会了哈希表法，用Java重新写了一遍代码：
思路：往哈希表中一次插入数组元素-数组索引组成的键值对，同时利用 containsKey 函数判断已有列表中是否存在与当前元素相加为 target 的键，由此可在一次循环以内完成目标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++) {
if(hashMap.containsKey(target - nums[i])) {
return new int[]{hashMap.get(target - nums[i]), i};
}
hashMap.put(nums[i], i);
}
return new int[0];
}
}
|
难度：中等
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
1
2
3
| 输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
|
示例 2：
1
2
| 输入：l1 = [0], l2 = [0]
输出：[0]
|
示例 3：
1
2
| 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
|
提示：
- 每个链表中的节点数在范围
[1, 100] 内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
我的答案
官方答案
（在自己编写超过80行代码且半小时仍无法通过编译时毅然决然放弃了原来的硬方法，参考了官方题解之后才最终重新编写如下代码，是我配不上第二题了。）
思路
创建两个空指针，一个指向头部，一个跟随程序指向尾部，利用三目运算符提取目标数字且在其一链表提前截止时以 0 赋值（必须加入 if 语句判断，切忌指针继续后移），将得到的数据处理后直接利用已有构造函数创建节点，同时指针跟随后移。最后输出头指针即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = nullptr, *p = nullptr;
int a = 0;
while(l1 || l2) {
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + a;
a = sum / 10;
if(!head) {
head = p = new ListNode(sum%10);
} else {
p->next = new ListNode(sum%10);
p = p->next;
}
if(l1) {
l1 = l1->next;
}
if(l2) {
l2 = l2->next;
}
}
if(a > 0) {
p->next = new ListNode(a);
}
return head;
}
};
|
拿 Java 练习一遍新学的算法：
思路：Java 没有指针概念，直接创建对象即可，思路同上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
ListNode p = head;
int a = 0;
while(l1 != null || l2 != null) {
int n1 = l1 == null ? 0 : l1.val;
int n2 = l2 == null ? 0 : l2.val;
int sum = n1 + n2 + a;
a = sum / 10;
p.next = new ListNode(sum % 10);
p = p.next;
if(l1 != null) {
l1 = l1.next;
}
if(l2 != null) {
l2 = l2.next;
}
}
if(a > 0) {
p.next = new ListNode(a);
}
return head.next;
}
}
|
总结
第一天，刷了两题。
