力扣 第 383 场周赛 解题报告 | 珂学家 | Z函数/StringHash

2024-02-04 13:52

本文主要是介绍力扣 第 383 场周赛 解题报告 | 珂学家 | Z函数/StringHash,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


前言

image.png

谁言别后终无悔
寒月清宵绮梦回
深知身在情长在
前尘不共彩云飞


整体评价

T3是道模拟题,但是感觉题意有些晦涩,T4一眼Z函数,当然StringHash更通用些。

新年快乐, _.


T1. 将单词恢复初始状态所需的最短时间 I

思路: 模拟

就是前缀和为0的次数

class Solution {public int returnToBoundaryCount(int[] nums) {int acc = 0;int res = 0;for (int v: nums) {acc += v;if (acc == 0) res++;}return res;}
}

T2. 将单词恢复初始状态所需的最短时间 I

和T4一起讲


T3. 找出网格的区域平均强度

思路: 模拟

感觉题意有些晦涩,窗口比较小,可以莽些。

如果窗口大小比较大,就需要

二维前缀和 + 二维差分 二维前缀和+二维差分 二维前缀和+二维差分

class Solution {int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int[] evaluate(int[][] image, int ty, int tx, int limit) {int res = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {for (int k = 0; k < 4; k++) {int dy = i + dirs[k][0];int dx = j + dirs[k][1];if (dy >= 0 && dy < 3 && dx >= 0 && dx < 3) {int dist = Math.abs(image[ty+i][tx+j] - image[ty+dy][tx+dx]);if (dist > limit) {return new int[] {0, 0};}}}res += image[ty + i][tx + j];}}return new int[] {1, res / 9};}public int[][] resultGrid(int[][] image, int threshold) {int h = image.length, w = image[0].length;int[][] sum = new int[h][w];int[][] cnt = new int[h][w];// 预处理,枚举左上角for (int i = 0; i < h - 2; i++) {for (int j = 0; j < w - 2; j++) {int[] res = evaluate(image, i, j, threshold);for (int s = 0; s < 3; s++) {for (int t = 0; t < 3; t++) {sum[s+i][t+j] += res[1];cnt[s+i][t+j] += res[0];}}}}// 统计值int[][] ans = new int[h][w];for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (cnt[i][j] == 0) {ans[i][j] = image[i][j];} else {ans[i][j] = sum[i][j] / cnt[i][j];}}}return ans;}
}

T4. 将单词恢复初始状态所需的最短时间 II

思路: Z函数/StringHash

属于思维题的范畴

S [ i : n ] = = S [ 0 : n − i ] ,那么该 i 就是满足要求的点 S[i:n] == S[0:n-i],那么该i就是满足要求的点 S[i:n]==S[0:ni],那么该i就是满足要求的点

因为字符串S很大,所以利用StringHash,可以 O ( N ) O(N) O(N)判定。

当然也可以转换下思维

S [ i : n ] = = S [ 0 : n − i ] 本质就是求 S [ i : n ] 和 S [ 0 : n ] 的最长前缀长度 S[i:n] == S[0:n-i] 本质就是求 S[i:n] 和 S[0:n]的最长前缀长度 S[i:n]==S[0:ni]本质就是求S[i:n]S[0:n]的最长前缀长度

这个就是属于Z函数的核心概念了。

  • Z函数
class Solution {// z函数模板, https://oi-wiki.org/string/z-func/static int[] zFunction(String a) {char[] s = a.toCharArray();int n = s.length;int[] z = new int[n];z[0] = n;for (int i = 1, l = 0, r = 0; i < n; ++i) {if (i <= r && z[i - l] < r - i + 1) {z[i] = z[i - l];} else {z[i] = Math.max(0, r - i + 1);while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];}if (i + z[i] - 1 > r) {l = i;r = i + z[i] - 1;}}return z;}public int minimumTimeToInitialState(String word, int k) {int n = word.length();int[] arr = zFunction(word);for (int i = k; i < n; i += k) {if (arr[i] == n - i) {return i / k;}}return (n + k - 1) / k;}}
  • StringHash
class Solution {staticclass StringHash {char[] str;long p, mod;int n;long[] pre; // hash前缀和long[] pow; // p的幂次public StringHash(String s, int p, long mod) {this.str = s.toCharArray();this.p = p;this.mod = mod;this.n = str.length;pre = new long[n + 1];pow = new long[n + 1];pow[0] = 1;for (int i = 1; i <= n; i++) {pow[i] = pow[i - 1] * p % mod;}for (int i = 0; i < str.length; i++) {pre[i + 1] = (pre[i] * p % mod + str[i]) % mod;}}long query(int l, int r) {long res = pre[r + 1] - pre[l] * pow[r - l + 1] % mod;return (res % mod + mod) % mod;}long rotate(int l) {if (l < 0 || l >= str.length - 1) {return query(0, str.length - 1);} else {long h1 = query(0, l);long h2 = query(l + 1, str.length - 1);return (h2 * pow[l + 1] % mod + h1) % mod;}}static long evaluate(String s, int p, long mod) {long h = 0;for (char c: s.toCharArray()) {h = (h * p % mod + c) % mod;}return h;}}public int minimumTimeToInitialState(String word, int k) {int p1 = 13, p2 = 17;long mod = (long)1e9 + 7;StringHash h1 = new StringHash(word, p1, mod);StringHash h2 = new StringHash(word, p2, mod);int res = 1;int n = word.length();for (int i = k; i < n; i += k) {int d = n - i;if (h1.query(i, n - 1) == h1.query(0, d - 1)&& h2.query(i, n - 1) == h2.query(0, d - 1)) {return res;}res++;}return res;}
}

写在最后

image.png

这篇关于力扣 第 383 场周赛 解题报告 | 珂学家 | Z函数/StringHash的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677722

相关文章

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

C++操作符重载实例(独立函数)

C++操作符重载实例,我们把坐标值CVector的加法进行重载,计算c3=c1+c2时,也就是计算x3=x1+x2,y3=y1+y2,今天我们以独立函数的方式重载操作符+(加号),以下是C++代码: c1802.cpp源代码: D:\YcjWork\CppTour>vim c1802.cpp #include <iostream>using namespace std;/*** 以独立函数

函数式编程思想

我们经常会用到各种各样的编程思想,例如面向过程、面向对象。不过笔者在该博客简单介绍一下函数式编程思想. 如果对函数式编程思想进行概括,就是f(x) = na(x) , y=uf(x)…至于其他的编程思想,可能是y=a(x)+b(x)+c(x)…,也有可能是y=f(x)=f(x)/a + f(x)/b+f(x)/c… 面向过程的指令式编程 面向过程,简单理解就是y=a(x)+b(x)+c(x)

利用matlab bar函数绘制较为复杂的柱状图,并在图中进行适当标注

示例代码和结果如下:小疑问:如何自动选择合适的坐标位置对柱状图的数值大小进行标注?😂 clear; close all;x = 1:3;aa=[28.6321521955954 26.2453660695847 21.69102348512086.93747104431360 6.25442246899816 3.342835958564245.51365061796319 4.87

OpenCV结构分析与形状描述符(11)椭圆拟合函数fitEllipse()的使用

操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C++11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆,该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使用了由[90]描述的第一个算法。开发者应该注意,由于数据点靠近包含的 Mat 元素的边界,返回的椭圆/旋转矩形数据

Unity3D 运动之Move函数和translate

CharacterController.Move 移动 function Move (motion : Vector3) : CollisionFlags Description描述 A more complex move function taking absolute movement deltas. 一个更加复杂的运动函数,每次都绝对运动。 Attempts to

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查