LeetCode精选好题（一）
本来想把三个月的题目全部重新做一遍，筛选一遍，再一次性发。 but眼看今天就断更了，算了算了，筛选到了链表部分了。
1、删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。
思路： 数组完成排序后，我们可以放置两个指针 i 和 j，其中 i是慢指针，而 j 是快指针。只要 nums[i]=nums[j]，我们就增加 j 以跳过重复项。
当我们遇到 nums[j]≠nums[i]时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i+1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。
优化： 此时数组中没有重复元素，按照上面的方法，每次比较时 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。
因此我们可以添加一个小判断，当 q - p > 1 时，才进行复制。
代码：
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0) return 0;
int p = 0;
int q = 1;
while(q < nums.size()){
if(nums[p] != nums[q]){
nums[p + 1] = nums[q];
p++;
}
q++;
}
return p + 1;
}2、买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示： 1 <= prices.length <= 3 * 10 ^ 4 0 <= prices[i] <= 10 ^ 4
思路： 假设给定的数组为： [7, 1, 5, 3, 6, 4] 如果我们在图表上绘制给定数组中的数字，我们将会得到：
如果我们分析图表，那么我们的兴趣点是连续的峰和谷。
代码实现：
int maxProfit(vector<int>& prices) {
int a = prices.size();
int i,j,k,sum = 0;
for(i = 0,j = 1,sum = 0 ;i<a-1,j<a;)
{
k = j+1;
if(prices.at(i)<prices.at(j) && j<a)
{
while (k<a&&prices.at(k)>=prices.at(j)) {
j=k;
k++;
}
sum+=prices.at(j)-prices.at(i);
}
i = j;
j++;
}
return sum;
}3、移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 思路： 双指针法：慢指针锚定一个0，快指针从慢指针后面一位开始找一个非0的值，找到之后交换快慢指针的值，然后慢指针继续溜达。 代码实现：
void moveZeroes(vector<int>& nums)
{
int fast = 0,slow = 0;
for(;fast<nums.size() && slow<nums.size();){
if(nums[slow] == 0){ //踩到0了
if(fast<=slow){
fast = slow+1;
}
while(fast<nums.size()){
if(nums[fast] != 0){
swap(nums[slow],nums[fast]);
break;
}
fast++;
}
}
slow++;
}
}4、整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 示例 1: 输入: 123 输出: 321 示例 2: 输入: -123 输出: -321 示例 3: 输入: 120 输出: 21
注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
思路： 主要就是“注意”的那一块，要是不越界，那很直观。 以前的做法傻的很，一层一层的判断，写了一百多行现在学聪明了，用结果来递归。
代码实现：
int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7))
return 0;
if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8))
return 0;
rev = rev * 10 + pop;
}
return rev;
}5、反转链表
反转一个单链表。
方法： 尾插法。其实最主要的是，看到这些熟悉的题目，别激动，一激动，就容易乱，一乱，就慌，一慌，就完蛋。
代码实现：
ListNode* reverseList(ListNode* head) {
if(head == NULL)
return NULL;
ListNode* temp;
ListNode* cur = head; //当前指针位置
while(cur->next!=NULL){
temp = cur->next;
cur->next = temp->next;
temp->next = head;
head = temp;
}
return head;
}6、回文链表
这么说吧，想一下前两题（哦，另一题在另一部分）。 感觉我的聪明花突然开了。先对链表后半段反转，在用双指针进行比对。
第一遍遍历，计数并找到中间节点。 第二遍遍历后半段，进行反转。 第三遍同步遍历前后半段，进行比对。 省着点算，遍历了两遍。
7、环形链表 题目不多做介绍了，解题思路嘛，快慢指针，快指针一次走两步，慢指针一次走一步。如果有环，那么快指针绕一圈之后一定会和慢指针偶遇。如果没有环，那么快指针就会走到穷途末路。
代码实现：
bool hasCycle(ListNode *head) {
if(head == NULL)
return false;
ListNode* fast = head;
ListNode* slow = head;
while(fast!=NULL && fast->next!=NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return true;
}
return false;
}8、环形链表寻找入环点 在快慢指针相遇时，在头结点再放一个慢指针，然后让环中那个慢指针继续走，再相遇，就是入环点。 证明：
在第一次相遇时，有等式：
2（D+S1） = D+nS2+(n+1)S1
->D+S1 = n(S1+S2)
->D = (n-1)(S1+S2)+S2也就是说，在快慢指针相遇时，在头结点再放一个慢指针，然后让环中那个慢指针继续走，再相遇，就是入环点。