leetcode problem (2-4)

Problem 2 --- Add Two Numbers

简单的模拟题。

Problem 3 --- Longest Substring Without Repeating Characters

题意：给定一个字符串序列，找出最长无重复的子序列。如"abcabcbb"的最长不重复子序列为"abc"

思路：　首先分配一个hashTable[256]，里面保存每个字符在当前字符序列中的位置，同时设置left变量表示当前无重复字符串的最左端位置。然后从头到尾扫面字符串S，每扫描一个字符便更新相应的hashTable，同时当前序列长度len+1。

　　　　如果遇到的字符在当前子序列中有重复(即hashTable[elem] >= left)，此时更新max和left： max = len > max ? len : max, left = hashtable[elem]。

　　　　最后返回max.

　　　　时间复杂度 O(n) 空间复杂度O(n)

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s){
        int max = 0;
        int index = 0;
        int len = 0;
        int left = 0;
        memset(m_hashTable, 0, sizeof(m_hashTable));
        for (auto elem : s) {
            if (m_hashTable[elem] != 0 && m_hashTable[elem] >= left) {
                max = max < len ? len : max;
                left = m_hashTable[elem];
                len = index - m_hashTable[elem];
            }    
            ++len;
            m_hashTable[elem] = ++index;
        }
        max = max < len ? len : max;
        return max;
    }
private:
    int m_hashTable[256];
};

View Code

Problem 4 --- Median of Two Sorted Arrays

题意：给出两个已经排序好的数列，得到它们合并后的数列中位数。

思路：这道题实际可以扩展为找到第k大的数。假定给出的序列为A[1..m]和B[1..n]，合并后的序列为C[1..m+n]。

　　　第一种方法，合并两个数组，直接返回C[k]，简单。时间复杂度是O（n）

　　　第二种方法是: 找到A[k/2]和B[k/2], 如果A[k/2] < B[k/2]。那么说明A[1..k/2]一定在C[k]的左侧。因此可以分解为子问题:找到A[k/2+1..m]和B[1..n]的第k-k/2大数。最终用递归解此题。

　　　　　　时间复杂度O(logk)

代码：

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m + n;
        if (total & 0x01) 
            return findKth(A, m, B, n, total / 2 + 1);
        else
            return (findKth(A, m, B, n, total / 2) + 
                    findKth(A, m, B, n, total / 2 + 1)) / 2.0;
    }

private:
    int findKth(int A[], int m, int B[], int n, int k) {
        if (m > n)
            return findKth(B, n, A, m, k);
        if (m == 0)
            return B[k-1];
        if (k == 1)
            return min(A[0], B[0]);
    
        
        int posA = min(k/2, m), posB = k - posA;
        if (A[posA - 1] < B[posB - 1]) 
            return findKth(A + posA, m - posA, B, n, k - posA);
        else if (A[posA - 1] > B[posB - 1]) 
            return findKth(A, m, B + posB, n - posB, k - posB);
        else 
            return A[posA-1];
    }
};

View Code