很多题目还是直接没有思路,如果只是暴力破解又没有什么作用,有的题目思考很长时间也是做不出来,
刷题顺序也没有什么规律,看到拿到刷哪个,搜了下资料,刷题比较少的可以最开始从头开始刷,目前先按照这个规律刷150题左右
1、建议未刷过题的新人按着顺序来。前 150 题覆盖了很多经典题目和知识点,指针法类如『3 sum』系列,动规类如『regex matching』,搜索类题目如『Sodoku Solver』。 2、基本熟悉知识点(图、树、堆、栈、链表、哈希表、记忆搜索、动态规划、指针法、并查集等)后,可以一类类标签强攻。Leetcode 右侧的标签系统虽然未必 100% 完整,但是大致分类做得还不错。 3、面试前的一个月可以只做『Hard』标签的题目,因为一般两遍之后对于大部分『Medium』难度以下的题目都是肌肉记忆了。多练习『Hard』类题目可以让自己的思路更开阔,因为很多题目使用的奇淫巧技让人惊讶,比如 Leetcode 精心设计连续题号的『84. Largest Rectangle in Histogram』、『85. Maximal Rectangle』。
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807.
输入:l1 = [0], l2 = [0] 输出:[0]
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1]
链表问题一般都会使用虚拟表头来控制循环,类似Java的AQS中哨兵节点,都是为了方便递归或者迭代
这道题目也是这个思路
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//冗余节点,为了循环方便
ListNode preNode = new ListNode(-1);
ListNode currentNode = preNode;
int shang = 0;
//长度以最长的链表为主
while (l1 != null || l2 != null) {
int sum = getSum(l1, l2);
//创建下一个节点
currentNode.next = new ListNode((sum + shang) % 10);
shang = (sum + shang) / 10;
//当前节点指向下一个节点
currentNode = currentNode.next;
//两个链表分别往后迭代
l1 = (l1 == null) ? null : l1.next;
l2 = (l2 == null) ? null : l2.next;
}
//链表长度内加完之后,最后余数还是大于0,说明扩展位数
if (yushu > 0) {
currentNode.next = new ListNode(yushu);
}
return preNode.next;
}
/**
* 节点为null时按照值为0处理
*/
private static int getSum(ListNode l1, ListNode l2) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
return val1 + val2;
}
执行用时:2 ms, 在所有 Java 提交中击败了94.18%的用户 内存消耗:38.6 MB, 在所有 Java 提交中击败了61.42%的用户
这道题加上调试,差不多也用了一个多小时,终于AC后感觉还是不错的,
然后再查看下官网的题解
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
}
执行用时:2 ms, 在所有 Java 提交中击败了94.18%的用户 内存消耗:38.7 MB, 在所有 Java 提交中击败了42.04%的用户
时间和内存几乎一样, 其实整体思路差不多,官网给出了虚拟节点的作用定义:
小技巧:对于链表问题,返回结果为头结点时,通常需要先初始化一个预先指针 pre,该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值,而且链表构造过程需要指针移动,进而会导致头指针丢失,无法返回结果。
同时在其他评论发现了另一个优化点
如果把 carry = sum / 10; 换成 carry = sum >9 ? 1 : 0 ; 这样 速度会快很多
结果:
执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗:38.5 MB, 在所有 Java 提交中击败了75.16%的用户
这里主要是因为除法运算相对比较耗时的原因,同时题目本身都是整数可以这么特殊处理
类似的优化手段还有位运算替代乘除法等
又是摸鱼+刷题的一天。开心