6.17号刷题

第一题 75. Sort Colors

题目描述

有0,1,2三种数，将他们排序

算法

bucket 排序O(2n)的时间复杂度

public class Solution {
    public void sortColors(int[] nums) {
        int[] bucket = new int[3];

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) bucket[0]++;
            else if (nums[i] == 1) bucket[1]++;
            else bucket[2]++;
        }

        int zero = bucket[0], one = bucket[1];

        for (int i = 0; i < zero; i++) nums[i] = 0;
        for (int i = zero; i < one + zero; i++) nums[i] = 1;
        for (int i = one + zero; i < nums.length; i++) nums[i] = 2;        
    }
}

第二题 154. Find Minimum in Rotated Sorted Array II

题目描述

假设一个排好序的数组在某处执行了一次“旋转”，找出最小的元素（数组元素可能重复）

此题目为”Find Minimum in Rotated Sorted Array”的扩展（去掉了数组不重复的限制条件）

可能出错的测试样例：[3,3,1,3]，[10,1,10,10,10]

算法

仍然使用二分查找，但是当high == low时，我们不能确定哪一个更小，因此只需要high–即可

public class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < nums[high])
                high = mid;
            else if (nums[mid] > nums[high])
                low = mid + 1;
            else high--;
        }
        return nums[low];        
    }
}

第三题 33. Search in Rotated Sorted Array

题目描述

找寻一个指定的数字在一个Array中

算法

利用二分查找

首先确定哪边是升序，在进行判断

public class search33 {
    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int high = nums.length - 1, low = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            //Ascending in the left, rotate point at the right
            if (nums[mid] >= nums[low]) {
                if (target >= nums[low] && target < nums[mid]) high = mid - 1;
                else low = mid + 1;
            }
            // Ascending in the right, rotate point at the left
            if (nums[mid] <= nums[high]) {
                if (target > nums[mid] && target <= nums[high]) low = mid + 1;
                else high = mid - 1;
            }

        }
        return -1;
    }
}

第四题 81. Search in Rotated Sorted Array II

题目描述

现在Array中可能包含重复的数字

算法

这种题目的关键点有两点：

• 找到mid的两边，哪边是sorted
• 判断结束的条件left < right 还是 left <= right

public class search81 {
    public boolean search(int[] nums, int target) {
        if (nums.length == 0) return false;
        int low = 0, high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return true;

            //Ascending is in the left
            if (nums[mid] > nums[low] || nums[mid] > nums[high]) {
                if (target >= nums[low] && target < nums[mid]) high = mid - 1;
                else low = mid + 1;
            } else if (nums[mid] < nums[low] || nums[mid] < nums[high]) { //Ascending is in the right
                if (target > nums[mid] && target <= nums[high]) low = mid + 1;
                else high = mid - 1;
            } else {
                high--;
            }
        }
        return false;
    }
}

第五题 289. Game of Life

题目描述

根据维基百科的文章：“生命游戏，也被简称为生命，是一款由英国数学家约翰·霍顿康威于1970年设计的细胞自动机。”

给定一个m * n的细胞隔板，每一个细胞拥有一个初始状态：存活(1)或者死亡(0)。每一个细胞与其周围的8个邻居细胞（水平，竖直，对角线）发生交互，依据如下四条规则（摘自维基百科）：

• 任何相邻存活细胞数小于2个的存活细胞都会死亡，模拟人口不足。
• 任何相邻存活细胞数为2个或者3个的存活细胞会存活到下一代。
• 任何相邻存活细胞数大于3个的存活细胞都会死亡，模拟人口过载。
• 任何相邻存活细胞数等于3个的死亡细胞都会成为一个存活细胞，模拟繁殖。
• 编写函数，根据隔板的当前状态，计算其下一个状态（一次更新之后）

进一步思考：

1. 你可以就地完成题目吗？记住隔板需要同时更新：你不能先更新某些细胞然后再以其变更后的值来更新其他细胞。
2. 在这个问题中，我们使用2维数组表示隔板。原则上，隔板是无穷的，这可能导致一些边界问题。你怎么处理边界问题？

算法

由于本题要求不需要多余的存储空间，因此我们需要某种方式来表示细胞的前一个状态和后一个状态。

由于细胞只存在0和1两种情况，因此我们可以利用位来表示两种状态。

[2nd bit, 1st bit] = [next state, current state]

- 00  dead (next) <- dead (current)
- 01  dead (next) <- live (current)  
- 10  live (next) <- dead (current)  
- 11  live (next) <- live (current) 

由此可以在不被需要存储空间的情况下解决该问题。

另外，这题查看周围边界的代码也写的很巧妙。可以借鉴下。

public class gameOfLife289 {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        if (m <= 0) return;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = calLive(board, m, i, n, j);
                int now = board[i][j] & 1;
                if (now == 1) {
                    if (live >= 2 && live <= 3) board[i][j] = 3;
                } else {
                    if (live == 3) {
                        board[i][j] = 2;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = board[i][j] >> 1;

    }

    public int calLive(int[][] board, int m, int i, int n, int j) {
        int live = 0;
        for (int k = Math.max(i - 1, 0); k <= Math.min(i + 1, m - 1); k++) {
            for (int z = Math.max(j - 1, 0); z <= Math.min(j + 1, n - 1); z++) {
                live += board[k][z] & 1;
            }
        }
        live -= board[i][j] & 1;
        return live;
    }
}

第六题 73. Set Matrix Zeroes

题目描述

如果某行某列有0，则将该行该列全部置为0。要求空间复杂度为0

算法

利用第一行和第一列作为指示列，循环整个数组两次完成整个算法。

public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        if (m <= 0) return;
        int n = matrix[0].length;
        boolean fc = false, fl = false;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    if (j == 0) fc = true;
                    if (i == 0) fl = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if (fc) 
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        if (fl)
            for (int j = 0; j < n; j++) matrix[0][j] = 0;        
    }
}

第七题119. Pascal’s Triangle II

题目描述

输出第i行的Pascal 矩阵

算法

利用list进行直接的加减

public class getRow119 {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < rowIndex + 1; i++) {
            list.add(i, 1);
            for (int j = i - 1; j > 0; j--)
                list.set(j, list.get(j) + list.get(j - 1));
        }

        return list;
    }
}

第八题 621. Task Scheduler

题目描述

假设给定一串字符串，每个相同的字符串之间至少相隔n个距离，最最短的包含所有字符串的长度是多少。

算法

这道题与358. Rearrange String k Distance Apart极其类似。都是要求有一个相隔距离，然后更新后的String的相关内容。对于这种类型的题目，我们可以用PriorityQueue进行求解。

public class leastInterval621 {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> charStore = new HashMap<>();

        for (char c : tasks) charStore.put(c, charStore.getOrDefault(c, 0) + 1);
        Queue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });

        Queue<Map.Entry<Character, Integer>> wait = new LinkedList<>();
        maxHeap.addAll(charStore.entrySet());
        int sum = 0, interval = 0;

        while (!maxHeap.isEmpty()) {
            for (int i = 0; i < n + 1; i++) {
                if (!maxHeap.isEmpty()) {
                    interval++;
                    Map.Entry<Character, Integer> map = maxHeap.poll();
                    int num = map.getValue() - 1;
                    if (num > 0) {
                        map.setValue(num);
                        wait.offer(map);
                    }
                }
            }

            while (!wait.isEmpty()) {
                Map.Entry<Character, Integer> map = wait.poll();
                maxHeap.offer(map);
            }

            sum += !maxHeap.isEmpty() ? (n + 1) : interval;
            interval = 0;
        }
        return sum;
    }
}

第九题 80. Remove Duplicates from Sorted Array II

题目描述

从一个数组中移除重复的数字，每个数字至多出现两次。

算法

利用一个id进行位置的指示

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 2) return nums.length;
        int id = 1, duplic = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                duplic = 1;
                nums[id++] = nums[i];
            } else {
                if (duplic == 1) {
                    nums[id++] = nums[i];
                    duplic++;
                }
            }
        }
        return id;
    }
}

第十题 611. Valid Triangle Number

题目描述

给定非负整数数组，求其中可以组成三角形的三元组的个数。

算法

主要可以考察利用双向的指针遍历一个数组。

public class triangleNumber611 {
    public int triangleNumber(int[] nums) {
        if (nums.length < 3) return 0;
        Arrays.sort(nums);

        int sum = 0;
        for (int i = nums.length - 1; i > 1; i--) {
            int low = 0, high = i - 1;
            while (low < high) {
                if (nums[low] + nums[high] > nums[i]) {
                    sum += high - low;
                    high--;
                } else {
                    low++;
                }
            }
        }
        return sum;
    }
}