力扣8.28

2024-08-29 18:12

文章标签 力扣 8.28

本文主要是介绍力扣8.28，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

219.存在重复元素Ⅱ

题目

给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回true ；否则，返回 false 。

数据范围

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

分析

双指针+map

代码

class Solution {
public:map<int, int> cnt;bool containsNearbyDuplicate(vector<int>& nums, int k) {int l = 0, r = 0;int t = min(k, (int)nums.size());for(int i = 0; i < t; i ++ ) {cnt[nums[i]] ++ ;if(cnt[nums[i]] >= 2) return true;}r = t;while(l < r && r < nums.size()) {if(cnt[nums[r]] >= 1) {return true;}else {cnt[nums[r ++ ]] ++ ;cnt[nums[l ++ ]] -- ;}}return false;}
};

73.矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

数据范围

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

分析

对于a[i][j]==0，将其所在行和列置0等价于先将a[i][0]和a[0][j]置为0，再将a[i][0]所在行和a[0][j]所在列置为0，所以第一轮扫描就可以将每个0元素行和列的开头置为0作为标记，然后第二轮扫描再将对应行和对应列的元素设置为0，需要注意的是，若第一行和第一列本来就有零元素，也需要做个标记，并在最后的时候将第一行和第一列置为0，注意一下细节，例如第一轮扫描时需要避开第一行和第一列，否则会影响到第二轮置零操作

代码

class Solution {
public:void print(int n, int m, vector<vector<int>>& matrix) {for(int i = 0; i < n; i ++ ) {for(int j = 0; j < m; j ++ ) {cout << matrix[i][j] << " ";}cout << endl;}}void setZeroes(vector<vector<int>>& matrix) {bool flagx = false, flagy = false;int n = matrix.size();int m = matrix[0].size();for(int i = 0; i < n; i ++ ) {if(matrix[i][0] == 0) flagx = true;}for(int i = 0; i < m; i ++ ) {if(matrix[0][i] == 0) flagy = true;}for(int i = 0; i < n; i ++ ) {for(int j = 0; j < m; j ++ ) {if(!i || !j) continue;if(!matrix[i][j]) { matrix[i][0] = 0;matrix[0][j] = 0;}}}for(int i = 1; i < n; i ++ ) {if(!matrix[i][0]) {for(int j = 0; j < m; j ++ ) {matrix[i][j] = 0;}} }for(int i = 1; i < m; i ++ ) {if(!matrix[0][i]) {for(int j = 0; j < n; j ++ ) {matrix[j][i] = 0;}}}if(!matrix[0][0]) {for(int i = 0; i < n; i ++ ) matrix[i][0] = 0;for(int i = 0; i < m; i ++ ) matrix[0][i] = 0;}if(flagx) {for(int i = 0; i < n ;i ++ ) {matrix[i][0] = 0;}}if(flagy) {for(int i = 0; i < m; i ++ ) {matrix[0][i] = 0;}}}
};