请判断一个链表是否为回文链表。
示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 解法1：动态数组 + 双指针思想 时间复杂度O(n)，空间复杂度O(n) class Solution { public: bool isPalindrome(ListNode* head) { //特判 if (!head || !head->next) { return true; } //用一个动态数组作为辅助数组 vector<int> rev; ListNode* first = head; while(first) { rev.push_back(first->val); first = first->next; } //然后双指针，一个个对比。 int l = 0, r = rev.size() - 1; while(l < r){ if(rev[l] != rev[r]) return false; l++; r--; } return true; } }; 解法2：反转链表 class Solution { public: bool isPalindrome(ListNode* head) { //特判 if(!head || !head->next) return true; //初始化 ListNode* slow = head; ListNode* fast = head; // 将slow指针移动到链表中间位置 // 快指针走两步，慢指针走一步，当快指针走到最后的时候，慢指针只走到了一半。 while(fast && fast->next){ slow = slow->next; fast = fast->next->next; } // 反转后半部分 ListNode* curNode = slow;//当前指针 ListNode* nextNode = slow->next; while (nextNode) { ListNode* tmp = nextNode->next; nextNode->next = curNode; curNode = nextNode; nextNode = tmp; } slow->next = nullptr; // 开始比较是否相等 while(head && curNode){ if(head->val != curNode->val) return false; head = head->next; curNode = curNode->next; } return true; } }; 缺失数字 解法1：n的总和 - 那些数的总和 时间复杂度 O(n) class Solution { public: int missingNumber(vector<int>& nums) { int sum = 0; for (int i = 0; i < nums.size(); ++i) { sum += nums[i]; } return nums.size() * (nums.size() + 1) / 2 - sum; } };有个小疑问：
为什么Java的运行时间这么短？Why？
为什么C++的运行时间那么长？想知道…
解法2：异或运算 时间复杂度 O(n) 异或运算法则：相同为0，不同为1 1^1=0 1^0=1 0^1=1 0^0=0 所以在这里，以这个为例子就是：3 ( 2 ) 3_{(2)} 3(2) = 0 1 1
0 ( 2 ) 0_{(2)} 0(2) = 0 0 0
1 ( 2 ) 1_{(2)} 1(2) = 0 0 1
可以推出这样一个性质：1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4= 4; 数组的下标为 0 ~ n - 1 ，但是数组元素是0 ~ n的，所以只要初始值设置为n，那么最终异或下去，就会得到缺失的那个数。 class Solution { public int missingNumber(int[] nums) { int res = nums.length; for (int i = 0; i < nums.length; ++i) { res ^= nums[i]; res ^= i; } return res; } }附上一个过程图：
关键是要把数组下标和值对应起来 ！！
总结： 异或和可以找出一段连续数据缺失的数。
第一个错误的版本题目说：尽量减少对调用 API 的次数
解法：二分查找 时间复杂度为 O(logn)
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ //上面说了已经有一个 boolean isBadVersion() 函数了 public class Solution extends VersionControl { public int firstBadVersion(int n) { //二分的关键就是找到 上界 int l = 0, r = n; while (l < r) { int mid = (int) (((long) l + r) >> 1); if (isBadVersion(mid)) { r = mid; } else { l = mid + 1; } } return l; } }整数二分模板 ①：使用条件是： 区间 [l, r] 被划分成 [l, mid] 和 [mid + 1, r] 时使用
public int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) // check()判断mid是否满足性质 r = mid; else l = mid + 1; } return l; }整数二分模板 ②：使用条件是： 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
public int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) // check()判断mid是否满足性质 l = mid; else r = mid - 1; } return l; }浮点二分模板 ：
public int bsearch_2(int l, int r) { double l = 0 , r = x; //比如如果题目要求保留4位小数，则应该写到-6次方，比有效小数的位数多2 while (r - l > 1e-6) { //还可以写成 for(int i = 0; i < 100; ++i) 循环100次相当于整个区间/ 2的100次方，最后的结果也是很精确的。 double mid = (l + r) / 2;//这里就不可以用l + r >> 1; if (mid >= x / mid)//防止溢出 r = mid; else l = mid; } return l; } 移动零 解法1：冒泡排序 时间复杂度：O(n^2) 解法2：快慢双指针 时间复杂度：O(n) 空间复杂度：O(1) 双指针算法，先用快指针遍历一遍数组，当快指针遍历的元素为非零的时候，将该元素赋值给慢指针。存在0的情况，所以一定存在快慢指针。如果不存在0的情况，则直接输出数组即可。 class Solution { public void moveZeroes(int[] nums) { //可写可不写，为了严谨一点还是写上好了 if (nums.length == 0) return; int idx = 0; for (int i = 0; i < nums.length; ++i) { //当快指针的元素遇到非零时，将值赋给慢指针。 if (nums[i] != 0) { nums[idx++] = nums[i]; } } //后续补0 while (idx < nums.length) { nums[idx++] = 0; } } }单词规律
Nim 游戏 （尼姆博弈）
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 ~ 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
class Solution { public: bool canWinNim(int n) { return n % 4; } };改一下题目，将每次你们轮流拿掉 1 ~ 3 块石头 ，改成每次你们轮流拿掉 1 ~ m 块石头
总是给对手留下 m + 1 块石头，那么对手一定会输。
解法1：% class Solution { public: bool canWinNim(int n) { return n % (m + 1); } }; 解法2：& class Solution { public: bool canWinNim(int n) { return n & m; } };