剑指offer系列之四十六:求1到n的和

题目描述

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

如果不能使用上面的操作,那么只能使用递归操作了。使用递归操作的思路是让函数不断调用自己,每调用一次值就减少1,这样完成了递归操作。还有一个问题是如何实现n范围的判断呢?注意到递归调用的n的值最小是1,所以可以通过逻辑与运算,判断是否递归到1。如果递归调用到1,那么递归就结束,并返回最后的结果。下面是这样思路的实现代码(已被牛客AC):

package com.rhwayfun.offer;

public class SumOfN {

    private int result = 0;

    public int Sum_Solution(int n) {
        calc(n);
        return result;
    }

    private boolean calc(int n) {
        result += n;
        return n != 0 && calc(n - 1);
    }

    public static void main(String[] args) {
        int res = new SumOfN().Sum_Solution(10);
        System.out.println(res);
    }
}
时间: 2024-12-24 21:59:32

剑指offer系列之四十六:求1到n的和的相关文章

剑指offer系列之四十二:约瑟夫环问题

题目描述 每年六一儿童节,NowCoder都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此.HF作为NowCoder的资深元老,自然也准备了一些小游戏.其中,有个游戏是这样的:首先,让小朋友们围成一个大圈.然后,他随机指定一个数m,让编号为0的小朋友开始报数.每次喊到m的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0-m-1报数-.这样下去-.直到剩下最后一个小朋友,可以不用表演,并且拿到NowCoder名贵的"名侦探柯南"

剑指offer系列之四十八:把字符串转成整数

题目描述 将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数 这里的关键是要对输入的字符串进行全面的考虑.包括字符串是否有效的判断.是否是负数以及字符串表示的整数是否越界等问题.对于字符串有效性的判断主要是null以及空串的判定:负数之所以需要判断是因为在计算的时候是有用的:而是否越界的问题也是需要考虑的.因为一个越界的数是不可能计算出来的,那么这时候可以简单返回一个0,表示越界的数.这三点都考虑之后,整体代码的健壮性就比较好了.下面是这种思路的实现代码(已被牛客AC),详细的已经在

剑指offer系列之三十六:数字在排序数组中出现的次数

题目描述 统计一个数字在排序数组中出现的次数. 因为是排序数组,自然联想到二分查找算法,这样我们在二分的时候可能会获取多个相同的数字.就是说,中间那个位置的值可能刚好是统计的那个值,假设为k.那么k还有可能在前面或者后面出现,在这个基础上继续二分当然也是可以的,如果能够在使用二分查找算法的时候统计出第一个k和最后一个k出现的位置,那么k出现的次数自然就确定了.第一个k出现的位置,可以使用二分查找算法,如果中间位置的值刚好是k,那么继续比较中间位置前面位置的值是不是也是k,如果不是那么该中间位置就

剑指offer系列之十六:树的子结构

题目描述 输入两颗二叉树A,B,判断B是不是A的子结构. 这实际上二叉树遍历算法的一种应用,要在原二叉树中查找是否具有某课子树,只需要判断每个节点是否都在二叉树中是否出现即可.所以需要先判断头结点,只有头结点符合要求才继续比较其子树是否符合,一样依次从头结点开始比较直到其左右子树进行比较,如果都符合则说明B是A的子结构.下面是基于这种思路实现的代码(已被牛客AC): package com.rhwayfun.offer; public class SubTree { public class T

剑指offer系列之四十:和为S的连续正数序列

题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100.但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数).没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22.现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! 输出描述: 输出所有和为S的连续正数序列.序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序 此题的思路是:设定两个指针,一个指向第一个

剑指offer系列之四十九:数组中重复的数字

题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内. 数组中某些数字是重复的,但不知道有几个数字是重复的.也不知道每个数字重复几次.请找出数组中任意一个重复的数字. 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3. 此题的思路还是比较简单的,与之前找出只出现一次的数字的题目有些类似,基本思路还是创建一个Map容器,key是出现的数字,value则是该数字出现的次数.在遍历数组的过程中,只要容器中已经出现了该数字,那么就直接返回给数组,

剑指offer系列之四十四:翻转单词顺序

题目描述 牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上.同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思.例如,"student. a am I".后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是"I am a student.".Cat对一一的翻转这些单词顺序可不在行,你能帮助他么? 可以发现,要对一个句子进行翻转,可以先对整个句子进行翻转,之后再对每个单词进行翻转.而不论是返

剑指offer系列之四十五:左旋转字符串

题目描述 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果.对于一个给定的字符序列S,请你把其循环左移K位后的序列输出.例如,字符序列S="abcXYZdef",要求输出循环左移3位后的结果,即"XYZdefabc".是不是很简单?OK,搞定它! 同上一题思路差不多,可以把需要左旋的字符串看成一部分,其他的字符串看成另一部分,比如字符串"abcdef",需要输出左移2位的结果,可以把字符串&q

剑指offer系列之五十六:对称二叉树的判断

题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 前面有一题是打印输出某二叉树的镜像,回想其实现的思路是:采用层序遍历的思路对每一个遍历的节点,如果其有孩子节点,那么就交换两者.直到遍历的节点没有孩子节点为止,然而此题是对二叉树木镜像的判断,明显是更简单的,只需要进行两个判断:对节点的左孩子与其兄弟节点右孩子的判断以及对节点右孩子与其兄弟节点左孩子的判断.这样就完成对对一棵二叉树是否对称的判断.下面是具体的实现代码(已被牛客