Go 两数相除

• By Admin
• 4个月前

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,  2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

解题思路

• 给出除数和被除数，要求计算除法运算以后的商。注意值的取值范围在 [−2^31, 2^31 − 1] 之中。超过范围的都按边界计算。
• 这一题可以用二分搜索来做。要求除法运算之后的商，把商作为要搜索的目标。商的取值范围是 [0, dividend]，所以从 0 到被除数之间搜索。利用二分，找到(商 + 1 ) * 除数 > 被除数并且 商 * 除数 ≤ 被除数 或者 (商+1)* 除数 ≥ 被除数并且商 * 除数 < 被除数的时候，就算找到了商，其余情况继续二分即可。最后还要注意符号和题目规定的 Int32 取值范围。
• 二分的写法常写错的 3 点：

1. low ≤ high (注意二分循环退出的条件是小于等于)
2. mid = low + (high-low)>>1 (防止溢出)
3. low = mid + 1 ; high = mid - 1 (注意更新 low 和 high 的值，如果更新不对就会死循环)

package leetcode

import (
	"math"
)

// 解法一 递归版的二分搜索
func divide(dividend int, divisor int) int {
	sign, res := -1, 0
	// low, high := 0, abs(dividend)
	if dividend == 0 {
		return 0
	}
	if divisor == 1 {
		return dividend
	}
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	if dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0 {
		sign = 1
	}
	if dividend > math.MaxInt32 {
		dividend = math.MaxInt32
	}
	// 如果把递归改成非递归，可以改成下面这段代码
	// for low <= high {
	// 	quotient := low + (high-low)>>1
	// 	if ((quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) <= abs(dividend)) || ((quotient+1)*abs(divisor) >= abs(dividend) && quotient*abs(divisor) < abs(dividend)) {
	// 		if (quotient+1)*abs(divisor) == abs(dividend) {
	// 			res = quotient + 1
	// 			break
	// 		}
	// 		res = quotient
	// 		break
	// 	}
	// 	if (quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) > abs(dividend) {
	// 		high = quotient - 1
	// 	}
	// 	if (quotient+1)*abs(divisor) < abs(dividend) && quotient*abs(divisor) < abs(dividend) {
	// 		low = quotient + 1
	// 	}
	// }
	res = binarySearchQuotient(0, abs(dividend), abs(divisor), abs(dividend))
	if res > math.MaxInt32 {
		return sign * math.MaxInt32
	}
	if res < math.MinInt32 {
		return sign * math.MinInt32
	}
	return sign * res
}

func binarySearchQuotient(low, high, val, dividend int) int {
	quotient := low + (high-low)>>1
	if ((quotient+1)*val > dividend && quotient*val <= dividend) || ((quotient+1)*val >= dividend && quotient*val < dividend) {
		if (quotient+1)*val == dividend {
			return quotient + 1
		}
		return quotient
	}
	if (quotient+1)*val > dividend && quotient*val > dividend {
		return binarySearchQuotient(low, quotient-1, val, dividend)
	}
	if (quotient+1)*val < dividend && quotient*val < dividend {
		return binarySearchQuotient(quotient+1, high, val, dividend)
	}
	return 0
}

// 解法二 非递归版的二分搜索
func divide1(divided int, divisor int) int {
	if divided == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	result := 0
	sign := -1
	if divided > 0 && divisor > 0 || divided < 0 && divisor < 0 {
		sign = 1
	}
	dvd, dvs := abs(divided), abs(divisor)
	for dvd >= dvs {
		temp := dvs
		m := 1
		for temp<<1 <= dvd {
			temp <<= 1
			m <<= 1
		}
		dvd -= temp
		result += m
	}
	return sign * result
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

package leetcode

import (
	"fmt"
	"testing"
)

type question32 struct {
	para32
	ans32
}

// para 是参数
// one 代表第一个参数
type para32 struct {
	s string
}

// ans 是答案
// one 代表第一个答案
type ans32 struct {
	one int
}

func Test_Problem32(t *testing.T) {

	qs := []question32{

		{
			para32{"(()"},
			ans32{2},
		},

		{
			para32{")()())"},
			ans32{4},
		},

		{
			para32{"()(())"},
			ans32{6},
		},

		{
			para32{"()(())))"},
			ans32{6},
		},

		{
			para32{"()(()"},
			ans32{2},
		},
	}

	fmt.Printf("------------------------Leetcode Problem 32------------------------\n")
	for _, q := range qs {
		_, p := q.ans32, q.para32
		fmt.Printf("【input】:%v    【output】:%v\n", p, longestValidParentheses(p.s))
	}
	fmt.Printf("\n\n\n")
}