4.14,堆排序,写点题目
今天学习了一下归并排序
利用的基本的思想的是二分
1把数组进行划分(二分的划分)
2对数组进行合并(排序的划分)
一共就是两步,看似确实简单
其实难度确实简单,代码的话稍稍的长了一点
#include<stdio.h>
#include<stdlib.h>int arr[1000010];
int n;//合并函数
void hbing(int jr[],int arr[],int l,int mid,int r){
int lr=l;
int rr=mid+1;
int pos=l;
while(lr<=mid&&rr<=r){if(arr[lr]<arr[rr])jr[pos++]=arr[lr++];elsejr[pos++]=arr[rr++];
}while(lr<=mid){jr[pos++]=arr[lr++];
}
while(rr<=r){jr[pos++]=arr[rr++];
}
for(int j=l;j<=r;j++)arr[j]=jr[j];}//划分函数
void msort(int jr[],int a[],int l,int r){if(r==l){return ;}else{int mid=(l+r)/2;msort(jr,a,l,mid);msort(jr,a,mid+1,r);hbing(jr,a,l,mid,r);}}//归并入口
void putsort(int arr[],int l,int r){int* jr=(int*)malloc(sizeof(int)*1000010);if(jr){msort(jr,arr,1,n);free(jr);}else{printf("sorry:error was happen\\n");}
}int main(){
scanf("%d",&n);for(int j=1;j<=n;j++)scanf("%d",&arr[j]);
putsort(arr,1,n);for(int j=1;j<=n;j++)printf("%d ",arr[j]);return 0;
}递归二分到只有一个元素
并且开一个数组记录合并的过程
最后把创建的数组,赋值给原数组,这样原数组就排好了
排序确实没啥好讲的
来点题目好搞
1641. 统计字典序元音字符串的数目
难度中等156收藏分享切换为英文接收动态反馈
给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
示例 1：
输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
示例 2：
输入：n = 2 输出：15 解释：仅由元音组成的 15 个字典序字符串为 ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"] 注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后
示例 3：
输入：n = 33 输出：66045
有点dp的味道
要得到ans[n]等于以每个原音字母结尾字符串的和
我们用a[]数组来记录每个字母结尾的数目
n长度的字符串的个数与n-1的字符串的尾字母有关
可以得到递推关系
a[n]=a[n-1]+a[n-2]......a[1];
不断的递推更新a[]数组
最后把a[]数组全部加起来就是答案了
int countVowelStrings(int n){int a[6];a[5]=1;a[4]=1;a[3]=1;a[2]=1;a[1]=1;for(int u=1;u<n;u++){a[5]+=a[4]+a[3]+a[2]+a[1];a[4]+=a[3]+a[2]+a[1];a[3]+=a[2]+a[1];a[2]+=a[1];}return a[5]+a[4]+a[3]+a[2]+a[1];
}懒得用递归了,用循环可以搞定的,就不上递归了
下一个
给你一个整数数组 nums ，返回出现最频繁的偶数元素。
如果存在多个满足条件的元素，只需要返回 最小 的一个。如果不存在这样的元素，返回 -1 。
示例 1：
输入：nums = [0,1,2,2,4,4,1]
输出：2
解释：
数组中的偶数元素为 0、2 和 4 ，在这些元素中，2 和 4 出现次数最多。
返回最小的那个，即返回 2 。
示例 2：
输入：nums = [4,4,4,9,2,4]
输出：4
解释：4 是出现最频繁的偶数元素。
示例 3：
输入：nums = [29,47,21,41,13,37,25,7]
输出：-1
解释：不存在偶数元素。
提示：
1 <= nums.length <= 2000
0 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/most-frequent-even-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
没啥技术和思想就,纯纯的枚举暴力出奇迹
int mostFrequentEven(int* nums, int numsSize){int a[10000];int b[10000]={0};int i=0;for(int j=0;j<numsSize;j++){if(nums[j]%2==0){int g;for(g=0;g<i;g++){if(a[g]==nums[j]){b[g]++;break;}}if(g==i){a[i]=nums[j];b[i]++;i++;}}}int max=-1;int l=0;for(int j=0;j<i;j++){if(b[j]>=l){if(b[j]==l){if(max>a[j]){l=b[j];max=a[j];}}else{l=b[j];max=a[j];}}}return max; }写的有点少没状态呀,可恶还是有点不习惯呀,但是越来越好了
对封装的能力越来越厉害了呀哈哈
还要写两题
但是先写到这了
撒花谢幕!!!!!!
