热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

C++编程实战训练营第二期

题目1:给定一个非空数组A,包含有N个整数,起始下标为0。数组包含有奇数个元素,其中除了唯一一个元素之外,其他

题目1:

给定一个非空数组 A,包含有 N 个整数,起始下标为 0。数组包含有奇数个元素,其中除了唯一一个元素之外,其他每个元素都可以与数组中另一个有相同值的元素配对。

比如,在下面这个数组中:

A[0] = 9 A[1] = 3 A[2] = 9A[3] = 3 A[4] = 9 A[5] = 7A[6] = 9

  • 下标为 0 和 2 的元素的值是 9
  • 下标为 1 和 3 的元素的值是 3
  • 下标为 4 和 6 的元素的值是 9
  • 下标为 5 的元素的值是 7,无法配对

写一个函数:

int solution(vector &A);

对满足上述条件的数组 A,返回数组中无法配对的元素的值。

假定:

  • N is an odd integer within the range [1..1,000,000];
  • 数组 A 每个元素是取值范围 [1..1,000,000,000] 内的 整数 ;
  • all but one of the values in A occur an even number of times.

比如,给定以下数组:

A[0] = 9 A[1] = 3 A[2] = 9A[3] = 3 A[4] = 9 A[5] = 7A[6] = 9

函数应该返回 7,如上述解释。

复杂度:

  • 最坏-情况下,期望的时间复杂度是 O(N);
  • 最坏-情况下,期望的空间复杂度是 O(1), 输入存储除外 (不计输入参数所需的存储空间).

程序:

#include
#include
using namespace std;
//输出容器内所有值
void printf_vector(vector &A)
{auto v&#61;A;auto it&#61;v.begin();while (it !&#61; v.end()){cout<<*it<<" ";it&#43;&#43;;}cout<}
/*在容器v中,从a处开始&#xff0c;b处结束&#xff0c;寻找c&#xff0c;最后返回c的位置*/
vector::iterator find_vector(vector &A, vector::iterator a, vector::iterator b, int c)
{auto it&#61;a;auto v&#61;A;while (it !&#61; b){if(*it&#61;&#61;c)return it;it&#43;&#43;;}return it;//没找到&#xff0c;返回A.endl()
}
int solution(vector &A)
{vector v&#61;A;auto it&#61;v.begin();while (it !&#61; v.end()){//printf_vector(v);//auto it_temp&#61;find(it&#43;1,v.end(),*it);//vector自带的find函数auto it_temp&#61;find_vector(v,it&#43;1,v.end(),*it);//自定义的find函数if(it_temp&#61;&#61;v.end())return *it;elsev.erase(it_temp); it&#43;&#43;;}return -1;
}
int main()
{
vector v&#61;{9,3,9,3,9,7,7,10,9};
cout<getchar();
}

程序虽然能得出正确结&#xff0c;但是当容器内容很大时&#xff0c;效率比较低&#xff0c;还有很大的优化空间&#xff0c;如果有大神有更好的解决办法&#xff0c;望告知&#xff0c;万分感谢&#xff01;&#xff01;

题目2&#xff1a;

A zero-indexed array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A &#61; [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

vector solution(vector &A, int K);

that, given a zero-indexed array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

A &#61; [3, 8, 9, 7, 6] K &#61; 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7] [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9] [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A &#61; [0, 0, 0] K &#61; 1

the function should return [0, 0, 0]

Given

A &#61; [1, 2, 3, 4] K &#61; 4

the function should return [1, 2, 3, 4]

Assume that:

  • N and K are integers within the range [0..100];
  • each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

程序&#xff1a;

#include
#include
using namespace std;//输出容器内所有值
void printf_vector(vector &A)
{auto v &#61; A;auto it &#61; v.begin();while (it !&#61; v.end()){cout <<*it <<" ";it&#43;&#43;;}cout <}vector solution1(vector &A, int K)//此处K<&#61;N
{auto v &#61; A;auto count &#61; K;vector v1;vector v2;while (count){v1.push_back(*(v.end() - count));//把容器v的最后K个元素保存到容器v1count--;}count &#61; K;auto it &#61; v1.begin();/*将在v1的元素&#xff08;即v的后K个元素&#xff09;保存进v2*/while (it !&#61; v1.end()){v2.push_back(*it);it&#43;&#43;;}/*容器v中的前面要右移的元素保存进v2*/it &#61; v.begin();while (it !&#61; v.end() - K){v2.push_back(*it);it&#43;&#43;;}return v2;
}vector solution(vector &A, int K)
{ if(A.empty()) return A;else if((K % (A.end() - A.begin()))&#61;&#61;0) return A; //K刚好为容器大小的整数倍else {auto v&#61;solution1(A,K%(A.end() - A.begin()));return v;}
}
int main()
{vector v&#61;{ 1,2,3,1};int K&#61;5;//printf_vector(v);vector v1 &#61; solution(v, K);
// cout <<"right shift " <}



推荐阅读
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 本章将深入探讨移动 UI 设计的核心原则,帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧,您将能够创建出既美观又实用的移动应用。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 1.如何在运行状态查看源代码?查看函数的源代码,我们通常会使用IDE来完成。比如在PyCharm中,你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢?当我们想使用一个函 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本文介绍如何使用 NSTimer 实现倒计时功能,详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器,确保在指定时间间隔内执行特定任务。 ... [详细]
  • 尽管使用TensorFlow和PyTorch等成熟框架可以显著降低实现递归神经网络(RNN)的门槛,但对于初学者来说,理解其底层原理至关重要。本文将引导您使用NumPy从头构建一个用于自然语言处理(NLP)的RNN模型。 ... [详细]
author-avatar
十月
我的征途是星辰大海!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有