20200615：力扣192周周赛下

题目

3. 设计浏览器历史记录
   
4. 给房子涂色Ⅲ

思路与算法

1. 第三题也是简单的书写题，注意格式即可，给出两种方式的代码实现，数组或list实现均可。
2. 第四题是一个动态规划的进阶题，这类题主要还是搞清楚转移方程即可，没太多说的地方，见代码就好。

代码实现

3. 设计浏览器历史记录

package com.immunize.leetcode.week192;import java.util.ArrayList;
import java.util.List;/*** 31. 设计浏览器历史记录* * 本题仔细一读要求就是一个简单的list实现或者数组实现,给上双指针,注意书写即可.* * 使用list实现* * @author Mr IMMUNIZE**/
public class BrowserHistory {// 初始化浏览记录list和指针List<String> list;// 双指针int cur = -1;int end = -1;/** 要求：BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。*/// 带参数构造器注意没有返回值，直接调用vist函数public BrowserHistory(String homepage) {list = new ArrayList<>();visit(homepage);}/** void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。*/// visit函数注意索引地址的设置public void visit(String url) {cur++;// 如果访问一个没访问过的网址，则直接添加到list即可if (list.size() <= cur) {list.add(url);} else {// 访问过的话直接将当前指针的位置索引给到url。list.set(cur, url);}// 记得尾指针始终指向当前cur。end = cur;}/** 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。 请返回后退 至多* steps 步以后的 url 。*/// back和forward只是简单的判断索引的位置并找到即可public String back(int steps) {cur = cur - steps < 0 ? 0 : cur - steps;return list.get(cur);}/** 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。* 请返回前进 至多 steps步以后的 url 。*/public String forward(int steps) {cur = cur + steps > end ? end : cur + steps;return list.get(cur);}
}/*** Your BrowserHistory object will be instantiated and called as such:* BrowserHistory obj = new BrowserHistory(homepage); obj.visit(url); String* param_2 = obj.back(steps); String param_3 = obj.forward(steps);*/

package com.immunize.leetcode.week192;/*** 32. 设计浏览器历史记录* * 本题仔细一读要求就是一个简单的list实现或者数组实现,给上双指针,注意书写即可.* * 使用数组实现* * @author Mr IMMUNIZE**/
public class BrowserHistory2 {// 初始化浏览记录数组String[] arr;// 双指针int cur = -1;int end = -1;/** 要求：BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。*/// 带参数构造器注意没有返回值，直接调用vist函数public BrowserHistory2(String homepage) {arr = new String[5000];visit(homepage);}/** void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。*/// visit函数注意索引地址的设置public void visit(String url) {cur++;arr[cur] = url;// 记得尾指针始终指向当前cur。end = cur;}/** 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。 请返回后退 至多* steps 步以后的 url 。*/// back和forward只是简单的判断索引的位置并找到即可public String back(int steps) {cur = cur - steps < 0 ? 0 : cur - steps;return arr[cur];}/** 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。* 请返回前进 至多 steps步以后的 url 。*/public String forward(int steps) {cur = cur + steps > end ? end : cur + steps;return arr[cur];}
}/*** Your BrowserHistory object will be instantiated and called as such:* BrowserHistory obj = new BrowserHistory(homepage); obj.visit(url); String* param_2 = obj.back(steps); String param_3 = obj.forward(steps);*/

4. 给房子涂色Ⅲ

package com.immunize.leetcode.week192;/*** * @author Mr IMMUNIZE**/
public class Solution4 {public int minCost(int[] houses, int[][] cost, int m, int n, int target) {final int max = Integer.MAX_VALUE;int[][][] dp = new int[m + 1][target + 1][n + 1];for (int i = 0; i < m + 1; i++) {for (int j = 0; j < target + 1; j++) {for (int k = 0; k < n + 1; k++) {dp[i][j][k] = max;}}}if (houses[0] > 0) {dp[0][1][houses[0]] = 0;} else {for (int i = 1; i <= n; i++) {dp[0][1][i] = cost[0][i - 1];}}for (int i = 1; i < m; i++) {for (int j = 1; j <= target; j++) {if (houses[i] > 0) {int temp = houses[i];for (int k = 1; k <= n; k++) {if (temp == k) {dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j][k]);} else {dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j - 1][k]);}}} else {for (int k = 1; k <= n; k++) {for (int s = 1; s <= n; s++) {if (k == s) {dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][s] + cost[i][k - 1]);} else {dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][s] + cost[i][k - 1]);}}}}}}int res = max;for (int i = 1; i <= n; i++) {res = Math.min(res, dp[m - 1][target][i]);}if (res == max)return -1;return res;}
}

复杂度分析

1. 第四题dp题的复杂度为O(MNP),分别为三维数组的三个维度

写在最后

1. 考研事宜尘埃落定，以后为硬件方向，但是希望这个刷题的过程能始终伴随着我自己的成长，诸君共勉！