翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
说明：
- 无空格字符构成一个 单词 。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 1：
输入："the sky is blue"
输出："blue is sky the"
示例 2：
输入：" hello world! "
输出："world! hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入："a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 4：
输入：s = " Bob Loves Alice "
输出："Alice Loves Bob"
示例 5：
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
提示：
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：
请尝试使用 O(1) 额外空间复杂度的原地解法。
解题思路：因为需要原地解法，所以不能申请额外的空间去存储字符串，只能在原字符串上面修改。所以想到的就是利用两次反转实现翻转。然后再次遍历删掉多余的空格。
class Solution {
public:
string reverseWords(string s) {
int i = 0, j = s.size()-1;
//第一次将整个字符串反转
while(i < j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++, j--;
}
i = 0, j = 0;
//第二次依次将每个单词反转
while(true) {
while(s[j] != ' ' && j < s.size()) j++;
int end = j;
j--;
while(i < j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++, j--;
}
i = end;
while(s[i] == ' ' && i < s.size()) i++;
if(i == s.size()) break;
j = i;
}
bool blank = false;
//删除多余1次的空格
for(auto it = s.begin(); it != s.end();) {
if(blank && *it == ' ') {
it = s.erase(it);
}else {
if(*it == ' ') blank = true;
else blank = false;
++it;
}
}
//删除头尾空格
if(s[0] == ' ') s.erase(s.begin());
if(s[s.size() -1] == ' ') s.erase(s.end()-1);
return s;
}
};
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
解题思路：以 0 为界，计算每一个连续数组的乘积，记录最大值。
遍历规则如下：
- 如果该连续数组乘积是正数，则可以直接比较；
- 若该连续数组是负数，则该连续数组的最大值只有可能会出现在四个位置上面，即 第一个负数前的乘积，第一个负数后的乘积，最后一个负数前的乘积，最后一个负数后的乘积。
虽然这么做是通过解题了，但是我发现在实操时有很多需要注意的小细节，所以感觉思路好像是不是不正确。
最后也是磕磕绊绊的 AC 了，不过也算是 常数空间复杂度，时间复杂度 O（n），也算不错了。
后面看题解发现，终究是错付了，正确动作应该是动态规划。因为有负数的存在，所以需要记录某点处的最大值和最小值。
动态规划两步走：
- 初始化，maxF[0] = nums[0], minF[0] = nums[0], ans = nums[0];
- 动态转移，
- maxF[i] = max(maxF[i-1] * nums[i], max(nums[i], minF[i-1] * nums[i]));
- minF[i] = min(minF[i-1] * nums[i], min(nums[i], maxF[i-1] * nums[i]));
- ans = max(ans, maxF[i]);
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0];
int subres = 0;
bool start = false;
int tmp1 = 0, tmp2 = 0, tmp3 = 0, tmp4 = 0, num = 0;
for(int i = 0; i < nums.size(); ++i) {
if(nums[i] != 0 ) {
if(!start) {
subres = nums[i];
start = true;
} else subres *= nums[i];
num++;
if(nums[i] < 0) {
if(tmp1 == 0) {
tmp1 = (num == 1) ? subres : subres / nums[i];
tmp2 = subres;
tmp3 = tmp1;
tmp4 = tmp2;
} else {
tmp3 = subres / nums[i];
tmp4 = subres;
}
}
}
if(nums[i] == 0 || i == nums.size() - 1) {
if(subres >= 0) {
res = max(res, subres);
}else {
int max1 = num == 1 ? tmp1 : max(tmp1, subres/tmp2);
int max2 = num == 1 ? tmp1 : max(tmp3, subres/tmp4);
res = max(res, max(max1, max2));
}
tmp1 = 0, tmp2 = 0, tmp3 = 0, tmp4 = 0, num = 0, subres = 0;
start = false;
}
}
return res;
}
};
寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
解题思路：查找有序数组最常使用的就是利用二分法去解决，所以其实这道题就是查找数组的最小值。
class Solution {
public:
int subFind(vector<int>& nums, int start, int end) {
int mid = start + (end - start) / 2;
int res = -1;
if(start == end) res = start;
else if (nums[mid] > nums[end]) {
res = subFind(nums, mid + 1, end);
}else {
res = subFind(nums, start, mid);
}
return res;
}
int findMin(vector<int>& nums) {
int res = subFind(nums, 0, nums.size()-1);
// cout << res << " " << nums[res] << endl;
return ((res == -1) ? nums[0] : nums[res]);
}
};
寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
- 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
进阶：
这道题是 寻找旋转排序数组中的最小值 的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
解题思路：这道题和上一道题本质上是一样的，但是需要注意的就是有重复值的存在，所以在切割的时候，不能简单的比较大小，还得比较相等的情况。
如果中值和尾值相等，那么将尾往后移一位继续二分。
class Solution {
public:
int subFind(vector<int>& nums, int start, int end) {
int mid = start + (end - start) / 2;
int res = -1;
if(start == end) res = start;
else if (nums[mid] > nums[end]) {
res = subFind(nums, mid + 1, end);
}else if (nums[mid] < nums[end]){
res = subFind(nums, start, mid);
}else {
res = subFind(nums, start, end-1);
}
return res;
}
int findMin(vector<int>& nums) {
int res = subFind(nums, 0, nums.size()-1);
// cout << res << " " << nums[res] << endl;
return ((res == -1) ? nums[0] : nums[res]);
}
};
最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
解题思路：直接利用栈和动态规划的思想，保存当前的 val，以及最小值，so easy！
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
class MinStack {
public:
/** initialize your data structure here. */
stack<pair<int, int>> mST;
MinStack() {
}
void push(int val) {
pair<int, int> it;
if(mST.empty()) {
it = make_pair(val, val);
}else {
it = make_pair(val, min(val, getMin()));
}
mST.push(it);
}
void pop() {
mST.pop();
}
int top() {
return mST.top().first;
}
int getMin() {
return mST.top().second;
}
};
上下翻转二叉树
用 Read4 读取 N 个字符
用 Read4 读取 N 个字符 II
至多包含两个不同字符的最长子串
会员专享，作为白嫖小王子当然选择跳过
相交链表
编写一个程序，找到两个单链表相交的起始节点。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
解题思路：首先遍历两个数组得到两个数组的长度，并且判断这两个数组的未节点是否是同一个，如果不是的话直接返回 NULL。
找到两个数组的长度之后，先让长的链表先走相差的节点，然后再一起遍历，找到第一个相同的节点返回。这样做的时间复杂度为 O(max(m, n)), 空间复杂度为 O(1);
ps: 看完解题发现可以用更优雅的方法去解决问题，就是利用双指针法；
- 用 a+c 表示链表 A， b+c 表示链表 B， 其中 c 为 A 和 B 相同的子链表，且 c 长度不可能为 0，因为有 NULL 节点的存在，c 长度至少为1。
- 这样会发现一个神奇的现象： a+c+b+c = b+c+a+c，这在数学中其实就是交换律。
- 根据这个等式可以发现不管 a 和 b 的长度是否相等，只要按照这个等式，两个指针一定会在 c 的头结点相遇。
- 漂亮！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lA = 0, lB = 0;
ListNode *scanA = headA, *scanB = headB;
while(scanA->next || scanB->next) {
if(scanA->next) {
lA++;
scanA = scanA->next;
}
if(scanB->next) {
lB++;
scanB = scanB->next;
}
}
if(scanA != scanB) return NULL;
ListNode *shortN, *longN;
if(lA > lB) {
shortN = headB, longN = headA;
}else {
shortN = headA, longN = headB;
int tmp = lA;lA = lB; lB =tmp;
}
while(lA >= 0) {
if(lA > lB) longN = longN->next;
else {
if(longN == shortN) return longN;
longN = longN->next;
shortN = shortN->next;
}
lA--;
}
return NULL;
}
};
