na982

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int nums1_size = nums1.size();
        int nums2_size = nums2.size();
        
        if(nums1_size > nums2_size) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int left = 0, right = nums1_size;
        int mid = (nums1_size + nums2_size + 1) / 2;
        
        int max_of_left = -1, min_of_right = -1;
        while(left <= right) {
            int i = (left + right) / 2;
            int j = (mid - i);
            
            if(i < nums1_size && nums1[i] < nums2[j - 1]) {
                left = i + 1;
            } else if(i > 0 && nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                if(i == 0) {
                    max_of_left = nums2[j - 1];
                } else if(j == 0) {
                    max_of_left = nums1[i - 1];
                } else {
                    max_of_left = max(nums1[i - 1], nums2[j - 1]);
                }
                
                if((nums1_size + nums2_size) % 2 == 1) {
                    return max_of_left;
                }
                
                if(i == nums1_size) {
                    min_of_right = nums2[j];
                } else if(j == nums2_size) {
                    min_of_right = nums1[i];
                } else {
                    min_of_right = min(nums1[i], nums2[j]);
                }
                return (max_of_left + min_of_right) / 2.0;
            }
        }
        return -1.0;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0, ret = 0;
        unordered_map<char, int> m;
        while(right < s.size()) {
            if(m.find(s[right]) != m.end()) {
                left = max(left, m[s[right]] + 1);
            }
            ret = max(ret, right - left + 1);
            m[s[right]] = right;
            ++right;
        }
        return ret;
    }
};

/**
 * 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 = new ListNode(-1);
        
        ListNode* target = dummy;
        int carry = 0;
        while(l1 || l2 || carry) {
            int l1_val = (l1) ? (l1->val) : (0);
            int l2_val = (l2) ? (l2->val) : (0);
            int sum = (l1_val + l2_val + carry);
            target->next = new ListNode(sum % 10);
            carry = sum / 10;
            
            target = target->next;
            l1 = (l1) ? (l1->next) : (l1);
            l2 = (l2) ? (l2->next) : (l2);
        }
        
        return dummy->next;
    }
};