剑指offer(C++)-JZ64:求1+2+3+...+n(算法-位运算)

这篇具有很好参考价值的文章主要介绍了剑指offer(C++)-JZ64:求1+2+3+...+n(算法-位运算)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

剑指offer(C++)-JZ64:求1+2+3+...+n(算法-位运算),剑指offer,算法,c++

题目描述:

求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

数据范围: 0<n≤200
进阶: 空间复杂度 O(1) ,时间复杂度O(n)

示例:

输入:

5

返回值:

15

解题思路:

本题考察位运算。两种解题思路。题目虽然是简单的求和,但因为加了许多限制条件,所以有点意思。

1)位运算递归

       利用递归,完成1到n的求和,结合与运算特性,当n为0时,&&右侧不执行,变相对递归进行了终止。

2)求和公式

       Sn=(n+1)*n/2,变形为(n*n+n)>>1,n*n用pow函数实现,规避了乘法限制,除以2用右移实现,规避了除法限制。

测试代码:

1)位运算递归

class Solution {
public:
    int Sum_Solution(int n) {
        // 与运算判断n是否为正数,若n为0,则与运算后续不执行
        n && (n += Sum_Solution(n - 1));
        return n;
    }
};

2)求和公式文章来源地址https://www.toymoban.com/news/detail-705862.html

class Solution {
public:
    int Sum_Solution(int n) {
        // Sn=(n*n+n)/2
        int result = (int(pow(n, 2)) + n) >> 1;
        return result;
    }
};

到了这里,关于剑指offer(C++)-JZ64:求1+2+3+...+n(算法-位运算)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指offer(C++)-JZ12:矩阵中的路径(算法-回溯)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 请设计一个函数,用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以

    2024年02月11日
    浏览(45)
  • 剑指offer(C++)-JZ13:机器人的运动范围(算法-回溯)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,

    2024年02月12日
    浏览(47)
  • 剑指offer(C++)-JZ63:买卖股票的最好时机(一)(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一

    2024年02月04日
    浏览(41)
  • 剑指offer(C++)-JZ46:把数字翻译成字符串(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 有一种将字母编码成数字的方式:\\\'a\\\'-1, \\\'b-2\\\', ... , \\\'z-26\\\'。 现在给一串数字,返回有多少种可能的译码结果 数据范围:字符串长度满足 0n≤90 进阶:空间复杂度

    2024年02月07日
    浏览(47)
  • 剑指offer(C++)-JZ48:最长不含重复字符的子字符串(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围:  s.length≤40000 s.length≤40000 示例: 输入: 返回值: 说明

    2024年02月06日
    浏览(59)
  • 《剑指offer》(5)搜索算法、位运算、模拟

    方法一: class Solution:     def GetNumberOfK(self , nums: List[int], k: int) - int:         #从两边开始找,找到之后记录当前位置         left = 0         right = len(nums) - 1         if k not in nums:             return 0         start = len(nums) - 1         end = 0         while left = right:      

    2024年02月14日
    浏览(80)
  • 剑指offer--JZ6 从尾到头打印链表

    我写不出来,参考别人的代码后理清思路后再写的C语言版本,代码如下: 最难理解的是创建结果数组那里。我竟然不知道有这种语法。我看了老半天。malloc动态申请的内存可以看作数组使用,而且能使用数组的方式来访问元素。 大致讲解下整体思路: 1.创建一个头结点hea

    2024年02月11日
    浏览(54)
  • 每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等&递归)

    求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等及条件判断语句(A?B:C)。 1 = n = 10000 使用递归,我们马上的想法是: 或者: 但是题目要求不能出现if、A?B:C这样的,所以,我们只能直接返回什么东西。返回什么?返回n。只不过n要进行自加

    2024年02月12日
    浏览(51)
  • 【LeetCode】剑指 Offer 64. 求1+2+…+n p307 -- Java Version

    题目链接 :https://leetcode.cn/problems/qiu-12n-lcof/ 求 1+2+...+n ,要求不能使用 乘除法 、 for 、 while 、 if 、 else 、 switch 、 case 等及 条件判断语句 (A?B:C)。 【测试用例】: 【条件约束】: 时间复杂度 O(n),空间复杂度 O(n) 【 解题思路 】: 关于求 1+ 2 + 3 + … + n的解法有很

    2023年04月22日
    浏览(66)
  • 剑指 Offer 56 - II. 数组中数字出现的次数 II(位运算 / 哈希表 / 排序)

    链接:剑指 Offer 56 - II. 数组中数字出现的次数 II 难度:中等 在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。 示例 1: 输入:nums = [3,4,3,3] 输出:4 示例 2: 输入:nums = [9,1,7,9,7,9,7] 输出:1 限制: 1 = nums.length = 10000 1

    2024年02月13日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包