|
桶排序代码
class Solution {
public:
int cnt[int(1e4 + 10)];
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> ans;
for(int i = 0;i<arr.size();i++){
cnt[arr[i]]++;
}
for(int i = 0;i<=10000;i++){
while(k && cnt[i]--){
ans.push_back(i);
k--;
}
if(k == 0) break;
}
return ans;
}
};
归并排序代码
const int maxn = 1e4 + 10;
class Solution {
public:
int tmp[maxn];
vector<int> arr;
void merge_sort(int l,int r){
if(l == r) return ;
int mid = (l + r)>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int idx1 = l,idx2 = mid+1;
for(int i = l;i<=r;i++){
if(idx1 <= mid && idx2 <= r){
if(arr[idx1] < arr[idx2]){
tmp[i] = arr[idx1++];
}else{
tmp[i] = arr[idx2++];
}
}else if(idx1 <= mid){
tmp[i] = arr[idx1++];
}else{
tmp[i] = arr[idx2++];
}
}
for(int i = l;i<=r;i++) arr[i] = tmp[i];
}
vector<int> getLeastNumbers(vector<int>& a, int k) {
arr = a;
merge_sort(0,arr.size()-1);
vector<int> ans;
for(int i = 0;i<k;i++) ans.push_back(arr[i]);
return ans;
}
};
#include <iostream>
#include <stdio.h>
using namespace std;
const int maxn = 1e6 + 10;
int N;
int arr[maxn];
void swap(int &a,int &b){
int tmp = a;
a = b;
b = tmp;
}
void quick_sort(int left,int right,int arr[]){
if(left >= right) return ;
int l = left,r = right,val = arr[left];
while(l < r){
while(l<r && val <= arr[r]) --r;
arr[l] = arr[r];
while(l<r && arr[l] <= val) ++l;
arr[r] = arr[l];
}
arr[l] = val;
quick_sort(left,l-1,arr);
quick_sort(l+1,right,arr);
}
int main(){
cin>>N;
for(int i = 1;i<=N;i++) cin>>arr[i];
quick_sort(1,N,arr);
for(int i = 1;i<=N;i++) cout<<arr[i]<<" ";cout<<'\n';
return 0;
}
class Solution {
public:
vector<int> ans;
void dfs(TreeNode *cur){
if(cur == NULL) return ;
ans.push_back(cur->val);
dfs(cur->left);
dfs(cur->right);
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};
class Solution {
public:
vector<int> ans;
void dfs(TreeNode *cur){
if(cur == NULL) return ;
dfs(cur->left);
dfs(cur->right);
ans.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};
class Solution {
public:
void dfs(TreeNode *cur){
if(cur == NULL) return ;
swap(cur->left,cur->right);
dfs(cur->left);
dfs(cur->right);
}
TreeNode* invertTree(TreeNode* root) {
dfs(root);
return root;
}
};
class Solution {
public:
int dfs(TreeNode *cur,int tag){
if(cur == NULL) return 0;
if(!cur->left && !cur->right) {
if(tag == 0) return cur->val;
else return 0;
}else{
return dfs(cur->left,0) + dfs(cur->right,1);
}
}
int sumOfLeftLeaves(TreeNode* root) {
return dfs(root,1);
}
};
class Solution {
public:
vector<int> pre,in;
int idxin[int(6e3 + 10)];
TreeNode * dfs(int l1,int r1,int l2,int r2){
if(l1 > r1 || l2 > r2) return NULL;
TreeNode *cur = new TreeNode(pre[l1]);
if(l1 == r1) return cur;
else{
int rt = pre[l1] + 3000;
int posmid = idxin[rt],len = posmid - l2;
cur->left = dfs(l1 + 1,l1 + len,l2,posmid-1);
cur->right = dfs(l1 + len + 1,r1,posmid+1,r2);
return cur;
}
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
pre = preorder,in = inorder;
for(int i = 0;i<in.size();i++){
idxin[in[i] + 3000] = i;
}
return dfs(0,pre.size()-1,0,in.size()-1);
}
};
const int maxn = 6e3 + 10;
class Solution {
public:
int ind[maxn];
vector<int> in,post;
TreeNode *dfs(int l1,int r1,int l2,int r2){
if(l1 > r1 || l2 > r2) return NULL;
int val = post[r2];
TreeNode *rt = new TreeNode(val);
if(l1 == r1) return rt;
else{
int mid = ind[val + 3000];
int len = mid - l1;
rt->left = dfs(l1,mid-1,l2,l2 + len - 1);
rt->right = dfs(mid+1,r1,l2 + len,r2-1);
return rt;
}
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
in = inorder,post = postorder;
for(int i = 0;i<in.size();i++){
ind[in[i] + 3000] = i;
}
return dfs(0,in.size()-1,0,post.size()-1);
}
};
class Solution {
public:
vector<int> arr;
TreeNode *dfs(int l,int r){
if(l > r) return NULL;
int mid = (l + r)>>1;
TreeNode *rt = new TreeNode(arr[mid]);
rt->left = dfs(l,mid-1);
rt->right = dfs(mid+1,r);
return rt;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
arr = nums;
return dfs(0,arr.size()-1);
}
};
class Solution {
public:
vector<double> ans;
queue<TreeNode *> q1,q2;
vector<double> averageOfLevels(TreeNode* root) {
if(root == NULL) return ans;
q1.push(root);
while(q1.size()){
double sum = 0,cnt = q1.size();
while(q1.size()){
TreeNode *cur = q1.front();q1.pop();
sum += cur->val;
if(cur->left) q2.push(cur->left);
if(cur->right) q2.push(cur->right);
}
ans.push_back(sum / cnt);
swap(q1,q2);
}
return ans;
}
};
class Solution {
public:
vector<int> ans;
queue<TreeNode *> q1,q2;
vector<int> largestValues(TreeNode* root) {
if(root == NULL) return ans;
q1.push(root);
while(q1.size()){
int mx = q1.front()->val;
while(q1.size()){
TreeNode *cur = q1.front();q1.pop();
mx = max(mx,cur->val);
if(cur->left) q2.push(cur->left);
if(cur->right) q2.push(cur->right);
}
ans.push_back(mx);
swap(q1,q2);
}
return ans;
}
};
class Solution {
public:
vector<int> arr;
struct node{
int sum,pre,suf,ans;
};
node solve(int l,int r){
if(l == r) {
return {arr[l],arr[l],arr[r],arr[l]};
}
int mid = (l + r)>>1;
node ansl = solve(l,mid);
node ansr = solve(mid+1,r);
return {ansl.sum + ansr.sum,max(ansl.pre,ansl.sum + ansr.pre),max(ansr.suf,ansr.sum + ansl.suf),max({ansl.ans,ansr.ans,ansl.suf + ansr.pre})};
}
int maxSubArray(vector<int>& nums) {
arr = nums;
node re = solve(0,arr.size()-1);
return re.ans;
}
};
|