剑指offer-47、求1+2+3...+n
<h2 id="题描述">题⽬描述</h2><p>求 1+2+3+...+n ，要求不能使⽤乘除法、 for 、 while 、 if 、 else 、 switch 、 case 等关键字及条件判断语句（ A?B:C ）。</p>
<p>示例<br>
输⼊：5<br>
输出：15</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="用for循环">用for循环</h3>
<p>这个问题，如果直接使⽤ for 循环，超级简单，重拳出击，时间复杂度为 O(n) 。代码如下：</p>
<pre><code class="language-java">public class Solution {
public int Sum_Solution(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
}
</code></pre>
<p>可是上⾯的明显违反了使⽤for 循环的原则</p>
<h3 id="乘除法">乘除法</h3>
<p>试试公式法， 1+2+3+...+(n-1)+n = n * (n+1)/2 ,</p>
<pre><code class="language-java">public class Solution {
public int Sum_Solution(int n) {
if (n >= 0) {
return n * (n + 1) / 2;
}
return 0;
}
}
</code></pre>
<p>但是上⾯的做法，同样是使⽤乘法，也违反了原则，那么要不使⽤循环，也不适⽤乘法，怎么做呢？</p>
<h3 id="递归">递归</h3>
<p>递归可以模拟出循环，⼏乎所有的for 循环操作，都可以以递归的⽅式实现。每⼀次递归，我们让n 减少1 ，直到减少为0 。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505181432794.png" alt="" loading="lazy"></p>
<pre><code class="language-java">public class Solution {
public int Sum_Solution(int n) {
if (n >= 0) {
return n + Sum_Solution(n - 1);
}
return 0;
}
}
</code></pre>
<ul>
<li>时间复杂度为O(n)</li>
<li>空间复杂度也是O(n)</li>
</ul>
<h3 id="位运算乘法">位运算乘法</h3>
<p>位运算乘法法：通过位运算实现乘法操作</p>
<p>思路：将n(n+1)用位运算实现，然后右移1位代替除以2</p>
<pre><code class="language-java">public class Solution {
public int sum(int n) {
// 计算n*(n+1) using bit manipulation
int result = multiply(n, n + 1);
// 右移1位相当于除以2
return result >> 1;
}
/**
* 位运算实现乘法：利用俄罗斯农民算法
* 原理：a * b = (a << i)的和，其中i对应b中为1的位
*/
private int multiply(int a, int b) {
int result = 0;
// 当a不为0时继续循环
while (a != 0) {
// 如果a的最低位是1，则加上对应的b值
if ((a & 1) != 0) {
result += b;
}
// a右移1位，b左移1位
a >>= 1;
b <<= 1;
}
return result;
}
// 无循环的位运算乘法版本（符合要求）
public int sumNoLoop(int n) {
int res = multi(n, n + 1);
return res >> 1;
}
private int multi(int a, int b) {
int res = 0;
// 通过多个位判断代替循环
res += ((a & 1) == 1) ? b : 0;
a >>= 1;
b <<= 1;
res += ((a & 1) == 1) ? b : 0;
a >>= 1;
b <<= 1;
// 继续处理更多位...（根据n的范围确定需要处理的位数）
return res;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(log n) - 取决于数字的位数</li>
<li>空间复杂度：O(1)</li>
</ul>
<p>案例解析：</p>
<pre><code class="language-text">计算 13 × 9:
13 = 1101(二进制)
9 = 1001(二进制)
13 × 9 = 13 × (1 + 0 + 0 + 1) 按位展开
= (13<<0) + (13<<3) 对应9中为1的位
= 13 + 104 = 117
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19316198
頁:
[1]