LeetCode OJ – 第40页 – 柳婼の blog

LeetCode 203. Remove Linked List Elements

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

/**
 * 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) {
        while(head != NULL && head->val == val) {
            head = head->next;
        }
        if(head == NULL) {
            return NULL;
        }
        ListNode *p = head;
        ListNode *q= p->next;
        while(p != NULL && p->next != NULL) {
            q = p->next;
            while(q != NULL && q->val == val) {
                q = q->next;
            }
            p->next = q;
            p = q;
        }
        return head;
    }
};

/**

* 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) {

while(head != NULL && head->val == val) {

head = head->next;

}

if(head == NULL) {

return NULL;

}

ListNode *p = head;

ListNode *q= p->next;

while(p != NULL && p->next != NULL) {

q = p->next;

while(q != NULL && q->val == val) {

q = q->next;

}

p->next = q;

p = q;

}

return head;

}

};

LeetCode 203. Remove Linked List Elements

203. Remove Linked List Elements
My Submissions QuestionEditorial Solution
Total Accepted: 59711 Total Submissions: 209326 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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

/**
 * 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) {
        while(head != NULL && head->val == val) {
            head = head->next;
        }
        if(head == NULL) {
            return NULL;
        }
        ListNode *p = head;
        ListNode *q= p->next;
        while(p != NULL && p->next != NULL) {
            q = p->next;
            while(q != NULL && q->val == val) {
                q = q->next;
            }
            p->next = q;
            p = q;
        }
        return head;
    }
};

/**

* 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) {

while(head != NULL && head->val == val) {

head = head->next;

}

if(head == NULL) {

return NULL;

}

ListNode *p = head;

ListNode *q= p->next;

while(p != NULL && p->next != NULL) {

q = p->next;

while(q != NULL && q->val == val) {

q = q->next;

}

p->next = q;

p = q;

}

return head;

}

};

LeetCode 38. Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

class Solution {
public:
    string countAndSay(int n) {
        string temp = "";
        string num = "";
        int cnt = 1;
        if(n == 1) {
            return "1";
        }
        if(n == 2) {
            return "11";
        }
        string a = "11";
        for(int i = 1; i <= n - 2; i++) {
            for(int j = 1; j < a.length(); j++) {
                if(a[j-1] == a[j]) {
                    cnt++;
                }
                if(a[j-1] != a[j]) {
                    while(cnt) {
                        num = (char)(cnt % 10 + '0') + num;
                        cnt = cnt / 10;
                    }
                    temp += num;
                    num = "";
                    temp += a[j-1];
                    cnt = 1;
                }
                if(j == a.length() - 1) {
                    while(cnt) {
                        num = (char)(cnt % 10 + '0') + num;
                        cnt = cnt / 10;
                    }
                    temp += num;
                    num = "";
                    temp += a[j];
                    cnt = 1;
                }
            }
            a = temp;
            temp = "";
        }
        return a;
    }
};

class Solution {

public:

string countAndSay(int n) {

string temp = "";

string num = "";

int cnt = 1;

if(n == 1) {

return "1";

}

if(n == 2) {

return "11";

}

string a = "11";

for(int i = 1; i <= n - 2; i++) {

for(int j = 1; j < a.length(); j++) {

if(a[j-1] == a[j]) {

cnt++;

}

if(a[j-1] != a[j]) {

while(cnt) {

num = (char)(cnt % 10 + '0') + num;

cnt = cnt / 10;

}

temp += num;

num = "";

temp += a[j-1];

cnt = 1;

}

if(j == a.length() - 1) {

while(cnt) {

num = (char)(cnt % 10 + '0') + num;

cnt = cnt / 10;

}

temp += num;

num = "";

temp += a[j];

cnt = 1;

}

a = temp;

temp = "";

}

return a;

}

};

LeetCode 290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = “abba”, str = “dog cat cat dog” should return true.
pattern = “abba”, str = “dog cat cat fish” should return false.
pattern = “aaaa”, str = “dog cat cat dog” should return false.
pattern = “abba”, str = “dog dog dog dog” should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<char, string> ptos;
        map<string, char> stop;
        int len = pattern.length();
        string *s = new string [len];
        int cnt = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str[i] == ' ')
                cnt++;
        }
        if(cnt != len - 1) {
            return false;
        }
        int t = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str[i] != ' ') {
                s[t] += str[i];
            } else {
                t++;
            }
        }
        for(int i = 0; i < len; i++) {
            if(ptos.find(pattern[i]) != ptos.end() && ptos[pattern[i]] != s[i]
            || stop.find(s[i]) != stop.end() && stop[s[i]] != pattern[i])
                return false;
            ptos[pattern[i]] = s[i];
            stop[s[i]] = pattern[i];
        }
        return true;
    }
};

class Solution {

public:

bool wordPattern(string pattern, string str) {

map<char, string> ptos;

map<string, char> stop;

int len = pattern.length();

string *s = new string [len];

int cnt = 0;

for(int i = 0; i < str.length(); i++) {

if(str[i] == ' ')

cnt++;

}

if(cnt != len - 1) {

return false;

}

int t = 0;

for(int i = 0; i < str.length(); i++) {

if(str[i] != ' ') {

s[t] += str[i];

} else {

t++;

}

for(int i = 0; i < len; i++) {

if(ptos.find(pattern[i]) != ptos.end() && ptos[pattern[i]] != s[i]

|| stop.find(s[i]) != stop.end() && stop[s[i]] != pattern[i])

return false;

ptos[pattern[i]] = s[i];

stop[s[i]] = pattern[i];

}

return true;

}

};

LeetCode 58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

class Solution {
public:
    int lengthOfLastWord(string s) {
        int cnt = 0;
        int flag = 0;
        for(int i = s.length() - 1; i >= 0; i--) {
            if(flag == 0 && s[i] == ' ') {
                continue;
            }
            if(s[i] != ' ') {
                flag = 1;
                cnt++;
            } else {
                break;
            }
        }
        return cnt;
    }
};

class Solution {

public:

int lengthOfLastWord(string s) {

int cnt = 0;

int flag = 0;

for(int i = s.length() - 1; i >= 0; i--) {

if(flag == 0 && s[i] == ' ') {

continue;

}

if(s[i] != ' ') {

flag = 1;

cnt++;

} else {

break;

}

return cnt;

}

};

LeetCode 19. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == NULL || head->next == NULL)
            return NULL;
        ListNode *p = head;
        ListNode *q = head;
        for(int i = 1; i <= n; i++) {
            p = p->next;
        }
        if(p == NULL) {
            head = head->next;
            return head;
        }
        p = p->next;
        while(p != NULL) {
            p = p->next;
            q = q->next;
        }
        q->next = q->next->next;
        return head;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* removeNthFromEnd(ListNode* head, int n) {

if(head == NULL || head->next == NULL)

return NULL;

ListNode *p = head;

ListNode *q = head;

for(int i = 1; i <= n; i++) {

p = p->next;

}

if(p == NULL) {

head = head->next;

return head;

}

p = p->next;

while(p != NULL) {

p = p->next;

q = q->next;

}

q->next = q->next->next;

return head;

}

};