暴力做法是循环 x -= y，x为被除数，y为除数，减到 x 小于 y 为止，每减一次计数变量 ++，最后输出计数变量。
然而以上这种做法显然是会超时的！！！
高级解法是二进制移位倍增，其实这也是计算机实现除法的本质。二进制倍增的意思就是暴力的做法让y一个一个地增太慢了，每次应该大一点地向x逼近，那么怎么确定这个大呢？
我们可以，以y为基数，并定义一个数组，在小于x的情况，y倍增一倍后存入该数组，循环，直到该数大于x。这时我们每次在向x逼近的时候就可以从上面那个数组中最大的数向x逼近，逼近成功（逼近的数小于x），那么商就加上 2的该数在数组中索引的次方（为什么是2？因为y在倍增准备的时候是一次增加一倍的）即可。
但现在lc已经规定假设只有int这一数据类型，所以这一解法是不成立的，但二进制的基本思路还是不变的。
实现的时候有两个难点：
1、 怎么产生倍增数组
2、不用乘法，商怎么加上 2的索引次方（这里使用了位运算，1 << i 的意义就是将1在二进制上向左移位 i 格，新移出的部分都会0，比如：1 << 3，实际上在二进制中就是0001 —> 1000，变为了2^3。从上面的例子可以看出对1做左移位，向左移动几位后其值就正好是2的 几次方）
若想进一步了解“位运算”，可以参考文章：
c++位运算中最常用的两种操作
【注】这里由于可能会出现溢出，即如果i==31时，2^31就已经超出了int的数据范围了，所以在1后面加上了 ll (long long)防止溢出。这是c++11中的新特性，将ll或LL加在某个数字的后面，可以将其提升为long long类型，也可以防止在后面的计算中溢出！！！
代码示例：
class Solution {
public:
int divide(int x, int y) {
typedef long long LL; // type + def : 由于long long写起来比较长，所以可以重新定义一下。定义的时候你可以读作：type long long def LL，这样更好记忆，long long要放在前面，LL 要放在后面
vector exp; // 用于存二进制倍增数组
bool is_minus = false;
if(x < 0 && y > 0 || x > 0 && y < 0) is_minus = true;
LL a = labs((LL)x), b = labs((LL)y); // x可能是-2^31，除以一个正数可能就溢出了（但现在题目规定了不能用long long，假设只有int存）
// 现在开始生成二进制倍增的前提，在小于a的前提下，每次都倍增一次
// 到时候减的时候，从大向小减
for(LL i = b; i <= a; i = i + i) exp.push_back(i); // 注意存入方式是push_back，注意是可以取到等于a的，最好的情况就是和a相等，这样就能够整除了
LL res = 0;
for(int i = exp.size() - 1; i >= 0; i --) { // 从大往小去减
while(a >= exp[i]) { // 这里while的时间复杂度为O(1)，因为只会执行一次，其实这里用if也行，只是while更好理解
a -= exp[i];
// 下面是关键代码：如何获取exp[i]对应多少商？
res += 1ll << i; // 为什么加上2的i次方，因为假设上面条件成立，那么x时减去了2个i次方的y成立，商则是要加上2的i次方
// 2的i次方注意会溢出，不过这里防止溢出的方式还是很难理解
}
}
if(is_minus) res = -res; // 注意：转化成负数，不用乘-1，直接在前面加一个负号
if(res > INT_MAX || res < INT_MIN) res = INT_MAX; // 正号的情况下判断最好
return res;
}
};
【注】typedef long long LL;
定义的时候你可以读作：type long long def LL，这样更好记忆，long long要放在前面，LL 要放在后面 ！！！
使用负数有什么好处？ 可以存-2^31，比正数可以多存一个数。这样在不能用long long存储数据而只能用int存数据时可以在计算时涵盖所有的情况，等计算完之后，再根据相应的值去做相应的值返回。
class Solution {
public:
int divide(int x, int y) {
// 由于负数的存储范围更大，所以我们将所有的运算数都转变为负数进行计算
if(x == INT_MIN && y == -1) return INT_MAX;
if(x == INT_MIN && y == 1) return INT_MIN; // 对两个特殊情况都执行特判，虽然很蠢。第一个特判是单例特判，这种情况是确定溢出的。第二个特判则是为了防止下面商加上2^i时溢出，即 res -= 1 << i;时1 << i会溢出！
vector exp;
bool is_minus = false;
if(x > 0 && y < 0 || x < 0 && y > 0) is_minus = true;
if(x > 0) x = -x;
if(y > 0) y = -y;
// 求倍增数组
// for(int i = y; y >= x ; i += i) exp.push_back(i); // 实际上是i + i >= INT_MIN，只有满足这个不越界才能继续翻倍加
int temp = y;
for(int i = y; i >= x;) {
exp.push_back(i);
if(i >= INT_MIN - i) i += i; // 现在由于要先判断是否会溢出才i += i，否则可能会溢出。故不把i+=i放在传统的位置上
else break;
}
// 这里是核心代码：不过把+= 变成 -=，但：
// x -= exp[i];
// res -= 1 << i; 的意义不同，一个是减负数(向0逼近)一个是减正数（累加）
int res = 0;
for(int i = exp.size() - 1; i >= 0; i --) {
while(x <= exp[i]) {
x -= exp[i];
res -= 1 << i; // 由于前面已经特判过了，所以不用担心越界的情况，如果不特判，就可能会出现i == 31，而溢出
}
}
// 结果输出，是正数的就要在数字前面加一个负号
if(is_minus) return res;
else return -res;
}
};
以上用特判处理后，仍然可能越界的情况就是：
在push_back倍增数组时，倍增后可能会越界，所以要把可能越界的数在不等号左右两边减一下，这样就不会溢出了，且若有这种情况，就立即break循环。
【思考】本题是不能用乘法、除法和 mod 运算符实现除法，那么这样情况的乘法怎么实现呢？
（二）LeetCode30：串联所有单词的子串在阅读本题的时候，要注意每个单词的长度都是相同的，了解这一点至关重要。
本题题文中有两个关键：①. 要找出所有的匹配情况 ②. 拼接时子串中的单词是无序排列的
先规定几个量：
- 字符串总长度n：s.size()
- 给的单词的个数m：words.size()
- 每个单词的长度w：word[0].size()
思路：
基本的遍历思路（对于每道算法题，了解暴力做法都非常重要，这样我们才能在它的基础上做优化）就是枚举字符串s中所有长度为m*w（同时，我们与它去匹配的子串又有很多种情况！）的子串，而枚举的起始位置为O(n)个，比如起始位置可以是0，可以是1，可以是2，可以是3…，具体有多个起始位置，由子串的长度决定，但大概就是O(n)个!
了解了基本思路，那就开始做一个优化：我们可以把所有起始位置都做一个分类间隔，比如对于0的，可以将s分割成：0, w, 2w, 3w, …；对于1的，可以分割为：1, w+1, 2w+1, 3w + 2…；… 对于为w - 1的，可以分割为w - 1, 2w - 1, 3w - 1, 4w - 1…，总共可以分成w组（为什么要分成w组呢？因为你再分，就重复了，比如以w为起始点的组，其实就是以0为起始点的组嘛，这有点像数学中去找一个规律的长度一样：找到一整个长度后，它后面的情况就一样了，重复了）。每一组都代表一类起始位置，比如第一组的起始位置可以是0， w， 2w， 3w，这每一个都可能成为起始位置，具体还取决于m的长度！
那么现在你一定想问了，这样分组有什么用吗？有什么好处吗？
这样限定之后，在其中随便找一个起始位置都能发现，每个单词都被限制在一个框里面了（因为每个单词都会等长的），每个单词都会被限定在一个区间当中，且是正好全在里面，不会发生一个单词同跨两个区间的情况（比如把第一种情况的起始点为0为例，如下图）！
同时因为每个单词都会在一个“坑”里面，所以我们可以把每一“坑”都当做一个点来看（以第一类为例）：
现在的问题就成功“将线转化成了点”：（关键点）
给我们一堆连续的元素（“圈”），先要我们找到连续m个“圈”，且这连续m个元素中的每一个元素都要使我们给定的那些元素
根据以上问题的描述，敏感的同学应该已经知道了，这就是一个经典的滑动窗口问题了！
怎么维护实现呢？(very important！)
把题目给定的所有单词都存到一个hash表1当中，然后用一个长度为m的滑动窗口来维护所有长度为m的所有子段，并把该子段中的每个单词也存到一个hash表2中（我们怎么获取该子段的所有单词，上面优化的作用就来了，因为现在的情况是每个“坑”都对应一个“单词”，虽然有些情况它可能不是有意义的单词，但还是可以按照坑把它们取出来），且当滑动窗口往后移动一位后，hash表2中就减一个元素和加一个元素，并将新的hash表2的集合与元素hash表1的集合作比较，如果元素都一一对应那就成功的一个组合！
上面的实现中有一个问题：如何判断两个hash表中的元素相等呢？
暴力判断当然可以，把一个hash表中的元素到另一个hash表中去查，看是否有返回结果，然后一一遍历，这样的时间复杂度就是O(n)了！
更优质的做法是定义一个计数变量cnt，该计数变量用于统计hash表2中的有效单词，cnt通过hash2中的value属性的值去判断该单词是否出现过和出现的次数是否符合。什么叫有效单词？在hash1中出现过的，且在hash表2中的个数与hash表1中的个数是符合的！这样不去一一遍历的时间复杂度就是O(1)了（具体实现看下面的代码）。
代码示例：
class Solution {
public:
vector findSubstring(string s, vector& words) {
vector res; // 最后返回的答案
if(words.empty()) return res; // 如果给的单词数组为空，那啥也不返回
int n = s.size(), m = words.size(), w = words[0].size();
// 定义给的words数组的hash表1：
unordered_map hash1; // 其中的String用于放置单词，而int则统计其中每个单词出现的次数
for(auto& word : words) hash1[word] ++; // &引用这里可以不加，加的话就快一些。其中hash1[word]++统计每个单词出现的次数
// 分组
for(int i = 0; i < w; i ++) {
// 每一个组都有的hash表，它和滑动窗口对应。所以它也要在循环中定义，一个组遍历完之后，有重新定义一个hash表
unordered_map hash2;
int cnt = 0; // 记录有效单词出现的个数
for(int j = i; j + w - 1 <= n - 1; j += w) { // 内部的滑动窗口在每个组内滑动，其中j为滑动窗口的尾部，从中止条件（中止条件为什么要去等？腰围这里我们是要取的是长度，若要取到最后一个点的前一段的长度就一定要取到最后一个点；但如果仅仅是下标的遍历，那就不要去最后一个点了）也可以看出来。
// 且内外循环是有联系的，某组中j的最开始起始点就是i
if(j >= i + m*w) { // 首先要判断一下最开始时j所在的位置往前的长度是否能够构成一个滑动窗口；如果这个成功了，往后随着j一直向后遍历，那其实也就不用判断了，那时往前长度一定够
auto word = s.substr(j - w*m, w);// 每次窗口往后移动，一定要把最开始的那个单词删掉
// substr是传入开始点和截取的长度
hash2[word] --; // 把该单词从滑动窗口中去掉
if(hash2[word] < hash1[word]) cnt --; // 该单词在滑动窗口中去掉后，如果总数小于hash1中该单词出现的次数，那么该单词为有效单词。cnt要--
}
// 往滑动窗口添加元素为什么要放在if语句的外面？
// 因为if窗口长度不够，就要往里添加元素；如果够，要往后遍历，也要添加元素，ifelse都躲不过，所以就放在if外，无论怎样都要加
// 去掉了头部的单词后，把下一个单词找到并添加
auto word = s.substr(j, w);
hash2[word] ++;
if(hash2[word] <= hash1[word]) cnt ++; // 和减的思路一致。但加之后就是小于等于了
// 下面这个if语句与上面的语句含义都不一样，这个是判断目前这个滑动窗口是否成功的
// 成功就将滑动窗口的开始索引值存入答案数组res中
if(cnt == m) res.push_back(j - (m - 1)*w); // 这里j要减的是(m - 1)*w个元素，因为滑动窗口已经向后移了一个w长度的单词了，但尾部j的坐标还未变！
// 所以cnt定义的位置也是很有讲究的，要放在内层循环的外面，下一组情况时就更新为0
}
}
return res;
}
};
【小结】
1、 时间复杂度分析：
对于每一组而言，其中一共有n/w个单词，而每一个单词进出滑动窗口，往hash表里插入的时候，时间复杂度则是O(w)的，因为一个单词插入hash表时，是要插入这整个单词的，然后这个单词有w个字符的！故而现在可以计算出每一组情况的时间复杂度为O(n/w*w) == O(n)!
现共有w组，所以总时间复杂度为O(nw)。
当然，本题还有一种更优质的优化？时间复杂度为O(n)
今天这里我们先不叙述，简单说就是：字符串哈希。我们上面不是因为在插入时每个单词的长度都为w，所以插入时才要乘以一个时间复杂度O(w)吗？字符串哈希就是把每个单词都映射成一个数字，这样在插入hash表时就不用乘以一个w了！！！
2、 滑动窗口其实就是双指针，但双指针不一定是滑动窗口！（滑动窗口问题是双指针的一个子集）
3、 引用&和指针*的区别与联系：它们都是与原始的赋值数据共用一个内存地址（原始数据变，它们的数据也跟着变），然后引用&相当于和原始数据签了一个终身合同（不平等条约：一个变量可以有多个引用，但一个引用只能专属于一个变量），不能再改变该引用的指向了，而指针只是临时合同，它可以随时换公司（更换指向的变量）。
【注：问题来源】for(auto& word : words)
4、 关于j的for循环的中止条件为什么取等？ 因为是长度的遍历，而不是索引的遍历。
5、 注意c++中的字符串截断函数为substr(param1, param2)，其中param1为截断的开始位置，而param2为将要截断的长度
（三）LeetCode31：下一个排列本题是要找所有数字排列结果中比当前排列下的值正好大一点的下一个值，比如当前的排列为123，它的下一个排列就是132；同时，其实c++中有一个与它描述功能相同的库函数：next_Permutation。
第一次接触本题，要想到思路还是比较难的。本题并不是某个典型的模板，而是智商题，见过就是见过，没见过就很难想到。
解决思路
从后往前找（当然是非严格的，即降序过程中允许有相等的）降序的这样一个排列，直到不是降序时，记住那个数x，然后在降序序列中找一个只比x大一点的数，并将它们交换。交换完之后（交换完之后仍然是降序序列，因为它取得是比它大的最小值，所以它后面的元素还是小于等于它的），将降序序列进行reverse之后，此时的排列就是比刚才的排列大一点的数了！
其中的关系如下图所示：1 > 3 > 2。且2的水平线之上对应的降序序列中的3下面没有其他的数，我们将2与3的值进行交换（其中1,3所在的是降序的序列）！
思路原理
本题有一个基本常识，就是要只小一点点的话，尽量不要从前面的数开始改，这样改动的会比较大，所以我们是从后开始改（遍历）。
同时，从后面开始找（当然，客观地看它还是从左到右的），找降序序列，是因为降序序列的最左边的数为局部最大点，右边的数都比他小，而该数左边的第一个数则为序列开始逐渐减小的趋势点（极端情况：若降序序列的第一个数为整个序列的第一个数，那么就不存在减小的趋势点了，此时整个序列也是最大的）。
有了以上概念后：现在我们若想将整个序列变大一点点，就要将减小的趋势点变大，当然，变大的方式有很多，用序列中哪个大于它的数与其交换呢？由于只要下一个序列，所以我们就要从那个找到的降序序列中找到一个比它大的第一个数（即只比它大一点的数），将两者交换，此种从后面的数进行的交换相对来说对整个序列的大小不会影响很大。交换之后还要将交换完的降序序列进行reverse，因为交换完之后，整个序列的减小区试点已经提升了，若要此时正好为下一个序列的值，那么该点后面的序列就要变小，且是该点情况下的最小情况，所以要将降序序列reverse一下，这样此时它就是最小的了。
当然，本题还有一个特判情况，如果当前数已经是最大了，那么就将它反转，转为最小的数！
class Solution {
public:
void nextPermutation(vector& nums) {
int k = nums.size() - 1;
while(k && nums[k - 1] >= nums[k]) k --; // 寻找降序序列
// 循环跳出后k为局部最大值
if(k > 0) { // 此时不是 3, 2, 1这种最大的特殊情况
int t = k;
while(t < nums.size() && nums[t] > nums[k - 1]) t ++; // 找到大于k - 1的最小值
swap(nums[k - 1], nums[t - 1]); // 将趋势较小点与t - 1交换，为什么要t - 1呢？
// 因为当nums[t] <= nums[k - 1]是，已经执行了t++了，这样为了获取正确的t就要t- 1
reverse(nums.begin() + k, nums.end()); // 将降序序列翻转
} else reverse(nums.begin(), nums.end()); // 特殊情况将降序序列翻转
}
};
