LeetCode OJ – 第39页 – 柳婼の blog

LeetCode 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

class Solution {
public:
    int strStr(string haystack, string needle) {
        int len1 = haystack.length();
        int len2 = needle.length();
        if(len2 == 0)
            return 0;
        for(int i = 0; i <= len1 - len2; i++) {
            for(int j = 0; j < len2 && needle[j] == haystack[i + j]; j++) {
                if(j == len2 - 1)
                    return i;
            }
        }
        return -1;
    }
};

class Solution {

public:

int strStr(string haystack, string needle) {

int len1 = haystack.length();

int len2 = needle.length();

if(len2 == 0)

return 0;

for(int i = 0; i <= len1 - len2; i++) {

for(int j = 0; j < len2 && needle[j] == haystack[i + j]; j++) {

if(j == len2 - 1)

return i;

}

return -1;

}

};

LeetCode 67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

class Solution {
public:
    string addBinary(string a, string b) {
        string s;
        int lena = a.length() - 1;
        int lenb = b.length() - 1;
        int temp = 0;
        char c;
        while(lena >= 0 && lenb >= 0) {
            c = (a[lena] - '0') + (b[lenb] - '0') + temp + '0';
            temp = 0;
            if((c - '0') >= 2) {
                temp = 1;
                c = c - 2;
            }
            s = c + s;
            lena--;
            lenb--;
        }
        while(lena >= 0) {
            c = (a[lena] - '0') + temp + '0';
            temp = 0;
            if((c - '0') >= 2) {
                temp = 1;
                c = c - 2;
            }
            s = c + s;
            lena--;
        }
        while(lenb >= 0) {
            c =(b[lenb] - '0') + temp + '0';
            temp = 0;
            if((c - '0') >= 2) {
                temp = 1;
                c = c - 2;
            }
            s = c + s;
            lenb--;
        }
        if(temp == 1) {
            s = '1' + s;
        }
        return s;
    }
};

class Solution {

public:

string addBinary(string a, string b) {

string s;

int lena = a.length() - 1;

int lenb = b.length() - 1;

int temp = 0;

char c;

while(lena >= 0 && lenb >= 0) {

c = (a[lena] - '0') + (b[lenb] - '0') + temp + '0';

temp = 0;

if((c - '0') >= 2) {

temp = 1;

c = c - 2;

}

s = c + s;

lena--;

lenb--;

}

while(lena >= 0) {

c = (a[lena] - '0') + temp + '0';

temp = 0;

if((c - '0') >= 2) {

temp = 1;

c = c - 2;

}

s = c + s;

lena--;

}

while(lenb >= 0) {

c =(b[lenb] - '0') + temp + '0';

temp = 0;

if((c - '0') >= 2) {

temp = 1;

c = c - 2;

}

s = c + s;

lenb--;

}

if(temp == 1) {

s = '1' + s;

}

return s;

}

};

LeetCode 234. Palindrome Linked List

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?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* func(ListNode* head) {
        if(head->next != NULL) {
            ListNode *tail = func(head->next);
            tail->next = head;
            head->next = NULL;
        }
        return head;
    }
    
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) 
            return head;
        ListNode *newhead = head;
        while(newhead->next != NULL) {
            newhead = newhead->next;
        }
        func(head);
        return newhead;
    }
    
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return true;
        ListNode *p, *q;
        p = head;
        q = head;
        while(q != NULL) {
            p = p->next;
            q = q->next;
            if(q != NULL) {
                q = q->next;
            }
        }
        p = reverseList(p);
        while(p != NULL) {
            if(head->val != p->val)
                return false;
            else {
                head = head->next;
                p = p->next;
            }
        }
        return true;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

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

* };

class Solution {

public:

ListNode* func(ListNode* head) {

if(head->next != NULL) {

ListNode *tail = func(head->next);

tail->next = head;

head->next = NULL;

}

return head;

}

ListNode* reverseList(ListNode* head) {

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

return head;

ListNode *newhead = head;

while(newhead->next != NULL) {

newhead = newhead->next;

}

func(head);

return newhead;

}

bool isPalindrome(ListNode* head) {

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

return true;

ListNode *p, *q;

p = head;

q = head;

while(q != NULL) {

p = p->next;

q = q->next;

if(q != NULL) {

q = q->next;

}

p = reverseList(p);

while(p != NULL) {

if(head->val != p->val)

return false;

else {

head = head->next;

p = p->next;

}

return true;

}

};

LeetCode 225. Implement Stack using Queues

Implement the following operations of a stack using queues.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.
Notes:
You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

class Stack {
public:
    // Push element x onto stack.
    queue<int> q1, q2;
    void push(int x) {
        q1.push(x);
    }

    // Removes the element on top of the stack.
    void pop() {
        while(q1.size() != 1) {
            int t = q1.front();
            q1.pop();
            q2.push(t);
        }
        q1.pop();
        while(!q2.empty()) {
            int t = q2.front();
            q2.pop();
            q1.push(t);
        }
    }

    // Get the top element.
    int top() {
        return q1.back();
    }

    // Return whether the stack is empty.
    bool empty() {
        return q1.empty();
    }
};

class Stack {

public:

// Push element x onto stack.

queue<int> q1, q2;

void push(int x) {

q1.push(x);

}

// Removes the element on top of the stack.

void pop() {

while(q1.size() != 1) {

int t = q1.front();

q1.pop();

q2.push(t);

}

q1.pop();

while(!q2.empty()) {

int t = q2.front();

q2.pop();

q1.push(t);

}

// Get the top element.

int top() {

return q1.back();

}

// Return whether the stack is empty.

bool empty() {

return q1.empty();

}

};

LeetCode 42. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

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

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num <= 0 ? false : pow(4, (round)(log(num) / log(4))) == num;
    }
};

class Solution {

public:

bool isPowerOfFour(int num) {

return num <= 0 ? false : pow(4, (round)(log(num) / log(4))) == num;

}

};

LeetCode 14. Longest Common Prefix

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

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0)
            return "";
        string s = strs[0];
        for(int i = 1; i < strs.size(); i++) {
            for(int j = 0; j < s.length(); j++) {
                if(s[j] != strs[i][j]) {
                    s = s.substr(0, j);
                    break;
                }
            }
        }
        return s;
    }
};

class Solution {

public:

string longestCommonPrefix(vector<string>& strs) {

if(strs.size() == 0)

return "";

string s = strs[0];

for(int i = 1; i < strs.size(); i++) {

for(int j = 0; j < s.length(); j++) {

if(s[j] != strs[i][j]) {

s = s.substr(0, j);

break;

}

return s;

}

};