5. 分治法实践

分治法实践


  • 最近整理了之前的分治法学习笔记，就寻思着在Leetcode上刷刷相关的题目，并有一些心得体会

    Leetcode分治法专题传送门

    刷题进度与解法

    • 目前用分治法写了6道算法题，2道Easy，3道Medium，1道Hard,选取了5道来做分析

    169. 求众数 [Easy]

    • 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

    问题分析:数组中的众数必定是两个子数组中众数中的一个

    • 最小子问题:当数组中只有一个数字时，该数字为众数
    class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.size() <= 1) return nums[0];
        int mid = nums.size()/2;
        vector<int> left(nums.begin(),nums.begin()+mid);
        vector<int> right(nums.begin()+mid,nums.end());
        int leftMax = majorityElement(left);
        int rightMax = majorityElement(right);
        if (leftMax == rightMax) return leftMax;
        else {
            int leftCount = count(nums.begin(),nums.end(),leftMax);
            int rightCount = count(nums.begin(),nums.end(),rightMax);
            return leftCount>rightCount ? leftMax : rightMax;
        }
                           
    }
};

    53. 最大子序和 [Easy]

    • 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

    问题分析:最大和子数组必定是左右两个子数组中的最大和子数组和跨越中间的最大和子数组中的一个

    • 最小子问题:当数组中只有一个数字时，该数的值即为最大子数组的和
    class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        int mid = nums.size()/2;
        vector<int> left(nums.begin(),nums.begin()+mid);
        vector<int> right(nums.begin()+mid,nums.end());
        int leftMax = maxSubArray(left);
        int rightMax = maxSubArray(right);
        int midMax = searchMidMax(nums,mid);
        return max(leftMax,max(rightMax,midMax));
    }
    
    int searchMidMax(vector<int>& nums,int mid) {
        if (nums.size() == 1) return nums[0];
        int maxl = nums[mid];
        int maxr = nums[mid];
        int sum = 0;
        for (int i = mid; i>=0; --i) {
            sum += nums[i];
            if (sum > maxl)
                maxl = sum;
        }
        sum = 0;
        for (int j = mid; j<nums.size(); ++j) {
            sum += nums[j];
            if (sum > maxr)
                maxr = sum;
        }
        return (maxr+maxl-nums[mid]);
        
    }
};

    241. 为运算表达式设计优先级 [Medium]

    • 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

    问题分析:式子的结果必定是某一个符号左右两边式子结果的乘积

    • 最小子问题:当式子中只有一个数字时，它的值等于该数字
    class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> result;
        int max = input.size();
        for (int i = 0; i<max; ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                string leftString = input.substr(0,i);
                string rightString = input.substr(i+1);
                // printf("%s\n%s\n",leftString.c_str(),rightString.c_str());
                vector<int> left = diffWaysToCompute(leftString);
                vector<int> right = diffWaysToCompute(rightString);
                for (int j = 0; j<left.size(); ++j)
                    for (int k = 0; k<right.size(); ++k) {
                        switch (input[i]) {
                            case '+':{
                                result.push_back(left[j] + right[k]);
                                break;
                            }
                            case '-':{
                                result.push_back(left[j] - right[k]);
                                break;
                            }
                            case '*':{
                                result.push_back(left[j] * right[k]);
                                break;
                            }
                        }
                    }
                
            }
        }
        if (result.size() == 0) result.push_back(atoi(input.c_str()));
        sort(result.begin(),result.end());
        return result;
    }
};

    240. 搜索二维矩阵 II [Medium]

    • 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
      • 每行的元素从左到右升序排列。
      • 每列的元素从上到下升序排列。

    问题分析:该元素是否存在于二位数组中取决于它在两个子数组中是否存在

    • 最小子问题:当数组中只有一行时，判断该数字在此行中是否存在

    • 第一版分治法实现的代码Timeout了

    class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 1) return SearchVector(matrix[0],target);
        if (matrix.size() == 0) return false;
        int mid = matrix.size()/2;
        vector<vector<int>> left(matrix.begin(),matrix.begin()+mid);
        vector<vector<int>> right(matrix.begin()+mid,matrix.end());
        return (searchMatrix(left,target) || searchMatrix(right,target));
    }
    bool SearchVector(vector<int>& aVector, int target) {
        vector<int>::iterator iter = find(aVector.begin(),aVector.end(),target);
        if (iter == aVector.end()) return false;
        else return true;
    }
    
    
};
    • 通过遍历实现的代码
    class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 1) return SearchVector(matrix[0],target);
        if (matrix.size() == 0) return false;
        int max = matrix.size();
        for (int i = max-1; i>=0; --i) {
            if (matrix[i][0] <= target) {
                if (SearchVector(matrix[i],target) == true)
                    return true;
            }
        }
        return false;
    }
        
    bool SearchVector(vector<int>& aVector, int target) {
        vector<int>::iterator iter = find(aVector.begin(),aVector.end(),target);
        if (iter == aVector.end()) return false;
        else return true;
    } 
};

    23. 合并K个排序链表 [Hard]

    • 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

    问题分析:最终的排序链表为两个链表的合并

    • 最小子问题:合并两个排序链表
    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 1) return lists[0];
        if (lists.size() == 0) return NULL;
        lists[0] = mergeTwoLists(lists[0],lists[1]);
        lists.erase(lists.begin()+1);
        return mergeKLists(lists);
        
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL)
            return l2;
        else if(l2 == NULL)
            return l1;
        ListNode *p = l1;
        ListNode *q = l2;
        ListNode *head;
        ListNode *l3;
        if (p->val <= q->val) {
            l3 = p;
            p = p->next;
        }
        else {
            l3 = q;
            q = q->next;
        }
        head = l3;
        while (p != NULL && q != NULL) {
            if (p->val > q->val) {
                l3->next = q;
                l3 = q;
                q = q->next;
            }
            else {
                l3->next = p;
                l3 = p;
                p = p->next;
                }
        }
        l3->next = (p == NULL) ? q : p;
        return head;
    }
};

    感想与总结

    • 1.从各题的问题分析中不难发现，这些问题的解都是由两个或三个子问题的解组合而来，所以分治法的实质，用一句谚语来说就是大事化小，小事化了

    • 2.拆分问题都是有套路的，在此提供两种思路：

      • 1)将问题拆分为两等分(类似于归并排序) 例如:求众数，最大子序和，搜索二维矩阵
      • 2)将问题逐条拆分，每次减少一个元素 例如:为运算表达式设计优先级，合并K个排序链表(此题也能用方法1拆分，可能效率会更高)

    • 3.在拆分问题时，方法1能减少递归次数，但空间复杂度较高，方法2需要额外调用的空间较少，但递归次数多，使用的时候需酌情考虑。

    • 4.分治法的弊病:在分治法定义中就提及了递归，也就是说，分治必定递归，这也就造就了分治法有空间复杂度高的问题，递归次数越多占用空间越大，在Leetcode刷题中，分配空间对时间的影响也非常大(在搜索二维矩阵中体现得非常突出)，所以这些题的优秀解法中极少使用分治法。

    • 5.虽然分治法并非一种优质解法，但其特点在于简单方便，代码量极少，比较适合用于需要快速解决小型问题的地方

    回复 引用 0
回复
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开，我们正在尝试重连，请耐心等待