Day 116, #231, #232, #234, Power of Two, Implement Queue using Stacks, Palindrome Linked List, Number of Digit One

Power of Two
Given an integer, write a function to determine if it is a power of two.
----------------------------------------------------------------------

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return !(n & (n - 1));
    }
};

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

---------------------------------------------
只有当output stack为空时，才会将input里的数全部压入output，抄的

class Queue {
public:
    // Push element x to the back of queue.
    void push(int x) {
        input.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        peek();
        output.pop();
    }

    // Get the front element.
    int peek(void) {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        return output.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return input.empty() && output.empty();
    }
private:
    stack<int> input;
    stack<int> output;
};

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?

-----------------------------------------------
找到中点，翻转其中一半，再比较
slow是中点（odd number）或者是后半部分的启示（even）

/**
 * 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) return true;
        ListNode *fast = head, *slow = head;
        while (fast != NULL) {
            fast = fast->next;
            if (fast != NULL) {
                fast = fast->next;
                slow = slow->next;
            }
        }
        
        // reverse the second half
        ListNode *newHead = NULL;
        while (slow != NULL) {
            ListNode *temp = slow->next;
            slow->next = newHead;
            newHead = slow;
            slow = temp;
        }
        
        while (newHead != NULL) {
            if (newHead->val != head->val) return false;
            newHead = newHead->next;
            head = head->next;
        }
        
        return true;
    }
};

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

1. Beware of overflow.

--------------------------------------------------------------
对每一位上的1可能出现的次数进行统计
ref：http://blog.csdn.net/xudli/article/details/46798619

class Solution {
public:
    int countDigitOne(int n) {
        int rt = 0;
        
        for (long long i = 1; i <= n; i *= 10) {
            int left = n / i;
            int right = n % i; // 当前位之后的数
            int cur = left % 10; // 当前位上的数
            left /= 10;  // 当前位之前的数
            
            if (cur == 0) {
                rt += left * i;
            }else if (cur == 1) {
                rt += left * i + right + 1;
            }else {
                rt += (left + 1) * i;
            }
        }
        
        return rt;
    }
};