LeetCode精选好题（一）
本来想把三个月的题目全部重新做一遍，筛选一遍，再一次性发。
but眼看今天就断更了，算了算了，筛选到了链表部分了。
注：本系列只记录奇技淫巧，不选入特殊数据结构如map、set、哈希等解法的题目。
要找数据结构，我建议点这里嘿嘿
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
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++; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
8、环形链表寻找入环点
在快慢指针相遇时，在头结点再放一个慢指针，然后让环中那个慢指针继续走，再相遇，就是入环点。
证明：
在第一次相遇时，有等式：
2（D+S1） = D+nS2+(n+1)S1
->D+S1 = n(S1+S2)
->D = (n-1)(S1+S2)+S2
- 1
- 2
- 3
也就是说，在快慢指针相遇时，在头结点再放一个慢指针，然后让环中那个慢指针继续走，再相遇，就是入环点。
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/107585599
- 点赞
- 收藏
- 关注作者
评论（0）