算法: 模拟题目练习

---

模拟

替换所有的问号

按照题目的要求写代码即可~

    public String modifyString(String ss) {int n = ss.length();if (n == 1) {return "a";}char[] s = ss.toCharArray();for (int i = 0; i < n; i++) {if (s[i] == '?') {for (char ch = 'a'; ch <= 'z'; ch++) {if (i == 0 && ch != s[i + 1]) {// 第一个s[i] = ch;} else if (i == n - 1 && ch != s[i - 1]) {// 最后一个s[i] = ch;}if (0 < i && i < n - 1 && ch != s[i + 1] && ch != s[i - 1]) {// 中间s[i] = ch;}}}}return String.valueOf(s);}

题解写的更加简洁.

题解代码:

    public String modifyString(String ss) {int n = ss.length();char[] s = ss.toCharArray();for (int i = 0; i < n; i++) {if (s[i] == '?') {for (char ch = 'a'; ch <= 'z'; ch++) {if ((i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch)) {s[i] = ch;break;}}}}return String.valueOf(s);}

提莫攻击

草稿:

    public int findPoisonedDuration(int[] timeSeries, int duration) {int tmp = timeSeries[0] + duration - 1;int sum = duration;for (int i = 1; i < timeSeries.length; i++) {if (tmp >= timeSeries[i]) {sum += timeSeries[i] - timeSeries[i - 1];} else {sum += duration;}tmp = timeSeries[i] + duration - 1;}return sum;}

题解代码:
草图:

    public int findPoisonedDuration(int[] timeSeries, int duration) {int sum = 0;for (int i = 1; i < timeSeries.length; i++) {int tmp = timeSeries[i] - timeSeries[i - 1];if (tmp > duration) {sum += duration;} else {sum += tmp;}}return sum + duration;}

Z 字形变换

虽然过了,但是稀里糊涂地过了~

开头和结尾都好说,主要是中间,不知道为啥要 - 2*i.

规律就是这样的~

做题思路就是:

• 题目让干啥,我们就干啥
• 画图找规律~

坑:

• numRows 可能为 1 .
• 放中间元素时,容易越界.

代码:

public String convert(String ss, int numRows) {if (numRows == 1)return ss;char[] s = ss.toCharArray();int n = s.length;char[] ret = new char[n];int gap = (numRows - 1) * 2;int k = 0;// 开头for (int j = 0; j < n; j += gap) {ret[k++] = s[j];}// 中间for (int i = 1; i <= numRows - 2; i++) {for (int j = i; j < n; j += gap) {ret[k++] = s[j];// 这里为啥 - i*2 就对了?int mid = j + gap - i * 2;if (mid < n) {ret[k++] = s[mid];}}}// 结尾for (int j = numRows - 1; j < n; j += gap) {ret[k++] = s[j];}return String.valueOf(ret);}

外观数列

终于过了~
不知道为啥,自己写的代码返回的结果一直只有两个数. 在这上面耗了20多分钟.
最后全删了.心态崩了呀.
吃完饭回来,重写了一遍,只用了不到6分钟就写出来了.

坑:

• 不用考虑怎么替换的问题,最开始我也被题目带偏了.如果用替换来写,需要考虑的情况就复杂了. 其实直接新建一个字符串,不断向这个字符串后面拼接就行了.

    public String countAndSay(int n) {StringBuilder ret = new StringBuilder("1");for (int i = 1; i < n; i++) {StringBuilder tmp = new StringBuilder();int len = ret.length();int left = 0, right = 0;while (right < len) {while (right < len && ret.charAt(left) == ret.charAt(right)) {right++;}tmp.append(right - left);tmp.append(ret.charAt(left));left = right;}ret = tmp;}return ret.toString();}

数青蛙

最后一个测试用例卡了好久.

坑:

• 如何判断给出的字符串不是 “croak” 的有效组合? 可以用最后的 sum 来判断,如果 sum 没有减到0,那就说明字符串不完整.

    public int minNumberOfFrogs(String croakOfFrogs) {if (croakOfFrogs.length() < 5 || croakOfFrogs.length() % 5 != 0) {return -1;}int sum = 0;int ret = 0;char[] str = {'c', 'r', 'o', 'a', 'k'};HashMap<Character, Integer> hash = new HashMap<>();HashMap<Character, Character> hash2 = new HashMap<>();for (int i = 1; i < 5; i++) {hash2.put(str[i], str[i - 1]);}int n = croakOfFrogs.length();for (int i = 0; i < n; i++) {char ch = croakOfFrogs.charAt(i);hash.put(ch, hash.getOrDefault(ch, 0) + 1);if (ch != 'c' && hash.getOrDefault(ch, 0) > hash.getOrDefault(hash2.get(ch), 0)) {return -1;}if (ch == 'c') {sum++;} else if (ch == 'k') {ret = Math.max(ret, sum);sum--;}}if (sum != 0) return -1;return ret;}

看了题解后又自己写了一遍:

    public int minNumberOfFrogs(String croakOfFrogs) {String str = "croak";HashMap<Character, Integer> hashIndex = new HashMap<>();for (int i = 0; i < 5; i++) {hashIndex.put(str.charAt(i), i);}HashMap<Character, Integer> hashCount = new HashMap<>();int n = croakOfFrogs.length();for (int i = 0; i < n; i++) {char ch = croakOfFrogs.charAt(i);if (ch != 'c') {// r,o,a,kchar prev = str.charAt(hashIndex.get(ch) - 1);int pervCount = hashCount.getOrDefault(prev, 0);if (pervCount > 0) {hashCount.put(prev, pervCount - 1);hashCount.put(ch, hashCount.getOrDefault(ch, 0) + 1);} else if (pervCount <= 0) {return -1;}} else {// cif (hashCount.getOrDefault('k', 0) > 0) {hashCount.put('k', hashCount.get('k') - 1);}hashCount.put(ch, hashCount.getOrDefault(ch, 0) + 1);}}// 检验给出的字符串是不是 "croak" 的有效组合。for (int i = 0; i < 4; i++) {if (hashCount.get(str.charAt(i)) != 0) {return -1;}}return hashCount.get('k');}

题解代码:

• 使用数组替代了 hash 表.

    public int minNumberOfFrogs(String c) {char[] croakOfFrogs = c.toCharArray();String str = "croak";int n = str.length();int[] hash = new int[n];HashMap<Character, Integer> index = new HashMap<>();// 建立字母和下标的关系for (int i = 0; i < n; i++) {index.put(str.charAt(i), i);}for (char ch : croakOfFrogs) {if (ch != 'c') {// r,o,a,kint i = index.get(ch);if (hash[i - 1] > 0) {hash[i - 1]--;hash[i]++;} else {return -1;}} else {// cif (hash[n - 1] > 0)hash[n - 1]--;hash[0]++;}}for (int i = 0; i < n - 1; i++) {if (hash[i] != 0) return -1;}return hash[n - 1];}

看题解看到了一个 if else 大法 :

public int minNumberOfFrogs(String croakOfFrogs) {int c,r,o,a,k;c = 0; r = 0; o = 0; a = 0;k = 0;char []chars = croakOfFrogs.toCharArray();int res = 0;for(int i = 0;i < chars.length;i++){if(chars[i] == 'c'){if(k > 0){k--;}else{res++;}c++;}else if(chars[i] == 'r'){c--;r++;}else if(chars[i] == 'o'){r--;o++;}else if(chars[i] == 'a'){o--;a++;}else if(chars[i] == 'k'){a--;k++;}if(c < 0 || r < 0 || o < 0 || a < 0){break;}}if(c != 0 || r != 0 || o != 0 || a != 0){return -1;}return res;}

总结

• 做模拟题时, 题目说啥咱干啥~
• 有难度的模拟题需要我们找规律.
• 画图是个好东西.

---

本文到这里就结束啦~