LeetCode-No-62-&-No-63-&-No-64

发表于 2020-02-17 分类于算法 Valine：

不同路径 I & II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。说明：m 和 n 的值均不超过 100。

示例 1:

输入: [ [0,0,0], [0,1,0], [0,0,0]] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径： 1. 向右 - 向右 - 向下 - 向下 2. 向下 - 向下 - 向右 - 向右

题目分析

对没有障碍物的情况

小学数学思想：走到终点总共需要的操作是 m-1个向下和 n-1个向右，那么即是一个组合数问题，在总共m-1+n-1的操作步中，选取m-1个操作步放置向下操作，剩下的放向右操作。\[C_{m+n-2}^{m-1}\]

2.当然，组合数是一个阶乘运算，不太理想。再用编程思想去想，直观上是一个深度遍历，或者说回溯遍历的问题。即尝试每种可能的走路方案，走到终点则计数+1。 3.说到回溯，大概率我们可以想想能不能换成动态规划？ ### 动态规划 1. 首先这显然是一个依赖子问题解决的问题。考虑位置[i][j]，有两种方式可以到达这，一种是从[i-1][j]向下，一种是[i][j-1]向右。即[i][j]位置解，即依赖于上和左两个位置的解。

考虑dp[i][j]为到达[i][j]位置的总方法数，那么假如[i-1][j]能往下，则dp[i][j]+=dp[i-1][j]，同理对dp[i][j-1]。
动态规划主体已经清晰了，再可以进一步优化空间细节。我们是按行遍历列，而每行开头的dp[i][0]仅依赖于dp[i-1][0]，即每行开头的dp可由列方向上的第一个生成。而每行的除开头外任意一个，在行方向上又仅依赖于前一个dp[i][j-1]。换句话说，我们至始至终在行方向上只需要一个O（1）的存储空间，保留行前一个的dp结果即可。 即我们只需要一个O（n）的一行大小的列dp组，一个常数大小的行dp存储数即可。
注意细节，dp数组要用long类型= =int会炸

No.64给每个位置加了权值，要求走到右下角的权值累计和最小

同样也是动态规划，到任意一位置的最小权值，必然是由[i-1][j] 和 [i][j-1]的最小值发展而来，以此类推。

题解代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int& obstacleGrid) 
    {
        //动态规划
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        long temp[n];//注意要用long 有样例爆int....
        int i;
        if(obstacleGrid[0][0]!=1)
            temp[0]=1;
        else
            return 0;
        for(i=1;i<n;i++)//首行处理
        {
            if(obstacleGrid[0][i]!=1)
                temp[i]=temp[i-1];
            else
                temp[i]=0;
        }

        int row=1;
        for(;row<m;row++)
        {
            
            if(obstacleGrid[row][0]==1)//首列障碍物处理
                temp[0]=0;

            for(i=1;i<n;i++)
            {   
                if(obstacleGrid[row][i]==1)
                    temp[i]=0;
                else
                    temp[i]+=temp[i-1];
            }
        }
        
        return temp[n-1];    
    }
};

LeetCode-No-69-（牛顿迭代法）

发表于 2020-02-17 分类于算法 Valine：

x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4 输出: 2

示例 2:

输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

题目分析

首先直接计算平方根不太现实，所以这是一个在有序的1~x中查找出平方根的问题。
查找有序整数中的特定值，正常思路即二分查找，实现也简单。
递归缩小求解： \[\sqrt{x}=2*\sqrt{rac{x}{4}}\] 因此可以递归找到易解的小x，然后再回溯整合到原x。注意为什么选择2作为系数进行递归呢？ ——x缩小和放大2的倍数，可以通过位操作实现，效率极高。

递归式为：mySqrt(x)=mySqrt(x2)<<1 4. 针对这个计算平方根的特定问题，有 牛顿迭代法： 牛顿法（英语：Newton's method）又称为牛顿-拉弗森方法（英语：Newton-Raphson method），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数$f(x)$ 的泰勒级数的前面几项来寻找方程的根。

\[x_{k+1}=rac{1}{2}[x_k+rac{x}{x_k}]\] 根据精度要求，$x_k$和$x_{k+1}$收敛后差距小于1即可返回结果。

迭代求解示意：

如上图所示，想求$\sqrt{a}$，图示a=2 先随便取xi=4，然后找到过(xi,yi)的切线，且$f(x)=x^2-a$的导数是$2x$ 即切线方程$f(x)-(x_i^2-a)=2x_i(x-xi)$ 显而易见这个切线与x轴的交点得$x_{i+1}=rac {2x_i^2-(x_i2-a)}{2x_i}= rac{1}{2} (x_i+rac{a}{x_i}) $ 即得$x_{i+1}$比$x_{i}$更接近解$\sqrt{a}$。

牛顿迭代题解代码

class Solution 
{
public:
    int mySqrt(int x) 
    {
        //牛顿迭代
        if(x<=1)
            return x;
        //注意long类型
        long last=x/2;
        long cur =(last+x/last)/2;
        while(abs(last-cur)=1)
        {   
            last=cur;
            cur=(cur +x/ cur) / 2.0 ;
            if(cur<=x/cur)
                return cur;
        }

        return cur;
    }
    
};

LeetCode-No-75

发表于 2020-02-17 分类于算法 Valine：

颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例:

输入:** [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

class Solution {
public:
    void sortColors(vector<int& nums) 
    {
        int left=0;
        int right=nums.size()-1;
        int cur=0;
        while(cur<=right)
        {   
            if(nums[cur]==0)//这个数字是0，移动0区域内，
            {
                swap(nums[cur],nums[left]);
                //假如curleft，left交换过来的值肯定已经被处理过了，但是处理时产生交换，原left指向的，一定是不用处理的吗？
                //jeromememory：准确的说 cur 如果 与 p0 不是指向同一个索引，那 cur 指向的索引值如果发生交换，那交换过来的一定是 1（原因是只有当遍历过的节点有1，p0 和 cur 才不会同步），而 如果索引是 1 刚好也就不用有任何操作，所以可以直接++。
                //假如cur==left==0，没啥好说的，下一个
                //假如cur<left, 可能吗？cur++的机会 = left++的机会
                left++;
            }
            else if(nums[cur]==2)//这个数字是2，移到2区域内
            {
                swap(nums[cur],nums[right]);
                right--;
                //交换过来的值，是右边过来的，cur没处理过，因此还需要对这个位置处理，--抵消++，位置不变
                cur--;
            }
            cur++;
        }
    }
};

LeetCode-No-72

发表于 2020-02-17 分类于算法 Valine：

编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符删除一个字符替换一个字符示例 1:

输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse - rorse (将 'h' 替换为 'r') rorse - rose (删除 'r') rose - ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention - inention (删除 't') inention - enention (将 'i' 替换为 'e') enention - exention (将 'n' 替换为 'x') exention - exection (将 'n' 替换为 'c') exection - execution (插入 'u')

题目分析

和字符串匹配之类的差不多，都是 动态规划，观察子问题状态，考虑转移状态
动态规划 dp[i][j]状态
对比dp[i-1][j]状态时，只需要把i代表的字母删除即可回到dp[i-1][j]
对比dp[i][j-1]状态，因为[i][j-1]代表word1 i位和 word2 j-1 位匹配，因此word2还多个j位没有匹配到，对word1增加操作即可
对比dp[i-1][j-1]状态，双方都多出个第i位和第j位，如果这两个相等，则和dp[i-1][j-1]一样，不相等，则需要一次替换操作。

dp题解代码

class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        //动态规划  dp[i][j]状态
        //对比dp[i-1][j]状态时，只需要把i代表的字母删除即可回到dp[i-1][j]
        //对比dp[i][j-1]状态，因为[i][j-1]代表word1 i位 和 word2 j-1 位匹配，因此word2还多个j位没有匹配到，对word1增加操作即可
        //对比dp[i-1][j-1]状态，双方都多出个第i位和第j位，如果这两个相等，则和dp[i-1][j-1]一样，不相等，则需要一次替换操作。
        int dp[word1.size()+1][word2.size()+1];
        dp[0][0]=0;
        for(int i=1;i<=word1.size();i++)
            dp[i][0]=i;
        for(int i=1;i<=word2.size();i++)
            dp[0][i]=i;
        
        int i;
        int j;
        for(i=1;i<=word1.size();i++)
            for(j=1;j<=word2.size();j++)
                if(word1[i-1]==word2[j-1])
                    dp[i][j]=1+min( min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]-1);
                else
                    dp[i][j]=1+min( min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);

        return dp[word1.size()][word2.size()];                    
    }
};

LeetCode-No-84

发表于 2020-02-17 分类于算法 Valine：

最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例: 输入: [2,1,5,6,2,3] 输出: 10

题目分析

想要知道最大矩形，肯定先要知道每根柱子怎么形成矩形的
对柱子 i，高度为 hi，以i为中心往两边扩展，只要碰到的柱子高度 Hj=hi，那么形成的矩形必然是以 hi 为高构造。
假如 Hj<hi，那么这个矩形的高就是新的 Hj，而这个 Hj 构造的矩形必然会出现在以柱子 j 为中心扩展的时候，所以不必考虑降低现在的高度。
所以对柱子 i 的扩展，往左右两边找，碰到矮的停下来，确定两边边界，边界高度 Hj=hi，这个即是这个 i 自己能做出来的最大矩形。可以双重循环扫描，但不是重点，这里学习题解大神的栈思路。 # 题解分析：栈保留边界
首先有一层主循环遍历所有柱子，从左到右，当前柱子为 i。
我们目的是要找i的两个边界，因为是从左到右扫描，即我们可以顺手找到 i 的右边界。只要扫描时碰到比 i 矮的就知道这个是右边界了。
但是碰到比 i 高或者相等的柱子 j 怎么办呢？j 不会是 i 的边界，但我们也要找 j 的边界。因此我们要把未处理的 i 和 j 都留下来。
而继续往后找的时候， i 的右边界x 必然是 j 的右边界或者之外（hi<=hj) 。 因此对于下一个柱子 x： 4.1 假如我们先判断 x 是不是 i 的边界，假如它是，它也不一定就是 j 的右边界，我们还得用 x 和 j 比较一次。假如它不是，它也不一定就不是 j 的右边界，还是得 x j 比较一次，所以先判定 i 的边界很鸡肋。 4.2 假如先判断 x 是不是更高的 j 的右边界，假如它不是，那么肯定也不是 i 的边界，假如它是，那么可以继续判定是不是更矮的 i 的右边界。
因此，我们的扫描过程是这样的，从左到右，且保留的柱子高度递增（因为只要更高的才会保留，否则是作为右边界判定）。且判定的顺序是高的在前，低的在后，即新的在前，旧的在后，因此保留柱子的数据结构是：栈。因此遇到一个新柱子，与栈顶比较，更高则继续压栈。更低则是栈顶的右边界，然后栈顶出栈，判定是不是下一个栈顶的右边界。
右边界解决了，我们还需要确定每个柱子 i 的左边界，左边界肯定在左边，并且左边界也要比 i 矮，而我们的栈又是高度递增的= =+显然，我们可以利用出栈过程。在栈顶确定了右边界，然后出栈的时候： 6.1 下面的那个柱子高度大于【栈顶右边界高度Hr】，那么这个柱子不是左边界，而可以组成这个矩形（因为有右边界后，矩形最低高度是Hr，只要高于Hr，都是）我们继续出栈寻找即可。 6.2 即一直出栈，直到出了个高度小于等于【栈顶右边界高度Hr】的柱子 x ，那么 x 就是上面这个矩形的左边界。出栈到边界了怎么办？在数组开头预备一个0作为栈底标志位结束出栈。同样压栈到边界了怎么办？在数组结尾预备一个0作为启动出栈的标志位。
此时 i 的左右边界都能找到，高度为 i ，计算面积。

总之精髓在于出栈过程，从栈顶的右边界，一直出栈到满足的左边界，中间这些柱子形成当前最大矩形。

题解代码

class Solution {
public:
    int largestRectangleArea(vector<int& heights) 
    {
        //题解学习
        std::stack<int Lefts;
        heights.insert(heights.begin(),0);//补0作为边界判断
        heights.insert(heights.end(),0);
        int result=0;
        int temp;
        for(int i=0;i<heights.size();i++)
        {   
            //栈单调递增，当碰到一个i 比栈顶矮，则它必是栈顶的右边界
            //再逐渐出栈，每次出栈循环，都是栈顶作为中心，而栈单调递增，栈顶下面一个更矮的必是栈顶的左边界，左右边界确定，则栈顶位置能形成的矩阵面积可计算完毕。
            //直到栈顶比 i 还矮，那 i 就不能作为右边界了 ，栈顶此时的右边界也找不到，则 i 入栈待命当左边界，然后for下一轮
            while(Lefts.empty()!=true && heights[Lefts.top()]heights[i])//找到比栈顶矮的柱子，即栈顶柱子的右边界
            {     
                temp=Lefts.top();
                Lefts.pop();
                result = max(result, (i - Lefts.top()-1)*heights[temp]);
            }
            Lefts.push(i);
        }

        return result;


    }
};