[人工智能]6. Z 字形变换 / 75. 颜色分类

6. Z 字形变换【中等题】【每日一题】

思路：【找规律】

1. 每一行开头的字符均为s中对应行号位置的字符，即，第i行的首字母对应s中第i个位置。
2. 以每一个竖直向下的列分隔，那么每一行的奇数列与偶数列之间的字符对应s中的下标存在如下对应关系：
3. 设周期为t=2*numRows-2，每两个相邻字符之间，
4. 第1行，t
5. 第2行，t-2，2
6. 第3行，t-4,4
7. …
8. 第倒数第3行，4，t-4
9. 第倒数第2行，2，t-2
10. 第倒数第1行，t 。

综上规律，定义中间行号mid=(numRows-1)/2，遍历每一行，定义j表示当前行的起始下标，初值为i。
首行或者尾行，依次添加s中所有的j+t位置字符，并更新j=j+t
其他行，判断是前一半还是后一半，前一半依次先添加j+（t-2i），j+（2i），并实时更新j；后一半依次添加j+（2i），j+t-（2i），并实时更新j。

代码：

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1){
            return s;
        }
        int t = 2*numRows-2,mid = (numRows-1)/2,len = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            int j = i;
            if (i == 0 || i == numRows-1){
                while (j<len){
                    sb.append(s.charAt(j));
                    j += t;
                }
            }else {
                if (i<=mid){
                    while (j<len){
                        sb.append(s.charAt(j));
                        j+=(t-2*i);
                        if (j<len && j>=numRows){
                            sb.append(s.charAt(j));
                        }
                        j+=2*i;
                    }
                }else {
                    while (j<len){
                        sb.append(s.charAt(j));
                        j+=2*(numRows-1-i);
                        if (j<len && j>=numRows){
                            sb.append(s.charAt(j));
                        }
                        j+=(t-2*(numRows-1-i));
                    }
                }
            }
        }
        return sb.toString();
    }
}

75. 颜色分类【中等题】

思路：【计数排序】

1. 因为数组里只有3个数，所以一次遍历统计0,1，2三个数的个数。
2. 设0,1，2三个数的个数分别为n0,n1，n2的个数。
3. 数组下标0~n0-1设置为0。
4. 下标n1~n2-1设置为 1。
5. 下标n2往后设为2。
6. 排序完毕。

代码：

class Solution {
    public void sortColors(int[] nums) {
        int[] cnt = new int[3];
        for (int num : nums) {
            cnt[num]++;
        }
        for (int i = 0; i < cnt[0]; i++) {
            nums[i] = 0;
        }
        for (int i = 0; i < cnt[1]; i++) {
            nums[cnt[0]+i] = 1;
        }
        for (int i = 0; i < cnt[2]; i++) {
           nums[cnt[0]+cnt[1]+i] = 2;
        }
    }
}

用时：