题目描述
求 1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 (A?B:C)。
数据范围
1≤n≤50000。
思路
等差数列求和n*(n+1)/2,由于不能使用乘除法,考虑将除法变为位运算(÷2相当于>>1)
对于n(n+1),一个长 n 宽为 m 的二维矩阵的大小为 n×m,
因此构建一个长为n,宽为n+1的二维矩阵,它的面积为n(n+1) [char所占字节为1,int占4个字节]
C++ 代码
class Solution {
public:
int getSum(int n) {
<!--int a[n][n+1];-->
<!--return sizeof(a)>>3;-->
char a[n][n+1];
return sizeof(a)>>1;
}
};