区块链技术博客
www.b2bchain.cn

程序员进阶之算法练习(五十一)求职学习资料

本文介绍了程序员进阶之算法练习(五十一)求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

正文

题目1

题目链接
题目大意:
给出一个图形,下面是n=1、2、3、4的时候:

程序员进阶之算法练习(五十一)

现在需要把上面的图形染色,由若干个菱形组成;
问,有多少种染色方法?

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每个样例一行,整数𝑛 (1≤𝑛≤10^9).

输出:
每个样例一行,染色的方法数量。

Examples
input
2
2
1
output
2
1
样例解释:
对于样例1,当n=2的时候一共有2种染色方法:
程序员进阶之算法练习(五十一)
对于样例2,当n=1的时候,只有1种染色方法:
程序员进阶之算法练习(五十一)

题目解析:
找规律的问题,先从n=1开始考虑,只有一种方案;
n=2的时候,我们可以采用染色方案1,将第一个竖着的菱形染色;也可以先上下斜着放,将第二个竖着的菱形染色;
同理n=3时,有将第1、2、3个菱形染色的方案;
总结规律, ans=n;

代码实现:

int main(int argc, const char * argv[]) {     // insert code here...      int t;     cin >> t;     while (t--) {         int n;         cin >> n;         cout << n << endl;     }         return 0; }

题目2

题目链接
题目大意:
有n个砝码,每个砝码的重量是一样的;
由于砝码的重量标识已经模糊,只能大概知道的重量区间是在 [a-b, a+b]这个区间内;
现在想知道,这n个砝码的重量,能否在区间[c-d, c+d]内;
如果可以,则输出YES;如果不可以,则输出NO;

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每个样例一行,5个整数 n,𝑎,𝑏,𝑐,𝑑 (1≤𝑛≤1000, 0≤𝑏<𝑎≤1000, 0≤𝑑<𝑐≤1000)

输出:
每个样例一行,如果可以,则输出YES;如果不可以,则输出NO;

Examples
input
5
7 20 3 101 18
11 11 10 234 2
8 9 7 250 122
19 41 21 321 10
3 10 8 6 1

output
Yes
No
Yes
No
Yes

题目解析:
因为a和b比较小,枚举下a和b的区间,可以解决问题;

但是假如,a和b很大呢?(0≤𝑏<𝑎≤10^9, 0≤𝑑<𝑐≤10^9)
我们用[l, r]来表示[c-d, c+d]的区间;
我们用[gapL, gapR] 来表示[(a-b)n, (a+b)n]的区间;
只要这俩个区间有重叠,则表示存在可能性;
这样就不用枚举,复杂度从O(N^2)变成O(1)。

代码实现:

int main(int argc, const char * argv[]) {     // insert code here...      int t;     cin >> t;     while (t--) {         lld n, a, b, c, d;         cin >> n >> a >> b >> c >> d;         lld l = (c - d), r = (c + d);         lld ans = -1;         lld gapL = (a - b) * n, gapR = (a + b) * n;         bool ok = 0;;         if (gapL <= l && l <= gapR) {             ok = 1;         }         else if (gapL <= r && r <= gapR) {             ok = 1;         }         else if (l <= gapL && gapL <= r) {             ok = 1;         }         else if (l <= gapR && gapR <= r) {             ok = 1;         }         if (ok) {             cout << "YES" << endl;         }         else {             cout << "NO" << endl;         }     }         return 0; }

题目3

题目链接
题目大意:
有n个整数组成的数组,现在对数组的元素重新组织,希望新的数组满足:
|𝑎[1]−𝑎[2]| ≤ |𝑎[2]−𝑎[3]| ≤ … ≤ |𝑎[𝑛−1]−𝑎[𝑛]|
求新的数组。

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每t个样例,第一行, 整数𝑛 (3≤𝑛≤10^5)
第二行是n个整数,𝑎1,𝑎2,…,𝑎𝑛 (−10^9≤𝑎𝑖≤10^9).

输出:
每个样例一行,新数组的n个整数;

Examples
input
2
6
5 -2 4 8 6 5
4
8 1 4 2
output
5 5 4 6 8 -2
1 2 4 8

题目解析:
假设n个数字散落在一维数轴上,那么任意两个数字的绝对值之差,就是两个数字在数轴之间的间距;
题目的问题转化为,求一个排列,使得相邻两个数字的间距越来越大;
假设从小到大排序完之后,数组是a[N];容易知道,所有数字中间距的是a[n]-a[1],那么可以将这个数字放到最右边;
同理,第二大的数字要么是a[1]和a[n-1],要么是a[2]和a[n],我们任取其中一种,假设是a[1]和a[n-1];
同理,第三大的数字就是a[2]和a[n-1];
同理,第四大的数字就是a[3]和a[n-1];
如此交替选择,会使得间距越来越小,得到了一种满足题意的解法;

代码实现:

“`
int a[N];
int ans[N];

int main(int argc, const char * argv[]) {
// insert code here…

int t; cin >> t; while (t--) {     int n;     cin >> n;     for (int i = 0; i < n; ++i) cin >>a[i];     sort(a, a + n);     int l = 0, r = n - 1, k = n - 1;     while (l <= r) {         ans[k--] = a[r--];         if (l <= r) {

正文

题目1

题目链接
题目大意:
给出一个图形,下面是n=1、2、3、4的时候:

程序员进阶之算法练习(五十一)

现在需要把上面的图形染色,由若干个菱形组成;
问,有多少种染色方法?

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每个样例一行,整数𝑛 (1≤𝑛≤10^9).

输出:
每个样例一行,染色的方法数量。

Examples
input
2
2
1
output
2
1
样例解释:
对于样例1,当n=2的时候一共有2种染色方法:
程序员进阶之算法练习(五十一)
对于样例2,当n=1的时候,只有1种染色方法:
程序员进阶之算法练习(五十一)

题目解析:
找规律的问题,先从n=1开始考虑,只有一种方案;
n=2的时候,我们可以采用染色方案1,将第一个竖着的菱形染色;也可以先上下斜着放,将第二个竖着的菱形染色;
同理n=3时,有将第1、2、3个菱形染色的方案;
总结规律, ans=n;

代码实现:

int main(int argc, const char * argv[]) {     // insert code here...      int t;     cin >> t;     while (t--) {         int n;         cin >> n;         cout << n << endl;     }         return 0; }

题目2

题目链接
题目大意:
有n个砝码,每个砝码的重量是一样的;
由于砝码的重量标识已经模糊,只能大概知道的重量区间是在 [a-b, a+b]这个区间内;
现在想知道,这n个砝码的重量,能否在区间[c-d, c+d]内;
如果可以,则输出YES;如果不可以,则输出NO;

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每个样例一行,5个整数 n,𝑎,𝑏,𝑐,𝑑 (1≤𝑛≤1000, 0≤𝑏<𝑎≤1000, 0≤𝑑<𝑐≤1000)

输出:
每个样例一行,如果可以,则输出YES;如果不可以,则输出NO;

Examples
input
5
7 20 3 101 18
11 11 10 234 2
8 9 7 250 122
19 41 21 321 10
3 10 8 6 1

output
Yes
No
Yes
No
Yes

题目解析:
因为a和b比较小,枚举下a和b的区间,可以解决问题;

但是假如,a和b很大呢?(0≤𝑏<𝑎≤10^9, 0≤𝑑<𝑐≤10^9)
我们用[l, r]来表示[c-d, c+d]的区间;
我们用[gapL, gapR] 来表示[(a-b)n, (a+b)n]的区间;
只要这俩个区间有重叠,则表示存在可能性;
这样就不用枚举,复杂度从O(N^2)变成O(1)。

代码实现:

int main(int argc, const char * argv[]) {     // insert code here...      int t;     cin >> t;     while (t--) {         lld n, a, b, c, d;         cin >> n >> a >> b >> c >> d;         lld l = (c - d), r = (c + d);         lld ans = -1;         lld gapL = (a - b) * n, gapR = (a + b) * n;         bool ok = 0;;         if (gapL <= l && l <= gapR) {             ok = 1;         }         else if (gapL <= r && r <= gapR) {             ok = 1;         }         else if (l <= gapL && gapL <= r) {             ok = 1;         }         else if (l <= gapR && gapR <= r) {             ok = 1;         }         if (ok) {             cout << "YES" << endl;         }         else {             cout << "NO" << endl;         }     }         return 0; }

题目3

题目链接
题目大意:
有n个整数组成的数组,现在对数组的元素重新组织,希望新的数组满足:
|𝑎[1]−𝑎[2]| ≤ |𝑎[2]−𝑎[3]| ≤ … ≤ |𝑎[𝑛−1]−𝑎[𝑛]|
求新的数组。

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每t个样例,第一行, 整数𝑛 (3≤𝑛≤10^5)
第二行是n个整数,𝑎1,𝑎2,…,𝑎𝑛 (−10^9≤𝑎𝑖≤10^9).

输出:
每个样例一行,新数组的n个整数;

Examples
input
2
6
5 -2 4 8 6 5
4
8 1 4 2
output
5 5 4 6 8 -2
1 2 4 8

题目解析:
假设n个数字散落在一维数轴上,那么任意两个数字的绝对值之差,就是两个数字在数轴之间的间距;
题目的问题转化为,求一个排列,使得相邻两个数字的间距越来越大;
假设从小到大排序完之后,数组是a[N];容易知道,所有数字中间距的是a[n]-a[1],那么可以将这个数字放到最右边;
同理,第二大的数字要么是a[1]和a[n-1],要么是a[2]和a[n],我们任取其中一种,假设是a[1]和a[n-1];
同理,第三大的数字就是a[2]和a[n-1];
同理,第四大的数字就是a[3]和a[n-1];
如此交替选择,会使得间距越来越小,得到了一种满足题意的解法;

代码实现:

“`
int a[N];
int ans[N];

int main(int argc, const char * argv[]) {
// insert code here…

int t; cin >> t; while (t--) {     int n;     cin >> n;     for (int i = 0; i < n; ++i) cin >>a[i];     sort(a, a + n);     int l = 0, r = n - 1, k = n - 1;     while (l <= r) {         ans[k--] = a[r--];         if (l <= r) {

正文

题目1

题目链接
题目大意:
给出一个图形,下面是n=1、2、3、4的时候:

程序员进阶之算法练习(五十一)

现在需要把上面的图形染色,由若干个菱形组成;
问,有多少种染色方法?

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每个样例一行,整数𝑛 (1≤𝑛≤10^9).

输出:
每个样例一行,染色的方法数量。

Examples
input
2
2
1
output
2
1
样例解释:
对于样例1,当n=2的时候一共有2种染色方法:
程序员进阶之算法练习(五十一)
对于样例2,当n=1的时候,只有1种染色方法:
程序员进阶之算法练习(五十一)

题目解析:
找规律的问题,先从n=1开始考虑,只有一种方案;
n=2的时候,我们可以采用染色方案1,将第一个竖着的菱形染色;也可以先上下斜着放,将第二个竖着的菱形染色;
同理n=3时,有将第1、2、3个菱形染色的方案;
总结规律, ans=n;

代码实现:

int main(int argc, const char * argv[]) {     // insert code here...      int t;     cin >> t;     while (t--) {         int n;         cin >> n;         cout << n << endl;     }         return 0; }

题目2

题目链接
题目大意:
有n个砝码,每个砝码的重量是一样的;
由于砝码的重量标识已经模糊,只能大概知道的重量区间是在 [a-b, a+b]这个区间内;
现在想知道,这n个砝码的重量,能否在区间[c-d, c+d]内;
如果可以,则输出YES;如果不可以,则输出NO;

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每个样例一行,5个整数 n,𝑎,𝑏,𝑐,𝑑 (1≤𝑛≤1000, 0≤𝑏<𝑎≤1000, 0≤𝑑<𝑐≤1000)

输出:
每个样例一行,如果可以,则输出YES;如果不可以,则输出NO;

Examples
input
5
7 20 3 101 18
11 11 10 234 2
8 9 7 250 122
19 41 21 321 10
3 10 8 6 1

output
Yes
No
Yes
No
Yes

题目解析:
因为a和b比较小,枚举下a和b的区间,可以解决问题;

但是假如,a和b很大呢?(0≤𝑏<𝑎≤10^9, 0≤𝑑<𝑐≤10^9)
我们用[l, r]来表示[c-d, c+d]的区间;
我们用[gapL, gapR] 来表示[(a-b)n, (a+b)n]的区间;
只要这俩个区间有重叠,则表示存在可能性;
这样就不用枚举,复杂度从O(N^2)变成O(1)。

代码实现:

int main(int argc, const char * argv[]) {     // insert code here...      int t;     cin >> t;     while (t--) {         lld n, a, b, c, d;         cin >> n >> a >> b >> c >> d;         lld l = (c - d), r = (c + d);         lld ans = -1;         lld gapL = (a - b) * n, gapR = (a + b) * n;         bool ok = 0;;         if (gapL <= l && l <= gapR) {             ok = 1;         }         else if (gapL <= r && r <= gapR) {             ok = 1;         }         else if (l <= gapL && gapL <= r) {             ok = 1;         }         else if (l <= gapR && gapR <= r) {             ok = 1;         }         if (ok) {             cout << "YES" << endl;         }         else {             cout << "NO" << endl;         }     }         return 0; }

题目3

题目链接
题目大意:
有n个整数组成的数组,现在对数组的元素重新组织,希望新的数组满足:
|𝑎[1]−𝑎[2]| ≤ |𝑎[2]−𝑎[3]| ≤ … ≤ |𝑎[𝑛−1]−𝑎[𝑛]|
求新的数组。

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
接下来每t个样例,第一行, 整数𝑛 (3≤𝑛≤10^5)
第二行是n个整数,𝑎1,𝑎2,…,𝑎𝑛 (−10^9≤𝑎𝑖≤10^9).

输出:
每个样例一行,新数组的n个整数;

Examples
input
2
6
5 -2 4 8 6 5
4
8 1 4 2
output
5 5 4 6 8 -2
1 2 4 8

题目解析:
假设n个数字散落在一维数轴上,那么任意两个数字的绝对值之差,就是两个数字在数轴之间的间距;
题目的问题转化为,求一个排列,使得相邻两个数字的间距越来越大;
假设从小到大排序完之后,数组是a[N];容易知道,所有数字中间距的是a[n]-a[1],那么可以将这个数字放到最右边;
同理,第二大的数字要么是a[1]和a[n-1],要么是a[2]和a[n],我们任取其中一种,假设是a[1]和a[n-1];
同理,第三大的数字就是a[2]和a[n-1];
同理,第四大的数字就是a[3]和a[n-1];
如此交替选择,会使得间距越来越小,得到了一种满足题意的解法;

代码实现:

“`
int a[N];
int ans[N];

int main(int argc, const char * argv[]) {
// insert code here…

int t; cin >> t; while (t--) {     int n;     cin >> n;     for (int i = 0; i < n; ++i) cin >>a[i];     sort(a, a + n);     int l = 0, r = n - 1, k = n - 1;     while (l <= r) {         ans[k--] = a[r--];         if (l <= r) {

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 程序员进阶之算法练习(五十一)求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们