LeetCode OJ – 第25页

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

}

};

LeetCode 153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

分析：二分搜索法，即使旋转过了也会一半的任何一个元素始终比另一半的任何一个元素大，所以如果nums[mid] < nums[high]，说明最小元素一定在[left, mid]中，所以令high = mid；否则一定在[mid + 1, high]中，令low = mid + 1～～

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        while(low < high) {
            int mid = (low + high) / 2;
            if(nums[mid] < nums[high])
                high = mid;
            else
                low = mid + 1;
        }
        return nums[low];
    }
};

class Solution {

public:

int findMin(vector<int>& nums) {

int low = 0, high = nums.size() - 1;

while(low < high) {

int mid = (low + high) / 2;

if(nums[mid] < nums[high])

high = mid;

else

low = mid + 1;

}

return nums[low];

}

};

LeetCode 167. Two Sum II – Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

分析：每个数遍历找他的后面是否存在与它相加等于target的数，如果存在就放入result数组中～

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result(2);
        for(int i = 0; i < numbers.size(); i++) {
            for(int j = i + 1; j < numbers.size(); j++) {
                if(numbers[i] + numbers[j] == target) {
                    result[0] = i + 1;
                    result[1] = j + 1;
                    break;
                } else if(numbers[i] + numbers[j] > target) {
                    break;
                }
            }
            if(result[0] != 0)
                break;
        }
        return result;
    }
};

class Solution {

public:

vector<int> twoSum(vector<int>& numbers, int target) {

vector<int> result(2);

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

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

if(numbers[i] + numbers[j] == target) {

result[0] = i + 1;

result[1] = j + 1;

break;

} else if(numbers[i] + numbers[j] > target) {

break;

}

if(result[0] != 0)

break;

}

return result;

}

};