4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

solution:

这个题目想一口气写好不容易。 需要考虑的细节很多。算法倒是很好理解。既然是sorted array, 那么必须用好排好的序。所以要追求 O(ln n).

代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double res;
        int l1=nums1.size();
        int l2=nums2.size();
        int total = l1 + l2;
        if(total & 0x1){ // total is odd;
            res = findKth(nums1, 0, l1, nums2, 0, l2, total/2 + 1)*1.0;
        }
        else {
            res = (findKth(nums1, 0, l1, nums2, 0, l2, total/2)  
                  + findKth(nums1, 0, l1, nums2, 0, l2, total/2 + 1))/2.0;
        }
        return res;
    }
private:    
    int findKth(vector<int>& v1, int a1, int b1, vector<int>& v2, int a2, int b2, int k){
        int x1=b1-a1;
        int x2=b2-a2;
        if(x1>x2) return findKth(v2, a2, b2, v1, a1, b1, k);
        if(x1==0) return v2[a2+k-1];
        if(k==1) return min(v1[a1], v2[a2]);
        int m=min(x1, k/2); 
        int n=k-m;
        if(v1[a1+m-1]<v2[a2+n-1]){
            return findKth(v1, a1+m, b1, v2, a2, b2, k-m);
        }
        else if(v1[a1+m-1]>v2[a2+n-1]){
            return findKth(v1, a1, b1, v2, a2+n, b2, k-n);
        }
        else {
            return v1[a1+m-1];
        }
    }    
};

3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

solution:
可以使用double pointers. 需要更新最左边和最右边。题目不难， 这时就是看代码怎么写的简洁。

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        int left = 0;
        vector<int> m(256, 0);
        for (int i=0; i<s.size(); ++i){
            left = max(left, m[s[i]]);
            m[s[i]] = i+1;
            res = max(res, i-left+1);
        }
        return res;
    } 
};

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

solution:
需要考虑进位的问题。 然后就是linked list细节了： 生成新节点等等。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(-1);
        ListNode* p = &dummy;
        int carrier = 0;
        while(l1||l2){
            if(l1) {
                carrier += l1->val;
                l1 = l1->next;
            }
            if(l2) {
                carrier += l2->val;
                l2 = l2->next;
            }
            p->next = new ListNode(carrier%10);
            p = p->next;
            carrier /= 10;
        }
        if(carrier){
            p->next = new ListNode(carrier);
            p = p->next;
        }
        return dummy.next;
   };

1: Two Sum

https://leetcode.com/problems/two-sum/

solution:
不用hash table的话，需要double pointers. 这样的就 O(n2) 了。
使用hash table的话， 就很直观的 O(n) 了。 然后需要注意一些细节， 比如不要重复计入了， 还有就是可以扫一遍就行了 （hash的同时就可以判断了）。

代码：

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