leetcode題解日練--2016.6.28

プログラミング日記は、毎日少なくとも3つのleetcode問題を保証し、学習したいくつかの問題の答えと構想だけを記録し、できるだけ多くの構想で問題を分析し、解決することを保証し、不足点は指摘してほしい.紅題は後でまた見るべき問題です.
今日のテーマ: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?
Related problem: Reverse Integer
題意:数字を与えて、そのバイナリ表現ビットを逆転します.構想:1、32回のサイクルで、毎回のサイクルはresを左に1ビット移動してnumの最低位を加える.コード:C++

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res=0;
        for(int i=0;i<32;i++,n>>=1)
        {
            res=res<<1;
            res |= n&1;

        }

        return res;
    }
};

結果:4 ms
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のノードに遭遇した場合、前ノード(Prev)を使用して現在のノードを削除します.難しくありませんが、自分で書いたコードは醜いので、ACを3回も貼ったほうがいいです.コード: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;
    }
};

結果:36 ms
2、参考になりましたhttps://leetcode.com/discuss/47642/simple-and-elegant-solution-in-cの方法では、2次ポインタを使用して、ポインタはノードを指し、最初のポインタはheadノードを指します.ポインタが指すノードがvalに等しい場合、ポインタが指すノードは直接次のノードに値を割り当て、現在のノードを削除することに相当する.ポインタが指すノードがvalに等しくない場合は、ポインタに格納されている内容を次のノードに変更する必要があります.ポインタの内容が空になるまで次の判断を行います.

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

結果:32 ms
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?
題意:チェーンテーブルをあげて、返事かどうかを判断する.O(N)の時間とO(1)の空間.考え方:まず、チェーンテーブルが一方向であるため、返事を判断するには、最初のノードと最後のノードを比較し、2つのノードを中間に近づける必要があります.まず、逆転を必要としない最後のノードを見つける必要があります.ノードの総数が奇数の場合、例えばn=7である場合、明らかに前の3つのノードと後の3つのノードを比較するだけで、4番目のノードは移動する必要はなく、中間ノードの下のラベルは(6-0)/2=3であり、n=8の場合、前の4つのノードと後の4つのノードを比較する必要があり、4番目のノードは移動する必要がないので、中間ノードの下のラベルは(7-0)/2=3である.そのため、最初のステップは中間ノードを見つけることです.次に,中間ノードを見つけた後,中間ノードの後のノードを逆順にし,中間ノードの次のノードから順にヘッダノードと比較する必要がある.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;

    }

};

結果:29 ms
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;
    }
};

結果:6 ms