[LeetCode]Array主题系列{35,39,40,48题}

1. 内容介绍

开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,反思}的格式来记录,供日后复习和反思[注:有些题目的解法比较单一,就没有优化过程]。题目的顺序按照leetcode给出的题目顺序,有些题目在并不是按照题目本身序号顺序排列的,也不是严格按照难易程度来排列的。

因此,这篇文章并不具有很强的归类总结性,归类总结性知识将会在其他文章记录,本篇重点在记录解题过程中的思路,希望能对自己有所启发。

2. 题目和解题过程

2.1 Search Insert Position

  • 题目:Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0
  • 分析:题目涉及到对有序数组的搜索,也暗含了使用二分搜索。
  • 初解:提前判断期望值是否在数组的数据范围之内,否则根据情况返回首索引或者尾索引,如果在数组范围内则使用二分搜索对数组进行搜索期望值,停止条件是:1.在mid出找到与期望值相同的值,返回mid索引;2.二分搜索的首尾指针交错,返回首指针的索引。
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.size()==0||target<nums.front())
            return 0;
        if(target>nums.back())
            return nums.size();
        int start=0, end=nums.size()-1, mid=0;
        while(start<=end)
        {
            mid = (start+end)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]>target)
                end = mid-1;
            else start = mid+1;
        }
        return start;
    }
};
  • 初解结果:
  • 反思:我还能说什么呢,二分搜索很厉害。。。

2.2 Combination Sum

  • 题目:Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.The same repeated number may be chosen from C unlimited number of times.Note:
    • All numbers (including target) will be positive integers.
    • The solution set must not contain duplicate combinations.

     For example, given candidate set [2, 3, 6, 7] and target 7,  A solution set is:  [ [7], [2, 2, 3] ]

  • 分析:题目本质是在数组中选择任意几个数,使得求和结果等于期望值,但是不同的是题目给的值序列是一个“隐形”值序列,其中可以衍生许多其他值序列,比如:对于2,期望值是7的话,那么衍生的值就有4(2*2)和6(2*3)。为什么没有把所有必须的数据给出来?隐藏的数据暗示了搜索空间的无限性,对应着需要对搜索空间进行剪枝操作,也就是说程序的求解过程很有可能是通过回溯法以递归来实现的。
  • 初解:先考虑以递归方式来解决问题,当给定一个期望值x,如果存在一个集合s,里面的数之和等于期望值x,那么根据题目条件,集合s里面的每个数都来自给定的候选数字集合。因此,反向考虑问题时,使用期望值减去集合s中每个候选数字的差值,如果在候选数字值的范围内,那么也是可以由来自于候选数字集合的一个子集求和而成。 通过递归分解这个期望值,最终能够搜索各种求和情况。最终再对结果中重复的解进行过滤化处理即可。该方法的时间复杂度近似是O(ax),a是递归深度,x是候选数字数目。
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> altered_candidates;
        vector<vector<int>> res;
        sort(candidates.begin(), candidates.end());
        int tail=0;
        while(candidates[tail]<=target&&tail<candidates.size())
            ++tail;
        if(tail==0)
            return res;
        altered_candidates.insert(altered_candidates.end(), candidates.begin(), candidates.begin()+tail);
        map<int, vector<vector<int>>> val_member;
        find_res(altered_candidates, val_member, target);
        res = val_member[target];
        deduplicate(res);
        return res;
    }
    void deduplicate(vector<vector<int>>& res)
    {
        set<vector<int>> set_res;
        for(auto begin_iter=res.begin(); begin_iter!=res.end(); ++begin_iter)
        {
            sort(begin_iter->begin(), begin_iter->end());//排序有助于set自动对比和去重
            set_res.insert(*begin_iter);
        }
        res.clear();
        res.insert(res.end(), set_res.begin(), set_res.end());
    }
    void generate_new_val(map<int, vector<vector<int>>>& val_seq, int& target, int& new_target, int& val)
    {
        auto& seq_vec = val_seq[new_target];
        for(auto seq_iter = seq_vec.begin(); seq_iter!=seq_vec.end(); ++seq_iter)
        {
            vector<int> val_tmp = *seq_iter;
            val_tmp.push_back(val);
            val_seq[target].push_back(val_tmp);
        }
    }
    void find_res(vector<int>& nums, map<int, vector<vector<int>>>& val_seq, int target)
    {
        for(auto val:nums)
        {
            int new_target = target - val;//分解期望值
            if(new_target==0)//如果恰好分解
            {
                val_seq[target].push_back(vector<int>{val});
                continue;
            }
            if(new_target<nums.front())//如果分解值不在范围内
                continue;
            if(val_seq.find(new_target)!=val_seq.end())//已经求解过该期望值
                generate_new_val(val_seq, target, new_target, val);
            else //尚未求解该期望值
            {
                find_res(nums, val_seq, new_target);
                generate_new_val(val_seq, target, new_target, val);
            }
        }
    }
};
  • 初解结果:
  • 优化解法:根据初解的思路来看,要想求解就必须搜索所有可能的值,但是搜索的过程中会出现重复可行解,而搜索和剔除这些重复可行解的过程带来额外的时间,因此优化思路是在搜索方式上做改变,使得求解的方式不可能出现重复可行解,这样就避免了上述两个额外过程。具体思路如下:所谓重复可行解就是指在前一个可行解中出现的所有元素,在后一个可行解中又全部出现了,但是仅仅是元素的顺序不一样,为了使得不会重复计算出可行解,我们固定元素出现的顺序,针对所有元素,考虑第一个元素出现在哪些可行解中,计算完之后,排除该元素,即其他的可行解将不再包含该元素,然后依次计算其他元素的可行解情况,以此类推。
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        sort(candidates.begin(), candidates.end());
        if(candidates.front() > target)
            return res;
        vector<int> index_result;
        search_result(0, candidates, res, target, index_result);
        return res;
    }
    void search_result(int index, vector<int>& candidates, vector<vector<int>>& res, int target, vector<int>& index_result)
    {
        while(index < candidates.size())
        {
            int val = candidates[index];
            if(val > target)
                break;
            int times = target / val, rest = target % val;
            while(times != 0)
            {
                vector<int> tmp_result(times, val);
                tmp_result.insert(tmp_result.end(), index_result.begin(), index_result.end());
                if(rest == 0)
                    res.push_back(tmp_result);    
                else
                    search_result(index+1, candidates, res, rest, tmp_result);   
                --times;
                rest = target - times * val;
            }
            ++index;
        }
    }
};
  • 优化结果:
  • 反思:求解需要对给定数据进行组合判断是否符合解的条件时,为了避免重复组合相同的数据,应该对数据出现的顺序进行固定,进而使用递归或者迭代方式来计算。

 2.3 Combination Sum II

  • 题目:Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.Each number in C may only be used once in the combination.Note:
    • All numbers (including target) will be positive integers.
    • The solution set must not contain duplicate combinations.

     For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,  A solution set is:  [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

  • 分析:题目要求不重复的使用给定元素的组合来匹配期望值,因此与上一题的差别仅仅是元素不可重复使用但是可能会有重复元素出现,因此针对某个元素计算出可行解之后,需要对相同的元素进行跳过处理,否则会重复计算。
  • 初解:按照上一题总结的方法,先对数据进行排序,然后针对每个不重复的元素进行递归向后计算可行解,在针对特定元素向后计算时,必须搜索所有可行解,也就是允许跳过某些元素向后搜索。
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        sort(candidates.begin(),candidates.end());
        if(candidates.front() > target)
            return res;
        vector<int> tmp;
        search_result(0, target, candidates, tmp, res);
        return res;
    }
    void search_result(int index, int target, vector<int>& candidates, vector<int>& index_result, vector<vector<int>>& res)
    {
        while(index < candidates.size())
        {
            int next_target = target - candidates[index];
            if(next_target < 0)
                return;
            else if(next_target == 0)
            {
                vector<int> final_res(index_result);
                final_res.push_back(candidates[index]);
                res.push_back(final_res);
            }
            else
            {
                vector<int> tmp_result{index_result};
                tmp_result.push_back(candidates[index]);
                search_result(index+1, next_target, candidates, tmp_result, res);
            }
            while(index+1 < candidates.size() && candidates[index]==candidates[index+1])
                ++index;
            ++index;
        }   
    }
};
  • 初解结果:
  • 反思:看似解空间纷繁复杂的情况需要先对解元素进行固定处理,这样将搜索的范围控制在了解元素范围上,从而可以结构化处理和避免重复计算;递归程序的设计需要考虑递归的行为(可能是有多种递归分支的)和停止条件,而且递归程序绝对是单个函数就能处理。

2.4 Rotate Image

  • 题目:You are given an n x n 2D matrix representing an image.Rotate the image by 90 degrees (clockwise).Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ]
  • 分析:题目要求对矩阵进行90度旋转,如果不考虑空间要求,可以将第一行放到最后一列,第二行放到倒数第二列,以此类推就可完成转置。90度转置本质上可以看做是坐标变换,而最简单的坐标变换就是对称变换,观察转置前后每个元素的坐标变化可以发现:如果先把每行元素做对称变换,得到的结果在每一列上与最终结果正好是逆序的,因此,在此基础上再做逆序变换即可。
  • 初解:对每行数据做对称变换,在对每列数据做逆序变换。
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int N = matrix.size();
        if(N == 0)
            return;
        for(int row = 0; row < N-1; ++row)
            for(int col = 0; col < N-row-1; ++col)
            {
                int new_col = -1 * row + N - 1;
                int new_row = -1 * col + N - 1;
                swap(matrix[row][col], matrix[new_row][new_col]);
            }
        for(int col = 0; col < N; ++col)
        {
            int start_row = 0, end_row = N-1;
            while(start_row < end_row)
            {
                swap(matrix[start_row][col], matrix[end_row][col]);
                ++start_row;
                --end_row;
            }
        }
    }
    void swap(int& a, int& b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
};
  • 初解结果:
  • 反思:矩阵转置本质上是坐标变换,利用坐标系来研究变化规律可以借用基本变换工具:对称变换。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏林德熙的博客

C# 搜索算法 Bdf 算法

数据“aaacbc”,匹配“abc”,也是匹配,因为数据按照“abc”的顺序,算法不管数据有多长,只要数据存在和匹配相同的顺序,那么就匹配。

1111
来自专栏程序员叨叨叨

5.1 基本数据类型第 5 章 CG 数据类型

本章将着重介绍Cg语言中预定义的内置(built in)的、或称为基本(primitive)的数据类型。然后介绍可以用来声明对象的各类类型,主要是数组和结构类型...

1113
来自专栏专知

关关的刷题日记13——Leetcode 414. Third Maximum Number

关小刷刷题13 – Leetcode 414. Third Maximum Number 题目 Given a non-empty array of integ...

3469
来自专栏我的博客

算法复杂度

算法复杂度 分为时间复杂度和空间复杂度。即算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。 时间复杂度 在计算机科学中,算法的时间复杂...

3306
来自专栏C/C++基础

最大子数组问题

炒股的人都知道,股票的价格是不稳定的。若想从炒股中赚钱,必须“低买高卖”,就是低价买进,高价卖出,赚取中间差价。那么给定一段时间,每一天都对应着不同的股价,如何...

1292
来自专栏用户2442861的专栏

**LeetCode—Word Break

http://blog.csdn.net/xietingcandice/article/details/43705383

1542
来自专栏算法channel

冒泡排序到快速排序做的那些优化

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

4139
来自专栏有趣的Python

玩转算法面试:(二)面试中的复杂度分析

面试中的时间复杂度分析 到底什么是大O n表示数据规模 O(f(n)) fn是关于n的一个函数。表示运行算法所需要执行的指令数,和f(n)成正比。 ? 常见...

8485
来自专栏大数据风控

Python中如何进行数据分组

数据分组 根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间进行研究,以揭示其内在联系和规律性。 cut 函数: cut(series,...

3247
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

2947

扫码关注云+社区

领取腾讯云代金券