Tag: LeetCode OJ

思路

换个方法想问题。
有n个数，每个数是否作为输出用0/1状态来表示，比如[1,2,3]全出现就是(1,1,1) => 7，那n个元素的子数组的生成就是以下过程：[0, 2^n)里的每个数i，看这个数i里第[0,n)位是否为1，若为1则表示nums[i]被选中了，否则不选。
比如[1,2,3]的所有子集:

[               [1, 2, 3]
  [3],        => 0, 0, 1  => 1
  [1],        => 1, 0, 0  => 4
  [2],        => 0, 1, 0  => 2
  [1,2,3],    => 1, 1, 1  => 7
  [1,3],      => 1, 0, 1  => 5
  [2,3],      => 0, 1, 1  => 3
  [1,2],      => 1, 1, 0  => 6
  []          => 0, 0, 0  => 0
]

代码

class Solution {
public:
    vector<int> decodeMask(unsigned int mask, const vector<int>& nums){
        vector<int> result;
        unsigned int tester = 0x1;
        for(unsigned int i=0; i<nums.size(); i++){
            if(mask & tester){
                result.push_back(nums[i]);
            }
            tester <<= 1;
        }
        return result;
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> results;
        const unsigned int MAX_MASK = pow(2, nums.size());
        for(unsigned int mask=0; mask < MAX_MASK; mask++){
            results.push_back(decodeMask(mask, nums));
        }
        return results;
    }
};

思路

回溯(backtracing)，用s的起始位置pos表示当前的状态（pos之前的已经处理完）。那么就依次尝试1~3位的字符看看是否符合要求，符合就把结果更新到buffer里，未完成就递归继续，然后递归返回的时候记得把buffer恢复到之前的状态。
按照题目的意思，应该不允许IP地址有前导0，即01.01.01.01这种状态.
对了，stoi函数很好用，应该是C++11新加的。

代码

class Solution {
public:
    bool isValidSubAddr(const string& s, int pos, int len){
        if(pos + len > s.size())
            return false;
        int val = stoi(s.substr(pos, len));
        if(val >= 0 && val <= 255){
            if(val < 10 && len > 1)
                return false;
            else if(val < 100 && len > 2)
                return false;
            return true;
        }
        return false;
    }
    void restoreSub(vector<string>& results, const string& s, int pos, int remainingDot, string& buffer){
        if(remainingDot == 0 || pos >= s.size())
            return;
        int buffSize = buffer.size();
        for(int len=1; len<=3; len++){
            if(!isValidSubAddr(s, pos, len))
                continue;
            buffer += s.substr(pos, len);
            if(pos + len == s.size()){
                //one solution
                if(remainingDot == 1) //otherwise, the split cannot be finished
                    results.push_back(buffer);
            } else {
                buffer += ".";
                //continue try
                restoreSub(results, s, pos+len, remainingDot-1, buffer);
            }
            buffer.erase(buffSize); //restore state
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> results;
        if(s.empty()){
            return results;
        }
        string buffer;
        restoreSub(results, s, 0, 4, buffer);
        return results;
    }
};

思路

警告：千万注意’0’这个异类，当然了还有空输入:(。
其实也是个动态规划?的问题，有点像那个走楼梯的题
当前能decode的方法数与之前的两种状态有关，就是

• 判断当前的字母s[i]能不能单个decode，如果可以，那方法数就要加上解码s[i-1]时的方法数，如果不能解那就不加；
• 判断两个字符s[i-1]s[i]的组合能不能解码（就是在不在10-26的范围内），如果可以，拿加上解码s[i-2]时的方法数；

所以事实上只要保存s[i],s[i-1]两个方法数的结果就行，我的代码空间复杂度还比较大，但是不想改了。

代码

class Solution {
public:
    bool isLegalBiChar(char m, char n){
        // is "mn" a legal word?
        if(m != '1' && m != '2')
            return false;
        if(m == '2'){
            if(n > '6')
                return false;
        }
        return true;
    }
    int numDecodings(string s) {
        if(s.empty() || s[0]=='0')
            return 0;
        int* decodeWays = new int[s.size()];
        //be care of '0's
        decodeWays[0] = 1;
        for(int i=1; i<s.size(); i++){
            int ways = 0;
            if(s[i] > '0' && s[i] <= '9'){
                ways += decodeWays[i-1];
            }
            if(isLegalBiChar(s[i-1], s[i])){
                if(i<2)
                    ways += 1;
                else
                    ways += decodeWays[i-2];
            }
            decodeWays[i] = ways;
        }
        return decodeWays[s.size()-1];
    }
};

思路

title真是长..给前序遍历和中序遍历，构造二叉树。
前序遍历就是Node, Left, Right，而中序遍历是Left, Node, Right，因此给一个前序遍历的序列，他的第一个节点肯定就是那个Node，然后在中序序列里找，就能把序列分成左中右三部分。
自然地就要用递归啦~

代码

/**
 * 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:
    TreeNode* buildTreeSub(const vector<int>& preorder, int p_start, int p_end,
                            const vector<int>& inorder, int i_start, int i_end){
        int pivot = preorder[p_start];
        TreeNode* root = new TreeNode(pivot);
        int indexPivotInorder = -1;
        for(indexPivotInorder=i_start; indexPivotInorder<=i_end; indexPivotInorder++){
            if(inorder[indexPivotInorder] == pivot)
                break;
        }
        int len_left = indexPivotInorder-i_start;
        if(indexPivotInorder > i_start){
            //if we still have left part
            root->left = buildTreeSub(preorder, p_start+1, p_start+len_left, inorder, i_start, indexPivotInorder-1);
        }
        if(indexPivotInorder < i_end){
            //if we still have right part
            root->right = buildTreeSub(preorder, p_start+len_left+1, p_end, inorder, indexPivotInorder+1, i_end);
        }
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || inorder.empty())
            return NULL;
        return buildTreeSub(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

思路

《剑指Offer》#26
基本步骤是：

1. 在每个节点后面，拷贝一个相同的节点：A->A’->B->B’…
2. 拷贝随机节点，即A’->random是A->random->next
3. 分离拷贝后的链表

代码

（脑抽了一下，break和continue打错，看了半天）

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    void makeNodeDup(RandomListNode* head){
        //make copy of linked node
        while(head!=NULL){
            RandomListNode* replica = new RandomListNode(head->label);
            replica->next = head->next;
            head->next = replica;
            head = replica->next;
        }
    }
    void copyRandomLink(RandomListNode* head){
        //copy random link in new-generated replicas
        while(head != NULL){
            if(head->random == NULL){
                head = head->next->next;
                continue;
            }
            RandomListNode* replica = head->next;
            replica->random = head->random->next;
            head = replica->next;
        }
    }
    RandomListNode* detachReplica(RandomListNode* head){
        RandomListNode* replicaHead = NULL;
        while(head != NULL){
            RandomListNode* replica = head->next;
            if(replicaHead == NULL){
                replicaHead = replica;
            }
            head->next = replica->next;
            if(replica->next != NULL){
                replica->next = replica->next->next;
            } else {
                replica->next = NULL;
            }
            head = head->next;
        }
        return replicaHead;
    }
    RandomListNode *copyRandomList(RandomListNode *head) {
        makeNodeDup(head);
        copyRandomLink(head);
        return detachReplica(head);
    }
};

思路

动态规划的问题，某一格的状态由它左侧及上侧的状态决定，即
[latex]minVal[x][y] = min( minVal[x-1][y], minVal[x][y-1] )[/latex]
当然了，第一行只由左侧决定，第一列只由上侧决定。

代码

class Solution {
public:
    int min(int x, int y){
        return x<y ? x : y;
    }
    int minPathSum(vector<vector<int>>& grid) {
        const int m = grid.size();
        if(m == 0)
            return 0;
        const int n = grid[0].size();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 && j==0)
                    continue;
                if(i == 0){
                    // min[0][i] = grid[0][i] + min[0][i-1]
                    grid[i][j] += grid[i][j-1];
                } else if(j == 0){
                    grid[i][j] += grid[i-1][j];
                } else {
                    grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
                }
            }
        }
        return grid[m-1][n-1];
    }
};

思路

回溯
先把candidate排个序，这样可以在中途直接cut掉后面的loop
为了避免重复结果，需要传入一个startIndex，在这之前的都不能作为candidate

代码

class Solution {
public:
    void combSumSub(vector<int>& candidates, int target, vector<vector<int>>& results, vector<int> currPath, int candStartIndex){
        for(int i=candStartIndex; i<candidates.size(); i++){
            if(target - candidates[i] < 0)
                break; //too big
            if(target == candidates[i]){
                currPath.push_back(candidates[i]);
                results.push_back(currPath);
                continue;
            }
            currPath.push_back(candidates[i]);
            combSumSub(candidates, target - candidates[i], results, currPath, i);
            currPath.erase(currPath.end()-1);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        combSumSub(candidates, target, result, vector<int>(), 0);
        return result;
    }
};

注意/思路

• 保存 被乘数*[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;
    }
};