精华内容
下载资源
问答
  • 给定一个正整数的数组和一个数sum,数组抽取n个数相加等于sum,找出所有的可能,也可能无解。 每个数有两种状态取和不取,用0,1表示,数组数字的组合可能有就 2**(length-1)种,如果是暴利破解就是2**length -1 ...

    给定一个正整数的数组和一个数sum,在数组抽取n个数相加等于sum,找出所有的可能,也可能无解。

    每个数有两种状态取和不取,用0,1表示,数组中数字的组合可能有就 2**(length-1)种,如果是暴利破解就是2**length -1 次计算。

    想想可以优化一下,求和的话可以先把数组排序,找到数组中比sum小的那一项a,然后用sum减去a得到b,那么可以看成是在a后面那一截数组中找到相加等于b的组合,依次这样递归下去。具体实现如下:

     

    const array = [1,2,3,4,5,6,10,9,7,11,23];
    const sum = 30;
    array.sort(function(a,b){
    return a-b;
    })
    
    console.log(array)
    const resultArray = [];
    
    function count(array,sum)
    {
    var length = array.length;
    if(array[0]>sum)
    {
    return false; 
    }
    else if(array.indexOf(sum)!=-1)
    {
    resultArray.push(sum);
    console.log(resultArray);
    resultArray.pop();
    
    }
    else{
    
    for(var i=length-1;i>=0;i--)
    { 
    if(array[i]<sum)
    {
    resultArray.push(array[i]);
    count(array.slice(0,i),sum-array[i])
    resultArray.pop();	
    }
    }
    
    } 
    }
    
    count(array,sum);
    

      

    结果是

    [ 23, 7 ]
    [ 11, 10, 9 ]
    [ 11, 9, 7, 3 ]
    [ 11, 9, 6, 4 ]
    [ 11, 9, 5, 4, 1 ]
    [ 11, 9, 5, 3, 2 ]
    [ 11, 9, 4, 3, 2, 1 ]
    [ 11, 7, 6, 5, 1 ]
    [ 11, 7, 6, 4, 2 ]
    [ 11, 7, 6, 3, 2, 1 ]
    [ 11, 7, 5, 4, 3 ]
    [ 11, 6, 5, 4, 3, 1 ]
    [ 10, 9, 7, 4 ]
    [ 10, 9, 6, 5 ]
    [ 10, 9, 5, 4, 2 ]
    [ 10, 9, 5, 3, 2, 1 ]
    [ 10, 7, 6, 5, 2 ]
    [ 10, 7, 6, 4, 3 ]
    [ 10, 7, 5, 4, 3, 1 ]
    [ 10, 6, 5, 4, 3, 2 ]
    [ 9, 7, 6, 5, 3 ]
    [ 9, 7, 6, 4, 3, 1 ]
    [ 9, 7, 5, 4, 3, 2 ]
    [ 9, 6, 5, 4, 3, 2, 1 ]

    转载于:https://www.cnblogs.com/chillaxyw/p/10633007.html

    展开全文
  • 整数相加

    2018-03-21 22:09:53
    C++ 大整数相加代码 C++ 大整数相加代码 C++ 大整数相加代码
  • 昨天碰到有人问起一个题目:1~500这500个整数中,找出连续相加等于500的数?

    昨天碰到有人问起一个题目:在1~500这500个整数中,找出连续相加等于500的数?

    其实这是一道很简单的面试题。为什么有人偏偏不喜欢自己解决呢?我想,最重要的是很多人不喜欢动脑动手。得罪很多人了啊。呵呵。

    简要分析:int[] X={1,2,i,…………499}

    条件是:i+(i+1)+ ……+(i+k)=500                                       (1式)

    运用等差数列求和公式:(k+1)*i+(k+1)*k/2=500                  (2式)

    其中i和k还有一个隐藏关系i*k<500                                       (3式)

    于是很自然得到如下解法:

    得出结果:

    xi=8;9;10;11;12;13;14;15;16;17;18;19;20;21;22;23;24;25;26;27;28;29;30;31;32
    xi=59;60;61;62;63;64;65;66
    xi=98;99;100;101;102

     

    eaglet 提出,该算法性能不佳,参照他的算法,修改如下:

     

    另外根据条件,

    (k+1)k<2*maxInt,可以得出(k+1)(k+1)<2*maxInt           (4式)

    可以提出连续的最多整数为32,故也可以得如下算法:

    邀月注:本文版权由邀月和CSDN共同所有,转载请注明出处。
    助人等于自助!   3w@live.cn
    
    
    展开全文
  • 最近碰到一道笔试题,是说一个int数组和一个数X,问以最优方案找出int数组是否有两个数相加等于X? 刚看到这道题时有点儿懵圈儿,后来经过网上看博客和自己思考终于有思路了,下边上代码

    最近碰到一道笔试题,是说一个int数组和一个数X,问以最优方案找出int数组中是否有两个数相加等于X?
    刚看到这道题时有点儿懵圈儿,后来经过网上看博客和自己思考终于有思路了,下边上代码

    MainActivity

    package com.example.cyy.work_resume_project;
    
    import android.support.v7.app.AppCompatActivity;
    import android.os.Bundle;
    import android.util.Log;
    import android.widget.TextView;
    import java.util.Arrays;
    
    public class MainActivity extends AppCompatActivity {
        private final String TAG = "MainActivity";
        private int[] mNums;
        //目标数
        private int mTarget;
        //显示的结果
        private String mStrResult;
        private TextView mTvShowResult;
    
        @Override
        protected void onCreate(Bundle savedInstanceState) {
            super.onCreate(savedInstanceState);
            setContentView(R.layout.activity_main);
            //初始化view
            initView();
            //初始化数据
            initData();
            //检测数组nums中是否存在两个数相加等于target
            Log.i(TAG, "原始方法前,系统当前时间为:" + System.currentTimeMillis());
            isTwoSumToTargerOld(mNums, mTarget);
            Log.i(TAG, "原始方法后,系统当前时间为:" + System.currentTimeMillis());
            Log.i(TAG, "优化方法前,系统当前时间为:" + System.currentTimeMillis());
            isTwoSumToTarger(mNums, mTarget);
            Log.i(TAG, "优化方法后,系统当前时间为:" + System.currentTimeMillis());
            //显示结果
            showResult();
        }
    
        private void initView(){
            mTvShowResult = (TextView) findViewById(R.id.tv_show_result);
        }
    
        private void initData(){
            mNums = new int[]{1, 19, 21, 16, 13, 9, 17, 3, 5, 7, 6, 12, 35, 36};
            mTarget = 18;
        }
    
        /**
         * 需求:检测一个int数组中是否存在两个数相加等于某个指定的数
         *
         * 思路:
         * (1)对int数组进行升序排序
         * (2)如果按照最原始的思路是双层循环,即固定住第一个数,第二个数依次往后循环,然后再固定住第二个数,依此类推,这样最多可能会进行2n(n代表数组的长度)次判断,显然不是最优方案,不妨换个思路,
         * 既然是升序排列,可以首尾相加,如果>target则把最大数往前移位,还大继续往前移位,相反<target则把最小数往后移位,直到这两个数重合,最多进行n次判断,这样做简化了判断次数。
         * @param nums
         * @param target
         * @return
         */
         private String isTwoSumToTargerOld(int[] nums, int target){
            if(nums.length >= 2){
                for(int i = 0; i < nums.length - 1; i++){
                    for(int j = i + 1; j < nums.length; j++){
                        if(nums[i] + nums[j] == target){
                            mStrResult = "nums存在两个数相加等于目标值\n第一个数=" + nums[i] + "\n第二个数=" + nums[j] + "\ntarget=" + target;
                            return mStrResult;
                        }
                    }
                }
            }
            mStrResult = "nums中不存在这样的两个数";
            return mStrResult;
        }
    
        private String isTwoSumToTarger(int[] nums, int target){
            //排序int数组
            Arrays.sort(nums);
            if(nums.length >= 2){
                //i是第一个数的下标索引,j是第二个数的下标索引
                int i = 0, j = nums.length - 1;
                //循环条件,i != j,直到i和j相等了再跳出循环
                while(i != j) {
                    int sum = nums[i] + nums[j];
                    //如果两个数的和大于目标值则最大值前移减小整体值,如果小于目标值则最小值后移增大整体值,如果等于目标值则说明int数组已经存在这样的两个数可以结束循环。
                    if (sum > target) {
                        j--;
                    } else if (sum < target){
                        i++;
                    } else{
                        mStrResult = "nums存在两个数相加等于目标值\n第一个数=" + nums[i] + "\n第二个数=" + nums[j] + "\ntarget=" + target;
                        return mStrResult;
                    }
                }
            }
            mStrResult = "nums中不存在这样的两个数";
            return mStrResult;
        }
    
        private void showResult(){
            mTvShowResult.setText(mStrResult);
        }
    }
    

    activity_main

    <?xml version="1.0" encoding="utf-8"?>
    <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
        xmlns:tools="http://schemas.android.com/tools"
        android:id="@+id/activity_main"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:paddingBottom="@dimen/activity_vertical_margin"
        android:paddingLeft="@dimen/activity_horizontal_margin"
        android:paddingRight="@dimen/activity_horizontal_margin"
        android:paddingTop="@dimen/activity_vertical_margin"
        tools:context="com.example.cyy.work_resume_project.MainActivity">
    
        <TextView
            android:id="@+id/tv_show_result"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:text="Hello World!" />
    </RelativeLayout>

    运行后效果如下图:
    这里写图片描述

    打印Log如下图:
    这里写图片描述

    如果两种方式打印时间都是相同的,可以多向int数组中添加一些数据就可以看出差别

    展开全文
  • 给定一个整数数组,找出其中两个数相加等于目标值  例如:给定数组及目标值 nums = [2,7,11,15] ,target = 9  因为nums[0] + nums[1] = 2 + 7 = 9  返回[0,1] /** * 使用辅助空间(使用哈希表,时间复杂度是O...

    给定一个整数数组,找出其中两个数相加等于目标值 
    例如:给定数组及目标值 nums = [2,7,11,15] ,target = 9 
    因为nums[0] + nums[1] = 2 + 7 = 9 
    返回[0,1]

    /**
         * 使用辅助空间(使用哈希表,时间复杂度是O(n),空间复杂度:O(n),n是数组大小)
         * @param nums
         * @param target
         * @return 没有找到的话数组中数值就是{-1,-1},否则找到,其实我想返回null的,但是觉得返回null不礼貌,因为null有毒
         */
        public static int[] findTwo3(int[] nums, int target)
        {
            // 结果数组
            int[] result={-1,-1};
            // 目标是数组下标,所以键值对为<数值,数值对应数组下标>,这里要说一下,哈希表的查找的时间复杂度是O(1)
            HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
            // 1.扫描一遍数组,加入哈希表,时间复杂度是O(n)
            for(int i=0;i<nums.length;i++)
            {
                map.put(nums[i], i);
            }
            // 2.第二次扫描,目标值-当前值,差值作为key,看看map里有木有,没有就下一个循环,直到数组扫描完毕或找到value,所以最坏情况的时间复杂度是O(n)
            for(int i=0;i<nums.length;i++)
            {
                // 得到第二个数的值
                int two=target-nums[i];
                // 如果存在第二个数的数组下标&&结果的两个数不是同一个数的值
                if(map.containsKey(two)&&target!=2*two)
                {
                    result[0]=i;
                    result[1]=map.get(two);
                    // 返回找到的两个数的数组下标
                    return result;
                }
            }
            // 没有找到
            return result;
        }
       
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    展开全文
  • 这是一个可以让C语言实现2个超大整数相加的程序,会给你设计C程序时有一定的启发!
  • 请用java实现输入一个正整数n,输出以下格式,全部连续正整数相加等于n的所有序列。 例如: 15=1+2+3+4+5; 15=4+5+6; 15=7+8; 我从网上文章得到的思路,进行了自己的想法的修改,代码如下:public ...
  • * 有集合N={1,2,3……,n},求a1+a2+……+an=m(ai属于N不等于0,i=1,2,……n)的所有组合,m,n都是自然数 */ public static void func1(int n, int m, int k, int door){ if(n>m) n = m; if(m==1&&m>=k){ System.out....
  • C语言,我们最常见的是整型与整型的相加,这里所说的整型都是带有符号的整数。 比如: 2+2 = 4; -1+5 = 4; 他们的类型都是int,即signed int,只不过我们写代码时为了人为的方便而把signed给省略掉了。 ...
  • C语言整数相加

    千次阅读 2018-03-09 13:08:57
    实现两个整数相加:#include &lt;stdio.h&gt;int main(){ int a; int b; printf("请输入两个整数:"); scanf("%d %d", &amp;a, &amp;b); printf("%d + %d = %d\n", a...
  • C++大整数相加

    千次阅读 2017-12-15 19:40:55
    C++大整数相加算法,采用数组保存大整数,然后进行大整数相加。#include #include char *LongAdd(char *b, char *c); int main() { int a,n,i; char *b=new char[1000]; char *c=new char[1000]; scanf("%d",
  • 给定一个整数数组,找出其中两个数相加等于目标值 例如:给定数组及目标值 nums = [2,7,11,15] ,target = 9 因为nums[0] + nums[1] = 2 + 7 = 9 返回[0,1] 利用HashMap private int[] findData(int[] array,int...
  • 任意位整数相加

    2012-06-01 20:48:35
    描述 ...每组数据有两个整数。范围 -231 ~ +231-1 之内。 输出 对每组数据,输出对应的a+b的和。范围 -231 ~ +231-1 之内。 样例输入 2 1 2 3 1 样例输出 3 4 用得比较多,分享一下~
  • C++之整数相加

    千次阅读 2018-09-05 22:34:59
    请设计一个算法能够完成两个用字符串存储的整数进行相加操作,对非法的输入则返回error 输入描述: 输入为一行,包含两个字符串,字符串的长度[1,100]。 输出描述: 输出为一行。合法情况输出相加结果,...
  • 求N个整数的平均值(注意N可能很大,N个数直接相加会造成整数溢出) 分析 这样显然不能直接相加。那么可以每个数先除以N,再将N个数相加。但是由于计算机整数相除的会舍去小数部分,那么我们可以用一个变量保存余数...
  • Java实现整数相加

    2019-09-21 00:36:45
    java实现整数相加,难点就是将字符转化为数字。这里只要解决这个问题就可以很简单的完成整个实验。利用:Scannerinput=newSc(System.in);inta=input.nextInt();这两句代码就可以实现将输入的字符转化为整数。...
  • 自己用C++写的一个整数相加相乘的控制台程序,用字符串来实现任意位数的整数之间的相加和相乘,通过string和int的相互转化达到我们正常计算时候的过程,不受整型规定字节数的影响,刚兴趣的朋友可以参考,有什么问题...
  • /* ...* All rights reserved. * 作 者:王颖 * 完成日期:2014 年 2 月 16 日 ...* 问题描述:输入一个整数,输出所有相加等于这个数的算式 * 程序输出:略 * 问题分析:略 * 算法设计:略 */ #include using namespac
  • 主要介绍了java超过long范围的超大整数相加算法(面试高频),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下
  • 给定一个数t,以及n个整数这n个整数中找到相加之和为t的所有组合,例如t = 4,n = 6,这6个数为[4, 3, 2, 2, 1, 1],这样输出就有4个不同的组合,它们的相加之和为4:4, 3+1, 2+2, and 2+1+1。请设计一个高效...
  • 特大整数相加

    千次阅读 2014-09-28 02:08:49
    一,特大整数描述  int和long作为基本的整数类型,取值范围和位数直接相关。如果是n位整数的话,最高位表示符号位,剩下的n-1位以补码形式表示绝对值,因此范围是整数区间[-2^(n-1),2^(n-1))。int和long并没有...
  • 杭州电子科技大学hdoj1002,大整数相加问题
  • 整数相加,计算两个非负整数的和,可以精确计算2的100次方,杨辉三角第100行等问题。
  • 无限大整数相加

    2012-12-01 12:17:56
    本程序的功能是实现无限大的2个整数相加或者相减,供编程初学者参考
  • 由于整数过大,不能一次完成相加,我们猜想能否将两个整数存储到数组,然后逐位相加。当然,这里实现的方法就是基于此。代码如下 public class bigIntegerSum { //两个大整数相加,这里将两个整数分别存储到...
  • C++语言实现长整数相加

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,459
精华内容 58,183
关键字:

在相加等于15的整数中