html5网站开发趋势,企业建站官网运营,jspajax网站开发典型实例,山东建设官方网站306. 累加数
题目描述#xff1a; 累加数 是一个字符串#xff0c;组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外#xff0c;序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 ‘0’-‘9’ 的字…306. 累加数
题目描述 累加数 是一个字符串组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 ‘0’-‘9’ 的字符串编写一个算法来判断给定输入是否是 累加数 。如果是返回 true 否则返回 false 。
说明累加序列里的数除数字 0 之外不会 以 0 开头所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
考察重点判断一个字符串是否符合前两个之和为第三个数 F(n)F(n - 1)F(n - 2)。我们使用go语言中的strconv是否报错来判断数字是否越界之后只需确定起始的两个数字AB并找到是否存在CAB,如果没有则跳出(使用AB两数的位数确定C的位数在max(A,B)与max(A,B)1之间)有则执行AB,BC,继续向后遍历。
func isLegal(a, b, c int) bool {return c-a b
}
func max1(a, b int) int {if a b {return a}return b
}
func IsAdditiveNumber(num string) bool {numA, numB, numC, lenA, lenB, lenC : 0, 0, 0, 0, 0, 0var err error/**本题最关键是找到前两个数用num[0:i]和num[i:j1]分别表示前两个数lenA, lenB记录这两个数长度则numC的长度lenC必然等于max(lenA,lenB)或者max(lenA,lenB)1*/for i : 1; i len(num); i {if numA, err strconv.Atoi(num[0:i]); err ! nil || (i ! 1 num[0] 0) { //求numAcontinue}tt : numAfor j : i 1; j len(num); j {if numB, err strconv.Atoi(num[i:j]); err ! nil || (j ! i1 num[i] 0) {//求numBcontinue}numA, lenA, lenB tt, i-0, j-ilenC max1(lenA, lenB)start, end : j, jlenC //记录numAnumB的长度同时numC只可能在num[j:jmax(lenA,lenB)] 与 num[j:jmax(lenA,lenB)1] 之中for end len(num) { //**********************************************************************************************************if numC, err strconv.Atoi(num[start:end]); err ! nil || (end ! start1 num[start] 0) { //如果num[start:end]大于MAXINT直接breakbreak}lenC end - startif !isLegal(numA, numB, numC) { //num[start:end]!numAnumB 则继续判断num[start:end1]if end1 len(num) {break}if numC, err strconv.Atoi(num[start : end1]); err ! nil || (end1 ! start1 num[start] 0) {break}if !isLegal(numA, numB, numC) {break}lenC lenC 1end end 1 //num[start:end1]numAnumB 则更新lenC和end的大小}//**********************************************************************************************************if end len(num) { //end等于len(num)且num[start:end]numAnumB说明该string满足条件return true}numA, numB, lenA, lenB numB, numC, lenB, lenC //numA,numB整体向后lenCstartend重新记录新的numC可能的取值范围lenC max1(lenA, lenB)start, end end, endlenC}}}return false
}
