$\it{***方法一***}$
思路:
利用递归
+位运算
,定义一个成员变量ans记录结果,递归函数时ans的值也实时更新,直至返回到最后一处
要点:
1.短路与&&
、短路或||
的短路作用:
短路与只要左侧表达式为假,就不会执行右侧表达式,若左侧表达式为真,则还会执行右侧表达式;短路或只要左侧表达式为真,就不会执行右侧表达式,若左侧表达式为假,则还会执行右侧表达式。
2.位运算左右侧必须是表达式
,不能是语句
(如return语句)
3.位运算的结果是1或0
代码:
class Solution {
public:
int ans;//记录运算结果
int getSum(int n) {
n>0&&(ans+=n);//若n>0,每一层函数都加上当前n值
return (!n||getSum(n-1))+ans-1;
}
};
$\it{优化:}\rm{(y’)}$
定义一个变量res值为n,若当前递归的函数参数n大于0,则加上下一递归函数的返回值,边界为n==0,返回值为res
class Solution {
public:
int getSum(int n) {
int res=n;
n>0&&(res+=getSum(n-1));
return res;
}
};
$\it{***方法二***}$
思路:使用数学公式$1+2+···+n=\dfrac{n·(n+1)}{2}$,巧妙之处在于定义数组char a[n][n+1],利用sizeof
求出n·(n+1),利用右移位运算>>
求出除以2的结果
要点:
1.乘法可以通过sizeof多维字符数组
实现
2.乘/除以$2^n$可以通过左/右移位运算符
实现
代码:
class Solution {
public:
int getSum(int n) {
char a[n][n+1];
return (sizeof a)>>1;
}
};