LeetCode OJ – 第11页

LeetCode 530. Minimum Absolute Difference in BST

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

1
\
3
/
2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.

题目大意：给一棵二叉搜索树，结点的值都为非负，找到两个元素值之差的绝对值的最小值～
分析：二叉搜索树，用中序遍历后得到的结果是从小到大的元素，遍历这个中序遍历后的结果数组，就可以得到两个元素值之差的绝对值的最小值～

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        inOrder(root);
        int result = INT_MAX;
        for (int i = 1; i < tree.size(); i++)
            result = min(result, tree[i] - tree[i-1]);
        return result;
    }
private:
    vector<int> tree;
    void inOrder(TreeNode* root) {
        if (root->left != NULL) inOrder(root->left);
        tree.push_back(root->val);
        if (root->right != NULL) inOrder(root->right); 
    }
};

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

inOrder(root);

int result = INT_MAX;

for (int i = 1; i < tree.size(); i++)

result = min(result, tree[i] - tree[i-1]);

return result;

}

private:

vector<int> tree;

void inOrder(TreeNode* root) {

if (root->left != NULL) inOrder(root->left);

tree.push_back(root->val);

if (root->right != NULL) inOrder(root->right);

}

};

LeetCode 526. Beautiful Arrangement

526. Beautiful Arrangement
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?

Example 1:
Input: 2
Output: 2
Explanation:

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
N is a positive integer and will not exceed 15.

题目大意：N个数1～N，求它有多少种排列方式，满足：对于每一位，i位上的数字能被i整除，或者i能被i位上的数字整除～
分析：深度优先搜索，从N开始一直到0，用visit标记当前元素是否访问过，当当前下标为1的时候表示当前深度优先的一条路径满足条件，result+1，否则遍历visit数组看有没有没被访问过的元素，如果满足(i % index == 0 || index % i == 0)就标记为已经访问过，然后继续向下遍历dfs(index-1)～最后返回result的结果～

class Solution {
public:
    int countArrangement(int N) {
        visit.resize(N+1);
        dfs(N);
        return result;
    }
private:
    int result = 0;
    vector<bool> visit;
    void dfs(int index) {
        if (index == 1) {
            result++;
            return;
        }
        for (int i = 1; i < visit.size(); i++) {
            if (visit[i] == false && (i % index == 0 || index % i == 0)) {
                visit[i] = true;
                dfs(index-1);
                visit[i] = false;
            }
        }
    }
};

class Solution {

public:

int countArrangement(int N) {

visit.resize(N+1);

dfs(N);

return result;

}

private:

int result = 0;

vector<bool> visit;

void dfs(int index) {

if (index == 1) {

result++;

return;

}

for (int i = 1; i < visit.size(); i++) {

if (visit[i] == false && (i % index == 0 || index % i == 0)) {

visit[i] = true;

dfs(index-1);

visit[i] = false;

}

};

LeetCode 525. Contiguous Array

525. Contiguous Array
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

题目大意：给一个二进制数组，找最长的连续子数组，要求子数组里面的0和1的个数相等～
分析：0和1数组，可以考虑把0换成-1，变成-1和0数组，那么本质上就是找是否有下标从i～j的总和为0的子数组～
令map保存sum和sum对应的下标的值，遍历数组每次计算数组当前的sum，如果当前sum之前已经出现过，比如说之前有过一个sum = 2，现在又sum = 2了，说明在第一次sum等于2的时候，它前面所有元素加起来总和是2，那么在它前面去掉2个元素1就能满足0，同理当前的sum = 2也可以通过去掉最前面的2个元素1使sum = 0，所以看看i – m[sum]是否比之前的最大值大，如果比之前最大值大就更新最大值～

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int result = 0, sum = 0;
        for (int i = 0; i < nums.size(); i++)
            if (nums[i] == 0) nums[i] = -1;
        map<int, int> m;
        m[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (m.find(sum) != m.end())
                result = max(result, i - m[sum]);
            else
                m[sum] = i;
        }
        return result;
    }
};

class Solution {

public:

int findMaxLength(vector<int>& nums) {

int result = 0, sum = 0;

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

if (nums[i] == 0) nums[i] = -1;

map<int, int> m;

m[0] = -1;

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

sum += nums[i];

if (m.find(sum) != m.end())

result = max(result, i - m[sum]);

else

m[sum] = i;

}

return result;

}

};

LeetCode 520. Detect Capital

520. Detect Capital
Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.
All letters in this word are not capitals, like “leetcode”.
Only the first letter in this word is capital if it has more than one letter, like “Google”.
Otherwise, we define that this word doesn’t use capitals in a right way.
Example 1:
Input: “USA”
Output: True
Example 2:
Input: “FlaG”
Output: False

题目大意：判断一个字母是否大小写正确：要么全是大写，要么全是小写，或者首字母大写其他小写，否则不满足题意～
分析：判断word[0]和word[1]的大小写，如果word[0]是小写，那后面必须是小写，如果word[0]是大写word[1]是小写，那后面也必须是小写，如果word[0]是大写word[1]也是大写那么后面必须都是大写～

class Solution {
public:
    bool detectCapitalUse(string word) {
        if (word.length() <= 1) return true;
        if (islower(word[0]) || (isupper(word[0]) && islower(word[1]))) {
            for (int i = 1; i < word.length(); i++)
                if (isupper(word[i])) return false;
        } else {
            for (int i = 1; i < word.length(); i++)
                if (islower(word[i])) return false;
        }
        return true;
    }
};

class Solution {

public:

bool detectCapitalUse(string word) {

if (word.length() <= 1) return true;

if (islower(word[0]) || (isupper(word[0]) && islower(word[1]))) {

for (int i = 1; i < word.length(); i++)

if (isupper(word[i])) return false;

} else {

for (int i = 1; i < word.length(); i++)

if (islower(word[i])) return false;

}

return true;

}

};

LeetCode 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

题目大意：给一个集合nums，nums中可能含有重复元素，求nums的所有子集集合～集合中的元素不能重复～

分析：首先对nums进行排序，接着用位运算，j从0到maxn变化，每一次计算j移动i位后最后一位是否为1，如果为1就将nums[i]的值放入result[j]～为了保证不重复，将result的结果放入集合s中，然后将s中的结果再放入result数组中返回～

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        int maxn = pow(2, len);
        vector<vector<int>> result(maxn);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < maxn; j++) {
                if ((j >> i) & 1)
                    result[j].push_back(nums[i]);
            }
        }
        set<vector<int>> s;
        for (int i = 0; i < result.size(); i++)
            s.insert(result[i]);
        result.resize(0);
        for (auto it = s.begin(); it != s.end(); it++)
            result.push_back(*it);
        return result;
    }
};

class Solution {

public:

vector<vector<int>> subsetsWithDup(vector<int>& nums) {

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

int len = nums.size();

int maxn = pow(2, len);

vector<vector<int>> result(maxn);

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

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

if ((j >> i) & 1)

result[j].push_back(nums[i]);

}

set<vector<int>> s;

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

s.insert(result[i]);

result.resize(0);

for (auto it = s.begin(); it != s.end(); it++)

result.push_back(*it);

return result;

}

};

LeetCode 129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

题目大意：给一个二叉树，上面的数字是0～9中的一个，每一个根到叶子结点的路径都代表一个数字。比如1->2->3就是组成一个数字123。找所有根到叶子结点组成数字的总和～

分析：设总和为result～从根结点开始深度优先搜索，如果已经是叶子结点（即左孩子和右孩子都为空）的时候，就将result累加root->val；否则如果左子树不为空，左子树的val值累加root->val的10倍，这样到最后叶子节点的值就变成了根结点到叶子节点组成的数字的值～

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        dfs(root);
        return result;
    }
private:
    int result = 0;
    void dfs(TreeNode* root) {
        if (root == NULL) return;
        if (root->left == NULL && root->right == NULL) {
            result += root->val;
            return;
        }
        if (root->left != NULL) {
            root->left->val += root->val * 10;
            dfs(root->left);
        }
        if (root->right != NULL) {
            root->right->val += root->val * 10;
            dfs(root->right);
        }
    }
};

class Solution {

public:

int sumNumbers(TreeNode* root) {

dfs(root);

return result;

}

private:

int result = 0;

void dfs(TreeNode* root) {

if (root == NULL) return;

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

result += root->val;

return;

}

if (root->left != NULL) {

root->left->val += root->val * 10;

dfs(root->left);

}

if (root->right != NULL) {

root->right->val += root->val * 10;

dfs(root->right);

}

};