刷leetCode算法题+解析（十二）
今天下班没事做，额外再刷几道题。
验证回文串
题目：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
思路：怎么说呢，这道题给我的感觉是挺简单的，我发现现在力扣上的题有个规律，暴力法能解决但是性能不行。这道题也是，注意点1.只要字母和数字。2.忽略字母大小写。只有这俩。做出来其实很容易的，处理步骤1.字符串处理成只有字母和数字并且全部大写或小写。2。遍历字符串第一个和最后一个比较，第二个和倒数第二个比较依此类推。中间比较有不等就是false，没有出了遍历返回true
直接上代码：
class Solution {
public boolean isPalindrome(String s) {
//先把这个字符串的所有特殊字符，空格什么的去掉
String regEx="[^a-zA-Z0-9]";
s = s.replaceAll(regEx,"").toUpperCase();;
int len = s.length();
//奇数偶数都是一样的。奇数是除了中位数剩下对称，偶数是各个对称。
int mid = len/2;
for(int i=0;i<mid;i++ ){
if(s.charAt(i)!=s.charAt(s.length()-1-i)){
return false;
}
}
return true;
}
}
代码简单，逻辑分明，就是性能感人。完全让我感受不到会了一道题的乐趣。而且我还没想出优化的办法。直接看题解吧。
public boolean isPalindrome(String s) {
//先把这个字符串的所有特殊字符，空格什么的去掉
String regEx="[^a-zA-Z0-9]";
s = s.replaceAll(regEx,"").toUpperCase();;
StringBuffer sb = new StringBuffer(s);
return sb.toString().equals(sb.reverse().toString());
}
这个是大佬思路，这个怪我基础差，意识薄，压根没想到还有这个反转方法。不过这都不重要，反正大佬的思路跑是跑通了，然后性能依然感人。
看了一圈，发现性能消耗主要是在字符串处理的的部分。如果想要性能好就不能用正则，要自己遍历，判断字符是不是在数字，字母范围。然后再判断。虽然性能不错但是麻烦也是真的麻烦。我就不自己做了。
只出现一次的数字
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
做不出来没思路烦，能做出来有思路了还烦。因为我不太懂这个不适用额外的空间是什么意思。还有我觉得我的思路应该又属于暴力解法，就是蠢笨蠢笨的。关于这种什么时间复杂度空间复杂度的话，有空是要补补课了。哎，哪怕是暴力解也先贴出来吧
class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
//出现两次则移除
if(map.containsKey(nums[i])){
map.remove(nums[i]);
}else{
//一次没出现则添加key
map.put(nums[i],0);
}
}
//最后剩下的那个key就是求的数值
for(Integer key:map.keySet()){
return key;
}
return -1;
}
}
其实性能还行，就是速度慢点：
image.png
然后有点小心烦，我发现没有数学功底真的有点难，哎，直接看大神思路了。做的题越多越发现无论是从知识量，api的熟悉度上来讲都差得多。
很漂亮，看了解析又发现了自己的知识盲区。这个题的最简单的解法是异或。
这块涉及的真的不多，还是这个题让我回忆了下知识。
首先5^5结果是0。
0^任何数结果是任何数原数。
我之前在eclipse做了几个简单的demo，看了demo大概就能明白异或的用法了。
image.png
所以这道题从头到尾异或一遍，成对的就消去了，单身狗就留下了。简单除暴。
image.png
public int singleNumber(int[] nums) {
int result = 0;
for(int i=0;i<nums.length;i++){
result = result^nums[i];
}
return result;
}
你看，我那么多行代码，人家这一个循环。只能说还是要学基础知识啊。
环形链表
题目：给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
这个题目其实只要知道什么叫环形链表就好了，环形链表，即原本末尾的节点的 next 指针，指向了链表的任意一个节点，形成了一个闭环。在这种环形链表中，遍历时会停不下来，因为在环中会一直循环，这是它的特点。
这样因为是循环的，所以肯定进入环节点的链表是存在的。打个比方：链表124124124124124..循环下去，你到第一个1的时候这个链表保存，继续往下走到第二个1，会发现这个链表已经存在。
按照这个想法其实很容易做出来（我在搜索啥叫环形链表的时候不小心看到一言两语，所以不能完全算是自己的思路）直接上代码:
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
//因为这个快的肯定比慢的先空，所以只要判断fast就行了，真空了说明到尾了，也就是不会是环
while(fast!= null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(fast==slow){
return true;
}
}
return false;
}
}
好的，这道就这么解了。因为本身性能已经很优了，所以不再看别的思路了。
不行，没忍住看了下评论，被各种人才吸粉了。各种秀！
简单的说几个骚操作：
- 把每一个元素值改成一个很奇葩的值，例如“sfasfasfasfas”，然后往下遍历。如果遍历到了这个奇葩值说明指针指回来了，这是个环形链表。不然等遍历完了就是不是环形链表。
- 据说leetCode测试链表数据最大8029个数据（不是环的情况下）。所以遍历到8029还没结束就是环了。
- 这个是js的。将此链表转化成字符串，如果是环会超出时间限制转化失败，然后catch错，如果能catch到就说明是环。
做题挺严肃的，看个解题给我笑抽了。真的是自古评论出人才。
好了，今天就写到这里，如果稍微帮到你了麻烦点个喜欢点个关注呦~~也祝大家工作顺顺利利！！
