Category: 不学无术

注意/思路

• 保存 被乘数*[0…9]的结果备用，然后移位相加即可
• 乘数末尾是0

代码

9ms

class Solution {
public:
    void ReverseStr(string& str){
        int left=0, right = str.size()-1;
        while(left<right){
            char c = str[left];
            str[left] = str[right];
            str[right] = c;
            left++;
            right--;
        }
    }
    void AddResult(string& result, const string& subProduct, const int shift){
        int carry = 0;
        while(result.size() < shift){
            result += "0";
        }
        for(int i=shift; i<subProduct.size() + shift; i++){
            if(i < result.size()){
                int subSum = (result[i]-'0') + (subProduct[i-shift]-'0') + carry;
                if(subSum >= 10){
                    subSum-= 10;
                    carry = 1;
                } else {
                    carry = 0;
                }
                result[i] = subSum + '0';
            } else {
                int subSum = (subProduct[i-shift]-'0') + carry;
                carry = subSum / 10;
                subSum = subSum % 10;
                result = result + (char)(subSum+'0');
            }
        }
        if (carry > 0) {
			result += (char)(carry + '0');
		}
    }
    string getSubProduct(char digit, string op){
        int carry = 0;
        int d = digit-'0';
        for(int i=0; i<op.size(); i++){
            int prod = (op[i]-'0') * d + carry;
            carry = prod / 10;
            prod = prod % 10;
            op[i] = '0' + prod;
        }
        if(carry > 0){
            op = op + (char)(carry+'0');
        }
        return op;
    }
    string multiply(string op1, string op2) {
        string result;
        if(op1.empty() || op2.empty())
            return result;
        if(op1.size() < op2.size()){
            string temp = op1;
            op1 = op2;
            op2 = temp;
        }
        string productSub[10];
        ReverseStr(op1);
        ReverseStr(op2);
        for(int i=0; i<op2.size(); i++){
            char digit = op2[i];
            if(digit == '0')
                continue;
            if(productSub[digit-'0'].empty()){
                productSub[digit-'0'] = getSubProduct(digit, op1);
            }
            AddResult(result, productSub[digit-'0'], i);
        }
        if(result.empty())
            return "0";
        ReverseStr(result);
        return result;
    }
};

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路

记住上一行的输出（结果）节点，每一次从后往前读出下一行，这样第2,4,6次读的时候其实就会翻转成正向了。唯一的问题是左右子节点写入下一行的顺序，按照当前顺序区分一下就行。不是左右左右，就是右左右左，具体看code吧。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == NULL)
            return result;
        vector<TreeNode*>* currRow = new vector<TreeNode*>();
        vector<TreeNode*>* nextRow = new vector<TreeNode*>();
        bool direction = true;  //true: R,L,R,L,...; false:L,R,L,R,...
        currRow->push_back(root);
        while(!currRow->empty()){
            //Output current row
            vector<int> currRowResult;
            for(int i=0; i<currRow->size(); i++){
                currRowResult.push_back( (*currRow)[i]->val );
            }
            result.push_back(currRowResult);
            //
            for(int i=currRow->size()-1; i>=0; i--){
                TreeNode* currNode = (*currRow)[i];
                if(direction){
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                } else {
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                }
            }
            //swap currRow and nextRow
            vector<TreeNode*>* temp = currRow;
            currRow = nextRow;
            nextRow = temp;
            nextRow->clear();
            direction = !direction;
        }
        return result;
    }
};

思路

双向链表+哈希表实现，要明白STL里的<map>是红黑树实现的，亲测速度不够，要用真.哈希表:<unordered_map>
可能有人要问，为啥不用单向链表？我的理解是为了删除元素的时候不用从头搜索。
当然，针对这道题是可以用单向链表的，即“删除”最无用节点的时候，对链表不作处理，而只是从哈希表里把值删掉。反正在搜索的时候也是直接查的哈希表。副作用是这个链表会越来越长。
另外，不想自己实现双向链表的话，可以用<list>

代码

struct LinkedNode{
    int key;
    LinkedNode* next;
    LinkedNode* prev;
    LinkedNode(int _key = -1){
        key = _key;
        next = NULL;
        prev = NULL;
    }
};
class LRUCache{
private:
    LinkedNode* pHeader;
    LinkedNode* pEnd;
    unordered_map<int, int> keyValueMap;
    int cap;
public:
    LRUCache(int capacity) {
        cap = capacity;
        pHeader = new LinkedNode(); //dummy node
        pEnd = new LinkedNode();
        pHeader->next = pEnd;
        pEnd->prev = pHeader;
    }
    void refreshQueue(int key){
        LinkedNode* pNode = pHeader;
        while(pNode->next != NULL){
            if(pNode->next->key == key)
                break;
            pNode = pNode->next;
        }
        //Move pNode->next to head
        LinkedNode* pPrevNode = pNode;
        LinkedNode* pHitNode = pNode->next;
        LinkedNode* pNextNode = pHitNode->next;
        pPrevNode->next = pNextNode;
        pNextNode->prev = pPrevNode;
        pHeader->next->prev = pHitNode;
        pHitNode->prev = pHeader;
        pHitNode->next = pHeader->next;
        pHeader->next = pHitNode;
    }
    int removeLast(){
        //Remove the last item and return its key
        LinkedNode* pToRemove = pEnd->prev;
        int key = pToRemove->key;
        LinkedNode* pPrev = pToRemove->prev;
        pPrev->next = pEnd;
        pEnd->prev = pPrev;
        delete pToRemove;
        return key;
    }
    int get(int key) {
        if(keyValueMap.count(key) > 0){
            //Change priority queue
            refreshQueue(key);
            //Get value
            return keyValueMap[key];
        } else {
            return -1;
        }
    }
    void insert(int key){
        LinkedNode* pNext = pHeader->next;
        LinkedNode* pNewNode = new LinkedNode(key);
        pNewNode->next = pNext;
        pNewNode->prev = pHeader;
        pHeader->next = pNewNode;
        pNext->prev = pNewNode;
    }
    void set(int key, int value) {
        if(keyValueMap.count(key)){
            keyValueMap[key] = value; //set key
            //Refresh queue
            refreshQueue(key);
        } else {
            if(keyValueMap.size() == cap){
                int oldKey = removeLast();
                keyValueMap.erase(oldKey);
            }
            keyValueMap[key] = value;
            insert(key);
        }
    }
};

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

思路

字符串处理的一个题目，首先想到的办法就是穷举：从头开始找N-letter word，查一下在不在字典里呗。但是纯穷举的话显然就会超时，因为这个问题可以分解成下面的子问题，即给定字符串s及起始位置start，寻找s[start…end]能不能够被拆分。这个子问题在暴力搜索的时候很容易被重复，所以得找个东西记录一下状态，碰到相同的子问题就不用再去查字典了。
所以，他是个动态规划的题。

代码

bool wordBreakSub(const string& s, unordered_set<string>& wordDict, int startPos, int* memory)
{
    if(memory[startPos] != -1)
        return memory[startPos]!= 0;
    string subStr;
    bool canBreak = false;
    for(int len=1; len <= s.size() - startPos; len++)
    {
        subStr = s.substr(startPos, len);
        if(wordDict.count(subStr) > 0) {
            if (startPos + len == s.size()) {
                memory[startPos] = 1;
                return true;
            }
            canBreak = wordBreakSub(s, wordDict, startPos + len, memory);
        }
        if(canBreak)
            break;
    }
    memory[startPos] = canBreak ? 1 : 0;
    return canBreak;
}
bool wordBreak(string s, unordered_set<string>& wordDict)
{
    int* memory = new int[s.size()];
    for(int i=0; i<s.size(); i++)
        memory[i] = -1; //-1:untest; 0-false; 1-true
    return wordBreakSub(s, wordDict, 0, memory);
}

思路

发现是一个树的遍历的题目，而且题目限制的比较死，是个满二叉树，这样处理的时候就避免了比较烦人的跨树指针的情况。比如下面这种建立4->5的指针：

    1
  2   3
4    5  6

第一时间想到的解法是弄个工作队列，然后一层一层遍历下去就行了，这个解法的空间复杂度是O(n)，不符合题目要求。后来再一想，其实既然上一层已经把下一层的next指针建立好了，就不用再从工作队列里去“回忆”了，只要在每一行的开头记住下一行在哪里就行，这样只要O(1)空间复杂度。
另外是如何设置next指针，一共有两个情况：

1. node自己的左孩子和右孩子连起来
2. node的右孩子与node右侧节点它的左孩子连起来

代码

O(n)空间复杂度方法

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        queue<TreeLinkNode*> workingQ;
        if(root == NULL)
            return;
        workingQ.push(root);
        while(!workingQ.empty())
        {
            TreeLinkNode* node = workingQ.front();
            workingQ.pop();
            if(node->left == NULL || node->right == NULL)
                continue;   //Leaf node
            node->left->next = node->right; //Inner connection
            if(node->next != NULL)
                node->right->next = node->next->left; //Outter connection
            workingQ.push(node->left);
            workingQ.push(node->right);
        }
    }
};

O(1)空间复杂度方法

class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* nextRowPtr = root;
        TreeLinkNode* node = root;
        bool atRowStart = true;
        while(nextRowPtr != NULL)
        {
            if(node->left == NULL || node->right == NULL)
                break;   //Leaf node
            if(atRowStart)
            {
                atRowStart = false;
                nextRowPtr = node->left;
            }
            node->left->next = node->right; //Inner connection
            if(node->next != NULL)
            {
                node->right->next = node->next->left; //Outter connection
                node = node->next;
            }
            else
            {
                node = nextRowPtr;
                atRowStart = true;  //End of current row
            }
        }
    }
};