Leetcode每日一题 —— 3653. 区间乘法查询后的异或 I
- 内容介绍
- 文章标签
- 相关推荐
3653. 区间乘法查询后的异或 I - 力扣（LeetCode）
3653. 区间乘法查询后的异或 I - 给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。 对于每个查询，按以下步骤执行操作： * 设定 idx = li。 * 当 idx <= ri 时： * 更新：nums[idx] = (nums[idx] * vi) % (109 + 7) * 将 idx += ki。 在处理完所有查询后，返回数组 nums...
思路
按题目意思模拟即可，明天估计就没这么简单了。
代码
private static final int MOD = 1000000007;
public int xorAfterQueries(int[] nums, int[][] queries) {
for (int[] query : queries) {
int idx = query[0];
while (idx <= query[1]) {
nums[idx] = (int) ((long) nums[idx] * query[3] % MOD);
idx += query[2];
}
}
int ans = 0;
for (int num : nums) {
ans ^= num;
}
return ans;
}
网友解答：
--【壹】--：
输入规模不大，直接模拟即可。看了一下题目标签有分治，一时没想到这玩意能怎么分治。
class Solution {
public:
int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
// l, r 范围内相隔 k 的元素都乘以 v
// 输入规模不大，可以直接模拟
for(auto& q:queries){
int idx=q[0];
while(idx<=q[1]){
nums[idx]=(int)(((long long)nums[idx]*q[3])%(int)(1e9+7));
idx+=q[2];
}
}
// 异或
int res=0;
for(int num:nums){
res^=num;
}
return res;
}
};
接着复习一些 Hot100 题：
21. 合并两个有序链表 - 力扣（LeetCode）
- 递归思路写起来挺自然的
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 这题可以用递归解决
if(list1==nullptr){
// 链表 1 空了，接下来接 list2 即可
return list2;
}
if(list2==nullptr){
return list1;
}
if(list1->val<=list2->val){
// 链表 1 当前节点值 <= 链表 2 的
list1->next=mergeTwoLists(list1->next,list2);
return list1;
}else{
list2->next=mergeTwoLists(list1,list2->next);
return list2;
}
return nullptr;
}
};
131. 分割回文串 - 力扣（LeetCode）
- 大胆回溯即可
class Solution {
public:
vector<vector<string>> partition(string s) {
// 可以看到 s 的输入范围很小，直接上回溯
vector<vector<string>> res;
vector<string> temp;
int n=s.size();
auto dfs=[&](auto&& self, int start){
if(start>=n){
res.emplace_back(temp);
return;
}
for(int i=start;i<n;i++){
int l=start,r=i;
bool flag=true;
while(l<r){
if(s[l]!=s[r]){
flag=false;
break;
}
l++;
r--;
}
if(flag){
temp.emplace_back(s.substr(start,i-start+1));
self(self,i+1);
temp.pop_back();
}
}
};
dfs(dfs,0);
return res;
}
};
169. 多数元素 - 力扣（LeetCode）
- 这题要求空间复杂度 O(1) 且时间复杂度 O(n)，首先能想到快速选择，因为排序后的中位数必然是结果。
- 除此之外还有比较有技巧的计数解法…这个没想出来。
快速选择：
class Solution {
public:
int majorityElement(vector<int>& nums) {
// 这题其实可以用快速选择写
// 因为出现次数 > floor(n/2)，那么 n/2 这个位置排序后必然是这个数
int n=nums.size();
auto partition=[&](int l, int r){
// 随机选择一个枢轴
int pivotPos=l+rand()%(r-l+1);
int pivot=nums[pivotPos];
nums[pivotPos]=nums[l];
while(l<r){
while(l<r&&nums[r]>pivot){
r--;
}
nums[l]=nums[r];
while(l<r&&nums[l]<=pivot){
l++;
}
nums[r]=nums[l];
}
nums[l]=pivot;
// 返回枢轴最终位置
return l;
};
int left=0,right=n-1;
int targetIdx=(n-1)>>1;
while(left<=right){
// 先划分
int pivotIdx=partition(left,right);
if(pivotIdx==targetIdx){
// pivotIdx 就是 n/2 这个位置
return nums[pivotIdx];
}else if(targetIdx<pivotIdx){
// 在左侧，进入左半边
right=pivotIdx-1;
}else{
// 否则在右侧
left=pivotIdx+1;
}
}
return -1;
}
};
计数方式：
class Solution {
public:
int majorityElement(vector<int>& nums) {
// O(n) 也可以是计数方式来解决
int res=-1;
int count=0;
for(int num:nums){
if(count==0){
// 计数归零，更新结果
res=num;
count++;
}else{
// 否则观察情况
if(num==res){
// 如果和当前数字一样则计数 +1
count++;
}else{
// 否则 -1
count--;
}
}
}
return res;
}
};
200. 岛屿数量 - 力扣（LeetCode）
- 看题目描述立马就能想到并查集。不过统计连通块这点还需要点技巧。
class UnionFind{
private:
vector<int> parents;
vector<int> sizes;
public:
UnionFind(int n){
parents.resize(n,-1);
sizes.resize(n,1);
}
// 带路径压缩查找
int find(int x){
return parents[x]==-1 ? x : parents[x]=find(parents[x]);
}
void merge(int x1,int x2){
int root1=find(x1),root2=find(x2);
if(root1==root2){
// 已经合并
return;
}
// 小树并入大树
if(sizes[root1]<sizes[root2]){
swap(root1,root2);
}
parents[root2]=root1;
sizes[root1]+=root2;
}
void markZero(int x){
parents[x]=-2;
}
int numConnected(){
// 获得连通块数量
int res=0;
for(int i=0;i<parents.size();i++){
if(parents[i]==-1){
res++;
}
}
return res;
}
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
// 连通块数量计数
// 并查集
int m=grid.size(),n=grid[0].size();
UnionFind uf(m*n);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='0'){
uf.markZero(i*n+j);
continue;
}
if(i>0&&grid[i-1][j]=='1'){
uf.merge((i-1)*n+j,i*n+j);
}
if(j>0&&grid[i][j-1]=='1'){
uf.merge(i*n+j-1,i*n+j);
}
}
}
return uf.numConnected();
}
};
--【贰】--：
哎？分治，我去瞅瞅，确实没想到要怎么分。
--【叁】--：
有点懵，一次写对
class Solution:
def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
n = len(nums)
for q in queries:
l, r, k, v = q
for idx in range(l, r + 1, k):
nums[idx] = (nums[idx] * v) % (10 ** 9 + 7)
ans = nums[0]
for i in range(1, n):
ans = ans ^ nums[i]
return ans
--【肆】--：
做完看了下跑得快的，不禁疑问，我是谁，我在哪，我在写什么？
class Solution {
public:
int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
int n =nums.size(),q = queries.size();
const int mod = 1e9 + 7;
int res = 0;
std::sort(queries.begin(),queries.end());
for(int i = 0; i < n; i++) {
for(int j = 0; j < q; j++) {
int l = queries[j][0],r = queries[j][1],k = queries[j][2],v = queries[j][3];
if(r < i) {
continue;
}
if(l > i) {
break;
}
if((i - l) % k == 0) {
nums[i] = (static_cast<long long>(v) * nums[i]) % mod;
}
}
res ^= nums[i];
}
return res;
}
};
--【伍】--：
class Solution:
def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
md = 1_000_000_007
for l, r, k, v in queries:
idx = l
while idx <= r:
nums[idx] = (nums[idx] * v) % md
idx += k
ans = 0
for x in nums:
ans ^= x
return ans
提前看了明天的，直接TLE了，明天看来是又是HOT 100的一天
3653. 区间乘法查询后的异或 I - 力扣（LeetCode）
3653. 区间乘法查询后的异或 I - 给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。 对于每个查询，按以下步骤执行操作： * 设定 idx = li。 * 当 idx <= ri 时： * 更新：nums[idx] = (nums[idx] * vi) % (109 + 7) * 将 idx += ki。 在处理完所有查询后，返回数组 nums...
思路
按题目意思模拟即可，明天估计就没这么简单了。
代码
private static final int MOD = 1000000007;
public int xorAfterQueries(int[] nums, int[][] queries) {
for (int[] query : queries) {
int idx = query[0];
while (idx <= query[1]) {
nums[idx] = (int) ((long) nums[idx] * query[3] % MOD);
idx += query[2];
}
}
int ans = 0;
for (int num : nums) {
ans ^= num;
}
return ans;
}
网友解答：
--【壹】--：
输入规模不大，直接模拟即可。看了一下题目标签有分治，一时没想到这玩意能怎么分治。
class Solution {
public:
int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
// l, r 范围内相隔 k 的元素都乘以 v
// 输入规模不大，可以直接模拟
for(auto& q:queries){
int idx=q[0];
while(idx<=q[1]){
nums[idx]=(int)(((long long)nums[idx]*q[3])%(int)(1e9+7));
idx+=q[2];
}
}
// 异或
int res=0;
for(int num:nums){
res^=num;
}
return res;
}
};
接着复习一些 Hot100 题：
21. 合并两个有序链表 - 力扣（LeetCode）
- 递归思路写起来挺自然的
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 这题可以用递归解决
if(list1==nullptr){
// 链表 1 空了，接下来接 list2 即可
return list2;
}
if(list2==nullptr){
return list1;
}
if(list1->val<=list2->val){
// 链表 1 当前节点值 <= 链表 2 的
list1->next=mergeTwoLists(list1->next,list2);
return list1;
}else{
list2->next=mergeTwoLists(list1,list2->next);
return list2;
}
return nullptr;
}
};
131. 分割回文串 - 力扣（LeetCode）
- 大胆回溯即可
class Solution {
public:
vector<vector<string>> partition(string s) {
// 可以看到 s 的输入范围很小，直接上回溯
vector<vector<string>> res;
vector<string> temp;
int n=s.size();
auto dfs=[&](auto&& self, int start){
if(start>=n){
res.emplace_back(temp);
return;
}
for(int i=start;i<n;i++){
int l=start,r=i;
bool flag=true;
while(l<r){
if(s[l]!=s[r]){
flag=false;
break;
}
l++;
r--;
}
if(flag){
temp.emplace_back(s.substr(start,i-start+1));
self(self,i+1);
temp.pop_back();
}
}
};
dfs(dfs,0);
return res;
}
};
169. 多数元素 - 力扣（LeetCode）
- 这题要求空间复杂度 O(1) 且时间复杂度 O(n)，首先能想到快速选择，因为排序后的中位数必然是结果。
- 除此之外还有比较有技巧的计数解法…这个没想出来。
快速选择：
class Solution {
public:
int majorityElement(vector<int>& nums) {
// 这题其实可以用快速选择写
// 因为出现次数 > floor(n/2)，那么 n/2 这个位置排序后必然是这个数
int n=nums.size();
auto partition=[&](int l, int r){
// 随机选择一个枢轴
int pivotPos=l+rand()%(r-l+1);
int pivot=nums[pivotPos];
nums[pivotPos]=nums[l];
while(l<r){
while(l<r&&nums[r]>pivot){
r--;
}
nums[l]=nums[r];
while(l<r&&nums[l]<=pivot){
l++;
}
nums[r]=nums[l];
}
nums[l]=pivot;
// 返回枢轴最终位置
return l;
};
int left=0,right=n-1;
int targetIdx=(n-1)>>1;
while(left<=right){
// 先划分
int pivotIdx=partition(left,right);
if(pivotIdx==targetIdx){
// pivotIdx 就是 n/2 这个位置
return nums[pivotIdx];
}else if(targetIdx<pivotIdx){
// 在左侧，进入左半边
right=pivotIdx-1;
}else{
// 否则在右侧
left=pivotIdx+1;
}
}
return -1;
}
};
计数方式：
class Solution {
public:
int majorityElement(vector<int>& nums) {
// O(n) 也可以是计数方式来解决
int res=-1;
int count=0;
for(int num:nums){
if(count==0){
// 计数归零，更新结果
res=num;
count++;
}else{
// 否则观察情况
if(num==res){
// 如果和当前数字一样则计数 +1
count++;
}else{
// 否则 -1
count--;
}
}
}
return res;
}
};
200. 岛屿数量 - 力扣（LeetCode）
- 看题目描述立马就能想到并查集。不过统计连通块这点还需要点技巧。
class UnionFind{
private:
vector<int> parents;
vector<int> sizes;
public:
UnionFind(int n){
parents.resize(n,-1);
sizes.resize(n,1);
}
// 带路径压缩查找
int find(int x){
return parents[x]==-1 ? x : parents[x]=find(parents[x]);
}
void merge(int x1,int x2){
int root1=find(x1),root2=find(x2);
if(root1==root2){
// 已经合并
return;
}
// 小树并入大树
if(sizes[root1]<sizes[root2]){
swap(root1,root2);
}
parents[root2]=root1;
sizes[root1]+=root2;
}
void markZero(int x){
parents[x]=-2;
}
int numConnected(){
// 获得连通块数量
int res=0;
for(int i=0;i<parents.size();i++){
if(parents[i]==-1){
res++;
}
}
return res;
}
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
// 连通块数量计数
// 并查集
int m=grid.size(),n=grid[0].size();
UnionFind uf(m*n);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='0'){
uf.markZero(i*n+j);
continue;
}
if(i>0&&grid[i-1][j]=='1'){
uf.merge((i-1)*n+j,i*n+j);
}
if(j>0&&grid[i][j-1]=='1'){
uf.merge(i*n+j-1,i*n+j);
}
}
}
return uf.numConnected();
}
};
--【贰】--：
哎？分治，我去瞅瞅，确实没想到要怎么分。
--【叁】--：
有点懵，一次写对
class Solution:
def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
n = len(nums)
for q in queries:
l, r, k, v = q
for idx in range(l, r + 1, k):
nums[idx] = (nums[idx] * v) % (10 ** 9 + 7)
ans = nums[0]
for i in range(1, n):
ans = ans ^ nums[i]
return ans
--【肆】--：
做完看了下跑得快的，不禁疑问，我是谁，我在哪，我在写什么？
class Solution {
public:
int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
int n =nums.size(),q = queries.size();
const int mod = 1e9 + 7;
int res = 0;
std::sort(queries.begin(),queries.end());
for(int i = 0; i < n; i++) {
for(int j = 0; j < q; j++) {
int l = queries[j][0],r = queries[j][1],k = queries[j][2],v = queries[j][3];
if(r < i) {
continue;
}
if(l > i) {
break;
}
if((i - l) % k == 0) {
nums[i] = (static_cast<long long>(v) * nums[i]) % mod;
}
}
res ^= nums[i];
}
return res;
}
};
--【伍】--：
class Solution:
def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
md = 1_000_000_007
for l, r, k, v in queries:
idx = l
while idx <= r:
nums[idx] = (nums[idx] * v) % md
idx += k
ans = 0
for x in nums:
ans ^= x
return ans
提前看了明天的，直接TLE了，明天看来是又是HOT 100的一天