不使用除法的“除法”
原创
题目：
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
提高效率快速逼近结果，
举个例子：11 除以 3 。
首先11比3大，结果至少是1， 然后我让3翻倍，就是6，发现11比3翻倍后还要大，那么结果就至少是2了，那我让这个6再翻倍，得12，11不比12大，吓死我了，差点让就让刚才的最小解2也翻倍得到4了。但是我知道最终结果肯定在2和4之间。也就是说2再加上某个数，这个数是多少呢？我让11减去刚才最后一次的结果6，剩下5，我们计算5是3的几倍，也就是除法，看，递归出现了。
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == 0) return 0;
if (divisor == 1) return dividend;
if (divisor == -1) {
//防止溢出
if (dividend > Integer.MIN_VALUE) return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦
return Integer.MAX_VALUE;// 是最小的那个，那就返回最大的整数啦
}
long a = dividend;
long b = divisor;
int sign = 1;
if ((a > 0 && b < 0) || (a < 0 && b > 0)) {
sign = -1;
}
a = a > 0 ? a : -a;
b = b > 0 ? b : -b;
int res = div(a, b);
if (sign > 0) return res;
return -res;
}
private int div(long a, long b) {
if (a < b) return 0;
int count = 1;
long tb = b; // 在后面的代码中不更新b
while ((tb + tb) <= a) {
count = count + count; // 最小解翻倍
tb = tb + tb; // 当前测试的值也翻倍
}
return count + div(a - tb, b);
}
public static void main(String[] args) {
Solution solution = new Solution();
int divide = solution.divide(-2147483648, 2);
System.out.println("divide result: " + divide);
}
}>链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。