陈中正的网络日志

APUE第三版源码编译问题解决[更新中。。]

下载了APUE的源码,在文件夹apue.3e下运行make时会抛出各种错误提示,在此记录各问题解决方案。环境是Linux。

错误提示:  ../systype.sh: Permission denied

问题解决: chmod a+x systype.sh

错误提示: fixup.awk: Permission denied

问题解决: chmod a+x fixup.awk

错误提示: /usr/bin/ld: cannot find -lbsd

问题解决:

错误提示:

问题解决:

错误提示:

问题解决:

参考

http://bbs.csdn.net/topics/80447869

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40182817

LeetCode: Search in Rotated Sorted Array II

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/

分析

这道题是Search in Rotated Sorted Array的变形,因为有重复元素的存在,之前的方法就不不能直接用了,比如在{1, 3, 1, 1, 1}中寻找3, 结果就会出错。

出错的原因在于因为重复元素的存在,A[m]==A[l]时就不能确定在中点的哪一边是有序的,那就不能砍掉一半的查找范围了。

解决的办法是将左边界向右移动,直至A[m]!=A[l],这样一来在最坏情况下时间复杂度会变为O(n)。

源码

class Solution
{
public:
    bool search(int A[], int n, int target)
    {
        int l = 0;
        int r = n - 1;
        int m;

        while (l <= r)
        {
            m = (l + r) >> 1;
            if (A[m] == target)
                return true;
            else
            {
                if (A[m] == A[l])
                    l++;
                else if (A[m] > A[l])
                {
                    if (target >= A[l] && target < A[m])
                        r = m - 1;
                    else
                        l = m + 1;
                }
                else
                {
                    if (target > A[m] && target <= A[r])
                        l = m + 1;
                    else
                        r = m - 1;
                }
            }
        }
        return false;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/20588511

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40156301

LeetCode: Search in Rotated Sorted Array

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

分析

还是运用二分的思想, 每次循环判断target在中点的左侧还是右侧,每次砍掉一半的查找范围, 直到得到最终结果。

在这个过程中用到的一个重要规律是: 

一个数字序列经过rotate之后, 以中间那个数字为边界, 一定一边是有序序列, 一边是 rotated有序序列(证明略)。

如何判断哪边是有序的呢? 如果中点大于左边界, 则左侧是有序序列, 否则右侧是有序序列。

分别用 l代表左边界, r代表右边界, m代表中间那个数,

如果A[m] == target, 则直接返回m即可。

如果A[m] >= A[l] ,说明左侧是有序序列

       如果target在左侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在右侧序列中, 则把 右边界r 设为 m-1

否则, 右侧是有序序列

       如果target在右侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在左侧有序序列范围内, 则把 右边界r 设为 m-1

 

P.S. 标准二分查找代码可以查看这里

代码

class Solution
{
public:
    int search(int A[], int n, int target)
    {
        if (n <= 0)
            return -1;
        int l = 0;
        int r = n - 1;
        int m;

        while (l <= r)
        {
            m = (l + r) / 2;
            if (A[m] == target)
                return m;
            else if (A[l] < A[m])
            {
                if (A[l] <= target && target <= A[m-1])
                    r = m - 1;
                else
                    l = m + 1;
            }
            else
            {
                if (A[m+1] <= target && target <= A[r])
                    l = m + 1;
                else
                    r = m - 1;
            }
        }
        return -1;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/20525681

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39860279

LeetCode: Divide Two Integers

题目

https://oj.leetcode.com/problems/divide-two-integers/

分析

  1. 题目要求实现除法运算且不能用乘除和取余运算, 一开始想用的递减计数的方式, 显然这种方法效率太低了, 从而导致超时。

不能用乘除和取余如何快速的逼近结果呢? 答案是采用移位运算, 以指数的形式增长, 快速逼近最终的结果。

举例来说明, 137 / 7 = 19如何用移位运算来快速得到最终结果呢?

           135 - 7 × 2 ^ 4 = 23    > 7

           23   - 7 * 2 ^ 1  = 9      > 7

           9     - 7 * 2 ^ 0  = 2      <  7    停止运算

最终结果    24 + 21 + 20 = 19

  1.  为了防止溢出, 将int型参数隐式转换为long long型参数。

代码

class Solution
{
public:
    int divide(long long dividend, long long divisor)
    {
        int res = 0;
        int sign = (dividend>0 && divisor>0) || (dividend<0 && divisor<0);
        dividend = dividend > 0 ? dividend : -dividend;
        divisor = divisor > 0 ? divisor : -divisor;

        while (dividend >= divisor)
        {
            long long res_temp = 1;
            while (res_temp * divisor <= dividend)
                res_temp <<= 1;
            res_temp >>= 1;
            res += res_temp;
            dividend -= res_temp * divisor;
        }
        return sign ? res : -res;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39558059

LeetCode: Remove Duplicates from Sorted Array II

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

分析

和Remove Duplicates from Sorted Array类似, 

从前向后遍历该序列, 如果该元素和前一元素相同则重复数加1。

只不过只有重复数小于等于2时才把该元素排到数组前面。

代码

class Solution
{
public:
    int removeDuplicates(int A[], int n)
    {
        if (n < 1)
            return n;
        int count = 1;
        int dup_times = 1;
        for (int i = 1; i < n; i++)
        {
            if (A[i] == A[i-1])
                dup_times++;
            else
                dup_times = 1;

            if (dup_times <= 2)
                A[count++] = A[i];
        }
        return count;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39546327

LeetCode: Remove Duplicates from Sorted Array

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/

分析

从前向后遍历, 如果该元素不和前面元素重复, 就该元素排到前面。

代码

class Solution
{
public:
    int removeDuplicates(int A[], int n)
    {
        if (n < 1) 
            return n;
        int count = 1;
        for (int i = 1; i < n; i++)
            if (A[i] != A[i-1])
                A[count++] = A[i];
        return count;
    }
};

参考

http://blog.csdn.net/xudli/article/details/8423225

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39544993

LeetCode: Remove Duplicates from Sorted List II

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

分析

  1. 双指针来实现, 左侧的指针指向上一个有效结点, 右侧的指针进行试探, 直到找出有效结点后和左侧的指针连接起来。

  2. 由于链表第一个结点可能被删除掉, 所以左侧指针初始化为头结点的前一个指针。

代码

class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        if (head == NULL)
            return head;

        ListNode *pre_head = new ListNode(0);
        pre_head->next = head;

        ListNode *pl, *pr;
        pl = pre_head;
        pr = head;
        while (pr != NULL)
        {
            if (pr->next != NULL && pr->val == pr->next->val)
            {
                pl = pl->next;
                pr = pr->next;
            }
            else
            {
                while (pr->next != NULL && pr->val == pr->next->val)
                {
                    ListNode *temp = pr;
                    pr = pr->next;
                    delete temp;
                }
                pr = pr->next;
            }
        }

        ListNode *temp = pre_head;
        pre_head = pre_head->next;
        delete temp;
        return pre_head;
    }
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-remove-duplicates-from-sorted.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39544599

LeetCode: Remove Duplicates from Sorted List

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/

分析

从前向后遍历即可

代码

class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *p = head;
        while (p != NULL && p->next != NULL)
        {
            if (p->val == p->next->val)
            {
                ListNode *temp = p->next;
                p->next = p->next->next;
                delete temp;
            }
            else
                p = p->next;
        }
        return head;
    }
};

参考

http://www.programcreek.com/2013/01/leetcode-remove-duplicates-from-sorted-list/

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39456291

11种常见排序算法总结(更新ING...)

1. 冒泡排序 (Bubble Sort)  [1]

1.1 算法描述

冒泡排序过程中, 从前往后依次扫描每一对相邻元素, 一旦发现逆序即交换二者的位置。  这一过程称作一趟扫描交换。

以此类推, 最多进行n-1趟扫描交换, 整个序列就排序完成了。

算法的平均时间复杂度为O(n2), 空间复杂度O(1), 是稳定排序算法。

1.2 代码实现

void bubble_sort(int a[], int n)
{
    bool sorted;
    int i;

    while (!sorted)
    {
        sorted = true;
        for (i = 1; i < n; i++)
        {
            if (a[i-1] > a[i])
            {
                int tmp = a[i-1];
                a[i-1] = a[i];
                a[i] = tmp;

                sorted = false;
            }
        }
        n--;
    }
}

2. 插入排序 (Insertion Sort)  [2]

2.1 算法描述

该算法将序列划分为两部分, 左侧的已排序部分和剩下的待排序部分, 一开始已排序部分为空, 待排序部分为整个序列。 

把待排序部分的第一个元素和已排序部分的元素从后往前依次进行比较, 直到找到合适的位置并插入进去。

如此重复直至待排序部分为空……

该算法平均时间复杂度为O(n2), 空间复杂度O(1), 是稳定排序算法。

2.2 代码实现

void insert_sort(int a[], int n)
{
    int i, j, temp;

    for (i = 1; i < n; i++) 
    {
        temp = a[i];
        for (j = i - 1; j >= 0 && temp < a[j]; j--)
            a[j+1] = a[j];

        a[j+1] = temp;
    }
}

3. 选择排序 (Selection Sort)    [3]

3.1 算法描述

该算法将序列划分为两部分, 左侧的已排序部分和剩下的待排序部分。 一开始已排序部分为空, 待排序部分为整个序列。 

接下来在待排序序列中找出最小值, 和待排序序列中最左侧的元素进行交换。 把已排序序列的边界右移一位。

如此重复n-1次……

算法的时间复杂度为Θ(n2) , 空间复杂度O(1), 是不稳定排序算法。

3.2 代码实现

void selection_sort(int a[], int n)
{
    int i, j, min;
    for (i = 0; i < n - 1; i++)
    {
        min = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;

        if (min != i)
        {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

4. 归并排序 (Merge Sort) [4]

4.1 算法描述

该算法采用分而治之的策略, 先把整个序列不断划分, 直至划分为单个元素, 

然后开始合并, 在合并的过程中进行排序。

算法的时间复杂度为O(nlogn), 空间复杂度为O(n), 为稳定排序算法。

4.2 代码实现

void merge(int[], int, int, int);

void merge_sort(int arr[], int l, int r)
{

    if (r - l < 2)
        return;
    else
    {
        //divide and conquer
        int m = (l + r) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

//merge two array, arr[l]...arr[m] and arr[m+1]...arr[r]
void merge(int arr[], int l, int m, int r)
{
    int n1 = m - l + 1;
    int n2 = r - m;
    int a[n1], b[n2];

    for (int i = 0, int j = l; i < n1; i++, j++)
        a[i] = arr[j];

    for (int i = 0, int j = m + 1; i < n2; i++, j++)
        b[i] = arr[j];

    int i = 0;
    int j = 0;
    int k = l;
    while (i < n1 && j < n2)
    {
        if (a[i] <= b[j]) 
        {
            arr[k] = a[i];
            i++;
        } 
        else 
        {
            arr[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < n1) 
    {
        arr[k] = a[i];
        k++;
        i++;
    }

    while (j < n2) 
    {
        arr[k] = b[j];
        k++;
        j++;
    }
}

5. 桶排序 (Bucket Sort) [5]

6. 计数排序 (Counting Sort) [6]

7. 基排序 (Radix Sort) [7]

8. 堆排序 (Heap Sort) [8]

8.1 算法描述

该算法可以说是选择排序的改进版本,把整个序列分为左侧的未排序序列(组织为大顶堆的形式)和右侧的已排序部分。一开始右侧的已排序部分为空,左侧的未排序的部分为整个序列。

接下来从左侧未排序部分取出最大元素, 把已排序序列的边界左移一位, 把取出的最大元素放到右侧已排序部分的最左侧。 

如此重复直至未排序部分(大顶堆)为空……

算法的时间复杂度为Θ(n*log(n)) , 空间复杂度O(1), 是不稳定排序算法。

8.2 代码实现 (需其他函数代码支持)

void head_sort(int a, int low, int high)
{
    PQ_complHeap H(a, low, high);  //floyd法建堆
    while (!H.empty())
        a[--high] = H.delMax();
}

9. 锦标赛排序 (Tournament Sort) [9]

10. 快速排序 (Quick Sort) [10]

10.1 算法描述

该算法和归并算法类似,快速排序也是采用分而治之的策略来提高排序效率的。所不同的是,归并排序的时间主要消耗在归并上, 而快速排序的时间主要消耗在划分上。

快速排序排序时, 首先把序列划分为两个子序列, 然后递归的对两个子序列进行快速排序。 直到划分到平凡情况,每个子序列的个数为1, 这时便返回。

问题的关键, 如何进行子序列的划分?

可以把该序列的第一个数移动到它排序后的正确位置,同时它左侧都是比它小的数, 它右侧都是比它大的数。 以该数作为轴, 将两边的数划分为两个子序列。

算法的平均时间复杂度为Θ(n*log(n))  , 平均空间复杂度O(n*log(n)), 是不稳定排序算法。

10.2 代码实现

int partition(int a[], int lo, int hi);
void quick_sort(int a[], int lo, int hi)
{
    if (hi - lo < 2)
        return;
    else
    {
        int mid = partition(a, lo, hi);
        quick_sort(a, lo, mid);
        quick_sort(a, mid + 1, hi);
    }
}

int partition(int a[], int lo, int hi)
{
    int pivot = a[lo];
    while (lo < hi)
    {
        while ((lo < hi) && (pivot <= a[hi]))
            hi--;
        a[lo] = a[hi];
        while ((lo < hi) && (pivot >= a[lo]))
            lo++;
        a[hi] = a[lo];
    }
    a[lo] = pivot;
    return lo;
}

11. 希尔排序 (Shell Sort) [11]

12. 性能总结 [12]

          排序法          

          平均时间         

        最差情形       

          稳定度          

       额外空间         

                                                   备注                                           

冒泡

 O(n2)

  O(n2)

 稳定

O(1)

n小时较好

插入

  O(n2)

  O(n2)

稳定

O(1)

大部分已排序时较好

选择

 O(n2)

 O(n2)

不稳定

O(1)

n小时较好

归并

 O(nlogn)

 O(nlogn)

稳定

O(1)

 n大时较好






基数

O(logRB)

O(logRB)

稳定

O(n)

B是真数(0-9)R是基数(个十百)s是所选分组


O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好

锦标赛






快速

O(nlogn)

O(n2)

不稳定 

O(nlogn)

n大时较好

Shell 

O(nlogn)  

O(ns) 1<s<2  

不稳定 

O(1)  



参考:

[1] 《数据结构》(C++语言版)(第3版) 邓俊辉  P5

[2] 《算法导论》

[3] http://en.wikipedia.org/wiki/Selection_sort

[4] 《数据结构》(C++语言版)(第3版) 邓俊辉  P63

[5]

[6]

[7]

[8] 《数据结构》(C++语言版)(第3版) 邓俊辉  P297

[9]

[10] 《数据结构》(C++语言版)(第3版) 邓俊辉  P335

[11]

[12] http://blog.csdn.net/iamfranter/article/details/6825207

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39400513

2014年美团校招笔试题解(更新ING……)

前几天参加了美团的校招笔试, 结果状态不好, 答得跟屎一样, 现在考完了总结一下好了。

5. 旋转二维数组

SouthEast

分析

就是一道找规律的题

代码

#include <iostream>

using namespace std;

#define N 3

class Solution
{
public:
    void print_rotate_matrix(int matrix[N][N], int n)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i + 1; j++)
                cout << matrix[j][j-i+n-1] << ' ';
            cout << endl;
        }

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
                cout << matrix[i+j+1][j] << ' ';
            cout << endl;
        }
    }
};

int main()
{
    int matrix[N][N] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    Solution s;
    s.print_rotate_matrix(matrix, N);

    return 0;
}

参考

http://blog.csdn.net/cow__sky/article/details/39226677

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39399955

C++: 生成100万随机数, 排序后保存到文件中

简介

这大概是大二数据结构课上老师布置的一个作业, 当年忙着打DOTA所以直接抄同学的, 今天补上。。。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

class Solution
{
public:
    void generate_nums()
    {
        srand(time(NULL));
        for (auto &r : nums_)
            r = rand();
    }

    void save_nums(string file_name)
    {
        ofstream ofs(file_name);

        for (auto &r : nums_)
            ofs << &r << '\n';

        ofs.close();
    }

    void sort_nums()
    {
        sort(nums_.begin(), nums_.end());
    }
private:
    vector<int> nums_ = vector<int>(1000000);
};

int main()
{
    Solution s;

    s.generate_nums();      //generate 1 million nums
    s.save_nums("nums");    //save to file "nums"
    s.sort_nums();          //sort
    s.save_nums("nums2");   //save to file "nums2"

    return 0;
}

参考

http://blog.csdn.net/hackbuteer1/article/details/6574908

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39398505

LeetCode: Remove Nth Node From End of List

题目

https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/

分析

  1. 两个指针, 第一个指针先走n步, 然后两个指针一起走, 直到第一个指针走到结尾处, 此时第二个指针即为要删除的结点的上一个结点。

  2. 特别要注意的一点是, 如果要删除的结点是第一个结点, 要特别的处理一下, 因为第二个指针无法指向第一个结点的上一个结点。

代码

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *l, *r;

        l = head;
        r = head;
        for (int i = 0; i < n; i++)
            r = r->next;

        if (r == NULL)
        {
            ListNode *t = head;
            head = head->next;
            delete t;
        }
        else
        {
            while (r->next != NULL)
            {
                l = l->next;
                r = r->next;
            }
            ListNode *t = l->next;
            l->next = t->next;
            delete(t);
        }
        return head;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39289759

LeetCode: Letter Combinations of a Phone Number

题目:

https://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/

分析:

DFS

代码:

class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        string solution;
        dfs(digits, 0, solution);

        return res;
    }
    void dfs(string &digits, int index, string &solution)
    {
        if (index == digits.size())
        {
            res.push_back(solution);
            return;
        }
        else
        {
            for (auto &r : key[digits[index] - '0'])
            {
                solution.push_back(r);
                dfs(digits, index+1, solution);
                solution.pop_back();
            }
        }
    }
    vector<string> res;
    string key[10] = {"", 
        "", "abc", "def", 
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz"};
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39272421

LeetCode: Maximum Subarray

题目

https://oj.leetcode.com/problems/maximum-subarray/

分析

  1. 一开始想用穷举法找出所有的子序列, 并求出最大的和,然后结果是超时了。

  2. 后来发现这道题是一道很巧妙的DP题,

首先我们先来求另一个问题, “数组A[]中包含最后一个元素的最大连续子序列的和为多少?”

包含最后一个元素的最大连续子序列的和有两种情况: 

最后一个元素和前面的元素构成一个子序列

或者最后一个元素自成一个子序列。

递归的求包含最后一个元素的最大连续子序列就是  f(n) = max(f(n-1), A[n]);

以此类推, 每个元素为结尾的最大连续子序列的和就求出来了,

  1. 在2中, 其中的最大值便是整个数列的最大连续子序列的和。

把上面递归用改写为递归的形式, 就是最终结果了。

代码

class Solution
{
public:
    int maxSubArray(int A[], int n)
    {
        int sum[n], res;

        sum[0] = A[0];
        res = sum[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] = max(A[i], sum[i-1] + A[i]);
            res = max(res, sum[i]);
        }

        return res;
    }
};

参考

http://blog.csdn.net/v_july_v/article/details/6444021

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39271637

LeetCode: Regular Expression Mathing

题目

https://oj.leetcode.com/problems/regular-expression-matching/

分析

  1. 普通字符和'.'的匹配很好解决, 直接匹配即可, 关键是'*'如何进行匹配

  2. 一开始我的想法是, ‘*’尽可能“贪婪”的匹配多个字符, 直到不再匹配为止。 然后在 s = "aaa", p = "a*a" 这个测试用例上跪了。。。

  3. 这说明'*'并不是尽可能多的进行匹配, 而是匹配一定数量的字符。 那么这个“一定数量”到底应该如何确定呢? 

可以这样确定, 每匹配一个字符, 就跳过'*'继续匹配下面的, 成功了就返回true, 如果失败了就返回'*'处再多匹配一个字符, 再跳过'*'匹配后面的……以此类推。 显然这的返回现场就是通过递归算法的DFS来实现了。

代码

class Solution
{
public:
    bool isMatch(const char *s, const char *p)
    {
        //递归基
        if (*p == '\0')
            return (*s == '\0');

        //如果下一个字符不是'*'
        if (*(p+1) != '*')
            return (*s != '\0') && (*s == *p || *p == '.') && isMatch(s+1, p+1);

        //如果下一个字符是'*'
        if (isMatch(s, p+2))
            return true;
        while ((*s != '\0') && (*s == *p || *p == '.')) 
        {
            s++;
            if (isMatch(s, p+2))
                return true;
        }
        return false;
    }
};

参考

http://leetcode.com/2011/09/regular-expression-matching.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39185791

LeetCode: Median of Two Sorted Arrays

题目

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

分析

如果这道题的时间复杂度要求是O(m+n)的话, 就很简单了, 直接merge之后找出中位数即可。 

如果时间复杂度要求为O(log(m+n))的话, 可以把这道题转化为求第k小的问题。

1. 如果(m+n)是奇数的话, 中位数就是第(m+n)/2+1小; 如果(m+n)是偶数, 中位数就是第(m+n)/2小和第(m+n)/2+1小的平均数。

  1. 然后问题是如何求解第k小的数?

           假设有两个数组:   

           A[0], A[1], ......A[m-1]

           B[0], B[1], ......B[n-1]

           两数组合并后为

           C[0], C[1], ...... C[m+n-1]

           不妨假设m和n都大于k/2, 比较A[k/2-1]和B[k/2-1], 

           如果A[k/2-1] < B[k/2-1], 那么A[k/2-1]及其左侧的元素一定小于合并后的第k小的那个数(即C[k-1])

           为什么?

           可以通过反证来证明, 

           假设A[k/2-1]等于合并后第k小元素 (即C[k-1]), 

           那么实际最多有多少个元素比A[k/2-1]小呢? A[0], A[1]......A[k/2-2]以及B[0], B[1].......B[k/2-2], 共k-2个元素。 也就是说A[k/2-1]最好情况下是第k-1小元素(即C[k-2])

           这与假设矛盾, 因此假设不成立

           因此可以说, A[k/2-1]及其左侧元素一定小于合并后的第k小那个数, 这样就可以排除掉这一范围的数,从而缩小了问题规模。

  1. 再来考虑递归基

           当A为空或者B为空时, 返回B[k-1]或A[k-1]

           当k == 1时, 返回A[0]和B[0]中较小的那个数

           当A[k/2-1] == B[k/2-1]时, 返回A[k/2-1]

           否则的话, 就递归缩小问题规模。

代码

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

    double findKth(int A[], int m, int B[], int n, int k)
    {
        if (m > n)
            return findKth(B, n, A, m, k);
        else if (m == 0)
            return B[k-1];
        else if (k == 1)
            return min(A[0], B[0]);
        else
        {
            int ALeftCount = min(k / 2, m);
            int BLeftCount = k - ALeftCount;

            if (A[ALeftCount-1] == B[BLeftCount-1])
                return A[ALeftCount-1];
            else if (A[ALeftCount-1] < B[BLeftCount-1])
                return findKth(A+ALeftCount, m-ALeftCount, 
                        B, n, k-ALeftCount);
            else//A[ALeftCount-1] > B[BLeftCount-1]]
                return findKth(A, m, 
                        B+BLeftCount, n-BLeftCount, k-BLeftCount);
        }
    }
};

参考

http://blog.csdn.net/yutianzuijin/article/details/11499917

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39156991

『转』LeetCode题目难度频率分布

20130909144941265

             

1 Two Sum 2 5 array sort

        set Two Pointers

2 Add Two Numbers 3 4 linked list Two Pointers

          Math

3 Longest Substring Without Repeating Characters 3 2 string Two Pointers

        hashtable  

4 Median of Two Sorted Arrays 5 3 array Binary Search

5 Longest Palindromic Substring 4 2 string  

6 ZigZag Conversion 3 1 string  

7 Reverse Integer 2 3   Math

8 String to Integer (atoi) 2 5 string Math

9 Palindrome Number 2 2   Math

10 Regular Expression Matching 5 3 string Recursion

          DP

11 Container With Most Water 3 2 array Two Pointers

12 Integer to Roman 3 4   Math

13 Roman to Integer 2 4   Math

14 Longest Common Prefix 2 1 string  

15 3Sum 3 5 array Two Pointers

16 3Sum Closest 3 1 array Two Pointers

17 Letter Combinations of a Phone Number 3 3 string DFS

18 4Sum 3 2 array  

19 Remove Nth Node From End of List 2 3 linked list Two Pointers

20 Valid Parentheses 2 5 string Stack

21 Merge Two Sorted Lists 2 5 linked list sort

          Two Pointers

          merge

22 Generate Parentheses 3 4 string DFS

23 Merge k Sorted Lists 3 4 linked list sort

        heap Two Pointers

          merge

24 Swap Nodes in Pairs 2 4 linked list  

25 Reverse Nodes in k-Group 4 2 linked list Recursion

          Two Pointers

26 Remove Duplicates from Sorted Array 1 3 array Two Pointers

27 Remove Element 1 4 array Two Pointers

28 Implement strStr() 4 5 string Two Pointers

          KMP

          rolling hash

29 Divide Two Integers 4 3   Binary Search

          Math

30 Substring with Concatenation of All Words 3 1 string Two Pointers

31 Next Permutation 5 2 array permutation

32 Longest Valid Parentheses 4 1 string DP

33 Search in Rotated Sorted Array 4 3 array Binary Search

34 Search for a Range 4 3 array Binary Search

35 Search Insert Position 2 2 array  

36 Valid Sudoku 2 2 array  

37 Sudoku Solver 4 2 array DFS

38 Count and Say 2 2 string Two Pointers

39 Combination Sum 3 3 array combination

40 Combination Sum II 4 2 array combination

41 First Missing Positive 5 2 array sort

42 Trapping Rain Water 4 2 array Two Pointers

          Stack

43 Multiply Strings 4 3 string Two Pointers

          Math

44 Wildcard Matching 5 3 string Recursion

          DP

          greedy

45 Jump Game II 4 2 array  

46 Permutations 3 4 array permutation

47 Permutations II 4 2 array permutation

48 Rotate Image 4 2 array  

49 Anagrams 3 4 string  

        hashtable  

50 Pow(x, n) 3 5   Binary Search

          Math

51 N-Queens 4 3 array DFS

52 N-Queens II 4 3 array DFS

53 Maximum Subarray 3 3 array DP

54 Spiral Matrix 4 2 array  

55 Jump Game 3 2 array  

56 Merge Intervals 4 5 array sort

        linked list merge

        red-black tree  

57 Insert Interval 4 5 array sort

        linked list merge

        red-black tree  

58 Length of Last Word 1 1 string  

59 Spiral Matrix II 3 2 array  

60 Permutation Sequence 5 1   permutation

          Math

61 Rotate List 3 2 linked list Two Pointers

62 Unique Paths 2 3 array DP

63 Unique Paths II 3 3 array DP

64 Minimum Path Sum 3 3 array DP

65 Valid Number 2 5 string Math

66 Plus One 1 2 array Math

67 Add Binary 2 4 string Two Pointers

          Math

68 Text Justification 4 2 string  

69 Sqrt(x) 4 4   Binary Search

70 Climbing Stairs 2 5   DP

71 Simplify Path 3 1 string Stack

72 Edit Distance 4 3 string DP

73 Set Matrix Zeroes 3 5 array  

74 Search a 2D Matrix 3 3 array Binary Search

75 Sort Colors 4 2 array sort

          Two Pointers

76 Minimum Window Substring 4 2 string Two Pointers

77 Combinations 3 4   combination

78 Subsets 3 4 array Recursion

          combination

79 Word Search 3 4 array DFS

80 Remove Duplicates from Sorted Array II 2 2 array Two Pointers

81 Search in Rotated Sorted Array II 5 3 array Binary Search

82 Remove Duplicates from Sorted List II 3 3 linked list Recursion

          Two Pointers

83 Remove Duplicates from Sorted List 1 3 linked list  

84 Largest Rectangle in Histogram 5 2 array Stack

85 Maximal Rectangle 5 1 array DP

          Stack

86 Partition List 3 3 linked list Two Pointers

87 Scramble String 5 2 string Recursion

          DP

88 Merge Sorted Array 2 5 array Two Pointers

          merge

89 Gray Code 4 2   combination

90 Subsets II 4 2 array Recursion

          combination

91 Decode Ways 3 4 string Recursion

          DP

92 Reverse Linked List II 3 2 linked list Two Pointers

93 Restore IP Addresses 3 3 string DFS

94 Binary Tree Inorder Traversal 4 3 tree Recursion

        hashtable morris

          Stack

95 Unique Binary Search Trees II 4 1 tree DP

          DFS

96 Unique Binary Search Trees 3 1 tree DP

97 Interleaving String 5 2 string Recursion

          DP

98 Validate Binary Search Tree 3 5 tree DFS

99 Recover Binary Search Tree 4 2 tree DFS

100 Same Tree 1 1 tree DFS

101 Symmetric Tree 1 2 tree DFS

102 Binary Tree Level Order Traversal 3 4 tree BFS

103 Binary Tree Zigzag Level Order Traversal 4 3 queue BFS

        tree Stack

104 Maximum Depth of Binary Tree 1 1 tree DFS

105 Construct Binary Tree from Preorder and Inorder Tr 3 3 array DFS

        tree  

106 Construct Binary Tree from Inorder and Postorder T 3 3 array DFS

        tree  

107 Binary Tree Level Order Traversal II 3 1 tree BFS

108 Convert Sorted Array to Binary Search Tree 2 3 tree DFS

109 Convert Sorted List to Binary Search Tree 4 3 linked list Recursion

          Two Pointers

110 Balanced Binary Tree 1 2 tree DFS

111 Minimum Depth of Binary Tree 1 1 tree DFS

112 Path Sum 1 3 tree DFS

113 Path Sum II 2 2 tree DFS

114 Flatten Binary Tree to Linked List 3 3 tree Recursion

          Stack

115 Distinct Subsequences 4 2 string DP

116 Populating Next Right Pointers in Each Node 3 3 tree DFS

117 Populating Next Right Pointers in Each Node II 4 2 tree DFS

118 Pascal's Triangle 2 1 array  

119 Pascal's Triangle II 2 1 array  

120 Triangle 3 1 array DP

121 Best Time to Buy and Sell Stock 2 1 array DP

122 Best Time to Buy and Sell Stock II 3 1 array greedy

123 Best Time to Buy and Sell Stock III 4 1 array DP

124 Binary Tree Maximum Path Sum 4 2 tree DFS

125 Valid Palindrome 2 5 string Two Pointers

126 Word Ladder II 1 1    

127 Word Ladder 3 5 graph BFS

          shortest path

128 Longest Consecutive Sequence 4 3 array  

129 Sum Root to Leaf Numbers 2 4 tree DFS

130 Surrounded Regions 4 3 array BFS

          DFS

131 Palindrome Partitioning 3 4 string DFS

132 Palindrome Partitioning II 4 3 string DP

转自:

http://blog.csdn.net/yutianzuijin/article/details/11477603

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39155255

LeetCode: Reverse Words in a String

题目:

https://oj.leetcode.com/problems/reverse-words-in-a-string/

分析:

解法一:(相比较更麻烦点)

  1. 运用栈来解题, 先把s中的一个个单词解析出来压到栈里, 然后再出栈重组成s

  2. 有一些特殊的边界需要考虑, 比如连续出现两个空格, 单词的头尾部出现空格等等, 这些情况需要特殊处理一下。

解法二:(更巧妙, 推荐)

从后向前进行循环

    处理空格部分

    如果结果res非空, 插入一个空格

    处理非空格部分

代码:

解法一:

class Solution
{
public:
    void reverseWords(string &s)
    {
        if (s.empty())
            return;

        string word;
        stack<string> stk;
        s.push_back(' ');
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != ' ')
                word.push_back(s[i]);
            else if (i > 0 && s[i] == ' ' && s[i-1] != ' ')
            {
                stk.push(word);
                word.clear();
            }
        }

        s.clear();
        if (stk.empty())
            return;
        while (true)
        {
            s += stk.top();
            stk.pop();
            if (stk.empty())
                break;
            else
                s.push_back(' ');
        }
        return;
    }
};

解法二:

class Solution
{
public:
    void reverseWords(string &s)
    {
        string res;

        int i = s.size() - 1;
        while (true)
        {
            while (s[i] == ' ' && i >= 0) 
                i--;
            if (i < 0) break;

            if (!res.empty())
                res.push_back(' ');

            string temp;
            while (s[i] != ' ' && i >= 0) 
            {
                temp.push_back(s[i]);
                i--;
            }
            reverse(temp.begin(), temp.end());
            res += temp;
            if (i < 0) break;
        }
        s = res;
    }
};

参考:

http://blog.csdn.net/kenden23/article/details/20701069

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39138373

LeetCode: Palindrome Partition

题目

https://oj.leetcode.com/problems/palindrome-partitioning/

分析

DFS来解决这个问题。

代码

class Solution
{
public:
    vector<vector<string>> partition(string s)
    {
        if (s.empty())
            return res;

        dfs(s, 0);

        return res;
    }

    void dfs(const string &s, int index)
    {
        if (index == s.size())
            res.push_back(solution);
        else
        {
            for (int i = index; i < s.size(); i++)
            {
                string substr = s.substr(index, i-index+1);
                if (isPalindrome(substr))
                {
                    solution.push_back(substr);
                    dfs(s, i+1);
                    solution.pop_back();
                }
            }
        }
    }

    bool isPalindrome(const string &s)
    {
        int left = 0;
        int right = s.size() - 1;

        while (left <= right)
        {
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

    vector<vector<string>> res;
    vector<string> solution;
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39064961