leetCode进阶算法题+解析（三）
电话号码的字母组合
题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
题目截图
思路：这个题怎么说呢，就是乘方的题，两个数字9中结果，3个数字27，四个数字81。。。其实我最真实的想法就是来回来去for循环，有几个数字就几层循环。。。反正这个题思路是很简单，但是真正实践可能有点性能问题？再说吧，我先去写代码了。
哇，今天 第一道题又一次过了，而且及格。性能超过百分之九十三的人，思路就是我想的那样，一个数一个数追加，写的挺恶心的，提交之前我一直害怕超时。哈哈，话不多说，直接贴代码：
class Solution {
char[][] d;
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<String>();
if(digits.length()==0) return res;
char[] c =digits.toCharArray();
res.add("");
d = new char[10][];
d[2] = new char[]{'a','b','c'};
d[3] = new char[]{'d','e','f'};
d[4] = new char[]{'g','h','i'};
d[5] = new char[]{'j','k','l'};
d[6] = new char[]{'m','n','o'};
d[7] = new char[]{'p','q','r','s'};
d[8] = new char[]{'t','u','v'};
d[9] = new char[]{'w','x','y','z'};
for(int i = 0;i<c.length;i++){
res = getList(res,c[i]-'0');
}
return res;
}
public List<String> getList(List<String> list,int n){
List<String> res = new ArrayList<String>();
for(String s:list){
for(int i = 0; i<d[n].length;i++){
StringBuffer sb = new StringBuffer(s);
sb.append(d[n][i]);
res.add(sb.toString());
}
}
return res;
}
}
感觉怎么也优化不到百分百了，我直接看了第一的代码。觉得果然比我的写的复杂多了，哈哈，所以只是贴上来排名第一的代码分享下，但是我就不研究了：
class Solution {
String[] allNumberString={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
if(digits==null||digits.length()==0){
return new ArrayList<>();
}
letterCombinations(digits,"",0);
return ans;
}
List<String> ans=new ArrayList<String>();
public void letterCombinations(String digits,String letter,int index){
if(index==digits.length()){
ans.add(letter);
return;
}
char c=digits.charAt(index);
int real=c-'0';
String realString=allNumberString[real];
for(int i=0;i<realString.length();i++){
letterCombinations(digits,letter+realString.charAt(i),index+1);
}
}
}
四数之和
题目：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路：昨天被三数之和支配的恐惧。。。卧槽，现在进化成四数了，社会社会。。。好的吧，说思路，就是昨天三数和的进化版。现在四数了，a+b+c+d=target.但是也可以理解为 b+c+d=target-a.所以这不就不回到了三数和么？别的要求的都是一模一样的，所以直接去撸代码了。
还好思路是对的，几乎是百分之八十套用三数之和就搞定了，我先贴代码
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums.length<4) return res;
Arrays.sort(nums);
int len = nums.length;
for(int i = 0;i<len;i++){
if(nums[i]>target/4) break;
if(i>0 && nums[i]==nums[i-1]) continue;
int sum = target-nums[i];
for(int j = i+1;j<len;j++){
if(nums[j]>sum/3) break;
if(j>i+1 && nums[j]==nums[j-1]) continue;
int l = j+1;
int r = len-1;
while(l<r){
if(nums[r]<sum/3) break;
int temp = nums[j] + nums[l] +nums[r];
if(temp == sum){
res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
while(l<r && nums[l] == nums[l+1]) l++;
while(l<r && nums[r] == nums[r-1]) r--;
l++;
r--;
}else if(temp>sum){//结果大了右指针往左
r--;
}else{//结果小了左指针往右
l++;
}
}
}
}
return res;
}
}
其实这段代码性能一般，只超过了百分之八十七的人。我感觉可能是因为某个地方该判断的但是我没有判断。但是我自己调了好几次也没get到优化的点，所以直接看排名第一的代码了：
好了，看完之后微改就超过百分之九十九了，先贴代码：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums.length<4) return res;
Arrays.sort(nums);
if(nums[0]>target/4 || nums[len-1]<target/4) return res;
for(int i = 0;i<len;i++){
if(nums[i]>target/4) break;
if(i>0 && nums[i]==nums[i-1]) continue;
int max1 = nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1];
if (max1 < target) continue;
int sum = target-nums[i];
for(int j = i+1;j<len;j++){
if(nums[j]>sum/3) break;
if(j>i+1 && nums[j]==nums[j-1]) continue;
int max2 = nums[j] + nums[len - 2] + nums[len - 1];
if(max2<sum) continue;
int l = j+1;
int r = len-1;
while(l<r){
if(nums[r]<sum/3) break;
int temp = nums[j] + nums[l] +nums[r];
if(temp == sum){
res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
while(l<r && nums[l] == nums[l+1]) l++;
while(l<r && nums[r] == nums[r-1]) r--;
l++;
r--;
}else if(temp>sum){//结果大了右指针往左
r--;
}else{//结果小了左指针往右
l++;
}
}
}
}
return res;
}
}
如下图改的点就是判断当前值为第一个/第二个能否满足target需求，如果已经和最大值组合还不够大，则直接continue。。其实很容易理解的，但是我当时就是没想到。。。下一题吧。
添加的细节
删除链表的倒数第N个节点
题目：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
思路：这个题如果没有进阶简直不要太简单，第一遍遍历出来，第二遍新挂链表，简直不要太完美。。但是一趟扫描。。我先想想思路吧。实在是没思路。我决定先笨实现再考虑进阶吧。
基本实现做出来了，2ms，性能超过百分之60.直接贴代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int len = 0;
int[] d = new int[1000];
int idx = 0;
while(head!=null){
d[idx] = head.val;
head = head.next;
idx++;
}
ListNode res = new ListNode(0);
ListNode cur = res;
int x = 0;
while(x<idx){
if(n+x==idx){
x++;
if(x==idx) break;
}
cur.next = new ListNode(d[x]);
cur = cur.next;
x++;
}
return res.next;
}
}
其实我自己都知道是一种很low的方法实现的，无奈思路挺多，变成代码就卡壳了。但是我觉得我还能换种方式做，再去考虑下。
第二种方法没借助数组，直接挂树，1ms，但是性能还是贼低，我先贴代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int len = 0;
ListNode cur = head;
while(cur!=null){
cur = cur.next;
len++;
}
if(n==len) return head.next;
ListNode res = head;
int temp = 1;
while(head!=null){
if(temp==len-n){
head.next = head.next.next;
}
head = head.next;
temp++;
}
return res;
}
}
看了题解才知道一次遍历怎么解题的（虽然我很奇怪快慢指针也算是两次遍历吧？）先贴代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode f = head;
ListNode s = head;
for(int i = 0;i<n+1;i++){
f = f.next;
if(i!=n && f==null) return head.next;
}
while(f!=null){
f = f.next;
s = s.next;
}
s.next = s.next.next;
return head;
}
}
讲解一下这个代码：
一次扫描的重点其实就是快慢指针，一个是从第一个开始，一个是从第n+1个开始，这样保证两个指针之间差n个节点。
然后两个指针一起往后一个节点一个节点移动，等快的节点移动到null的时候，这个时候慢的节点正好距离结尾差n个节点。也就是到了我们要删除的节点的下一个了。
这里有两点要注意：
- 有可能要删除的节点就在第一次快指针移动n个节点中，这个时候要处理一下。如果快节点没等移动到n个null了，只有一种可能，第一个就是要删除的元素。所以这个时候直接返回head.next就行了。
- 其实这就是一个逻辑问题，第n个要删除，而不是隔着倒数n个删除。所以等到快指针null了要删除的是当前慢指针的下一个而不是当前这个。所以是s.next=s.next.next。
然后剩下的就没什么了，这个题其实说难也不是那么难，主要是一次扫描要好好想想。总体来说复习链表知识了吧。
括号生成
题目：给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路：这道题暂时没思路。就这么一个demo,我先自己看看有没有什么规律。
咳咳，不断用测试案例测试，发现这个n不能大于12，因为当输入12的时候就不给正确答案了，11是可以的，如图：
输入12
输入11
咳咳，我有一个大胆的想法，这个题用switch-case是否可以啊?好的吧，不然思路是真的没有。我直接看题解吧，毕竟觉得这道题确实超出我的知识范围了。
好的，这道题看了别人的代码半理解的做出来了。其实不算是很难理解，就是很麻烦，我一开始就是懒得想。然后说思路，这道题就是左括号右括号的摆放位置。
- 首先这是一个二叉的选择，除了第一个元素剩下的可以选择加左括号和右括号。
- 因为都是有效的括号，所以一定要保证不管到哪一个为止，只能左括号大于等于右括号，如果右括号大于左括号说明有无效的括号了。
- 这是一个乘积的形式，所以用的递归解决。
根据以上三点贴出代码:
class Solution {
List<String> res;
public List<String> generateParenthesis(int n) {
res = new ArrayList<String>();
dfs("",0,0,n);
return res;
}
public void dfs(String s,int l,int r,int n){
if(l>n || r>n) return;
if(l==n && r==n) res.add(s);
if(l>=r){
dfs(s+"(",l+1,r,n);
dfs(s+")",l,r+1,n);
}
}
}
这道题其实说实话我不觉得是很难，但是一下子不容易理出头绪，尤其是做题要心静，今天因为要过年回家所以收拾东西然后没静下心来好好寻思思路而是直接看的题解，现在想想还有点小愧疚。
今天的笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！明天又是周末，如果放假的就祝大家周末愉快！不放假的应该也是为了年假调休，也祝大家有一个好的精神面貌！我希望每天进步一点点！
