x的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4 输出: 2

示例 2:

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

题目分析

1. 首先直接计算平方根不太现实，所以这是一个在有序的1~x中查找出平方根的问题。
2. 查找有序整数中的特定值，正常思路即二分查找，实现也简单。
3. 递归缩小求解： \[\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}\)。

牛顿迭代题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
    }
    
};

编辑距离

给定两个单词 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')

题目分析

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

dp题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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()];                    
    }
};

颜色分类

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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++;
        }
    }
};

最大矩形

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

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

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

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

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

题目分析

1. 想要知道最大矩形，肯定先要知道每根柱子怎么形成矩形的

2. 对柱子 i，高度为 hi，以i为中心往两边扩展，只要碰到的柱子高度 Hj=hi，那么形成的矩形必然是以 hi 为高构造。

3. 假如 Hj<hi，那么这个矩形的高就是新的 Hj，而这个 Hj 构造的矩形必然会出现在以柱子 j 为中心扩展的时候，所以不必考虑降低现在的高度。

4. 所以对柱子 i 的扩展，往左右两边找，碰到矮的停下来，确定两边边界，边界高度 Hj=hi，这个即是这个 i 自己能做出来的最大矩形。 可以双重循环扫描，但不是重点，这里学习题解大神的栈思路。 # 题解分析：栈保留边界

5. 首先有一层主循环遍历所有柱子，从左到右，当前柱子为 i。

6. 我们目的是要找i的两个边界，因为是从左到右扫描，即我们可以顺手找到 i 的右边界。只要扫描时碰到比 i 矮的就知道这个是右边界了。

7. 但是碰到比 i 高或者相等的柱子 j 怎么办呢？j 不会是 i 的边界 ，但我们也要找 j 的边界。因此我们要把未处理的 i 和 j 都留下来。

8. 而继续往后找的时候， i 的右边界x 必然是 j 的右边界或者之外 （hi<=hj) 。 因此对于下一个柱子 x： 4.1 假如我们先判断 x 是不是 i 的边界，假如它是，它也不一定就是 j 的右边界 ，我们还得用 x 和 j 比较一次。假如它不是，它也不一定就不是 j 的右边界，还是得 x j 比较一次，所以先判定 i 的边界很鸡肋。 4.2 假如先判断 x 是不是更高的 j 的右边界，假如它不是，那么肯定也不是 i 的边界，假如它是，那么可以继续判定是不是更矮的 i 的右边界。

9. 因此，我们的扫描过程是这样的，从左到右，且保留的柱子高度递增（因为只要更高的才会保留，否则是作为右边界判定）。 且判定的顺序是高的在前，低的在后，即新的在前，旧的在后，因此保留柱子的数据结构是：栈。 因此遇到一个新柱子，与栈顶比较，更高则继续压栈。更低则是栈顶的右边界，然后栈顶出栈，判定是不是下一个栈顶的右边界。

10. 右边界解决了，我们还需要确定每个柱子 i 的左边界，左边界肯定在左边 ， 并且左边界也要比 i 矮，而我们的栈又是高度递增的= =+显然，我们可以利用出栈过程。 在栈顶确定了右边界，然后出栈的时候： 6.1 下面的那个柱子高度大于【栈顶右边界高度Hr】，那么这个柱子不是左边界，而可以组成这个矩形（因为有右边界后，矩形最低高度是Hr，只要高于Hr，都是）我们继续出栈寻找即可。 6.2 即一直出栈，直到出了个高度小于等于【栈顶右边界高度Hr】的柱子 x ，那么 x 就是上面这个矩形的左边界。 出栈到边界了怎么办？在数组开头预备一个0作为栈底标志位结束出栈。 同样压栈到边界了怎么办？在数组结尾预备一个0作为启动出栈的标志位。

11. 此时 i 的左右边界都能找到，高度为 i ，计算面积。

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

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;


    }
};

分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1-4-3-2-5-2, x = 3 输出: 1-2-2-4-3-5

题目分析

1. 直接思路是第一次遍历找到中间节点，并且划分为左右两边，然后再重新遍历链表元素，按大小分类到两边去。
2. 但这样要来回遍历链表，还要不停的交换节点很麻烦，换个逆向思路：既然是一个链表分成两个区域，不就相当于两个链表合成一个区域
3. 因此，即构造两个链表，遍历原链表元素，分类接在两个链表上。
4. 遍历结束合成两个链表。

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {   
        //逆向想问题，既然分成了两段，那也可以是两段连成了一段

        ListNode lefthead(0);
        ListNode* left=&lefthead;
        ListNode righthead(0);
        ListNode* right=&righthead;


        while(head!=NULL)
        {
           if(head-val<x)
           {
               left-next=head;
               left=left-next;
           }
           else
           {
               right-next=head;
               right=right-next;
           }
           head=head-next;

          
        }
        right-next=NULL;//注意赋值null，否则下面的链表连接会无限循环超时
        left-next=righthead.next;
        return lefthead.next;


    }
};