LeetCode Daily 26

2022-2-9 T.2006 差的绝对值为k的数对数目

 

题目描述:

给你一个整数数组 nums 和一个整数 k ,请你返回数对 (i, j) 的数目,满足 i < j 且 |nums[i] - nums[j]| == k 。

|x| 的值定义为:

如果 x >= 0 ,那么值为 x 。
如果 x < 0 ,那么值为 -x 。

 

示例:

输入:nums = [1,2,2,1], k = 1
输出:4
解释:差的绝对值为 1 的数对为:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

 

思路 ①:

正常遍历数组,符合题意则记录。时间复杂度为O(n^2), 空间复杂度为O(1).

 

代码 ①:

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int ans = 0;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(abs(nums[i] - nums[j]) == k)
                    ans++;
            }
        }
        return ans;
    }
};

 

思路 ②:

题目所求为两数差的绝对值,则去统计 nums[i] - k,nums[i] + k两种情况即可。使用哈希表统计数目即可。

 

代码 ②:

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int ans = 0;
        unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); i++) {
            ans += (map.count(nums[i] + k) ? map[nums[i] + k] : 0);
            ans += (map.count(nums[i] - k) ? map[nums[i] - k] : 0);
            map[nums[i]]++;
        }    
        return ans;
    }
};

 

推荐这些文章:

LeetCode Daily 24

2022-2-6 T.1748 唯一元素的和 
 
题目描述:

给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。

请你返回 nums 中唯一元素的 和 。

 
示例:

输入:nums = [1,2,3,2]
输出:4
解释:唯一元素为 [1,3] ,和为 4 。

 
代码:

class Solution {
public:
int sumOfUnique(vector<int>& nums) {
int sum = 0;
for(int p: nums)...

LeetCode Daily 22

2022-2-3 T.1414 和为 K 的最少斐波那契数列
 
题目描述:

给你数字 k ,请你返回和为 k 的斐波那契数字的最少数目,其中,每个斐波那契数字都可以被使用多次。

斐波那契数字定义为:

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 , 其中 n > 2 。
数据保证对于给定的 k ,一定能找到可行解。

 
示例:

输入:k = 7
输出:2
解释:斐波那契数字为:1,1,2,3,5,8,13,……
对于 k = 7 ,我们可以得到 2 + 5 = 7 。

 
思...

LeetCode Daily 27

2022-2-10 T.1447 最简分数
 
题目描述:

给你一个整数 n ,请你返回所有 0 到 1 之间(不包括 0 和 1)满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。

 
示例:

输入:n = 4
输出:["1/2","1/3","1/4","2/3","3/4"]
解释:"2/4" 不是最简分数,因为它可以化简为 "1/2" 。

 
思路:
分子分母最大公约数为1时则为最简分数。
 
代码:

class Solution {
public:
void cac(int m, vector<st...

LeetCode Daily 23

2022-2-4 T.1725 可以形成最大正方形的矩形数目
 
题目描述:

给你一个数组 rectangles ,其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。

如果存在 k 同时满足 k <= li 和 k <= wi ,就可以将第 i 个矩形切成边长为 k 的正方形。例如,矩形 [4,6] 可以切成边长最大为 4 的正方形。

设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。

请你统计有多少个矩形能够切出边长为 maxLen 的正方形,并返回矩形...

【LeetCode】560. 和为 K 的子数组

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n=nums.size();

int presum[20010]={0};

unordered_map<int,int> mp;
mp[0]=1; //前n项和0,出现次数为1次
int ans = 0;

for(int i=1;i<=n;++i)
{
pres...

LeetCode 1748. 唯一元素的和

1748. 唯一元素的和
Solution
思路:看值域范围非常小,可以直接数组存值,就数组记录出现次数即可。
class Solution {
public int sumOfUnique(int[] nums) {
int len = nums.length;
int[] cnt = new int[100 + 1];
for (int i = 1; i <= 100; i++) {
cnt[i] = 0;
}
for (int i = 0; i < len; i...

LeetCode第 278 场周赛

A
class Solution {
public:
int findFinalValue(vector<int>& nums, int original) {
for (int i = 1; i <= 1000; i ++ ) {
for (auto x : nums) {
if (x == original) {
original *= 2;
}
}
}
r...

【LeetCode】137. 只出现一次的数字 II

class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
int total = 0;
for(int i = 0; i<32 ; ++i)
{
total = 0;
for(int j=0; j<nums.size(); ++j)
{
total+=(nums[j]>>i)&am...

LeetCode第 277 场周赛

A
class Solution {
public:
int countElements(vector<int>& nums) {
int minn = 0x3f3f3f3f, maxx = 0xcfcfcfcf;
for (auto x : nums)
minn = min(minn, x), maxx = max(maxx, x);
int cnt = 0;
for (auto x : nums)
if (x > minn &&...

LeetCode 1765. 地图中的最高点

1765. 地图中的最高点
Solution
思路:开始的思路是直接把水域固定,然后扩散,但是扩散的方式不对,我是默认一圈的最小值直接加1,但是会出现问题,正确做法多源BFS,就是全部默认为-1,然后从水域开始做BFS,如果遇到不是-1的格子,说明一定是从之前的水域出发了,所以不能重复更新,不然就不满足要求了。
class Solution {
int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
Queue<int[]> queue = new ArrayDeque<int[]>();
publi...

文章标题:LeetCode Daily 26
文章链接:https://www.dianjilingqu.com/51170.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>