中级提升班3

题目一洗衣机问题

有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同,
返回-1。
例如[1, 0, 5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后:

1
2
3

第一轮:1   0 <- 5 => 1 1 4
第二轮:1 <-1 <- 4 => 2 1 3
第三轮:2   1 <- 3 => 2 2 2

移动了3轮，每个机器上的物品相等，所以返回3
例如[2, 2, 3]表示有3个机器，每个机器上分别有2、2、3个物品，
这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1

leetcode517 超级洗衣机

贪心

衣服和机器必须正好均分sum%n==0才能移动，将机器以机器i分开，为此时有以下几种情况：

i的左侧缺少A件，i的右侧缺少B件，对于i来说它至少需要移动A+B轮；
i的左侧多余A件，i的右侧多余B件，对于i来说至少需要移动max(A,B)；
i的左侧缺少A件，i的右侧多余B件，对于i来说至少需要移动max(A,B)，因为必须要把最大的移动完才可以

将每个位置的移动情况都求出，其中最大的就是整体最少的移动次数。这是个瓶颈问题，只有解决最大位置才是整体解决的情况。

public static int minOps(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int size = arr.length;
    int sum = 0;
    for (int num : arr) {
        sum += num;
    }

    if (sum % size != 0) {
        return -1;
    }
    int avg = sum / size;
    int leftSum = 0; // 左侧部分
    int ans = 0;
    for (int i = 0; i < size; i++) {
        // 负需要输入 正需要输出
        int leftRest = leftSum - i * avg;  // 左侧部分 - 平均值
        // 负需要输入 正需要输出
        // 右侧部分 - 平均值
        int rightRest = (sum - leftSum - arr[i]) - (size - i - 1) * avg;
        int need = 0; // i位置需要的移动次数
        if (leftRest < 0 && rightRest < 0) {
            need = Math.abs(leftRest) + Math.abs(rightRest);
        } else {
            need = Math.max(Math.abs(leftRest), Math.abs(rightRest));
        }
        ans = Math.max(ans, need);
        leftSum += arr[i];
    }
    return ans;
}

题目二 zigzag打印矩阵

用zigzag的方式打印矩阵，比如如下的矩阵

1
2
3

0	1	2	3
4	5	6	7
8	9	10	11

打印顺序为:0 1 4 8 5 2 3 6 9 10 7 11

leetcode 498 对角线遍历

解

这类题目是有技巧的，首先看打印的原理，类似于2个点之间的数据打印，所以取a,b两点，a点的行动轨迹从左到右，到边界后向下，b点的行动轨迹从上到下，到边界后向右走。

a和b的行动轨迹确定后，打印ab之间的数据，从a->b的轨迹为a的点纵轴+1，横轴-1,从b->a的轨迹为横轴+1，纵轴-1。每找到新的ab点就交换ab的打印顺序数据。

public int[] findDiagonalOrder(int[][] mat) {

    int aRow = 0;
    int aCol = 0;
    int bRow = 0;
    int bCol = 0;
    int endR = mat.length - 1;
    int endC = mat[0].length - 1;
    List<Integer> list = new ArrayList<>();
    boolean flag = false; // true向上遍历
    int index = 0;
    while (aRow != endR + 1) {
        print(mat, aRow, aCol, bRow, bCol, flag, list);
        // a 是先向左，再向下 分界点是endC 左上角
        aRow = aCol == endC ? aRow + 1 : aRow;
        aCol = aCol == endC ? aCol : aCol + 1;
        // b 是先向下，再向左 分界点是endR 右上角
        bCol = bRow == endR ? bCol + 1 : bCol;
        bRow = bRow == endR ? bRow : bRow + 1;

        flag = !flag;
    }
    int[] ret = new int[mat.length * mat[0].length];
    for (int i = 0; i < list.size(); i++) {
        ret[i] = list.get(i);
    }
    return ret;
}

public static void print(int[][] m, int aRow, int aCol, int bRow, int bCol, boolean flag, List<Integer> list) {
    if (flag) {
        // 从 a向b移动
        while (aRow != bRow + 1) {
            list.add(m[aRow++][aCol--]);
        }
    } else {
        // 从 b向a移动
        while (bCol != aCol + 1) {
            list.add(m[bRow--][bCol++]);
        }
    }
}

题目三螺旋打印矩阵

用螺旋的方式打印矩阵，比如如下的矩阵

1
2
3

0	1	2	3
4	5	6	7
8	9	10	11

打印顺序为:01237 11 10 98456

leetcode 54 螺旋矩阵

解法

螺旋打印，从整体上分析，就是一圈一圈的打印，所以获取每一圈的左上角和右下角，然后打印这个圈，然后2个点收缩，有以下三种情况

点和点刚好构成一个圈，循环打印
点和点在横线，打印横线
点和点在竖线，竖着打印

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> list = new ArrayList<>();
    int tR = 0;
    int tC = 0;
    int dR = matrix.length -1;
    int dC = matrix[0].length -1;
    while (tR <= dR && tC <= dC){
        printEdge(matrix, tR++, tC++, dR--, dC--, list);
    }
    return list;
}

public static void printEdge(int[][] m, int a, int b, int c, int d, List<Integer> list) {
    if (a == c) { //一条横线
        for (int i = b; i <= d; i++) {
            list.add(m[a][i]);
        }
    } else if (b == d) { // 一条竖线
        for (int i = a; i <= c; i++) {
            list.add(m[i][b]);
        }
    } else {
        int curC = b;
        int curR = a;
        while (curC != d) {
            list.add(m[a][curC]);
            curC++;
        }
        while (curR != c) {
            list.add(m[curR][d]);
            curR++;
        }
        while (curC != b) {
            list.add(m[c][curC]);
            curC--;
        }
        while (curR != a) {
            list.add(m[curR][b]);
            curR--;
        }
    }
}

题目四旋转矩阵

给定一个正方形矩阵，只用有限几个变量，实现矩阵中每个位置的数顺时针转动90度，比如如下的矩阵

0	1	2	3
4	5	6	7
8	9	10	11
12	13 	14 	15

矩阵调整为

leetcode 48 旋转图像

解

从整体上分析，就是一圈一圈的转换，所以获取每一圈的左上角和右下角，然后转换这个圈，然后2个点收缩，在转换。

每一圈自己怎么转换?

坐上角点(a,b),右下角点(c,d)，每条边上的点的数量较少转换的轮数，一共有d-b+1轮转换，每轮转换4个点

m[a][b+i]
m[a+i][d]
m[c][d-i]
m[c-i][b]

逆序直到一圈换完

public void rotate(int[][] matrix) {
    int aRow = 0;
    int aCol = 0;
    int bRow = matrix.length - 1;
    int bCol = matrix[0].length - 1;
    while (aRow <= bRow){
        rotateEdge(matrix, aRow, aCol, bRow, bCol);
        aRow++;
        aCol++;
        bRow--;
        bCol--;
    }
}

private void rotateEdge(int[][] m, int aRow, int aCol, int bRow, int bCol) {
    for (int i = 0; i< bCol - aCol; i++){
        int tmp =  m[aRow][aCol+i];
        m[aRow][aCol+i] = m[bRow-i][aCol];
        m[bRow-i][aCol] = m[bRow][bCol-i];
        m[bRow][bCol-i] = m[aRow+i][bCol];
        m[aRow+i][bCol] = tmp;
    }
}

题目五搜索二维矩阵

给定一个元素为非负整数的二维数组matrix,每行和每列都是从小到大有序的。再给定一个非负整数aim,请判断aim是否在matrix中。

leetcode240 搜索二维矩阵 II

解

从右上角开始找，这个值大于就向下找，小于就向左找，最多找O(M+N)的时间复杂度。

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    //从矩阵右上角找
    int col = matrix[0].length - 1;
    int row = 0;
    while (col >= 0 && row <= matrix.length - 1) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] < target) {
            row++;
        } else {
            col--;
        }
    }
    return false;
}

类型变化

一个矩阵，里面的数字不是0就是1，0永远在1的左边，求1最多的行。

解

从第一行开始，准备2个变量,list保存行数，ans保存最大值；获取到第一个1开始的坐标，查看该坐标下一行的该位置是否为1，并看坐标是否可以左移，能够左移，就更新list和ans，否则继续下一行。

题目六 SM操作

假设s和m初始化，s=”a”;m=s;
再定义两种操作，第一种操作:
m = s;
s= s+s;
第二种操作:
s = s+m;
求最小的操作步骤数，可以将s拼接到长度等于n

解

如果是质数只调用操作2，因为如果调用了操作1，加入s为k个a，那没最后m也会为k个a，是以k为因子的数，必然不可能组成质数。N-1次
n不是质数，n由某些质数因子构成n=a*b*c*d,a*b*c构成了那么d就一定是通过操作构成的d-1次，a*b构成了那么c就需要通过c-1构成，最后a+b+c+d-4，质数因子的和-质数因子的个数。

public static int minOps(int n) {
    if (n < 2) {
        return 0;
    }
    if (isPrim(n)) {

        return n - 1;
    }
    // n不是质数
    int[] divSumAndCount = divSumAndCount(n);
    return divSumAndCount[0] - divSumAndCount[1];
}

private static boolean isPrim(int n) {
    if (n <= 3) {
        return n > 1;
    }
    if (n % 6 != 1 && n % 6 != 5) {
        return false;
    }
    int k = (int) Math.sqrt(n);
    for (int i = 5; i <= k; i++) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;

}

private static int[] divSumAndCount(int n) {
    int sum = 0;
    int count = 0;
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            sum += i;
            count++;
            n /= i;
        }
    }
    return new int[]{sum, count};
}

题目七字符串数组出现最大的前k个

给定一个字符串类型的数组arr，求其中出现次数最多的前K个.

leetcode347 前 K 个高频元素

leetcode692 前K个高频单词

解

解法一：先用map统计词频，然后使用大根堆排序，弹出k个就是结果

解法二：小根堆（最小的弹出），容量为k，保存目前为止出现次数最大的前2个，节省空间

//通过建立词频表，放在大根堆，根据出现次数排列的大根堆
public String[] preKOfMaxTimes1(String[] arr,int K){
    HashMap<String,Integer> hashMap = new HashMap<>();
    for(String s : arr){
        if(!hashMap.containsKey(s)){
            hashMap.put(s,1);
        }else {
            hashMap.put(s,hashMap.get(s) + 1);
        }
    }
    //根据词出现的个数建立对应的大根堆
    PriorityQueue<Map.Entry<String,Integer>> priorityQueue
            = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            return o2.getValue() - o1.getValue();
        }
    });
    //存入大根堆
    for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
        priorityQueue.add(entry);
    }
    //取出前K个
    String[] str = new String[K];
    for(int i = 0;i < K;i++){
        String key = priorityQueue.poll().getKey();
        str[i] = key;
    }
    return str;
}

//也可以建立只具有K个容量的小根堆，这样存放词频表，能进入门槛的放入(多了就开始删门槛放入)
public String[] preKOfMaxTimes2(String[] arr,int K){
    HashMap<String,Integer> hashMap = new HashMap<>();
    for(String s : arr){
        if(!hashMap.containsKey(s)){
            hashMap.put(s,1);
        }else {
            hashMap.put(s,hashMap.get(s) + 1);
        }
    }
    //建立小根堆
    PriorityQueue<Map.Entry<String,Integer>> priorityQueue
            = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            return o1.getValue() - o2.getValue();
        }
    });
    for (Map.Entry<String, Integer> entry : hashMap.entrySet()){
        if(priorityQueue.size() <= 7){
            priorityQueue.add(entry);
        }else if (priorityQueue.size() > K
                && priorityQueue.peek().getValue() < entry.getValue()){ //小根堆顶部词数小于后序添加的
            priorityQueue.poll();
            priorityQueue.add(entry);
        }
    }
    //取出前K个
    String[] str = new String[K];
    for(int i = 0;i < K;i++){
        String key = priorityQueue.poll().getKey();
        str[i] = key;
    }
    return str;
}

难度提示已经上堆的数据，再局部调整，需要新增加一个数据结构

准备3个数据结构,实现排行榜

词频表（key字符串，value频率）
堆[初始k长度]
堆位置map (key字符串，value堆位置)

实时显示前K个，需要自己创建堆结构（类似于排行榜）

// 堆上放的数据
public static class Node {
    public String str;
    public int times;

    public Node(String s, int t) {
        str = s;
        times = t;
    }
}

public static class TopKRecord {
    private Node[] heap;
    private int heapSize;
    private HashMap<String, Node> strNodeMap;
    private HashMap<Node, Integer> nodeIndexMap;

    public TopKRecord(int size) {
        heap = new Node[size];
        heapSize = 0;
        strNodeMap = new HashMap<>();
        nodeIndexMap = new HashMap<>();
    }

    public void add(String str) {
        Node curNode = null;
        int preIndex = -1;
        // 是不是新节点
        if (!strNodeMap.containsKey(str)) {
            curNode = new Node(str, 1);
            strNodeMap.put(str, curNode);
            nodeIndexMap.put(curNode, preIndex);
        } else {
            curNode = strNodeMap.get(str);
            curNode.times++;
            preIndex = nodeIndexMap.get(curNode);
        }
        // 不在堆上
        if (preIndex == -1) {
            if (heapSize == heap.length) { //堆满了
                if (heap[0].times < curNode.times) { // 大于门槛
                    nodeIndexMap.put(heap[0], -1);
                    nodeIndexMap.put(curNode, 0);
                    heap[0] = curNode;
                    // 调整堆
                    heapify(0, heapSize);
                }
            } else { // 堆没满
                nodeIndexMap.put(curNode, heapSize);
                heap[heapSize] = curNode;
                // 新增元素
                heapInsert(heapSize++);
            }
        } else {
            // 调整堆
            heapify(0, heapSize);
        }
    }

    public void printHeap() {
        for (int i = 0; i != heap.length; i++) {
            if (heap[i] == null) {
                break;
            }
            System.out.println("Str:" + heap[i].str + " Times:" + heap[i].times);
        }
    }

    private void heapInsert(int index) {
        while (index != 0) {
            int parent = (index - 1) / 2;
            if (heap[index].times < heap[parent].times) {
                swap(parent, index);
                index = parent;
            } else {
                break;
            }
        }
    }

    private void swap(int index1, int index2) {
        nodeIndexMap.put(heap[index1], index2);
        nodeIndexMap.put(heap[index2], index1);
        Node tmp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = tmp;
    }

    private void heapify(int i, int index) {
        int l = index * 2 + 1;
        int r = index * 2 + 2;
        int smallest = index;
        while (l < heapSize) {
            if (heap[i].times < heap[index].times) {
                smallest = l;
            }
            // 操作右节点
            if (r < heapSize && heap[r].times < heap[smallest].times) {
                smallest = r;
            }
            // 最小值不是index,调整堆
            if (smallest != index) {
                swap(smallest, index);
            } else {
                break;
            }
            index = smallest;
            l = index * 2 + 1;
            r = index * 2 + 2;
        }
    }

}