83. Remove Duplicates from Sorted Listの解答

https://leetcode.com/problems/remove-duplicates-from-sorted-list/solution/

141のポインタでの解き方を考えて解けました。一度配列にためてというのも思い浮かべましたが、これに関してはそれは面倒ですね。

ポインタ

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
                   
        ListNode* temp = head;
        
        while(temp && temp->next){
            if(temp->val == temp->next->val){
                temp->next = temp->next->next;
            }
            else{
                temp=temp->next;
            }
        }
        
        return head;
    }
};

MVCモデルとは

MVCモデルとは

Model、View、Controllerでプログラムの処理を分けて開発する方法。

  • Model

  • View

    • データの表示と入出力を行う部分。GUI
  • Controller

    • ViewとModelを制御する部分。Viewからのリクエストを受け取り、Modelにそれを渡す。Modelがそのデータを処理後に再び受け取り、Viewに渡す。

右記サイトより概念図 やはりお前らのMVCは間違っている

f:id:aloealoe:20210226214827j:plain

MVCの何が良いのか

  1. 3つが独立しているのでどれかを変更する場合に、その他のものが影響を受けにくい

ポインタの何が混乱を引き起こすのか自分の経験を思い出してみた

大学の授業で初めてポインタを習ったときはこのように習ったと思う。

#include <stdio.h>
 
int main(void) {
    int num = 1;
    int *p;

    p = &num;

    printf("int型変数numのアドレス:%p\n", p);
    printf("int型変数numのアドレス先の値:%d\n", *p);
}

ポインタの宣言時にとpがくっついていて、pで一つの変数のように見える。 そして、ポインタの先を参照するときに「*p」と書くが、宣言した変数としか思えないのに、全く違うものと説明されても意味がわからず、混乱していたのでプログラムなんか二度とやるかと思っていた。

C99ではint pと宣言できるのだから、これで宣言して教えてほしかった。 これならば、pが別物であるということがよく分かる。

142.Linked list cycle 2の解答

Linked list cycle 2https://leetcode.com/problems/linked-list-cycle-ii/ 2はループの有無ではなくループの始まる数字を答える問題。

setを使用した解答 setを使う場合は、配列の数字を頭から比較するだけなので1と同じ考え方でよかった。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr){
            return nullptr;
        }

        set<ListNode*> temp;
        
        while(head!=nullptr){
            if(temp.find(head)==temp.end()){
                temp.insert(head);                  
            }else{
              return head;
            }            
            head = head->next;
        }
        return nullptr;
    }
};

ポインタを使用した解答 ポインタのほうは少し異なり、2つのポインタを使うのは同じだが、2つのポインタが重なった位置がループの開始位置とは限らないので、開始位置を探す必要がある。回答を見たが下記部分の意味が分からなかったので、説明を探した。

 slow=head;
    while(slow!=fast){
         fast=fast->next;
         slow=slow->next;
    }

下記のblogがとてもわかりやすかった。 mhiro216.hatenablog.com

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr) return nullptr;
        ListNode *slow=head, *fast=head;
        while(fast !=nullptr && fast->next != nullptr){
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){
                while(slow!=head)
                {
                    slow=slow->next;
                    head=head->next;
                }                
                return slow;
            }
        }
        return nullptr;
    }
};

メールのアドレス偽装はどうやるのか調べた

迷惑メールフォルダに成り済ましメールを見つけたので、アドレス偽装はどうやっているのかを調べてみた。

参考 なぜ、嘘のメールアドレスが書けるの? (中級) : 迷惑メール対策委員会

わかったこと

  1. メールの送信にはメーラーから見える宛先、送信元は使用していない。

  2. メールの送信にはenvelopという部分の宛先、送信元を使用している。

結論 envelopには本物の送信者、メーラー上の送信元は宛先のものとすると、アドレス偽装のメールを送信できる

連想配列 setとmapはどちらが速いのか

Linked List Cycleを解くときに連想配列を使用したが、連想配列のset、unordered_set、map、unordered_mapはどれが速いのか比べてみた。比較方法はLinked List Cycleの実効値を比べる。

unorderedはソートを行わないので、unordered有りが速い予想ではあるが、setとmapはどちらが速いのだろうか?

 

結果

配列名 速度(ms) memory(MB)
unordered_map 24 11.2
map 32 11
unordered_set 24 10.5
set 32 11

 

unorderdのある方とない方はそれぞれが同じ速度となった。ただし使用Memoryが異なっていた。

 

結論

どちらも使える状況ならば、好きな方を使えばいいなという結果でした。

 

141. Linked List Cycleの解答

解答1は思いついたが、2は思いつかなかった。よく思いつくなと思う  

 解答1:値を連想コンテナに保存して、比較する方法

  1. リストの先頭の値がset内にあるか検索する
  2. 見つからなかったら、リストの先頭の値をsetに保存する。
  3. リストの次の値がset内にあるか検索する。これを値が見つかるまで繰り返す。
 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode*> t;        
        while(head!=nullptr){
            if(t.find(head) == t.end()){
                t.insert(head);
            }else{
                return true;
            }
            head=head->next;
        }
        return false;
    }
};

 

解答2:1要素ずつ進むポインタと2要素ずつ進む2つのポインタを使い、この2つが重なるところがあるかを確認する方法

1.要素ポインタと2要素ポインタが同じ数値を確認する 2.違ったら、1要素ポインタは1要素進む、2要素ポインタは2進む。これを同じ値になるまで繰り返す。

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