liuchuo – 第160页

LeetCode 406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

题目大意：给一组序列(h, k), h表示身高，k表示在当前人的前面有k个人比他高，求满足这样的排队序列～

分析：先将所有人按照身高h排序，如果他们的身高h相同就按照k从小到大排序～接下来就可以构建result数组了，从排序好的序列第一个数开始一直遍历到最后一个，依次把它插入到result数组的第k位，因为对于当前这个人，他说了比他高的人是k个，而整个数组按照身高排序了，所以前面的所有人都是比他高的，排他的队伍的时候只需要排到第k位就能满足他前面比他高的人是k个～这样将所有人都插入后得到的result即为所求队伍的顺序～～

class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        vector<pair<int, int>> result;
        if(people.size() == 0)
            return result;
        auto cmp = [](pair<int, int> p1, pair<int, int> p2) {
            if(p1.first == p2.first)
                return p1.second < p2.second;
            else
                return p1.first > p2.first;
        };
        sort(people.begin(), people.end(), cmp);
        for(auto it : people) {
            result.insert(result.begin() + it.second, it);
        }
        return result;
    }
};

class Solution {

public:

vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {

vector<pair<int, int>> result;

if(people.size() == 0)

return result;

auto cmp = [](pair<int, int> p1, pair<int, int> p2) {

if(p1.first == p2.first)

return p1.second < p2.second;

else

return p1.first > p2.first;

};

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

for(auto it : people) {

result.insert(result.begin() + it.second, it);

}

return result;

}

};

LeetCode 413. Arithmetic Slices

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.
Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

题目大意：求一个数组中能构成至少连续三个数的等差数列的个数

分析：有一个规律是：
连续3个数构成等差数列，能组成的等差数列个数是1
连续4个数构成等差数列，能组成的等差数列个数是3（1+2）
连续5个数构成等差数列，能组成的等差数列个数是6（1+2+3）
……
所以每次当有三个构成等差数列的时候，cnt = 1，之后每连续增加一个数满足与之前的数构成等差数列，就令cnt++，并且将结果加到最终的result里面～

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int cnt = 0, result = 0;
        for(int i = 2; i < A.size(); i++) {
            if(A[i-1] - A[i-2] == A[i] - A[i-1]) {
                cnt++;
                result += cnt;
            } else {
                cnt = 0;
            }
        }
        return result;
    }
};

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

int cnt = 0, result = 0;

for(int i = 2; i < A.size(); i++) {

if(A[i-1] - A[i-2] == A[i] - A[i-1]) {

cnt++;

result += cnt;

} else {

cnt = 0;

}

return result;

}

};

LeetCode 11. Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

题目大意：给出一个数组height, height[i] = j表示横坐标为i处的高为j，以(i, j)与x轴作垂线段，计算两条垂线段和x轴组成的容器能装的最多的水的容量是多少~

分析：容器两条边中取最短的那条边为影响容器容积的高，所以说，我们先假设left和right分别在最左边最右边，要想求得容器容积的最大值，需要考虑改变最短边的高度，如果左边短就让left++，如果右边短就让right–，直到直到一个area容积最大的值返回～

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, area = 0;
        while(left < right) {
            area = max(area, min(height[left], height[right]) * (right - left));
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        return area;
    }
};

class Solution {

public:

int maxArea(vector<int>& height) {

int left = 0, right = height.size() - 1, area = 0;

while(left < right) {

area = max(area, min(height[left], height[right]) * (right - left));

if(height[left] < height[right])

left++;

else

right--;

}

return area;

}

};

LeetCode 451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
“tree”

Output:
“eert”

Explanation:
‘e’ appears twice while ‘r’ and ‘t’ both appear once.
So ‘e’ must appear before both ‘r’ and ‘t’. Therefore “eetr” is also a valid answer.
Example 2:

Input:
“cccaaa”

Output:
“cccaaa”

Explanation:
Both ‘c’ and ‘a’ appear three times, so “aaaccc” is also a valid answer.
Note that “cacaca” is incorrect, as the same characters must be together.
Example 3:

Input:
“Aabb”

Output:
“bbAa”

Explanation:
“bbaA” is also a valid answer, but “Aabb” is incorrect.
Note that ‘A’ and ‘a’ are treated as two different characters.

分析：在cnt数组中保存每个字母出现的次数，然后按照出现次数的顺序对字符串进行排序～

class Solution {
public:
    string frequencySort(string s) {
        int cnt[256] = {0};
        for(int i = 0; i < s.length(); i++)
            cnt[s[i]]++;
        sort(s.begin(), s.end(), [&](char a, char b) {
            return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
        });
        return s;
    };
};

class Solution {

public:

string frequencySort(string s) {

int cnt[256] = {0};

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

cnt[s[i]]++;

sort(s.begin(), s.end(), [&](char a, char b) {

return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);

});

return s;

};

LeetCode 145. Binary Tree Postorder Traversal

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

分析：后序遍历，左右根～

/**
 * 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> result;
    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return result;
    }
    void dfs(TreeNode* root) {
        if(root == NULL) return;
        dfs(root->left);
        dfs(root->right);
        result.push_back(root->val);
    }
};

/**

* 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> result;

vector<int> postorderTraversal(TreeNode* root) {

dfs(root);

return result;

}

void dfs(TreeNode* root) {

if(root == NULL) return;

dfs(root->left);

dfs(root->right);

result.push_back(root->val);

}

};

LeetCode 94. Binary Tree Inorder Traversal

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

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

分析：中序遍历，先遍历左子树，再输出中间，再遍历右子树～

/**
 * 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> result;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return result;
    }
    void dfs(TreeNode* root) {
        if(root == NULL) return ;
        dfs(root->left);
        result.push_back(root->val);
        dfs(root->right);
    }
};

/**

* 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> result;

vector<int> inorderTraversal(TreeNode* root) {

dfs(root);

return result;

}

void dfs(TreeNode* root) {

if(root == NULL) return ;

dfs(root->left);

result.push_back(root->val);

dfs(root->right);

}

};