模拟

替换所有的问号

在这里插入图片描述
按照题目的要求写代码即可~

    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,k
                char 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 {
                // c
                if (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,k
                int i = index.get(ch);
                if (hash[i - 1] > 0) {
                    hash[i - 1]--;
                    hash[i]++;
                } else {
                    return -1;
                }
            } else {
                // c
                if (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;
    }
上一篇:类型


下一篇:信息安全工程师(58)网络安全漏洞处置技术与应用