Categories
不学无术

LeetCode 64. Minimum Path Sum

思路

动态规划的问题，某一格的状态由它左侧及上侧的状态决定，即
[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];
    }
};

 

Categories
不学无术

48. Rotate Image

思路

剥洋葱一样的过程可以实现原位替换，只要一个最大为n的暂存数组就行了。

0, 1, 2, 3
4, 5, 6, 7
8, 9, A, B
C, D, E, F

这么个矩阵，首先从最外面一圈剥起，将[0,1,2]记录下来，然后替换为[C,8,4]；然后顺时针继续，将[3,7,B]记录下来，然后用刚才记住的[0,1,2]替换…

代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int floor = 0;
        int ceiling = matrix.size() - 1;
        if(ceiling < 0)
            return; //empty
        vector<int> temp;
        while(floor < ceiling){
            //up
            for(int col=floor; col<ceiling; col++){
                temp.push_back(matrix[floor][col]); //remember current
                matrix[floor][col] = matrix[ceiling-(col-floor)][floor]; //replace with left column values
            }
            //right
            for(int row=floor; row<ceiling; row++){
                temp.push_back(matrix[row][ceiling]);  //remember current
                matrix[row][ceiling] = temp[0]; //replace
                temp.erase(temp.begin());
            }
            //bottom
            for(int col=ceiling; col>floor; col--){
                temp.push_back(matrix[ceiling][col]);
                matrix[ceiling][col] = temp[0];
                temp.erase(temp.begin());
            }
            //left
            for(int row=ceiling; row>floor; row--){
                matrix[row][floor] = temp[0];
                temp.erase(temp.begin());
            }
            floor++;
            ceiling--;
        }
    }
};

 

Categories
不学无术

LeetCode 39. Combination Sum

思路

回溯
先把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;
    }
};

 

Categories
不学无术

LeetCode 43. Multiply Strings

注意/思路

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

 

Categories
未分类

LeetCode 29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

思路

边界条件：比如被除数、除数是0，另外结果的正负号要注意。
除法可以用减法实现，不过如果干减的话会很费时间，所以要想想怎么加速。
容易知道，一个数左移一位相当于乘以2。我们可以一次次把除数乘以2试探一下，到底最多能减掉 2^n*除数 多少次，这就相当于做了2^n次除法。由于试探的时候一次次做了乘方，所以试探的次数是log级别的，比原来一个个减要快多了。

代码

class Solution {
public:
	int divide(int dividend, int divisor) {
		if (dividend == 0)
			return 0;
		if (divisor == 0)
			return INT_MAX;
		bool posResult = true;
		if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor >0))
			posResult = false;
		long long lDividend = dividend;
		if (lDividend < 0)
			lDividend = ~(lDividend-1);
		long long lDivisor = divisor;
		if (lDivisor < 0)
			lDivisor = ~(lDivisor-1);
		long long currDivisor = lDivisor;
		long long accRate = 1;
		long long result = 0;
		while (lDividend >= lDivisor) {
			while ((currDivisor << 1) < lDividend) {
				currDivisor <<= 1;
				accRate <<= 1;
			}
			while (currDivisor > lDividend) {
				currDivisor >>= 1;
				accRate >>= 1;
			}
			lDividend -= currDivisor;
			result += accRate;
		}
		if (posResult) {
			if (result > INT_MAX) {
				return INT_MAX;
			}
			else {
				return (int)result;
			}
		}
		else {
			result = -result;
			if (result < INT_MIN)
				return INT_MIN;
			else
				return (int)result;
		}
	}
};

 
 
 

Categories
不学无术

LeetCode 103. Binary Tree Zigzag Level Order Traversal

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;
    }
};

 

Categories
木有技术

LeetCode 173. Binary Search Tree Iterator

思路

画一个简单的BST，然后可以看出有三种情况

  • 如果当前节点有右孩子，那就在右子树里找到值最小的那个，显然是右子树里最左下侧的那个节点
  • 如果当前节点没有右孩子，由于左子树的值肯定都比当前节点的值小，左右要找父节点
    • 如果找到某个父节点的值比当前节点值大，那这个父节点就是下一节点
    • 否则，当前节点就是最后一个节点

因此，需要一个栈结构记录当前节点的父亲们（有点像调用栈）。
测试例：NULL根节点，只有一个节点，只有单侧树

代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> callStack;
    TreeNode* currNode;
    TreeNode* rootNode;
public:
    BSTIterator(TreeNode *root) {
        currNode = NULL;
        rootNode = root;
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(currNode == NULL){
            currNode = rootNode;
            while(currNode!=NULL && currNode->left != NULL){
                callStack.push(currNode);
                currNode = currNode->left;
            }
            return currNode!=NULL;
        }
        if(currNode->right != NULL){
            //left-most node in right sub-tree
            callStack.push(currNode);
            currNode = currNode->right;
            while(currNode->left != NULL){
                callStack.push(currNode);
                currNode = currNode->left;
            }
            return true;
        } else {
            //look for first parent whos val is > currNode->val. If not available, return false
            int currVal = currNode->val;
            while(!callStack.empty()){
                TreeNode* parent = callStack.top();
                callStack.pop();
                if(parent->val > currVal){
                    currNode = parent;
                    return true;
                }
            }
            currNode = NULL;
            return false;
        }
    }
    /** @return the next smallest number */
    int next() {
        if(currNode != NULL)
            return currNode->val;
        return INT_MIN;
    }
};
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

 

Categories
不学无术

LeetCode 50. Pow(x, n)

边界检查：0，INT_MAX, INT_MIN

class Solution {
private:
    map<int, double> memory;
public:
    double myPow(double x, int n) {
        if(n == 0)
            return 1.0;
        if(n == 1)
            return x;
        if(n == -1)
            return 1/x;
        if(memory.count(n)>0)
            return memory[n];
        double result = myPow(x, n/2) * myPow(x, n/2);
        if(n%2 != 0){
            result *= (n<0)? 1/x : x;
        }
        memory[n] = result;
        return result;
    }
};

 

Categories
不学无术

LeetCode 134. Gas Station

思路

O(n^2)做法：直接嵌套循环，暴力试就行
O(n)做法：类似贪心的思路。主要还是看gas[i]-cost[i]，如果减出来是正的，那么可以为后面的路段留下点资源，如果减出来是负的话，那么最好的做法是在之前积累最多的资源来解决这个debt. 那什么时候有可能积累到最多资源呢？只能将这个有欠债的站点作为最后一站，所以将该站点的下一站作为起始试试。

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalLoss = 0;
        int tank = 0;
        int max_i = 0;
        for(int i=0; i<gas.size(); i++){
            tank += gas[i] - cost[i];
            if(tank < 0){   //Owe!
                max_i = i+1; //next possible start
                totalLoss += tank;  //add in the debt
                tank = 0;
            }
        }
        if(totalLoss + tank < 0)    //if the debt cannot be paid
            return -1;
        return max_i;
    }
};

 

Categories
不学无术

LeetCode 7. Reverse Integer

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

思路

检测溢出要在溢出之前，因为溢出的结果是undefined的。
比如要判断加法溢出，想当然的就是 A + B > INT_MAX，但是这是不对的，A + B指不定加出什么东西来，应当是 A > INT_MAX – B.

代码

class Solution {
public:
    bool safeMultiply10(int& result){
        //Multiply result by 10 if not overflow
        //Return false if it overflows
        if(result > 0){
            if(result > INT_MAX / 10)
                return false;
        } else if(result < 0) {
            if(result < INT_MIN / 10)
                return false;
        }
        result *= 10;
        return true;
    }
    bool safePlus(int& result, int r){
        //Return false if it overflows
        if(result > 0){
            if(result > INT_MAX - r)
                return false;
        } else if (result < 0) {
            if(result < INT_MIN - r)
                return false;
        }
        result += r;
        return true;
    }
    int reverse(int x) {
        int result = 0;
        //bool negFlag = x<0;
        while(x != 0){
            int r = x % 10;
            if(!safeMultiply10(result))
                return 0;
            if(!safePlus(result, r))
                return 0; //overflow
            x /= 10;
        }
        return result;
    }
};