剑指offer

除法

不能使用除法的情况下实现除法的功能。

想法是这里依次的去减除数，知道不能减了为止。但是这样如果碰到被除数极大，除数极小，很可能会超时。一个思路是：尝试在不断倍增除数，扩大2 4 8 16 ……倍，让这样的分割越来越大，减的速度越来越快，是 logN 的时间复杂度。考虑到仍然可能会余数还要重复操作，所以一次减完还不够，有点类似TCP发包的慢启动环节。

为了处理负数，把一开始的参数都强制用绝对值在后面的计算中。最后再判断正负

 while(a >= b){
   long n = 1, base = b;
   while((base << 1) <= a){
		base <<= 1;
		n <<= 1;
   }

   a -= base;
   ans += n;
}

二进制求值

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。

按照二进制加法求出加法后的当前位和进位，注意这里的求出方式：最后保存的答案不要通过数组到字符串的转换，直接就用string初始化。

while(i >= 0 || j >= 0 || carry){
	int adda = (i >= 0) ? a[i--]-'0' : 0;
	int addb = (j >= 0) ? b[j--]-'0' : 0;

	int sum = adda + addb + carry;
	ans.push_back((char)(sum % 2 + '0'));
	carry = sum / 2;

}

reverse(ans.begin(), ans.end());
return ans;

最大单词长度乘积

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

两个字符串找乘积最大值也只能两两比较，加快的技巧在如何快速检查是否重叠。数组遍历时间爆炸，哈希表保存每一个字符串的 char 可行，但是必须更大的 set，不能每次比较单独生成，这样会很耗时。用数组记录每个字母是否出现过也是很好的办法，用到的还是位运算。

字符串保存处理——数组
用位运算把每一个字母位标记下来，字符串中出现字母为 1，否则为 0. 相对哈希表保存字符串更简单高效。

for(int i = 0; i < n; i++){
	for(char ch: words[i]){
		mask[i] |= (1 << ch - 'a');
	}
}

for(int i = 0; i < n; i++){
	for(int j = i+1; j < n; j++){
		if(!(mask[i] & mask[j]))
			maxlen = max(maxlen, (int)(words[i].length() * words[j].length()));
	}
}

滑动窗口

怎么用好滑动窗口来对序列提取目标子数组？
窗口一般符合 “右边界每次迭代向右移动，左边界只在满足特定条件下尝试多次移动” ，这样一个模型对应的题目情况是：子序列为满足目标条件，for 循环不断向前；每次迭代中检查是否满足条件 T，如果满足，则 while 循环内不断前进左边界。

这个模型一般针对 “子序列窗口一般需要较长才满足及其变种问题” ，也就是右边界尝试先移动一段距离，eg：找到数组中大于某一个数的所有子序列。

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0 。

这道题是典型的滑动窗口例题，窗口有指针在不满足条件时不断向右移，一旦发现满足条件，在当次右指针位置不断移动左指针直到收缩到边界情况。题目的条件刚好是大于等于，也是窗口的典例。

for(left = 0, right = 0; right < n; right++){
	sum += nums[right];

	while(sum >= target){
		minLen = min(minLen, right-left+1);
		sum -= nums[left];
		left++;
	}
}

和为 K 的子数组