[leetcode]题目解析（190423）

Remove duplicates from sorted list

题目描述

Given a sorted linked list, delete all duplicates such that each element appear only once.For example,
Given1->1->2, return1->2.
Given1->1->2->3->3, return1->2->3.（保留1个）

题目解析

对于当前节点和下一节点的值不相等的情况，那就一直往下走，代码中是p1移动到下一个节点的操作。代码如下：

            if(p1->val != p2->val) {
                p1 = p1->next;
                continue;
            }

当然如果当前节点和下一节点相同的情况下，我们就需要做两件事：

• 不断判断下面有几个点和当前点相等，代码如下：

while(p2->next != NULL && p1->val == p2->next->val) p2 = p2->next;

• 找到最后一个点和当前点相等的时候，直接把那个点的next赋值给当前点的next，然后那些点。即：

p1->next = p2->next;
delete p2;

代码实现

    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* p1 = head;
        while(p1 != NULL && p1->next != NULL) {
            ListNode* p2 = p1->next;
            if(p1->val != p2->val) {
                p1 = p1->next;
                continue;
            }
            while(p2->next != NULL && p1->val == p2->next->val) p2 = p2->next;
            p1->next = p2->next;
            delete p2;
            p1 = p1->next;
        }
        return head;
    }

删除链表中重复的节点（全部删除）

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

题目解析

代码实现

ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead == NULL)
            return NULL;
        if(pHead->next== NULL)
            return pHead;
        if(pHead->val==pHead->next->val)
        {
            ListNode* pNode = pHead->next;
            while(pNode!=NULL && pNode->val==pHead->val)
                pNode=pNode->next;
            return deleteDuplication(pNode);
        }
        else
        {
            pHead->next=deleteDuplication(pHead->next);
            return pHead;
        }

    }

Jump Game

题目说明

Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.Determine if you are able to reach the last index.For example:
A =[2,3,1,1,4], returntrue.A =[3,2,1,0,4], returnfalse.

题目解析

这个题解析起来我的想法很容易，复杂度为O(n)。就是：我记录当前A[i]的值，然后把i加上这个值，就相当于从当前这个位置往前走相应的步数。退出循环的判断条件有两个：

• 当前是第i个元素，但是i已经大于n-1了（下标从0开始，所以第n个数是第n-1）。
• A[i]为0：这里面又分两种情况，一种是如题目所给的第2种情况，在中间为0的这个位置不走了，还有一种情况是我这个数组一共1个元素，就是0。那么跳出。

交给下面的return语句后面判断。就是判断当做的位置是否是越过了最后一个位置？若越过了或者正好在最后一个位置，自然是return true；否则return false。

代码展示

bool canJump(int A[], int n) {
    int i = 0;
    while (A[i] != 0)
    {
        int jumpNum = A[i];
        i += jumpNum;
        if (i >= n-1)
            break;
    }
    return i >= n-1 ? true : false;

}

rotate image

题目描述

You are given an n x n 2D matrix representing an image.Rotate the image by 90 degrees (clockwise).Follow up:
Could you do this in-place?

题目解析

旋转90°，可以当做两步：第一步是关于对角线取对称；第二步是关于水平线取上下对称。
记住这个原理。

代码实现

    void rotate(vector<vector<int> > &matrix) {
        //对角线对称
        int n=matrix.size();
        for(int i=0;i<n;i++)
            for(int j=0;j<n-i;j++)
                swap(matrix[i][j],matrix[n-1-j][n-1-i]);
        //上下交换
        for(int i=0;i<n/2;i++)
            for(int j=0;j<n;j++)
                swap(matrix[i][j],matrix[n-1-i][j]);

    }

Trapping Rain Water

题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example, 
Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcosfor contributing this image!

题目分析

这个题目的想法，最容易想到的就是将它以最高的地方为基准分为左右两列进行相加计算，因为相加不可能跨过最高的那个地方。
对于左侧，我们从0向最高值靠拢，首先判断当前位置的值是否小于left（left刚开始是第0个，判断从第0个开始判断没问题），如果小于，那么就将suml累加上left-A[i]即可，如果不是小于，那么代表着从这一点开始，又要重新计算一个容量，所以令left=A[i]。如下所示：

if (A[i] < left)
            suml += left - A[i];
        else
            left = A[i];

对于右侧同理，从最右侧n-1开始往左判断，过程与上面相同，不再重复。代码如下：

        if (A[i] < right)
            sumr += right - A[i];
        else
            right = A[i];

代码实现

int trap(int A[], int n) {
    int maxHeight = 0;
    int left = 0;//由左往最大值计算
    int right = 0;//由右往最大值计算
    int suml = 0;
    int sumr = 0;
    //寻找到高度的最大值，将区间分为左侧和右侧两部分进行分别处理
    for (int i = 0; i < n; i++)
        if (A[i] > A[maxHeight])
            maxHeight = i;
    //先计算左侧的容量
    for (int i = 0; i < maxHeight; i++)
    {
        if (A[i] < left)
            suml += left - A[i];
        else
            left = A[i];
    }
    for (int i = n-1; i > maxHeight; i--)
    {
        if (A[i] < right)
            sumr += right - A[i];
        else
            right = A[i];
    }
    return suml + sumr;

}