程序员人生网站导航

leetcode题解日练--2016.6.28

栏目：综合技术时间：2016-07-09 13:26:49

编程日记，尽可能保证每天最少3道leetcode题，仅此记录学习的1些题目答案与思路，尽可能用多种思路来分析解决问题，不足的地方还望指出。标红题为以后还需要再看的题目。

本日题目：1、反转比特位；2、移除链表元素；3、回文链表；4、最长公共前缀

190. Reverse Bits | Difficulty: Easy

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

203. Remove Linked List Elements | Difficulty: Easy

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

题意：删除链表中值为val的元素。
思路：
直接从头开始，首先肯定头的值不是val，然后逐一遍历，如果碰到值为val的节点则利用1个前节点（Prev）来删除当前的节点。不难，但是自己写的代码很丑，3次才AC，还是贴上来好了。
代码：
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *Prev,*Node;
        if(!head)   return head;
        while(head)
        {
            if(head->val==val)
                head = head->next;
            else
                break;
        }
        Node = head;
        Prev = NULL;
        while(Node)
        {
            if(Node->val==val)  
            {
                Prev->next = Node->next;
                delete Node;
                Node = Prev->next;
            }
            else
            {
                Prev = Node;
                Node = Node->next;

            }
        }
        return head;
    }
};

结果：36ms

2、参考了https://leetcode.com/discuss/47642/simple-and-elegant-solution-in-c的做法，用1个2级指针，指针指向的是节点，最初指针指向的是head节点。当指针指向的节点等于val的的时候，指针指向的节点直接赋值为下1个节点，也就相当因而删除当前的节点；当指针指向的节点不等于val的时候，需要更改指针内寄存的内容为下1个节点。进行下1次的判断直到指针的内容为空。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode ** list = &head;
        while(*list)
        {
            if((*list)->val==val)
                *list = (*list)->next;
            else
                list = &(*list)->next;
        }
        return head;
    }
};

结果：32ms

234. Palindrome Linked List | Difficulty: Easy

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

题意：给1个链表，判断是不是是回文。O（N）的时间和O（1）的空间。
思路：
首先，由于链表是单向的，那末要判断回文就需要将第1个节点和最后1个节点比较，然后两个节点向中间靠拢。首先我们需要找到中间的节点，即不需要逆转的最后1个节点。当节点总数是奇数的时候，例如n=7，明显我们只需要比较前3个节点和后3个节点，第4个节点不需要移动，中间节点下标是(6-0)/2=3，当n=8的时候，需要比较前4个节点和后4个节点，第4个节点不需要移动，因此中间节点下标还是(7-0)/2 = 3。因此第1步就是找到中间结点。
其次，找到中间节点以后，需要将中间节点以后的节点逆序，然后从中间节点的下1个节点开始顺次和头部节点相比较。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL||head->next==NULL) return true;
        ListNode*slow,*fast;
        slow=head,fast = head;
        while(fast->next!=NULL && fast->next->next!=NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow->next = ReverseList(slow->next);
        while(slow->next!=NULL)
        {
            if(slow->next->val!=head->val)  return false;
            slow = slow->next;
            head = head->next;
        }
        return true;
    }

    ListNode* ReverseList(ListNode* head)
    {
        ListNode*Prev,*next;
        Prev = NULL;
        while(head!=NULL)
        {
         next = head->next;
         head->next = Prev;
         Prev = head;
         head = next;
        }
        return Prev;

    }

};

结果：29ms

14. Longest Common Prefix | Difficulty: Easy

Write a function to find the longest common prefix string amongst an array of strings.

题意：求1组字符串的最长公共前缀
思路：
逐一字符开始比较，先比较第0个字符是不是符合，知道找到不符合的位为止返回前缀。
代码：
C++

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = "";
        if(strs.size()<=0)  return prefix;
        //k代表判断的前缀字符数，从第0个字符开始，判断每个strs的元素的第k位是不是相等，如果全部相等了则最长公共前缀加1
        for(int k = 0;k<strs[0].size();k++)
        {
            //i代表第i个字符串，每次循环的i需要小于strs的个数和最少为k位，由于之前的前缀已有k位了，某个字符串没有到达k位那末没必要继续计算了
            int i=1;
            for(;i<strs.size()&&strs[i].size()>k;i++)
            {
                if(strs[i][k]!=strs[0][k])  return prefix;
            }
             if(i==strs.size())     prefix +=strs[0][k];
        }
        return prefix;
    }
};

结果：6ms

------分隔线----------------------------

上一篇 添物零基础到大型全栈架构师服务器架构及实战（架构篇）- 概述

下一篇 英文，数字和中文混合的彩色验证码实现

------分隔线----------------------------