- 1. 15.三数之和
- 1. 题目描述
- 2. 题目解析
- 2. 17.电话号码的字母组合
- 1.题目描述
- 2. 题目解析
- 3. 19.删除链表的倒数第 N 个结点
- 1.题目描述
- 2. 题目解析
- 1. 方法一：获取长度再找到要删除的结点
- 2. 方法二：栈
- 3. 方法三：快慢指针
- 4. 20.有效的括号
- 1.题目描述
- 2. 题目解析
- 5. 21.合并两个有序链表
- 1. 题目描述
- 2. 题目解析
1. 题目描述 2. 题目解析没有复杂度要求就好好解
首先人来求三个数相加为0，先看小的加大的是不是等于0，小于0则小数替换成较大的，大于0则大数替换成较小的，所以计算机算首先应该排序。
- 排序：将数组从小到大进行排序；
- 遍历：首先以第一个数为基准，选择后续最小与最大的数，看三者相加是否为0，如果小于0，则替换最小的那个数，选取后面较大的数，如果大于0，最大的数替换掉，选取前面较小的数；直至两个数重合，才把以第一个数为基准的情况找完；
- 重复遍历：选取第二个数为基准重复操作，注意：因为答案中不能包括重复的结果，所以如果该数与前一个数值相等，则再往后挪；直至挪到该数大于0为止（因为大于0则三数之和肯定会比0大）。
class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List>res=new ArrayList<>();
for(int i=0;i
if(nums[i]>0)break;
if(i>0&&nums[i]==nums[i-1])continue;
int j=i+1;
int k=nums.length-1;
while(j
int sum=nums[i]+nums[j]+nums[k];
if(sum<0){
while(j0){
while(j
res.add(new ArrayList(Arrays.asList(nums[i], nums[j], nums[k])));
while(j
2. 17.电话号码的字母组合
1.题目描述
2. 题目解析
首先看到所有组合，就可以想到回溯。
回溯模板：
- 全局变量： 保存结果；
- 参数设计： 状态变量和条件变量。一个是最后结果要保存的值，一个是决定搜索是否完毕或者合法的值；
- 完成条件： 完成条件是决定 状态变量和条件变量 在取什么值时可以判定整个搜索流程结束。搜索流程结束有两种含义： 搜索成功并保存结果 和 搜索失败并返回上一次状态。
- 递归过程： 传递当前状态给下一次递归进行搜索。
result = []//全局变量，存储结果
void backtrack(全局变量result,条件变量,状态变量):
if (满足结束条件){
result.add(状态变量);
return;
}
else if(不合法){
剪枝
return;
}
# 主要递归过程，一般是带有 循环体 或者 条件体
for(满足执行条件){
做选择;
backtrack(全局变量result,条件变量,状态变量);
撤销选择;
}
class Solution {
public List letterCombinations(String digits) {
if(digits.length()==0){
return new ArrayList();
}
Listres=new ArrayList<>();
Map phone=new HashMap<>();
phone.put('2',"abc");
phone.put('3',"def");
phone.put('4',"ghi");
phone.put('5',"jkl");
phone.put('6',"mno");
phone.put('7',"pqrs");
phone.put('8',"tuv");
phone.put('9',"wxyz");
dfs(res,phone,digits,0,new StringBuffer());
return res;
}
public void dfs(List res, Map phoneMap, String digits, int index, StringBuffer tmp){
if(index==digits.length()){
res.add(tmp.toString());
return;
}
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {
tmp.append(letters.charAt(i));
dfs(res, phoneMap, digits, index + 1, tmp);
tmp.deleteCharAt(index);
}
}
}
注意：string==""与string.length()==0与string==null 的区别。
3. 19.删除链表的倒数第 N 个结点
1.题目描述
2. 题目解析
在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
1. 方法一：获取长度再找到要删除的结点
删去倒数第n个结点，首先需要获取到链表结点个数L，然后再获取到第L-n即可，它的下一个即L-n+1个即为要删除的结点。
问题在于如果删除后，还要将头结点输出？
上边提到，增加一个结点可以将头结点问题统一；
所以首先增加一个哑结点，然后将一个指针指向它，再进行遍历，找到第L-n+1个结点，去除第L-n+1的下一个结点，输出哑结点的下一个即可。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode h=new ListNode(0,head);
int l=getLength(head);
ListNode cur=h;
for(int i=1;i
cur=cur.next;
}
cur.next=cur.next.next;
return h.next;
}
public int getLength(ListNode head) {
int res=0;
ListNode tmp=head;
while(tmp!=null){
res++;
tmp=tmp.next;
}
return res;
}
}
2. 方法二：栈
删除倒数第n个，将链表倒过来删除第n个结点即可。
首先将所有结点压入栈，然后抛出前n个结点，则栈顶结点就是要删除结点的前一个，所以只要将该结点的下一个指向下一个的下一个即可删除。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
Stack stack = new Stack();
ListNode cur = dummy;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
for (int i = 0; i < n; ++i) {
stack.pop();
}
ListNode prev = stack.peek();
prev.next = prev.next.next;
ListNode ans = dummy.next;
return ans;
}
}
栈在Java中使用Stack和Deque（双端队列）都可以。
3. 方法三：快慢指针
即使不知道链表的长度，也可以获取倒数第n个结点，只需要快慢指针即可：一个指针first超前另一个指针second n-1个结点，则当first指针走到最后时，second指针所在的即为倒数第n个。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode h = new ListNode(0, head);
ListNode first = h;
ListNode second = h;
for (int i = 0; i <= n; ++i) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return h.next;
}
}
4. 20.有效的括号
1.题目描述
2. 题目解析
括号是否匹配主要有两个条件：1.左右括号同类型匹配，2.匹配顺序正确。对于条件1，我们只需做一个判断即可；对于条件2，正确顺序就是先出现左括号，就要先匹配对应的右括号，所以就是后来的先匹配走，对应栈，先进后出。
所以首先遍历字符串，左括号进栈，对于右括号，只需要判断栈顶元素是否是匹配的，如果不匹配直接返回false，匹配则直接推出栈顶元素。遍历完毕后如果栈为空，则完成匹配，否则返回false。
class Solution {
public boolean isValid(String s) {
Stackstack=new Stack<>();
for(int i=0;i
if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{'){
stack.push(s.charAt(i));
}
else if(s.charAt(i)==')'&&!stack.empty()&&stack.peek()=='('){
stack.pop();
}
else if(s.charAt(i)==']'&&!stack.empty()&&stack.peek()=='['){
stack.pop();
}
else if(s.charAt(i)=='}'&&!stack.empty()&&stack.peek()=='{'){
stack.pop();
}
else{
return false;
}
}
if(stack.empty()){
return true;
}
return false;
}
}
5. 21.合并两个有序链表
1. 题目描述
2. 题目解析
合并两个升序链表，首先新建一个哑结点，然后用一个指针cur指向结点，用两个指针分别指向两个链表的头部，比较两个结点的大小，取值小的结点为cur的下一个结点，然后将指向该结点的指针后移，直至一条链表遍历完毕，然后将cur指向不为空的链表即可。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode n1=list1;
ListNode n2=list2;
ListNode head=new ListNode(0);
ListNode cur=head;
while(n1!=null&&n2!=null){
if(n1.val<=n2.val){
cur.next=n1;
n1=n1.next;
}else{
cur.next=n2;
n2=n2.next;
}
cur=cur.next;
}
if(n1==null){
cur.next=n2;
}
else{
cur.next=n1;
}
return head.next;
}
}
递归：
题解中有递归实现，同理。
