Java 模拟算法题目练习

时间复杂度：O(n) 空间复杂度：O(n)

提莫攻击

题目解析：提莫会对艾希释放技能，让艾希处于中毒状态，求出中毒的总时间 模拟：会出现一次技能持续时间还没有结束，又释放了一个技能 因此我们要判断相邻两次释放技能时间差值与技能持续时间进行对比 如果差值大于或者等于技能持续时间，总时间就加上 duration 反之，总时间就加上差值 但是这加上的都是上一次技能的持续时间，因此最后要加上 duration，因为最后一次技能肯定会执行完

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        // 判断这次攻击与上次攻击的时间差值即可
        // 差值 >= duration，上一次执行时间为 duration
        // 反之 < duration, 上一次执行的时间就是差值
        int sum = 0;
        for (int i = 1; i < timeSeries.length; i++) {
            int x = timeSeries[i] - timeSeries[i - 1];
            if (x >= duration) {
                sum += duration;
            } else {
                sum += x;
            }
        }
        // 加上最后一次技能的持续时间
        return sum + duration;
    }
}

时间复杂度：O(n) 空间复杂度：O(1)

Z 字形变换

题目解析：给一个字符串，输出其 Z 字形转换后，按行放入一个新的字符串中返回 模拟：可以直接将其全部字符按照 Z 字形放到二维矩阵中，并遍历即可，但是时间复杂度和空间复杂度较高，因此我们看看可以找规律吗

此时要注意当 n = 1 时候，其可能会死循环，因此要判断一下

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        int n = s.length();
        // 公差
        int d = 2 * numRows - 2;
        StringBuffer ret = new StringBuffer();
        // 第一行
        for (int i = 0; i < n; i += d) {
            ret.append(s.charAt(i));
        }
        // 中间行
        for (int k = 1; k < numRows - 1; k++) {
            for (int i = k, j = d - i; i < n || j < n; i += d, j += d) {
                if (i < n) {
                    ret.append(s.charAt(i));
                }
                if (j < n) {
                    ret.append(s.charAt(j));
                }
            }
        }
        for (int i = numRows - 1; i < n; i += d) {
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }
}

时间复杂度：O(n) 空间复杂度：O(n)

外观数列

题目解析：就是有很多行的字符串，每一行字符串都是解释的上一行字符串，找出第 n 行字符串 模拟 + 双指针

class Solution {
    public String countAndSay(int n) {
        // 一直解释，解释到第 n 行
        String ret = "1";
        for (int i = 1; i < n; i++) {
            // 存放当前这一行的解释
            StringBuilder tem = new StringBuilder();
            // 当前行的长度
            int len = ret.length();
            // 开始解释
            for (int left = 0, right = 0; right < len;) {
                while (right < len && ret.charAt(left) == ret.charAt(right)) {
                    right++;
                    // 直到不相同为止
                }
                tem.append(Integer.toString(right - left));
                tem.append(ret.charAt(left));
                left = right;
            }
            ret = tem.toString();
        }
        return ret;
    }
}

数青蛙

题目解析：给了一个字符串，求最小青蛙数量，这里完整的 croak 才是哇叫，如果存在不完整的就返回 -1 模拟 + 哈希表 因此每次遍历到那个字符都要判断其前驱字符是否存在 使用一个数组放 croak 对应元素个数 因为这里要找前驱，所以一个哈希表，存放 croak 这些字符对应下标关系，这样可以对应到上面数组中个数

可以直接使用 5 个变量记录这个字符出现的个数，不断 if else 即可

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        if (croakOfFrogs.length() % 5 != 0) {
            return -1;
        }
        int c = 0;
        int r = 0;
        int o = 0;
        int a = 0;
        int k = 0;
        int ret = 0;
        for (int i = 0; i < croakOfFrogs.length(); i++) {
            char ch = croakOfFrogs.charAt(i);
            // 每次都要判断其前驱字符个数
            if (ch == 'c') {
                // 判断有没有青蛙叫完，有的话就可以从后面直接调取即可
                if (k > 0) {
                    --k;
                    ++c;
                } else {
                    ++c;
                }
            } else if (ch == 'r') {
                if (c == 0) {
                    return -1;
                } else {
                    --c;
                    ++r;
                }
            } else if (ch == 'o') {
                if (r == 0) {
                    return -1;
                } else {
                    --r;
                    ++o;
                }
            } else if (ch == 'a') {
                if (o == 0) {
                    return -1;
                } else {
                    --o;
                    ++a;
                }
            } else {
                if (a == 0) {
                    return -1;
                } else {
                    --a;
                    ++k;
                }
            }
        }
        if (c != 0 || r != 0 || o != 0 || a != 0) {
            return -1;
        }
        return k;
    }
}

使用数组存放对应数量，哈希表来对应下标关系

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        // 使用数组模拟哈希
        String t = "croak";
        int n = t.length();
        int[] hash = new int[n];
        // 存放对应元素个数
        // 使用哈希表来映射他们的下标
        java.util.Map<Character, Integer> map = new java.util.HashMap<>();
        // 先放入哈希中
        for (int i = 0; i < n; i++) {
            map.put(t.charAt(i), i);
        }
        // 此时就要开始判断
        for (char ch : croakOfFrogs.toCharArray()) {
            // 如果是 c 字符要进行判断，k 是否存在
            if (ch == t.charAt(0)) {
                if (hash[n - 1] != 0) {
                    hash[n - 1]--;
                }
                hash[0]++;
            } else {
                // 中间字符
                // 因为要判断前驱字符，这里要获取下标
                int index = map.get(ch);
                if (hash[index - 1] == 0) {
                    return -1;
                } else {
                    hash[index - 1]--;
                    hash[index]++;
                }
            }
        }
        // 最后要判断其除了 k 字符，前面字符是否还有
        for (int i = 0; i < n - 1; i++) {
            if (hash[i] != 0) {
                return -1;
            }
        }
        return hash[n - 1];
    }
}