您當前位置：首頁 > php開源 > 綜合技術 > leetcode題解日練--2016.6.28

leetcode題解日練--2016.6.28

來源：程序員人生發布時間：2016-07-09 13:26:49 閱讀次數：2659次

編程日記，盡可能保證每天最少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;
    }
};