LeetCode OJ – 第36页

LeetCode 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

分析：用一个dp二维数组标记当前方格的最小值～

0.当i == 0 && j == 0的时候，dp[i][j] = grid[i][j];

1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以dp[i][j] = dp[i][j-1] + grid[i][j];

2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以dp[i][j] = dp[i-1][j] + grid[i][j];

3.其他情况下，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

最后直到一直递推输出到终点(m-1, n-1)的时候return dp[m-1][n-1];～～

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

class Solution {

public:

int minPathSum(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

if(m == 0 || n == 0)

return 0;

vector<vector<int>> dp(m, vector<int>(n));

for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) {

if(i == 0 && j == 0) {

dp[i][j] = grid[i][j];

} else if(i == 0) {

dp[i][j] = dp[i][j-1] + grid[i][j];

} else if(j == 0) {

dp[i][j] = dp[i-1][j] + grid[i][j];

} else {

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

}

return dp[m-1][n-1];

}

};

LeetCode 63. Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

分析：这道题是上一道题的升级版~加了障碍物~加不加障碍物差别就在于，当当前地域有障碍物的时候，a[i][j] = 0，其余的不变：
0.a[0][0] = 1; 1.对于i==0的时候，为最上面一排，当前方格只能由左边方格来，所以a[i][j] = a[i][j-1]; 2.对于j==0的时候，为最左边一排，当前方格只能由上边方格来，所以a[i][j] = a[i-1][j]; 3.其余情况，当前方格能由左边和上边两个方向过来，所以a[i][j] = a[i-1][j] + a[i][j-1]; 最后直到一直递推输出到终点(m-1, n-1)的时候return a[m-1][n-1];

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        int a[100][100];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    a[i][j] = 0;
                } else if(i == 0 && j == 0) {
                    a[i][j] = 1;
                } else if(i == 0) {
                    a[i][j] = a[i][j-1];
                } else if(j == 0) {
                    a[i][j] = a[i-1][j];
                } else {
                    a[i][j] = a[i-1][j] + a[i][j-1];
                }
            }
        }
        return a[m-1][n-1];
    }
};

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

int m = obstacleGrid.size();

int n = obstacleGrid[0].size();

int a[100][100];

for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) {

if(obstacleGrid[i][j] == 1) {

a[i][j] = 0;

} else if(i == 0 && j == 0) {

a[i][j] = 1;

} else if(i == 0) {

a[i][j] = a[i][j-1];

} else if(j == 0) {

a[i][j] = a[i-1][j];

} else {

a[i][j] = a[i-1][j] + a[i][j-1];

}

return a[m-1][n-1];

}

};

LeetCode 347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

分析：先遍历数组将数组的值与出现的次数用map映射，因为根据map的值来排序，所以用pair<int, int>类型的vector转存后用sort实现排序方法。从大到小排序，然后取前k个值储存在新的vector v中返回v。

typedef pair<int, int> PAIR;
class Solution {
public:
    static int cmp(const PAIR &x, const PAIR &y) {  
        return x.second > y.second;  
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> v;
        map<int, int> m;
        vector<PAIR> pair_vec;
        for(int i = 0; i < nums.size(); i++) {
            m[nums[i]]++;
        }
        for(map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
            pair_vec.push_back(make_pair(it->first, it->second));
        }
        sort(pair_vec.begin(), pair_vec.end(), cmp);
        vector<PAIR>::iterator curr = pair_vec.begin();
        while(k--) {
            v.push_back(curr->first);
            curr++;
        }
        return v;
    }
};

typedef pair<int, int> PAIR;

class Solution {

public:

static int cmp(const PAIR &x, const PAIR &y) {

return x.second > y.second;

}

vector<int> topKFrequent(vector<int>& nums, int k) {

vector<int> v;

map<int, int> m;

vector<PAIR> pair_vec;

for(int i = 0; i < nums.size(); i++) {

m[nums[i]]++;

}

for(map<int, int>::iterator it = m.begin(); it != m.end(); it++) {

pair_vec.push_back(make_pair(it->first, it->second));

}

sort(pair_vec.begin(), pair_vec.end(), cmp);

vector<PAIR>::iterator curr = pair_vec.begin();

while(k--) {

v.push_back(curr->first);

curr++;

}

return v;

}

};

LeetCode 144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].

/**
 * 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<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        if(root == NULL) {
            return v;
        }
        TreeNode *p = root;
        s.push(p);
        while(!s.empty()) {
            p = s.top();
            s.pop();
            v.push_back(p->val);
            if(p->right != NULL) {
                s.push(p->right);
            }
            if(p->left != NULL) {
                s.push(p->left);
            }
        } 
        return v;
    }
};

/**

* 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<int> preorderTraversal(TreeNode* root) {

stack<TreeNode*> s;

vector<int> v;

if(root == NULL) {

return v;

}

TreeNode *p = root;

s.push(p);

while(!s.empty()) {

p = s.top();

s.pop();

v.push_back(p->val);

if(p->right != NULL) {

s.push(p->right);

}

if(p->left != NULL) {

s.push(p->left);

}

return v;

}

};

LeetCode319. Bulb Switcher

319. Bulb Switcher
My Submissions QuestionEditorial Solution
Total Accepted: 17314 Total Submissions: 42815 Difficulty: Medium
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3.

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].

So you should return 1, because there is only one bulb is on.

分析：可知题意是想判断1~n中那些数的因子个数是奇数，一个数 a = b x c 当 b = c 的时候 a 的因子个数就是奇数，所以就是判断1~n当中有多少个是某数的平方～

class Solution {
public:
    int bulbSwitch(int n) {
        int ans = 0;
        for(int i = 1; i * i <= n; i++) {
            ans++;
        }
        return ans;
    }
};

class Solution {

public:

int bulbSwitch(int n) {

int ans = 0;

for(int i = 1; i * i <= n; i++) {

ans++;

}

return ans;

}

};

LeetCode 8. String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert… click to show requirements for atoi.

Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

class Solution {
public:
    int myAtoi(string str) {
        if(str.length() == 0)
            return 0;
        int i = 0, flag = 1;
        while(isspace(str[i])) {
            i++;
        }
        if(str[i] == '+' || str[i] == '-') {
            if(str[i] == '-')
                flag = 0;
            i++;
        }
        str = str.substr(i);
        for(int j = 0; j < str.length(); j++) {
            if(!isdigit(str[j])) {
                str = str.substr(0, j);
                break;
            }
        }
        if(str.length() == 0)
            return 0;
        if(str.length() > 10) {
            if(flag == 0)
                return -2147483648;
            else
                return 2147483647;
        }
        long long int ans = stoll(str);
        if(flag == 0)
            ans = 0 - ans;
        if(ans > 2147483647) {
            return 2147483647;
        } else if (ans < -2147483648) {
            return -2147483648;
        } else {
            return (int)ans;
        }
    }
};

class Solution {

public:

int myAtoi(string str) {

if(str.length() == 0)

return 0;

int i = 0, flag = 1;

while(isspace(str[i])) {

i++;

}

if(str[i] == '+' || str[i] == '-') {

if(str[i] == '-')

flag = 0;

i++;

}

str = str.substr(i);

for(int j = 0; j < str.length(); j++) {

if(!isdigit(str[j])) {

str = str.substr(0, j);

break;

}

if(str.length() == 0)

return 0;

if(str.length() > 10) {

if(flag == 0)

return -2147483648;

else

return 2147483647;

}

long long int ans = stoll(str);

if(flag == 0)

ans = 0 - ans;

if(ans > 2147483647) {

return 2147483647;

} else if (ans < -2147483648) {

return -2147483648;

} else {

return (int)ans;

}

};