转载

挑战编程题(二)

昨天的题目:http://www.cnblogs.com/qiange/p/5062213.html

1. 求两个数的和

给定一个整型数组,从中挑选两个数字,使其相加为一个为一个给定的值,返回这两个值所有数组中位置下标,位置下标小的在前面,位置下标从1开始。

例如:

输入:nums= {2,7,11,13}  target=24

输出:3,4
//解法1:最简单的方法,用两层循环,算法如下,算法复杂度为O(n*n) //这个也是最容易想到的。 vector<int> twoSum1(vector< int>& nums, int target) {                  int i=0;                  int count = nums.size();                  while(i<count){                                  int j=i+1;                                  while(j<count){                                                  if(nums[i]+nums[j]==target){                                                                 vector< int> r;                                                                 r.push_back(i+1);   //下标+1 因为下标从1开始的                                                                 r.push_back(j+1);                                                                  return r;                                                 }                                                 j++;                                 }                                 i++;                 }   }   //解法2:利用hash表,c++中可以使用map。时间复杂度O(n) vector<int> twoSum2(vector< int>& nums, int target){                 vector< int> result;                 unordered_map< int,int > maping;                  //1.用数组中nums中的值key,用下标作为value;                   for (int i=0;i<nums.size();i++){                                 maping[nums[i]]=i;                 }                    for (int i=0;i<nums.size();i++){                                  //2.求的另一个加数                                  int otherNum = target-nums[i];                                  //3.从maping中寻找key为另一个加数的value                                  if(maping.find(otherNum)!=maping.end() && maping[otherNum]!=i){                                                 result.push_back(i+1);                                                 result.push_back(maping[otherNum]+1);                                                  break;                                 }                 }                    return result; }

两种算法的运行结果如下:

挑战编程题(二)

挑战编程题(二)

第二种方法是一种很巧妙的利用空间来换取时间,并利用了hash快速定位的特别

今天的题目( Add Two Numbers)

  1. 有两个非负数的链表,每个链表都反序的存储一个多位数字的每一位,(例如:链表2->4->3  数字342),现在求两个链表数字的相加,求和的链表。

例如: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

/**

* Definition for singly-linked list.

* struct ListNode {

*     int val;

*     ListNode *next;

*     ListNode(int x) : val(x), next(NULL) {}

* };

*/

//函数

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

}

如有问题,欢迎和我联系。 我的邮箱 cq20151207@163.com 

正文到此结束
Loading...