删除排序链表中的重复元素2
题目：给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
思路：这个题怎么说呢，说简单就简单，最笨最笨的方法就是直接存数组，排除重复元素挂树。但是那么做就没必要刷算法了。我目前的想法直接遍历。就是和上一个原地删除数字重复元素差不多。这里也是用双指针。不过这个不需要在原有的链表上操作，而是用一个新链表，所有非重复的元素都一个个挂上。
emmm...思路是没问题的，我直接贴代码了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode res = new ListNode(0);
ListNode temp = res;
while (head != null) {
boolean flag = false;
while (head != null && head.next != null && head.val == head.next.val) {
head = head.next;
flag = true;
}
if (!flag) {
res.next = head;
res = res.next;
}
head = head.next;
}
res.next = null; //防止res后面还有重复的节点
return temp.next;
}
}
就是如图，不是重复的才往上挂，是重复的就跳过。然后思路没啥问题，并且执行速度1ms，超过百分之九十八的人，所有我就不看题解了，直接下一题了。
分割链表
题目：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
思路：这个题感觉比较容易，就是创建两个链表。然后遍历这个给定链表。小于x的挂在第一个链表。大于等于x的挂在第二个链表。等遍历完给定链表了，小于的接上大于等于的，就完事了。不知道我思路有没有问题，我去实现试试。
思路没问题，我直接贴代码;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if(head==null) return head;
ListNode n1 = new ListNode(0);//存小于的元素
ListNode n2 = new ListNode(0);//存大于等于的元素
ListNode cur1 = n1;
ListNode cur2 = n2;
while(head!=null){
if(head.val<x){
cur1.next = new ListNode(head.val);
cur1 = cur1.next;
}else{
cur2.next = new ListNode(head.val);
cur2 = cur2.next;
}
head = head.next;
}
cur1.next = n2.next;
return n1.next;
}
}
这个题其实这么做是没问题，但是性能有点扎心啊。其实是我处理的问题，这个是第一版本的代码，我去试着小小的优化一下。
好了，0ms，超过百分百了。我先贴代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if(head==null) return head;
ListNode n1 = new ListNode(0);//存小于的元素
ListNode n2 = new ListNode(0);//存大于等于的元素
ListNode cur1 = n1;
ListNode cur2 = n2;
while(head!=null){
if(head.val<x){
cur1.next = head;
head = head.next;
cur1 = cur1.next;
cur1.next = null;
}else{
cur2.next = head;
head = head.next;
cur2 = cur2.next;
cur2.next = null;
}
}
cur1.next = n2.next;
return n1.next;
}
}
其实就是一些微改。我之前是每次都创建一个新节点，来回来去挂。这样开销可能比较大。现在是直接挂原有节点。代码是复杂了，但是性能好了。然后这道题比较简单所以也直接过了，下一题。
子集2
题目：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路：其实这个题和子集1息息相关。要回忆一下子集1的解法：首先创建一个小list，添加到结果集中，然后每次遍历结果集中的小list（这里是用每一个给定集合的每个元素遍历，我可能说的不清楚，就是一个双层for循环）。添加当前的给定元素，变成新list再添加进结果集。不过因为这道题给定的元素是有重复的可能的，所以还是那么操作肯定是会有重复元素了。对于这种情况我的第一反应就是排序，然后第一个正常add，如果后面的元素等于前面的元素则直接跳过（这个思路在好多地方都有，类似组合排序2.全排序2之类的。）暂时是有思路了，我去实现下看看。
好了，做完了，这个思路和之前的略有不同。反正大体的解法和子集1是一样的。先把基础代码列出来，然后在这个基础上做改动。之前我说的判重有点问题，因为如果这个元素直接跳过去，那么[2，2 ] [1，2，2]这两个解集就没了。所以这里其实仔细看了就会发现不是完全的跳过，而是有一些需要跳过。就拿例子讲：这个[] 是要跳过的，不然+2是2，重复了， 同样[1]也是要跳过的，不然1，2也会重复。而哪些跳过哪些续加其实是有规律的。一开始我想错的，以为是第i个开始，但是后来发现不对。然后发现规律是上一个相同元素的初始size之前是不用续加的。所以专门设置一个变量保存这个size，我直接贴代码：
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
res.add(list);
Arrays.sort(nums);
int lastLen = 1;
for(int i = 0;i<nums.length;i++){
int len = res.size();
//当后一个和前一个元素一样，则j不用从0开始.否则就替换lastLen为当前size
if(i!=0 && nums[i]!=nums[i-1]){
lastLen = len;
}
for(int j = len-lastLen;j<len;j++){
List<Integer> temp = new ArrayList<Integer>(res.get(j));
temp.add(nums[i]);
res.add(temp);
}
}
return res;
}
}
其实重点代码就那一两句，就是那个如果不是相等的记录size，是相等的则从size往后开始。这个题不算难，尤其是有了子集1的底子的话，用心就能做出来。
不过我这个代码性能不咋地，2ms。只超过四十多的人，我去看看排行第一的代码是什么思路（ps：其实这个题的思路还是很多的，之前做子集1就是，可以迭代也可以回溯）。
我直接贴排行第一的代码;
class Solution {
public void genSubsets(List<List<Integer>> sublist,List<Integer> list,int cur,int nums,int []array){
for(int i=cur;i<nums;i++){
if(i>cur&&array[i]==array[i-1])continue;
List<Integer> tmplist = new ArrayList<Integer>(list);
tmplist.add(array[i]);
sublist.add(tmplist);
genSubsets(sublist,tmplist,i+1,nums,array);
}
return ;
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> sublist = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
sublist.add(list);
genSubsets(sublist,list,0,nums.length,nums);
return sublist;
}
}
就是一个很标准的回溯，然后判重的思路也差不多。我一开始想的continue就是按照回溯的思路，但是我偏偏不是回溯实现的，哈哈。反正这个题就这样吧，直接下一题了。
解码方法
题目：一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
思路：不得不说，这个题我的思路是动规。毕竟有点经典啊。一个一个数字解，但是又隐隐觉得这个题也每这么难。毕竟是只给一个字符。一个个数拆分可能也行，我去实际敲代码试试再回来写思路。
额，两个结果：
- 确实用的动规。
- 测试案例居然有00的，疯了吧?
反正做是做出来了，先说说思路(这个是我看到的一个比较好的题解，直接copy了一下。)：
此题和爬楼梯是同一个类型的问题，难点在于其添加了许多限制条件，只要避开限制条件就可以完美解题了
每次递进，可以选取一个数也可以选取两个数：
s[i] != '0'
如果 s[i-1]s[i] <= 26, 则 dp[i] = dp[i-1] + dp[i-2]
如果 s[i-1]s[i] > 26, 则 dp[i] = dp[i-1], 这是因为 s[i-1]s[i] 组成的两位数无法翻译
s[i] == '0'
如果 s[i-1]s[i] <= 26, 则 dp[i] = dp[i-2], 这是因为 s[i] 无法翻译
还有一些情景直接使得整个序列无法被翻译：
相邻的两个 ‘0’
以 ‘0’ 结尾的大于 26 的数字
去除这些限制条件，此题就是爬楼梯的问题了，一次可以爬一步，也可以爬两步，问有多少中方式到达终点。
这个思路其实很清楚。所以我直接贴代码了（代码是我自己写的）：
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int help = 1;
int res = 0;
if (s.charAt(len - 1) != '0') {
res = 1;
}
for (int i = len - 2; i >= 0; i--) {
if (s.charAt(i) == '0') {
help = res;
res = 0;
continue;
}
if ((s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0') <= 26) {
res += help;
//help用来存储res以前的值
help = res-help;
} else {
help = res;
}
}
return res;
}
}
这个思路就是如果倒数第二个数是0，则倒数第一个数只能是单独的，不会有多种方法，所以res不变，直接continue。同理往前，前一个数是0，后一个不会有多种解法。另外这里因为测试案例的奇葩，00非法输入，连着进入两次第一个if则res，help都是0了。最后结果也是0，符合测试案例的要求。
我觉得挺喜欢那句话的：这道题就是爬楼梯添加了各种限制条件的进阶版。
今天的笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，最近做题遇到瓶颈了，顺便换个心情，所以现在在系统的学习整理多线程高并发这块，这个不能保证每天一篇笔记了，随缘更新吧~~每天进步一点点！
