精华内容
下载资源
问答
  • 今天复习了一下C语言的数组部分,练习了数组元素求和与冒泡排序。

    今天复习了一下C语言的数组部分。

    练习了数组元素的求和与冒泡排序。主要内容就是 C语言中函数的声明和调用,数组的表示,还有数组长度的求法。

    其中,数组长度的求法用sizeof()函数,用数组占内存总空间,除以单个元素占内存空间大小,即可求出数组长度。

    此外,冒泡排序主要是运用for循环,来达到依次比较的目的,将数组中较大的元素逐渐“浮到”最上层。


    代码如下:

    #include<stdio.h>
    
    int array_sum(int array[],int n);
    void paopao(int array1[],int n);
    
    int main()
    {
    	int data[] = {2,7,9,10,45,15,38};
    
    	int size = sizeof(data)/sizeof(data[0]);     //求数组长度
    
    	printf("求和结果是:%d\n",array_sum(data,size));
       printf("\n");
        paopao(data,size);
    	return 0;
    }
    
    
    int array_sum(int array[],int n)                   //求和函数
    {
    	int sum=0;
    	for(int i=0;i<n;i++)
    	{
    		sum+=array[i];
    	}
    	return sum;
    }
    
    void paopao(int array1[],int n)                  //冒泡排序函数
    {
         int temp=0;
         for(int i=0;i<n-1;i++)
    		 for(int j=0;j<n-1-i;j++)
    		 {
               if(array1[j]>array1[j+1])
    		   {
    			   temp=array1[j];
    			   array1[j]=array1[j+1];
    			   array1[j+1]=temp;
    		   }
    		 }
      printf("冒泡排序结果是: ");
      for(int k=0;k<n;k++)
      {
    	  printf("%d ",array1[k]);
      }
      printf("\n");
    }



    展开全文
  • 分治算法题之数组元素求和

    千次阅读 2013-03-19 23:38:26
    题目只是给出个元素求和一个特例,我们可以把题目定义的更宽泛些。给定一个连续的自然数数组a(a[i]>0,a.length>0),求所有数据元素的加法运算,使得其和等于另一个给定的整数数值m (m>0)。  这是个分治算法的场景...

            前几天逛论坛,看到一个帖子里说到一个算法题目: 给出1到19的连续递增自然数数组,求所有和为20的可能元素加法组合。每个加法组合中的元素不能重复使用。 题目只是给出个元素求和一个特例,我们可以把题目定义的更宽泛些。给定一个连续的自然数数组a(a[i]>0,a.length>0),求所有数据元素的加法运算,使得其和等于另一个给定的整数数值m (m>0)。

            这是个分治算法的场景,题目的出发点如下

    • 得到给定的m,可能要通过多步加法运算得到。一次性得出结果往往很难。但我们可以将加法步骤进行拆分,每次拆分可以穷举出所有的可能排列。比如m=10,那么两步加法得到10的排列会有几种? 很明显 [0,10],[1,9],[2,8],[3,7],[4,6],[5,5],[6,4],[7,3],[8,2],[9,1],[10,0] 就是所有的穷举结果。
    • 在每次进行步骤一的加法拆分时,可以将数组同时按照中间位置进行拆分。并将步骤一得到的加法穷举结果代入。如此递归,直至数组中只有一个元素存在。

           如下以a=[1,2,3,4,5,6,7,8,9], m=10为例对步骤进行一下说明

           1. 将m进行两步加法划分得到[0,10],[1,9],[2,8],[3,7],[4,6],[5,5],[6,4],[7,3],[8,2],[9,1],[10,0] 所有的穷举结果。

           2. 将数组从中间数进行划分得到两个子数组left = [1,2,3,4,5] ,right =[6,7,8,9],如下图所示

           3. 对所有加法组合及对应子数组进行递归拆分求解,这里以加法组合[10,0]为例进行展开,如下图示


                 如上图所示, 子数组[6,7,8,9] 求和为0的可能组合很明显根本不需要去求。我们只关心子数组[1,2,3,4,5] 求和为10的所有组合即可。那同样对10和子数组[12,3,4,5]进行同样的拆分。我们还可以继续拆分,直到数组中只有一个元素为止。但在这一步,我们直观上已经很明显能看出可能的组合结果如下图


    4. 将数组[1,2,3,4,5] = 10,和[6,7,8,9] = 0 两个数组的求解结果进行合并,就是我们所要的对于[10,0]这个加法拆分方式的结果。

    代码如下

    import java.util.Arrays;
    
    public class EqualsTeller {
    
    	/**
    	 * 将两个一维数组left[m],right[j]合并成m[m+j]数组。
    	 */
    	private int[] merge(int[] left,int[] right){
    		int[] m = new int[left.length + right.length];
    		System.arraycopy(left,0,m,0,left.length);
    		System.arraycopy(right, 0, m, left.length, right.length);
    		return m;
    	}
    	/**
    	 * 将二维数组left[m][x] 和 right[n][y]数组合并为二维数组 merge[m*n][x+y]
    	 */
    	private int[][] crossMerge(int[][] left,int[][] right){
    		
    		if (left[0][0] == 0)
    			return right;
    		if (right[0][0] == 0)
    			return left;
    		
    		int[][] m = new int[left.length * right.length][];
    		int row = 0;
    		for (int i=0;i< left.length;i++){
    			for (int j=0;j< right.length;j++){
    				int[] l = left[i];
    				int[] r = right[j];
    				m[row] = merge(l,r);
    				row++;
    			}
    		}
    		
    		return m;
    		
    		
    	}
    	
    	private int[][] appendMerge(int[][] left,int[][] right){
    		int[][] m = new int[left.length + right.length][];
    		for (int i=0;i< left.length;i++){
    			     m[i] = left[i];
    		}
    		for (int i=left.length;i< m.length;i++){
    			    m[i] = right[i - left.length];
    
    		}
    		
    		return m;
    		
    		
    	}
    	
    	
    	/**
    	 * 给定数组 a,和一个大于零的数值sum. 找出所有合计值为sum的加法运算,加法运算中所有的元素必须来自数组a,且不能重复。
    	 * @param a 给定的数组。数组中的元素必须是连续的,递增的。例如[1,2,3,4,5,6,7,8,9]
    	 * @param sum 假定的合计值。要求大于零。
    	 * @return 二维数组,含有所有可能加法组合的方案。
    	 */
    	private int[][] findEqualFormula(int[] a,int sum){
    		boolean valid_flag = false;
    		int[][] m = new int[0][0];
    		
    		if (sum == 0){ //如果传入的sum是零的话,则无需再当前数组a中寻找可能的加法解。直接返回{{0}};
    			m = new int[1][1];
    		    m[0] = new int[]{0};
    		}
    		else
            if (a.length > 1){
                if (sum < a[0]){ //小于数组中最小值,返回{{-1}}即当前数组无法得出对应的Sum值。
                	m = new int[1][1];
        		    m[0] = new int[]{-1};
                }else if (sum > (a[0] + a[a.length -1])*(a.length)/2){ //大于数组和,返回{{-1}}即当前数组无法得出对应的Sum值。
                	m = new int[1][1];
        		    m[0] = new int[]{-1};
                }else{
                 int middle = (a.length -1)/2; //取中间数,然后对数组进行左右划分。
        		 int[] left  = Arrays.copyOfRange(a, 0, middle+1);
        	     int[] right = Arrays.copyOfRange(a, middle+1, a.length);
        		 for (int i=0;i<=sum;i++){//通过for循环将Sum值得所有两步运算进行穷举。
        			int[][] la = findEqualFormula(left,i);//递归调用,直到传入的数组中只有一个元素为止
        			if (la[0][0] == -1) //如果返回{{-1}},则说明上述数组left元素无法通过加法运算得到对应的Sum值。这时,则说明当前for循环中的两步运算组合无效。忽略当前运算组合,继续下一个组合的尝试。
        				continue;
        			int[][] ra= findEqualFormula(right,sum - i);//递归调用,直到传入的数组中只有一个元素为止
                    if (ra[0][0] == -1) //如果返回{{-1}},则说明上述数组right元素无法通过加法运算得到对应的Sum值。这时,则说明当前for循环中的两步运算组合无效。忽略当前运算组合,继续下一个组合的尝试。 			
        			    continue;
                    int[][] ma = crossMerge(la,ra);//如果上述两个递归方法返回有效的元素组合,则将元素进行交叉合并,得出当前数组元素中可用的加法组合
                    m = appendMerge(m,ma);
                    valid_flag = true;
        		 }
        		 if (!valid_flag){ // 如果for循环中所有穷举的两步运算组合都不适用,则返回{{-1}}
        			 m = new int[1][1];
        			 m[0] = new int[]{-1};
        		 }
        		 
                }
    
            }else if (a.length == 1){
            	m = new int[1][1];
            	if (a[0] == sum) //如果分解到数组中只有一个元素时,如果与sum值相等,则是我们需要找的值。返回数组{{a[0]}}
            		m[0] = new int[]{a[0]};
            	else
            		m[0] = new int[]{-1};//如果分解到数组中只有一个元素时,如果与sum值不相等,则说明数组中的值无法通过求和得到我们的预期结果。返回数组{{-1}}
            }
            
         return m;   
    
    	}
    	
    }
    

    运行结果如下 以[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] = 20 为例


    1 19 
    2 18 
    3 17 
    1 2 17 
    4 16 
    1 3 16 
    5 15 
    1 4 15 
    2 3 15 
    6 14 
    1 5 14 
    2 4 14 
    1 2 3 14 
    7 13 
    1 6 13 
    2 5 13 
    3 4 13 
    1 2 4 13 
    8 12 
    1 7 12 
    2 6 12 
    3 5 12 
    1 2 5 12 
    1 3 4 12 
    9 11 
    1 8 11 
    2 7 11 
    3 6 11 
    1 2 6 11 
    4 5 11 
    1 3 5 11 
    2 3 4 11 
    1 9 10 
    2 8 10 
    3 7 10 
    3 8 9 
    1 2 7 10 
    1 2 8 9 
    4 6 10 
    4 7 9 
    1 3 6 10 
    1 3 7 9 
    5 6 9 
    5 7 8 
    1 4 6 9 
    1 4 7 8 
    2 3 6 9 
    2 3 7 8 
    1 5 6 8 
    2 4 6 8 
    1 2 3 6 8 
    2 5 6 7 
    3 4 6 7 
    1 2 4 6 7 
    1 4 5 10 
    2 3 5 10 
    1 2 3 4 10 
    2 4 5 9 
    1 2 3 5 9 
    3 4 5 8 
    1 2 4 5 8 
    1 3 4 5 7 
    2 3 4 5 6 
    


    展开全文
  • 让自己经常做些算法训练, 目前在LeetCode上面找Easy类型的做起, 俗话说柿子要挑软的捏嘛. Problem => Algorithms => Two Sum 一个非常简单的题目: 幸亏下面有Example说明, 不然我以为用两个元素的Index...

    让自己经常做些算法训练, 目前在LeetCode上面找Easy类型的做起, 俗话说柿子要挑软的捏嘛.
    一个非常简单的题目:
    在这里插入图片描述
    幸亏下面有Example说明, 不然我以为用数组中两个元素的Index相加, 尴尬⊙﹏⊙‖∣
    二话不说, 直接上双层for循环:

    public int[] twoSum(int[] nums, int target) {
            for(int i = 0; i < nums.length - 1; i ++){
                for(int j = i + 1; j < nums.length; j ++){
                    if(nums[i] + nums[j] == target) {
                        return new int[]{i, j};
                    }
                }
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    

    嗯, 说到最后面一行抛异常, 我最开始是return null, 要善用异常处理, 后面我会专门花一块时间学一下.

    看了答案, 我的解法被归类于暴力法(Brute force), 有点儿尴尬. 说实话, 虽然很久没写代码, 但是我其实觉得我的变成思想是有所提升的.

    瞄了一下第二个解法----Two-pass Hash Table

    public int[] twoSumMap(int[] nums, int target){
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for(int i = 0; i < nums.length; i ++){
                map.put(nums[i], i);
            }
            for(int i = 0; i < nums.length; i ++){
                int complement = target - nums[i];
                if(map.containsKey(complement) && map.get(complement) != i){
                    return new int[] {i, map.get(complement)};
                }
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    

    原来是用了Hash Map进行两次遍历, 豁然开朗, 第一次遍历将数组中所有的元素和下标, 以key:value的形式组装成map, 元素是key, 下标是value.
    在此遍历数组时, 用target - nums[i] 的值去map中判断, true时成功.

    两个对比一下, 第二种方法最多只是完整的遍历2次, 但是第一种方法会随着数组元素数量的增多, 而使执行时间的增长远超于第二种方法.

    这里关于时间复杂度方面就不写了, 因为不懂, 出差不方便, 等回家要啃《算法》

    另外第三种解法就更效率了-------One-pass Hash Table

    public int[] twoSumMapOneFor(int[] nums, int target){
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int i = 0; i < nums.length; i++) {
                int complement = target - nums[i];
                if(map.containsKey(complement)){
                    return new int[]{map.get(complement), i};
                }
                map.put(nums[i], i);
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    

    可以看出这段代码非常高效, 一次遍历就搞定, 并且因为实在if语句结束后才执行map的put方法, 所以不需要判断是否为同一个数组元素, 因为当前元素还没进入map中.

    总结一下, 后两种方法一看就明白, 说明并没有超出自己的能力或技术范围, 说明自己需要提升自己的经验并多做相关的训练和学习. 另外就是自己以前写代码的时候, map用的少, 所以没有第一时间想到它. 还有就是这个题目太简单了, 写文字的时间远大于写代码加思考的时间, 性价比太低, 以后这种简单的题目我就简单总结.

    展开全文
  • 但是,数组中同一个元素在答案里不能重复出现。 要求复杂度低于O(n^2),那么双重for循环就不能使用了。 使用 HashMap 可完美实现。代码如下: class Solution { public int[] twoSum(int[] nums, int target) { ...

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

    要求复杂度低于O(n^2),那么双重for循环就不能使用了。

    使用 HashMap 可完美实现。代码如下:

    class Solution {
        public int[] twoSum(int[] nums, int target) {
            HashMap<Integer, Integer> hashtable = new HashMap<>(nums.length - 1);
            for (int i = 0; i < nums.length; i++) {
                if (hashtable.containsKey(target - nums[i])) {
                    return new int[]{hashtable.get(target - nums[i]), i};
                }
                hashtable.put(nums[i], i);
            }
    
            return new int[0];
        }
    }
    

    知识点记录

    HashMap 的特点

    几种常见的数据结构有:顺序结构、链表结构、hash结构和树状结构。HashMap是 key-value 形式存储。哈希表将 key 的 Hash 值映射到内存地址,即根据 key 获取对应的值,并将其存储到内存地址。也就是说 HashMap 是根据 key 的 Hash 值来决定对应值的存储位置。通过这种索引方式,HashMap 获取数据的速度会非常快。

    例如,存储键值对(x,“aa”)时,哈希表会通过哈希函数 f(x) 得到 Hash 值("aa"的实现存储位置)。

    但也会有新的问题。如果再来一个 (y,“bb”),哈希函数 f(y) 的 Hash 值跟之前 f(x) 是一样的,这样两个对象的存储地址就冲突了,这种现象就被称为哈希冲突。那么哈希表是怎么解决的呢?方式有很多,比如,开放定址法、再哈希函数法和链地址法。

    开放定址法很简单,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把 key 存放到冲突位置后面的空位置上去。这种方法存在着很多缺点,例如,查找、扩容等,所以不建议作为解决哈希冲突的首选

    再哈希法顾名思义就是在同义词产生地址冲突时再计算另一个哈希函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但却增加了计算时间。如果我们不考虑添加元素的时间成本,且对查询元素的要求极高,就可以考虑使用这种算法设计。

    **HashMap 则是综合考虑了所有因素,采用链地址法解决哈希冲突问题。**这种方法是采用了数组(哈希表)+ 链表的数据结构,当发生哈希冲突时,就用一个链表结构存储相同 Hash 值的数据。

    什么是HashCode

    Hash 值就是 HashCode。HashCode的产生上面已经说了——通过key生成。

    HashMap的初始容量一般设置2的整数幂,原因?

    2的幂次方减1后每一位都是1,让数组每一个位置都能添加到元素。 例如十进制8,对应二进制1000,减1是0111,这样在&hash值使数组每个位置都是可以添加到元素的,如果有一个位置为0,那么无论hash值是多少那一位总是0,例如0101,&hash后第二位总是0,也就是说数组中下标为2的位置总是空的。 如果初始化大小设置的不是2的幂次方,hashmap也会调整到比初始化值大且最近的一个2的幂作为capacity。

    简单说就是减少哈希冲突,均匀分布元素。

    展开全文
  • 递归实现数组求和

    2021-03-01 21:10:21
    #include <iostream> using namespace std; int sum(int ht[], int n) { if (n>0) { return sum(ht, n-1)+ht[n-1]; } else { return 0; } } int main(int argc, char* argv[]) ... int
  • #include<iostream> using namespace std; int sumI(int A[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += A[i]; return sum; } int main() ... int a[] = ...
  • 数组求和的方法

    万次阅读 2018-07-20 15:14:56
    对于数组求和有多种方法: 1:递归方法 function sum(arr){  var len =arr.length;  if(len==0){  return 0;  }else if(len==1){  return arr[0];  }else{  return arr[0]+sum(arr.slice(1));  } } var a=...
  • 题目: 给定一个整形数组和一个整数target,返回2个元素的下标,它们满足相加的和为target。你可以假定每个输入,都会恰好有一个满足条件的返回结果。 思路: 一次遍历即可,借助一个Map用于存储value-index,每次去...
  • js数组求和的5种方法

    千次阅读 2020-10-27 10:29:06
    js数组求和的5种方法 题目描述 计算给定数组 arr 中所有元素的总和 输入描述: 数组中的元素均为 Number 类型 输入例子: sum([ 1, 2, 3, 4 ]) 输出例子: 10 1、不考虑算法复杂度,用递归做: function ...
  • C语言递归实现数组求和

    千次阅读 2019-11-14 23:25:57
    C语言递归实现数组求和 一.基本思想(分而治之): 1.基线条件: 显然最简单的情况:数组只有一个数时,无需任何操作,直接返回其值即可; 所以基线条件为数组长度为1; 2.递归条件: 每一次加上数组最后一位并缩短...
  • #include<iostream.h> struct sss { int a; int v; }; void ss(int a) { int c[5]={1,2,3}; for(int i=0;i<3;i++) a+=c[i];...} //求数组内数据和 void ss(sss s) { cout<<s.a+s.v...
  • 数组求和算法系列

    千次阅读 2011-08-24 17:28:58
    数组求和算法系列 一直想写一个数组求和算法系列博客,但由于自己算法能力有限,完成不了,只能完成其中简单的部分,难的部分希望有园友愿意和我一起完成。在写这篇博客的过程中借用了别人的思路,有的的确是要一定...
  • 问题描述:  编写一个简单的用递归求一...// 递归实现数组求和 #include int sum(int A[], int n) { if (n ) //递归出口 return 0; //下标为0 else return sum(A,n-1) + A[n-1]; } int main() { int n = 3;
  • } // 定义新数组,新数组长度等于原数组中1个元素的长度 int newArr[] = new int[targetArr[0].length]; for (int i = 0; i ; i++) { for (int j = 0; j [i].length; j++) { newArr[j] += targetArr...
  • java对int数组求和

    2021-09-29 15:13:20
    // 求和 OptionalDouble avg = Arrays.stream(arr1).average(); // 求平均值 double average = avg.getAsDouble(); int min = Arrays.stream(arr1).min().getAsInt(); // 最小值 int max = Arrays.
  • 数组元素求和,顾名思义就是求数组中所有元素的和,比如有数组X:X的所有元素和就是:如果按串行顺序求上式还是很好理解的,就是一个逐渐累加的过程,如下图,按照step1~stepn的步骤,依次...
  • //对一个整型数组求和 //数组传递和指针传递两种方式 //默认数组传递 #include <stdio.h> int addArray(int array[],int n); //int addArray(int *array,int n); int main() { int data[]={0,1,2,3,4,5...
  • 数组求和相关算法

    千次阅读 2016-09-04 18:54:21
    问题1、输入一个数组,在数组中查找两个数,使得它们的和正好是targetvoid FindTwoSum(int a[],int n,int target){ sort(a,a+n); int sum=0; int i=0; int j=n-1; while(i){ sum=a[i]+a[j]; if(sum==target)
  • 用递归实现数组求和

    千次阅读 2017-04-19 20:36:11
    题目:给定一个len长度的数组,用递归的方法求数组和 C代码实现: #include #include int getSum(int a[],int len) { if(len == 0) //要考虑空数组的情况 { return 0; } else { int n = len-1; if...
  • C++数组求和:新手实用技巧 使用自带的库函数 accumulate 的方法 首先: accumlate 所在头文件是:<numeric> #include <iostream> #include <numeric> using namespace std;
  • 记录学习 import java.util.Scanner; public class JW5_1{ public static void main(String ar[]){ testArray(); } public static void testArray() { int[][] array = new int[3][3];//创建二维数组 ...
  • 递归求数组元素的和(C++)

    千次阅读 2020-03-19 09:39:29
    在主函数中输入元素个数和数组元素,调用函数求和,在主函数中输出结果。设数组类型为整型,元素不超过100个。 输入:元素个数n和n个元素,用空格或换行隔开。 输出:数组元素和。 【提示】元素个数为0时返回和是0. ...
  • 如何用递归实现数组求和

    千次阅读 2017-07-17 09:36:27
    给定一个含有n个元素的整型数组a,求a中所有元素的和。 解法 1.不递归#include <stdio.h>int main() { int a[] = { 3,6,8,2,1}; int i; int len = sizeof(a)/sizeof(a[0]); int sum = 0; for(i = 0;i;i++) {
  • 在一个2维矩阵中,返回由左上角(row1, col1)和右下角(row2, col2)所固定的矩形中的元素的和。 问题分析: 解法1 建立前缀数组,然后行遍历时累加 解法2 动态规划,可以看看这个链接: ...
  • JS 数组求和的5种方法

    2021-01-15 13:59:36
    计算给定数组 arr 中所有元素的总和 输入描述: 数组中的元素均为 Number 类型 输入例子: sum([ 1, 2, 3, 4 ]) 输出例子: 10 最简单的方法eval: function sum(arr) { return eval(arr.join("+")); }; 不考虑算法...
  • [数组]递归方式求和

    千次阅读 2017-07-21 17:14:37
    首先,如果不需要用递归方法,我们可以用遍历的方式来实现数组元素求和。 #include int main() { int a[] = {3,6,8,2,1}; int i; int sum = 0; int len = sizeof(a) / sizeof(a[0]); for(i = 0; i ; i++) { sum +...
  • 普通迭代法,求解一个n个数组元素的和vector<int> v = { 4, 7, 8, 32, 7,9 }; int sum = 0; for (int i = 0; i < v.size(); i++) { sum += v[i]; } return sum; 时间复杂度T(n) = 1 + n * 1 + 1 = n + 2...
  • python-(数组的)累计求和

    千次阅读 2020-01-17 11:29:23
    1、一维数组的累计求和: a = np.random.randint(1,10,5) out:array([6, 4, 5, 7, 2]) a.cumsum() out:array([ 6, 10, 15, 22, 24]) 2、二维数组的累计求和: b = np.random.randint(1,10,(...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,709
精华内容 10,683
关键字:

数组元素求和算法