算法奇妙屋(二)-模拟

    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        int len = s.length();
        int d = 2 * numRows - 2;
        StringBuffer ret = new StringBuffer();
        for (int i = 0; i < len; i += d) {
            ret.append(s.charAt(i));
        }
        for (int k = 1; k < numRows - 1; k++) {
            for (int i = k, j = d - i; i < len || j < len; i += d, j += d) {
                if (i < len) {
                    ret.append(s.charAt(i));
                }
                if (j < len) {
                    ret.append(s.charAt(j));
                }
            }
        }
        for (int i = numRows - 1; i < len; i += d) {
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }

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

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

    public int minNumberOfFrogs(String croakOfFrogs) {
        int[] arr = new int[128];
        for (int i = 0; i < croakOfFrogs.length(); i++) {
            char ch = croakOfFrogs.charAt(i);
            if (ch == 'c') {
                if (arr['k'] == 0) {
                    arr['c']++;
                }else {
                    arr['k']--;
                    arr['c']++;
                }
            }else if (ch == 'r') {
                if (arr['c'] != 0) {
                    arr['c']--;
                    arr['r']++;
                }else {
                    return -1;
                }
            }else if (ch == 'o') {
                if (arr['r'] != 0) {
                    arr['r']--;
                    arr['o']++;
                }else {
                    return -1;
                }
            }else if (ch == 'a') {
                if (arr['o'] != 0) {
                    arr['o']--;
                    arr['a']++;
                }else {
                    return -1;
                }
            }else if (ch == 'k') {
                if (arr['a'] != 0) {
                    arr['a']--;
                    arr['k']++;
                }else {
                    return -1;
                }
            }
        }
        if (arr['c'] != 0 || arr['r'] != 0 || arr['o'] != 0 || arr['a'] != 0) {
            return -1;
        }
        return arr['k'];
    }

    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] c = croakOfFrogs.toCharArray();
        String s = "croak";
        int n = s.length();
        int[] hash = new int[n];
        HashMap<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(s.charAt(i),i); // 哈希表中让哈希值key与下标value对应
        }
        for (char ch : c) {
            int index = map.get(ch);
            if (index == 0) {
                if (hash[n - 1] != 0) {
                    hash[n - 1]--;
                }
                hash[index]++;
            }else {
                if (hash[index - 1] != 0) {
                    hash[index - 1]--;
                    hash[index]++;
                }else {
                    return -1;
                }
            }
        }
        for (int i = 0; i < n - 1; i++) {
            if (hash[i] != 0) {
                return -1;
            }
        }
        return hash[n - 1];
    }