当前位置: 首页> 房产> 建材 > 品牌推广总监_茂名seo网站推广_真正的免费建站在这里_2345网址导航浏览器

品牌推广总监_茂名seo网站推广_真正的免费建站在这里_2345网址导航浏览器

时间:2025/7/11 23:45:22来源:https://blog.csdn.net/weixin_73861555/article/details/144644935 浏览次数:0次
品牌推广总监_茂名seo网站推广_真正的免费建站在这里_2345网址导航浏览器

目录

排序⼦序列(模拟)

题目解析

讲解算法原理

编写代码

削减整数(贪⼼)

题目解析

讲解算法原理

编写代码


排序⼦序列(模拟)

题目解析

1.题目链接:排序子序列_牛客笔试题_牛客网

2.题目描述

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述:

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)

第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。


 

输出描述:

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列

示例1

输入

6
1 2 3 2 2 1

输出

2

讲解算法原理

解法:
算法思路:

根据题意,⽤指针模拟即可。
(注意:本道题的测试数据不严谨,有可能错误的代码也能提交过~)

编写代码

c++算法代码:

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N];
int main()
{cin >> n;for(int i = 0; i < n; i++) cin >> arr[i];int ret = 0, i = 0; while(i < n){if(i == n - 1){ret++;break;}if(arr[i] < arr[i + 1]){while(i + 1 < n && arr[i] <= arr[i + 1]) i++; ret++;}else if(arr[i] > arr[i + 1]){while(i + 1 < n && arr[i] >= arr[i + 1]) i++; ret++;}else{while(i + 1 < n && arr[i] == arr[i + 1]) i++;}i++;}cout << ret << endl;return 0;
}

java算法代码:

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++)  { arr[i] = in.nextInt();}int ret = 0, i = 0; while(i < n){if(i == n - 1){ret++; break; }if(arr[i] < arr[i + 1]){while(i + 1 < n && arr[i] <= arr[i + 1]) i++; ret++;}else if(arr[i] > arr[i + 1]){while(i + 1 < n && arr[i] >= arr[i + 1]) i++; ret++;}else{while(i + 1 < n && arr[i] == arr[i + 1]) i++;}i++;}System.out.println(ret);}
}

削减整数(贪⼼)

题目解析

1.题目链接:登录—专业IT笔试面试备考平台_牛客网

2.题目描述

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

题目描述

给出一个正整数H,从1开始减,第一次必须减1,每次减的数字都必须和上一次相同或者是上一次的两倍,请问最少需要几次能把H恰好减到0。

输入描述:

第一行给出一个正整数T{T}T,1≤T≤1041 \le T \le 10^41≤T≤104

接下来T行每行一个H,1≤H≤109H,1 \le H \le 10^9H,1≤H≤109

输出描述:

每行一个正整数代表最少的次数

示例1

输入

3 3 5 7

3
3
5
7

输出

2 3 3

2
3
3

讲解算法原理

解法:
算法思路:

贪⼼+数学。
a. 尽可能的翻倍;
b. 不能⽆脑翻倍,只能是 2 * cur 的倍数时,才能翻倍。

编写代码

c++算法代码:

#include <iostream>
using namespace std;
int t, h;
int fun()
{int ret = 0, a = 1;while(h){h -= a;ret++;if(h % (a * 2) == 0){a *= 2;}}return ret;
}
int main()
{cin >> t;while(t--){cin >> h;cout << fun() << endl;}return 0;
}

java算法代码:

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- != 0){int h = in.nextInt(); int ret = 0, a = 1; while(h != 0){h -= a; ret++; if(h % (a * 2) == 0) {a *= 2;}}System.out.println(ret);}}
}

关键字:品牌推广总监_茂名seo网站推广_真正的免费建站在这里_2345网址导航浏览器

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: