代码随想录算法训练营14期第6天| 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

本文主要是介绍代码随想录算法训练营14期第6天| 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

242. 有效的字母异位词https://leetcode.cn/problems/valid-anagram/

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

因为本题比较基础,所以给出完整的输入输出代码如下:

#include<iostream>
#include<map>
#include<string>
using namespace std;class Solution {
public:bool isAnagram(string s, string t) {int record[26] = {0};for (int i = 0; i < s.size(); i++) {record[s[i] - 'a']++;}for (int i = 0; i < t.size(); i++) {record[t[i] - 'a']--;}for (int i = 0; i < 26; i++) {if (record[i] != 0)return false;}return true;}
};int main() {string s;string t;Solution Judge;cout << "String s:" << endl;cin >> s;cout << "String s:" << endl;cin >> t;if (Judge.isAnagram(s, t)) {cout << "True" << endl;}else {cout << "False" << endl;}
}

总结:

1.本题用的是最简单的哈希法,数组。因为数组本身包含了键值顺序,而本题的键值要求仅有26个,故本题中可以使用数组。

2.哈希法在时间复杂度上具有优势,和暴力破解的O(n²)相比,哈希法避免了重复比较操作,但是在空间复杂度上具有劣势,也是属于以空间换时间的方法。

349. 两个数组的交集https://leetcode.cn/problems/intersection-of-two-arrays/

给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的

解法1(数组实现):

 鉴于上一题数组的成功经验,这里也同样尝试一下先用数组;

思路是先用两个包含bool值的数组来记录数字在各集合中出现的次数,随后将同时为true的键值push到int型的数组中

(涉及知识点:vector容器)

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<bool> sect_1(1001, false);vector<bool> sect_2(1001, false);vector<int> inter_sect;for (int i = 0; i < nums1.size(); i++){sect_1[nums1[i]] = true;}for (int i = 0; i < nums2.size(); i++){sect_2[nums2[i]] = true;    //直接复制代码改造的时候记得改变量 }for(int i = 0; i < 1001; i++){if (sect_1[i] && sect_2[i]) inter_sect.push_back(i); }return inter_sect;}
};

结果: 

解法2(集合实现):

1.考虑到数组在实现时需要提前知道数据量的大小,如果不知道的话本题的两个统计用的bool数组便无从谈起,为此我们可以尝试用集合的办法解决本题

2.for (declaration : expression){...},原文中的这个循环条件是C++ 11标准中的另一种循环格式,其中:

declaration的效果类似于int i=0,和后面的expression类型应该是一样的,定义的变量还可以用auto关键字表示,进而对数据类型形成自适应。

expression就是需要遍历的序列,一般是事先定义好的。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set;int hash[1005] = {0};for (int num: nums1){hash[num] = 1;}for (int num:nums2){if(hash[num] == 1){result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());}
};

  结果: 

总结:

感觉集合方面的一些操作还是不够熟练,依然得多练练

202. 快乐数https://leetcode.cn/problems/happy-number/

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2:

输入:n = 2
输出:false

提示:

  • 1 <= n <= 231 - 1

解法1:(集合统计方法)

#include<iostream>
#include<unordered_set>
#include<set>
#include<string>
using namespace std;class Solution {
public:int getsum(int n) {int sum = 0;while (n) {sum += (n % 10) *(n % 10);n /= 10;}return sum;}bool isHappy(int n) {unordered_set<int> s1;while (1) {int sum = getsum(n);if (sum == 1) {return true;}else if (s1.find(sum) != s1.end()) {return false;}else {s1.insert(sum);}n = sum;}}
};void main() {int n;cout << "Number to identify:" << endl;cin >> n;Solution Judge;if (Judge.isHappy(n)) {cout << "True" << endl;}else {cout << "False" << endl;}}

总结:

1.这道题依然个人还是有些不熟练,可能日后还得多练练,并且找一些相关的题目

2.对于为什么要使用集合而不是使用数组,这里我还是不是很清楚,我并不了解集合在这道题里面的优势

3.对于求每一位的和这个基本操作仍然不熟练,需要多多练习

1. 两数之和https://leetcode.cn/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

解法1(Map实现):

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> destin;for (int i = 0; i < nums.size(); i++) {int se = target - nums[i];unordered_map<int, int>::iterator iter = destin.find(se);if (iter != destin.end()) {return { iter->second, i };		// What does "{" mean here?}destin.insert(pair<int, int>(nums[i], i));		// What to be inserted should be maps and pairs}return {};}
};

总结:

1. 这题已经纠结很久了,没啥好说的哈哈哈

2.依然不熟练,还是又不懂得地方

3.return { iter->second, i },这句话的意思还需要再明确一下

4.对于map的insert形式还需要再推敲一下

这篇关于代码随想录算法训练营14期第6天| 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/767394

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim