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...