LeetCode第1题-两数之和（C++实现）

大家好，我是一只学弱狗，记录学习的点点滴滴！
算法才是程序设计的灵魂，每日一题！

优质文章
  • 一张黄图的故事
  • JavaSE练习项目
  • 我是菜鸟、我小试牛刀
  • linux指令太多记不住？小白看这篇就够了！
优质专栏
  • 数据库就该这样学
  • 爪哇外步篇

第一想法，就是暴力枚举

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result(2);for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){if(nums[i]+nums[j]==target){return {i,j};}}}return {};}
};

第二种做法，网上看的，查找表法

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {map<int,int> recode;for(int i=0;i<nums.size();i++){if(recode.find(target-nums[i]) == recode.end()){recode[nums[i]]=i;}else{return {recode[target-nums[i]],i};}}return {};}
};

因为是第一次刷LeetCode的题目，有些规则还是不太懂的，搞了挺长时间的。。
以后没做一个题，我都会写一些感想与经验，但是每篇均不会重复

规则此题：我再次熟悉了vector和map的使用

对于vector，它更像java中的ArrayList，如果是函数返回值的时候，可以直接写{1,2}
对于map来说，就比好重要了，有普通的map，也有unordered_map，但是devcpp好像不支持，，，，解决方法如何在Dev-Cpp中使用C++11中的函数
然后就是一些编程习惯，比如若常常使用多次同一个值，像双层for循环使用数组的长度，可以用一个变量来保存，当然，这也是看大佬学到的，

最后就是用查找表法解决这个题，也是我没想到的。。

map的底层实现时红黑树
而unordered_map的底层实现时哈希，如果不考虑排序的话，用unordered_map更快一些

附上最好的代码

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> rec;for(int i=0;i<nums.size();i++){if(rec.find(target-nums[i])==rec.end()){rec[nums[i]]=i;}else{return {rec[target-nums[i]],i};}}return {};}
};

看了解析，这种能写更少的代码，大家参考下就行，思路一样的

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head = new ListNode;ListNode* front = head;int jinwei = 0; while(l1!=NULL && l2!=NULL){int sum = l1->val + l2->val + jinwei;ListNode* tmp = new ListNode(sum%10);jinwei = sum/10;front->next = tmp;front = tmp;l1 = l1->next;l2 = l2->next;}while(l1!=NULL){int sum = l1->val + jinwei;ListNode* tmp = new ListNode(sum%10);jinwei = sum/10;front->next = tmp;front = tmp;l1 = l1->next;}while(l2!=NULL){int sum = l2->val + jinwei;ListNode* tmp = new ListNode(sum%10);jinwei = sum/10;front->next = tmp;front = tmp;l2 = l2->next;}if(jinwei!=0){ListNode* tmp = new ListNode(jinwei);front->next = tmp;}return head->next;}
};

但是还没上面的那个执行的快。。。