Code – 第243页

一脸懵比：length() 以及 size_t

刚刚刷 leetcode 的时候又发生了一件灵异事件：

Snip20160420_20

//题目很简单：

Implement strStr().

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

但是报错了：

Snip20160420_21

奇怪点不在这，在于如果我把两个.length()替换成 int 型的len1和 len2，就 Accepted了。。

就是写成这样就对了：

Snip20160420_22

啊，为什么。。。为什么。。什么都没干啊只是等价替换了啊。。

a82aa4a836975b078e8d_size71_w440_h774

后来机智的我想起，原来在 IDE 里面编程的时候，每次用 .length()会有警告提醒：

Snip20160420_26

size_type。。。

Snip20160420_29

所以说在 unsigned 情况下，如果两个 length()相减，得到的是一个好大好大的值，因为unsingned和unsigned相减得到unsigned的数，也就是如果是负数的话得到的是int的最大值那样的数，但是在转为 int 型之后就会允许相减得到负数，是这样的么。。。验证一下：

Snip20160420_32

啊，我怎么可以这么机智~~(｀･ω･´)

746-160311154339 ~~~~~~~~~~~~

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;

}

};