在哪里可以做个人网站,emulate wordpress,计算机网站建设方向,备案信息网站被注册2024.1.29 题目来源我的题解方法一 动态规划 题目来源
力扣每日一题#xff1b;题序#xff1a;514
我的题解
方法一 动态规划 定义 dp[i][j] 表示从前往后拼写出 key的第 i个字符#xff0c; ring 的第 j个字符与 12:00 方向对齐的最少步数#xff08;下标均从 0 开始题序514
我的题解
方法一 动态规划 定义 dp[i][j] 表示从前往后拼写出 key的第 i个字符 ring 的第 j个字符与 12:00 方向对齐的最少步数下标均从 0 开始。 显然只有当字符串 ring 的第 j个字符需要和 key 的第 i 个字符相同时才能拼写出 key 的第 i 个字符因此对于 key 的第 i个字符需要考虑计算的 ring 的第 j 个字符只有 key[i] 在 ring 中出现的下标集合。对每个字符维护一个位置数组 pos[i]表示字符 ii在 ring 中出现的位置集合用来加速计算转移的过程。 对于状态 dp[i][j]需要枚举上一次与 12:00 方向对齐的位置 k因此可以列出如下的转移方程 dp [ i ] [ j ] min k ∈ p o s [ k e y [ i − 1 ] ] { d p [ i − 1 ] [ k ] min { abs ( j − k ) , n − abs ( j − k ) } } \textit{dp}[i][j]\min_{k \in pos[key[i-1]]}\{dp[i-1][k]\min\{\text{abs}(j-k),n-\text{abs}(j-k)\}\} dp[i][j]mink∈pos[key[i−1]]{dp[i−1][k]min{abs(j−k),n−abs(j−k)}} 其中 min { abs ( j − k ) , n − abs ( j − k ) } \min\{\text{abs}(j-k),n-\text{abs}(j-k)\} min{abs(j−k),n−abs(j−k)} 表示在当前第 k 个字符与 12:00方向对齐时第 j 个字符旋转到 12:00 方向并按下拼写的最少步数。 最后答案即为 min i 0 n − 1 { dp [ m − 1 ] [ i ] } m \min_{i0}^{n-1}\{\textit{dp}[m-1][i]\}m mini0n−1{dp[m−1][i]}m。 时间复杂度 O( m n 2 mn^2 mn2) 空间复杂度 O(mn) public int findRotateSteps(String ring, String key) {int n ring.length(), m key.length();//存储每个字符所在的位置ListInteger[] pos new List[26];for (int i 0; i 26; i) {pos[i] new ArrayListInteger();}for (int i 0; i n; i) {pos[ring.charAt(i) - a].add(i);}int[][] dp new int[m][n];for (int i 0; i m; i) {Arrays.fill(dp[i], Integer.MAX_VALUE);}for (int i : pos[key.charAt(0) - a]) {dp[0][i] Math.min(i, n - i);}for (int i 1; i m; i) {for (int j : pos[key.charAt(i) - a]) {for (int k : pos[key.charAt(i - 1) - a]) {dp[i][j] Math.min(dp[i][j], dp[i - 1][k] Math.min(Math.abs(j - k), n - Math.abs(j - k)));}}}return Arrays.stream(dp[m - 1]).min().getAsInt()m;}//优化空间版本
// 考虑到每次转移状态 dp[i][] 只会从 dp[i−1][] 转移过来因此可以利用滚动数组优化第一维的空间复杂度public int findRotateSteps(String ring, String key) {int n ring.length(), m key.length();ListInteger[] pos new List[26];for (int i 0; i 26; i) {pos[i] new ArrayListInteger();}for (int i 0; i n; i) {pos[ring.charAt(i) - a].add(i);}//空间优化dp[]int[] dp new int[n];for (int i : pos[key.charAt(0) - a]) dp[i] Math.min(i, n - i);for (int i 1; i m; i) {//若当前与上一次相同则不需要转动ringif(key.charAt(i)key.charAt(i-1))continue;for (int j : pos[key.charAt(i) - a]) {dp[j]Integer.MAX_VALUE;for (int k : pos[key.charAt(i - 1) - a]) {dp[j] Math.min(dp[j], dp[k] Math.min(Math.abs(j - k), n - Math.abs(j - k)));}}}return pos[key.charAt(m - 1) - a].stream().mapToInt(i - dp[i]).min().orElse(Integer.MAX_VALUE)m;}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
