leetcode难题笔记
- 0002 - 两个链表分别表示两个数字,求和
- 0003 - 在一个字符串中寻找最长无重复字符的连续子串
- 0004 - 两个有序数组中的中位数
- 0005 - 最长回文子串
- 0006 - ZigZag
- 0007 - 将32位整数反转,如果溢出返回0
- 0009 - 回文数字
- 0011 - 能盛最多水的容器
- 0015 - 给定一个数组,找到所有不重复的三元组,满足三个数之和为0
- 0017 - 给定一组输入数字,给出所有这组数字对应到手机上英文输入法对应字符的组合
- 0019 - 将列表中倒数第N个元素删除
- 0020 - 给出一个仅包括括号的字符串,判断该字符串内的括号似乎否均合法
- 0021 - 合并两个有序链表
- 0022 - 有N对括号,生成所有可能的组合的字符串组
- 0023 - 将K个有序链表合并 (0021的升级版本)
- 0032 - 输入一串仅包括括号的字符串,找到其中最长的合法括号组的长度
本文仅记录思路,具体代码都在github的repo中。
0002 - 两个链表分别表示两个数字,求和
挺简单的,只要记得最后考虑进位就可以了。
0003 - 在一个字符串中寻找最长无重复字符的连续子串
例如:给定 abcbdfgd
, 最长子串为 cbdfg
. 直观的方法是使用一个map外加一个移动的窗口,类似:
a b c b d f g d
^ ^
| |
l r
map:
{
b: 3
d: 4
f: 5
g; 6
}
0004 - 两个有序数组中的中位数
记len(s1) == n, len(s2) == m
, 最直观的想法是一个一个去比较,算法复杂度为:O((n+m)/2) => O(n)。
不过,我们可以根据中位数的定义以及s1
, s2
为有序数组的条件,更快的获得答案。其思路大概为:由于我们要找第k (= (n+m)/2)个数,那么我们可以比较s1
中第k/2个数和s2
中第k/2个数(假设它们都有那么多数字)。假设s1
中的那个数字更小,那么我们将s1
的前k/2个数丢弃,即s1 <- s1[k/2:]
.
注意:我们总是能够保证s1
或者s2
中至少有一组的前k/2个数是包含在合并的有序数组的前k个数中(反证法证明).
然后,再同上去比较两边的第(k-k/2)/2… 直到这个值 = 0为止。那么,我们基本已经去除中位数之前的所有数字,而这仅耗费了O(log(k/2)) => O(log(n)).
举个例子:
假设:
s1 = []int{1,6,7,10,12}
s2 = []int{2,4,6,7}
k = 9/2 = 4
那么先找两边的第4/2 = 2个数:
s1[1] = 6
s2[1] = 4
由于s2[2]的更小,因此取 s2 = s2[2:] = []int{6,7}
接下来,找两边的第(4-2)/2=1个数:
s1[0] = 1
s2[0] = 6
因此:s1 = []int{6,7,10,12}
接下来,因为((4-2)/2-1)/2 = 0,因此,我们停止迭代。数数看,我们已经去除了前4个中的1+2=3个数字.
最后,(对于总共为奇数的情况)我们只要去掉当前最小数字,剩下的数字中最小的那个即为要找的中位数了;对于偶数的情况,我们只要去掉当前最小的数字,剩下的数字中最小的两个数字的平均数就是要找的中位数。
0005 - 最长回文子串
直观的做法是:循环每一个数,对每一个数以及数字之间的位置进行从中间往两边展开的方式进行比较。
0006 - ZigZag
找规律
0007 - 将32位整数反转,如果溢出返回0
每次除以10取商和余数,需要注意的是溢出的处理,题目不允许使用大于32位的类型存储,因此,判断溢出的算式必须是当前累计的值与math.MaxInt32 - remainder
/math.MinInt32 - remainder
除以10之后的值比较,而不是当前累计的值*10
+remainder
与math.MaxInt32
/math.MinInt32
比较。
值得注意的是,当反转一个负数的时候,比较的值是math.MinInt32-remainder
/10,这里在golang中是成立的,也即math.MinInt32-remainder
不会溢出,因为remainder
总是为负数。Go语言中,整数除法总是zero rounded,因此如果被除数是负数,那么余数总是为负数。
0009 - 回文数字
给定一个数字,判断这个数字是否为回文数字。注意,负数总是不是回文数字,因为有个负号。
做法是通过栈或者计算返转数字(每次除以10,累计余数),然后比较是否与输入数字相同。这里的不需要考虑溢出,因为溢出的话一定不会与输入相同。
0011 - 能盛最多水的容器
两边往中间靠拢。
0015 - 给定一个数组,找到所有不重复的三元组,满足三个数之和为0
首先对数组进行排序,从小到大。然后,从小到大循环每个不重复的数字,对于每次循环idx = i
,在右边的子数组中找到和为sum - nums[i]
(即为t
)的所有不重复的二元组。
由于数组是排序的,所以要寻找这对二元组的方法是从两边往中间收拢的方式,即先计算nums[i+1] + nums[len(nums)-1]
,看它是否等于t
,如果等于,那么记录这个数字,继续往中间靠拢,靠拢的时候注意跳过重复数字;否则,如果<k
,那么将左边的边界右移,如果>k
,那么将右边的边界左移.
0017 - 给定一组输入数字,给出所有这组数字对应到手机上英文输入法对应字符的组合
感觉直接循环就行了。好像叫做backtrack。
0019 - 将列表中倒数第N个元素删除
维护三个指针,最左边两个中间相隔1个元素(即将要被删除的那个元素),最右边那个和最左边那个相隔N个元素,用来指示是否到链表结尾了。
0020 - 给出一个仅包括括号的字符串,判断该字符串内的括号似乎否均合法
使用栈. 需要注意在最后的时候保证栈内部已经为空。
0021 - 合并两个有序链表
分别从头开始比较。如果使用递推的方式进行计算,有个技巧是设置一个beforeHeadNode
,可以是计算过程统一。
0022 - 有N对括号,生成所有可能的组合的字符串组
回溯。
要生成合法括号,那么当前的open括号数目一定是小于等于close括号。每次递归的时候如果open括号的数目等于close括号,那么仅递归open括号;否则如果是open<close
,并且open>0
,则即递归open括号,也递归close括号;否则如果open==0
,则返回剩余的close括号。
每次递归返回是一个数组,在回溯的时候扩展数组中每个元素。
0023 - 将K个有序链表合并 (0021的升级版本)
- 使用和0021一样的方法,每次比较得到这三个里最小的那个
- 每次两两链表合并 (#TODO)
0032 - 输入一串仅包括括号的字符串,找到其中最长的合法括号组的长度
使用栈的方式保存每一个未配对的括号,当下一个括号与当前栈定括号匹配,则出栈。另外,维护一个数组保存在不同情况下的最长合法括号的长度。如果当前栈的长度减少为n,那么数组arr[idx] = arr[idx] + arr[idx+1] + 2
, 然后将arr[idx+1]
还原为0
Comments