LeetCode OJ – 第32页

LeetCode 257. Binary Tree Paths

257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:

[“1->2->5”, “1->3”]
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

/**
 * 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:
    void dfs(vector<string> &v, TreeNode *node, string s) {
        if(node->left == NULL && node->right == NULL) {
            v.push_back(s);
            return ;
        }
        if(node->left != NULL) {
            dfs(v, node->left, s + "->" + to_string(node->left->val));
        }
        if(node->right != NULL) {
            dfs(v, node->right, s + "->" + to_string(node->right->val));
        }
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> v;
        if(root == NULL) {
            return v;
        }
        dfs(v, root, to_string(root->val));
        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:

void dfs(vector<string> &v, TreeNode *node, string s) {

if(node->left == NULL && node->right == NULL) {

v.push_back(s);

return ;

}

if(node->left != NULL) {

dfs(v, node->left, s + "->" + to_string(node->left->val));

}

if(node->right != NULL) {

dfs(v, node->right, s + "->" + to_string(node->right->val));

}

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> v;

if(root == NULL) {

return v;

}

dfs(v, root, to_string(root->val));

return v;

}

};

LeetCode 475. Heaters

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:
Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
As long as a house is in the heaters‘ warm radius range, it can be warmed.
All the heaters follow your radius standard and the warm radius will the same.
Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Example 2:
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

题目大意：给出房子的坐标和供暖器的坐标，求供暖器的最小供热半径是多少才能满足让所有房子都暖和。

分析：先将houses和heaters排序，计算每一个house左右的供暖器的距离最小的那个值，然后将所有的这些最小值中取最大的值。
因为houses和heaters都是排序好的，所以heater[j]与houses[i]的距离应该越来越小，如果突然间变大了，说明不是最小值了，就break掉。这样就能得知最小值。

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int startindex = 0, maxn = 0;
        for(int i = 0; i < houses.size(); i++) {
            int tempmin = INT_MAX;
            for(int j = startindex; j < heaters.size(); j++) {
                if(abs(heaters[j] - houses[i]) <= tempmin) {
                    tempmin = abs(heaters[j] - houses[i]);
                    startindex = j;
                } else {
                    break;
                }
            }
            maxn = max(maxn, tempmin);
        }
        return maxn;
    }
};

class Solution {

public:

int findRadius(vector<int>& houses, vector<int>& heaters) {

sort(houses.begin(), houses.end());

sort(heaters.begin(), heaters.end());

int startindex = 0, maxn = 0;

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

int tempmin = INT_MAX;

for(int j = startindex; j < heaters.size(); j++) {

if(abs(heaters[j] - houses[i]) <= tempmin) {

tempmin = abs(heaters[j] - houses[i]);

startindex = j;

} else {

break;

}

maxn = max(maxn, tempmin);

}

return maxn;

}

};

LeetCode 387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.
Note: You may assume the string contain only lowercase letters.

分析：map存储每个字符的出现次数，从头遍历数组return第一个m[s[i]] == 1的下标。如果没有就return -1。

class Solution {
public:
    int firstUniqChar(string s) {
        map<char, int> m;
        for(int i = 0; i < s.length(); i++)
            m[s[i]]++;
        for(int i = 0; i < s.length(); i++) {
            if(m[s[i]] == 1)
                return i;
        }
        return -1;
    }
};

class Solution {

public:

int firstUniqChar(string s) {

map<char, int> m;

for(int i = 0; i < s.length(); i++)

m[s[i]]++;

for(int i = 0; i < s.length(); i++) {

if(m[s[i]] == 1)

return i;

}

return -1;

}

};

LeetCode383. Ransom Note

Given  an  arbitrary  ransom  note  string  and  another  string  containing  letters from  all  the  magazines,  write  a  function  that  will  return  true  if  the  ransom   note  can  be  constructed  from  the  magazines ;  otherwise,  it  will  return  false.

Each  letter  in  the  magazine  string  can  only  be  used  once  in  your  ransom  note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

题目大意：给两个string，判断第一个string能否由第二个string里面所含有的字母组成，第二个string里面的所有字母只能使用一次~

分析：建立一个hash数组，对第二个string遍历并记录每个字符出现的次数，然后遍历第一个string，如果有出现hash里面不存在的字符，那么return false～

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> hash(256);
        for(int i = 0; i < magazine.size(); i++)
            hash[magazine[i]]++;
        for(int i = 0; i < ransomNote.size(); i++)
            if(hash[ransomNote[i]])
                hash[ransomNote[i]]--;
            else
                return false;
        return true;
    }
};

class Solution {

public:

bool canConstruct(string ransomNote, string magazine) {

vector<int> hash(256);

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

hash[magazine[i]]++;

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

if(hash[ransomNote[i]])

hash[ransomNote[i]]--;

else

return false;

return true;

}

};

LeetCode 371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

分析：位运算~
首先，已知异或（就是这个“^”符号）可以得到：
0^0 = 0
0^1 = 1
1^1 = 0
正是位相加时该位的结果~（只不过还有个进位没加罢了~）
所以对于还没有加进位的result，result可以暂时等于a^b

其次，已知与运算（就是这个“&”符号）可以得到：
0&0 = 0
0&1 = 0
1&1 = 1
正是位相加时候有进位的那一位标注为了1~
但是进位是往前一个位相加上去的呀~
所以carry = (a & b) << 1

现在处理要把result加上进位的事情～
如果进位carry等于0，那么不用加～直接等于result的值就好了～
如果进位不等于0，那么就要把result和carry的值按位相加～
按位相加的结果也可能导致进位~所以先用个临时变量temp把carry的值保存，然后令carry = (result & temp) << 1（也就是result和原来carry按位相加后进位的结果～），然后result = result ^ temp（也就是result和原来carry按位相加的结果～），不断循环往复，直到有一次carry等于0，不再需要进位了～～

class Solution {
public:
    int getSum(int a, int b) {
        int carry = (a & b) << 1;
        int result = (a ^ b);
        while(carry != 0) {
            int temp = carry;
            carry = (result & temp) << 1;
            result = result ^ temp;
        };
        return result;
    }
};

class Solution {

public:

int getSum(int a, int b) {

int carry = (a & b) << 1;

int result = (a ^ b);

while(carry != 0) {

int temp = carry;

carry = (result & temp) << 1;

result = result ^ temp;

};

return result;

}

};

LeetCode 349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1;
        set<int> s2;
        for(int i = 0; i < nums1.size(); i++) {
            s1.insert(nums1[i]);
        }
        for(int i = 0; i < nums2.size(); i++) {
            if(s1.find(nums2[i]) != s1.end()) {
                s2.insert(nums2[i]);
            }
        }
        vector<int> v;
        for(set<int>::iterator it = s2.begin(); it != s2.end(); it++) {
            v.push_back(*it);
        }
        return v;
    }
};

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

set<int> s1;

set<int> s2;

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

s1.insert(nums1[i]);

}

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

if(s1.find(nums2[i]) != s1.end()) {

s2.insert(nums2[i]);

}

vector<int> v;

for(set<int>::iterator it = s2.begin(); it != s2.end(); it++) {

v.push_back(*it);

}

return v;

}

};