leetCode，leetcode hot 1-2

1.兩數之和

解法1：暴力遍歷

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {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{};}
};

遇到的問題：

在開始的時候，第二重循環將j設置成 j=i 結果第一個數相加兩次等于target

輸入：

[3,2,4] 6

leetCode、輸出：

[0,0]

預期結果：

[1,2]

此時將j 指向 i的下一個便能通過

暴力解法的時間復雜度是n^2

leetcode premium、解法2：哈希表

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {map<int,int>m;for(int i=0;i<nums.size();i++){auto it=m.find(target-nums[i]);//如果查找成功，find返回下標，如果沒找對，返回end（）if(it!=m.end()){return {it->second,i};}m[nums[i]]=i;}return {};}
};

遇到的問題：

插入的時候使用insert結果報錯了

哈希表的高效查找可以使時間復雜度降下到o（n）

2.兩數相加

解法1：模擬

直接遍歷鏈表對應數字相加即可。逐位計算它們的和，并與前面的進位值相加

LEETCODE，比如，兩個鏈表對應位的數字分別為n1和n2，進位為carry（通常為0和1），則它們的和為(n1 + n2 + carry)，對應位上數字變為(n1 + n2 + carry)%10，新的進位為(n1 + n2 + carry)/10。

如果兩個鏈表長度不一樣，長度短的鏈表后續對應位上值均為0即可。如果遍歷結束之后，carray大于0（也就是等于1），則在結構鏈表后面新增一個節點，

/*** 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=nullptr,*tail=nullptr;int carry=0;while(l1||l2){int n1=l1?l1->val:0;int n2=l2?l2->val:0;int sum=n1+n2+carry;if(!head){head=tail=new ListNode(sum%10);}else{tail->next=new ListNode(sum%10);tail=tail->next;}carry=sum/10;if(l1){l1=l1->next;}if(l2){l2=l2->next;}}if(carry>0) {tail->next=new ListNode(carry);}return head;}
};

遇到的問題：
int n1=l1?l1->val:0; int n2=l2?l2->val:0; 一開始沒看懂這兩句，其實它們等價于

            int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;

另外又將這兩句放在了while之外，結果造成節點一直指向第一個，沒有更新

之后又將 tail->next=new ListNode(carry); 寫成 tail=new ListNode(carry); tail=tail->next；

最后造成當 最后相加carry存在的時候，沒有進位

leetcode all in one、上述方法時間復雜度的計算與鏈表的長度有關，比如兩個鏈表的長度分別為m和n，則遍歷的次數為max(m,n)，也就m和n中取最大值，所以時間復雜度為O(n)。

解法2：遞歸

不用遞歸沒有靈魂。盡管多數時候，遞歸不見得更有效率

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {if(!l1) return l2;if(!l2) return l1;int target=l1->val+l2->val;ListNode* res=new ListNode(target%10);res->next=addTwoNumbers(l1->next,l2->next);if(target>=10) {res->next=addTwoNumbers(res->next,new ListNode(1)); }return res;}
};

遞歸解法非常巧妙。

做遞歸題目一定要牢記「遞歸函數的定義」。

遞歸函數定義：addTwoNumbers 表示將兩個鏈表 l1 和 l2 相加得到的新鏈表；
遞歸終止條件：如果 l1 和 l2 有一個為空，則返回另外一個。
遞歸函數內容：

leetcode hard，把兩個鏈表節點的值相加（結果記為 add ）。把 add 模 1010 作為當前的鏈表節點的值。
把兩個鏈表的 next 節點相加。（注意：如果當前相加的結果 add >= 10add>=10，需要把 next 節點相加得到的結果 + 1。）

遞歸解法妙在天然地處理好了兩個鏈表不一樣長、最終相加結果有進位的情況。

可以推演一下遞歸調用的時間復雜度。針對遞歸調用的時間復雜度計算，本質上要看：遞歸的次數??每次遞歸中的操作次數。那么，上述方法遞歸了幾次呢？遞歸的次數也是與兩個鏈表最長的那個的長度有關，最后可能會因為進位多算一次，因此遞歸次數為n或n+1，而內部計算并不隨n的變化而變化，執行次數為常數。因此整體時間復雜度為n*1 = O(n)。

空間復雜度依舊與結果鏈表的長度有關，因此依舊為O(n)。