202.快乐数
题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ;不是,则返回 false 。
示例 1:
输入:n = 19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2:
输入:n = 2
输出:false
提示:
1 <= n <= 2^31 - 1
方法
本题是简单题,就是思路有点绕
根据解释我们需要确定该数不断平方相加是否为1
不断平方相加不为1,肯定有个终止条件来return false;
在这里的终止条件是出现重复元素。
所以思路如下:
当 n 不为1 的时候,我们比较map中是否有n,有的话说明重复了,return false;如果没有,那么我们将该元素加入map中,然后更新n
直到n=1,我们结束循环,并返回true
代码
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
let map = new Map();
while (n !== 1) {
if (map.has(n)){
return false;
}
map.set(n,1);
n = getNewNumber(n);
}
return true;
};
var getNewNumber = function(n) {
let number = 0;
while (n !== 0) {
// 下面两步可以利用JS语法改成如下:
// number += (n % 10) ** 2 **:指数运算
let ge = n % 10;
number += ge * ge;
n = Math.floor(n / 10);
}
return number;
}
1.两数之和
题目
给定一个整数数组 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
只会存在一个有效答案
方法
简单的Map数据结构应用
遍历数组,如果数组中的元素没有在哈希表中,那么我们将target - nums[i]加入进去,否则将返回[map.get(nums[i]), i]
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let map = new Map();
let res = [-1,-1];
for (let i = 0;i < nums.length;i++){
if (!map.has(nums[i])) {
map.set(target - nums[i],i);
} else {
res[0] = map.get(nums[i]);
res[1] = i;
}
}
return res;
};
454.四数相加 II
题目
给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1:
输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出:2
解释:
两个元组如下:
- (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2:
输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出:1
提示:
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28
方法
解析来源:代码随想录
本题解题步骤:
- 首先定义 一个map,key放a和b两数之和,value 放a和b两数之和出现的次数。
- 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中。
- 定义变量count,用来统计 a+b+c+d = 0 出现的次数。
- 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话,就用count把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[]} nums3
* @param {number[]} nums4
* @return {number}
*/
var fourSumCount = function(nums1, nums2, nums3, nums4) {
let map = new Map();
for (let i = 0;i < nums1.length;i++){
for (let j = 0;j < nums2.length;j++){
let temp = nums1[i] + nums2[j];
map.set(temp,(map.get(temp) || 0) + 1);
}
}
let count = 0;
for (let i = 0;i < nums3.length;i++){
for (let j = 0;j < nums4.length;j++) {
let temp = nums3[i] + nums4[j];
if (map.has(-temp)){
count += map.get(-temp);
}
}
}
return count;
};
15 三数之和
题目
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
方法
哈希表不太适用于本题,本题采用双指针
自己隐隐记得,一个for循环,然后另外设置指针移动
但记岔了,记成了移动 i
本题是for循环中 left = i + 1 移动left和right
nums[i] + nums[left] + nums[right] > 0 则移动right指针
nums[i] + nums[left] + nums[right] < 0 则移动left指针
nums[i] + nums[left] + nums[right] = 0 需要移动right和left指针,移动后要确认一下,是否有重复元素
而 < 0 和 > 0 ;不需要检测有无重复元素,反正不符合条件,不会往res数组中加
代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
nums.sort((a,b) => a-b);
let res = [];
if (nums[0] > 0 || nums[nums.length - 1] < 0) {
return res;
}
for (let i = 0;i < nums.length;i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
} else {
res.push([nums[i],nums[left],nums[right]]);
right--;
left++;
while (right < nums.length - 1 && nums[right] == nums[right+1]) right--;
while (left > 0 && nums[left] == nums[left - 1]) left++;
}
}
}
return res;
};
18.四数之和
题目
给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]
提示:
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
方法
方法同上,多了一层循环文章来源:https://www.toymoban.com/news/detail-417728.html
注意剪枝去重文章来源地址https://www.toymoban.com/news/detail-417728.html
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
let res = [];
nums.sort((a,b) => a-b);
for (let i = 0; i < nums.length; i++) {
// nums[i] > target 直接返回, 剪枝操作
if (nums[i] > 0 && nums[i] > target) {
return res;
}
if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重
continue;
}
for (let j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重
continue;
}
let left = j + 1;
let right = nums.length - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target
let sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
res.push([nums[i],nums[j],nums[left],nums[right]]);
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return res;
};
到了这里,关于代码随想录二刷-哈希表-几数之和 (JS)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!