2021-03-28:定义一种数:可以表示成若干(数量>1)连续正数和的数 。比如:5 = 2+3,5就是这样的数 ;12 = 3+4+5,12就是这样的数 。1不是这样的数,因为要求数量大于1个、连续正数和 。2 = 1 + 1,2也不是,因为等号右边不是连续正数 。给定一个参数N,返回是不是可以表示成若干连续正数和的数 。

福大大 答案2021-03-28:

1.自然智慧。
滑动窗口。中点到1。L左移,和增大;R左移,和减小。如果和=N,成立。

2.根据结果反推,找规律。
N是2次幂,不能表示成连续正数和;N不是2次幂,是连续正数和的数。

代码用golang编写。代码如下:

package main

import "fmt"

func main() {
    for i := 1; i <= 64; i++ {
        fmt.Println(i, isMSum1(i), isMSum2(i))
    }
}

func isMSum1(num int) bool {
    if num == 1 {
        return false
    }
    R := (num + 1) >> 1
    L := R - 1
    sum := R
    for {
        if sum == num {
            return true
        } else if sum > num {
            sum -= R
            R--
        } else {
            if L == 0 {
                break
            }
            sum += L
            L--

        }
    }
    return false
}
func isMSum2(num int) bool {
    return num != (num & (^num + 1))
    //return num != (num & (-num))

    //return (num & (num - 1)) != 0
}

执行结果如下:
图片


左神java代码
评论