1. NC140 排序
题目来源
要求使用堆进行排序
class Solution {
public: void adjustDown(vector<int>& arr, int root, int n){int parent = root;int chiled = root * 2 + 1;while (chiled < n){if (chiled + 1 < n && arr[chiled + 1] > arr[chiled]){chiled++;}if (arr[parent] < arr[chiled]){swap(arr[parent], arr[chiled]);parent = chiled;chiled = parent * 2 + 1;}else{break;}}}vector<int> MySort(vector<int>& arr) {// write code here// 堆排序——升序建大堆int n = arr.size();for(int i = n - 1; i >= 0; i--){adjustDown(arr, i, n);}for(auto &x : arr){std::cout << x << " ";}// 交换 + 调整for (int i = n - 1; i >= 0; i--){adjustDown(arr, 0, i + 1);swap(arr[0], arr[i]);}return arr;}
};
2. 盛最多水的容器
题目来源
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1;int ret = 0;while (left < right){int len = right - left;if (height[left] < height[right]){ret = max(ret, height[left] * len);left++;}else{ret = max(ret, height[right] * len);right--;}}return ret;}
};
