题目描述
下面是一个一维数组的 “最大子数组的和” 的动态规划的解法
# include <iostream>
# include <stdio.h>
# include <string.h>
int MaxSum(int* arr, int size)
{
int current = arr[0]; //current max sum
int max = current;
for (int i = 0; i < size; i++)
{
if (current < 0)
current = 0;
current += arr[i];
if (current > max)
max = current;
}
return max;
}
int main(void)
{
char x[40], y[40];
int a1[5] = { -1, 5, 6, -7, 3 };
int a2[5] = { -5, -4, -8, -1, -10 };
int a3[5] = { -1, 5, 6, -7, 10 };
int max1, max2, max3;
max1 = MaxSum(a1, 5);
max2 = MaxSum(a2, 5); //这个应该返回 -1，
max3 = MaxSum(a3, 5);
}
如果我需要返回值返回这个最大子数组的开始和结束的下标，你要怎么修改这个程序？
输入描述：
第一行输入一个整数n，表示数组长度（n < 100000） 第二行输入数组元素
输出描述：
输出和最大的子数组的开始下标、结束下标
示例
输入
9
-2 1 -3 4 -1 2 1 -5 4
输出
3 6
提示
解释：连续子数组 [4,-1,2,1] 的和最大，该子数组在原数组中开始下标为 3， 结束下标为 6。
跟题意，参考代码进行修改，其实不给，都练了这么多了，我们自己应该也能做了
但只有80%通过，就不知道为什么了
#include <stdio.h>
#include <stdlib.h>
void solution(int n,int arr []){
int current = arr[0]; //current max sum
int max = current;
int a=0,b=0;
int ca=0;
for (int i = 0; i < n; i++)
{
if (current < 0){
current = 0;
ca=i;
}
current += arr[i];
if (current > max){
max = current;
a=ca;
b=i;
}
}
printf("%d %d",a,b);
}
int main() {
int n;
scanf("%d", &n);
if(n<1){
printf("-1");
return;
// printf("-1 -1");
}
int* arr;
arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
solution(n, arr);
return 0;
}
题目描述
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如： 两颗二叉树是: Tree 1 1 / 3 2 / 5 Tree 2 2 / 1 3 4 7 合并后的树为 3 / 4 5 / 5 4 7
输入描述：
第一行输入整数n，m。(分别表示树1和树2的节点数,1<=n<=100) 第二行，第三行分别输入两棵树每个节点的权值p。(1<=p<100)
输出描述：
输出合并后的树。
示例
输入
5 7
1 3 2 5 0
2 1 3 0 4 0 7
输出
3 4 5 5 4 0 7
按示例就是同位置上的数相加就行
示例是这样的
如果还有第三层，空子树就会影响
原题应该是Leetcode617，人家直接用的树，就比较简单，这里要自己整理，就比较繁琐。
直接同位相加有60%通过率
到最后还是没通过，先记下
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void count(int n,int m,int arr1[],int arr2[]){
for(int i=0;i<m;i++){
if(i<n){
printf("%d ",arr1[i]+arr2[i]);
}else{
printf("%d ",arr2[i]);
}
}
}
void solution2(int n, int m, int arr1[], int arr2[]){
if(n<m){
count(n,m,arr1,arr2);
}else{
count(m,n,arr2,arr1);
}
}
void solution(int n, int m, int arr1[], int arr2[]){
int line_num=1;
int pn=0;
int pm=0;
int arrn1[1024]={0};//上一行
int arrm1[1024]={0};
int arrn2[1024]={0};//当前行
int arrm2[1024]={0};
arrn1[0]=arr1[0];
arrm1[0]=arr2[0];
line_num=2;
pn=1;
pm=1;
printf("%d ",arr1[0]+arr2[0]);
while(pn<n && pm<m){
//while(0){
for(int i=0;i<line_num;i++){
if(arrn1[i]>0 && pn<n){
arrn2[i*2]=arr1[pn++];
arrn2[i*2+1]=arr1[pn++];
}else{
arrn2[i*2]=-1;
arrn2[i*2+1]=-1;
}
if(arrm1[i]>0 && pm<m){
arrm2[i*2]=arr2[pm++];
arrm2[i*2+1]=arr2[pm++];
}else{
arrm2[i*2]=-1;
arrm2[i*2+1]=-1;
}
}
for(int i=0;i<line_num;i++){
//都是-1就不打印
//printf("num:%d i:%d %d %d\n",line_num,i,arrn2[i],arrm2[i]);
if(arrn2[i]==-1&&arrm2[i]==-1){
continue;
}
int s=0;
if(arrn2[i]>0){
s+=arrn2[i];
}
if(arrm2[i]>0){
s+=arrm2[i];
}
printf("%d ",s);
}
line_num*=2;
memcpy(arrn1,arrn2,sizeof(arrn1));
memcpy(arrm1,arrm2,sizeof(arrm1));
memset(arrn2,0,sizeof(arrn2));
memset(arrm2,0,sizeof(arrm2));
}
while(pn<n){
printf("%d ",arr1[pn++]);
}
while(pm<m){
printf("%d ",arr1[pm++]);
}
}
int main() {
int n;
int m;
scanf("%d", &n);
scanf("%d", &m);
int* arr1;
arr1 = (int*)malloc(n * sizeof(int));
int* arr2;
arr2 = (int*)malloc(m * sizeof(int));
for (int i = 0; i < n; i++)
{
scanf("%d", &arr1[i]);
}
for (int i = 0; i < m; i++)
{
scanf("%d", &arr2[i]);
}
solution(n, m, arr1, arr2);
return 0;
}
题目描述
小艺酱走到一个花之占卜店中。 店员小Q看到小艺酱可怜的样子，允许小艺酱免费占卜一次。 花瓣占卜： 1. 一瓣“在一起”，一瓣“不在一起”；开始的花瓣表示“在一起”。 2. 直到最后一个花瓣落地游戏结束。 3. 可以选择多朵花，选择撕一朵花就必须撕完。
输入描述：
第一行输入花的数量n。(1<=n<=1000) 第二行输入每朵花的花瓣数量。(1<=an<=1e5)
输出描述：
输出小艺酱最多撕下了多少花瓣结果还是在一起。
示例
输入
1
1
输出
1
简单的说就是凑奇数，有n个数，凑最大的奇数。
偶数全都有，如果奇数个数是奇数个，就全要，否则去掉最小的奇数即可
这里用qsort进行奇偶排序，奇数在前，偶数在后，较小的在前。
这个思路经测试只过了70%
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int cmp(const void*pa,const void*pb){
int a=*(int*)pa;
int b=*(int*)pb;
if(a%2==b%2){
//同奇偶，大的放后面
return a>b;
}else{
//偶数放后面
return a%2<b%2;
}
}
void solution(int n,int a []){
int64_t s=0;
qsort(a,n,sizeof(int),cmp);
for(int i=0;i<n;i++){
//printf("%d ",a[i]);
s+=a[i];
}
if(s%2==0){
s-=a[0];
}
if(s%2==0){
printf("%d",0);
}else{
printf("%ld",s);
}
}
int main() {
int n;
scanf("%d", &n);
int* a;
a = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
solution(n, a);
return 0;
}