热门标签 | 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 " <}



推荐阅读
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文详细介绍了 GWT 中 PopupPanel 类的 onKeyDownPreview 方法,提供了多个代码示例及应用场景,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 导航栏样式练习:项目实例解析
    本文详细介绍了如何创建一个具有动态效果的导航栏,包括HTML、CSS和JavaScript代码的实现,并附有详细的说明和效果图。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 1.如何在运行状态查看源代码?查看函数的源代码,我们通常会使用IDE来完成。比如在PyCharm中,你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢?当我们想使用一个函 ... [详细]
  • 本文详细介绍如何使用arm-eabi-gdb调试Android平台上的C/C++程序。通过具体步骤和实用技巧,帮助开发者更高效地进行调试工作。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 在 Windows 10 中,F1 至 F12 键默认设置为快捷功能键。本文将介绍几种有效方法来禁用这些快捷键,并恢复其标准功能键的作用。请注意,部分笔记本电脑的快捷键可能无法完全关闭。 ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
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社区 版权所有