怎样应对IT面试与笔试-(十)

怎样应对IT面试与笔试-(十)

Dynamic Programming(动态规划) 53. Maximum Subarray 最大和子数组(元素连续) 例如题目中给出的例子: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. 代码: class Solution { public: int maxSubArray(ve...

Dynamic Programming(动态规划)

53. Maximum Subarray

最大和子数组(元素连续)
例如题目中给出的例子:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

代码:

class Solution {
public:
    int maxSubArray(vector& nums) {
        int currentSum = 0, maxvalue = INT_MIN;
        for(int i = 0; i 

思路:
currentSum 是加到第i个元素为止的最大和,maxvalue 是以0,1,2,3……i个元素结尾的currentSum中最大的currentSum

53.png

动态规划一般解题思路是
(1)将原问题分解为子问题
(2)确定状态和初始条件
(3)构造状态转移方程
一开始接触动态规划,建议小伙伴们将注意力集中在怎么样将原问题规模缩小为子问题,多接触一些不同类型动归题目,多动手画图表或示意图,培养分解问题的直觉。

Greedy(贪婪算法)

55. Jump Game

给定一个非负整数的数组,每个数字表示在当前位置的基础上最多可以走的步数,求判断能不能到达最后一个位置。
Input: [2,3,1,1,4]
在第一个元素2处,可以走到第二个元素3,也可以走到第三个元素1

class Solution {
public:
    bool canJump(vector& nums) {
        //reach为以当前元素为起点所能达到的最远元素位置
        int n = nums.size(), reach = 0;
        for (int i = 0; i  reach || reach >= n - 1) break;
            //计算当前元素所能到达的最远元素位置
            reach = max(reach, i + nums[i]);
            cout= n - 1;
    }
};

贪婪算法,顾名思义,就是考虑当前每个元素所能达到的最远距离,满足条件就可以返回,下面是例子[2,3,1,1,4]的示意图

55 (1).png

遍历数组中的每个元素,查看每个元素所能到达的最远距离,满足条件就返回,继续看例子[3,2,1,0,4]的示意图:

55-1.png

怎样应对IT面试与笔试-(一)
怎样应对IT面试与笔试-(二)
怎样应对IT面试与笔试-(三)
怎样应对IT面试与笔试-(四)
怎样应对IT面试与笔试-(五)
怎样应对IT面试与笔试-(五-1)
怎样应对IT面试与笔试-(六)
怎样应对IT面试与笔试-(七)
怎样应对IT面试与笔试-(八)
怎样应对IT面试与笔试-(九)
怎样应对IT面试与笔试-(十)
怎样应对IT面试与笔试-(十一)
怎样应对IT面试与笔试-(十二)
怎样应对IT面试与笔试-(十三)
怎样应对IT面试与笔试-(十四)
怎样应对IT面试与笔试-(十五)
怎样应对IT面试与笔试-(十六)

文章来源于互联网:怎样应对IT面试与笔试-(十)

0

评论0

鱼翔浅底,鹰击长空,驼走大漠
没有账号? 注册  忘记密码?