6.21号刷题

第一题 277. Find the Celebrity

题目描述

给定n个人，需要找出其中的名人。名人的规则是，其余所有人都知道他，但是他不知道任何其他人。

算法

O(n^2)的方法

public class findCelebrity277 {
    public int findCelebrity(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    boolean noknow = knows(i, j);
                    boolean know = knows(j, i);
                    if (noknow) break;
                    if (!know) break;
                    if (j == n - 1) return i;
                    if (i == n - 1 && j == n - 2) return i;
                }
            }
        }
        return -1;
    }
}

O(n)的方法

这个方法需要两次循环，第一次循环找到可能的候选人。候选人的选择条件是（假设是k），前面k-1个人都有认识的人。从k+1到结尾，k不认识任何人

第二次循环对这个候选人进行验证

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i))
                candidate = i;
        }
        
        for (int i = 0; i < n; i++) {
            if (i != candidate && knows(candidate, i) || !knows(i, candidate)) return -1;
        }
        
        return candidate;        
    }
}

第二题 74. Search a 2D Matrix

题目描述

在一个2维数组中，找是否存在目标值。这个数组满足，下一行的头一个数字，小于上一行的最后一个数字。

算法

一维解决

可以将其看作一个一维数组，转化的方式如下：

n m matrix convert to an array => matrix[x][y] => a[x m + y]

an array convert to n * m matrix => a[x] =>matrix[x / m][x % m];

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m <= 0) return false;
        int n = matrix[0].length;
        if (n <= 0) return false;

        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = low + (high - low) /2;
            int mid_value = matrix[mid / n][mid % n];
            
            if (mid_value > target) high = mid - 1;
            else if (mid_value < target) low = mid + 1;
            else return true;
        }
        return false;        
    }
}

二维数组正常解决

public class searchMatrix74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m <= 0) return false;
        int n = matrix[0].length;
        if (n <= 0) return false;

        int row = 0;
        for (int i = 0; i < m; i++) {
            if (target <= matrix[i][n - 1] && target>= matrix[i][0]) {
                row = i;
                break;
            }
        }
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (matrix[row][mid] > target) high = mid - 1;
            else if (matrix[row][mid] < target) low = mid + 1;
            else return true;
        }
        return false;
    }
}

第三题 240. Search a 2D Matrix II

题目描述

编写一个高效的算法，从一个m × n矩阵中寻找一个值。矩阵具有如下性质：

每一行的整数从左向右递增
每一列的整数从上往下递增

测试样例见题目描述。

算法

从右上角开始，由于每行和每列都是递增的，因此我们可以通过大于小于关系排除不不符合要求的行或者列。

public class searchMatrix240 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length <= 0 || matrix[0].length <= 0) return false;
        int col = matrix[0].length - 1, row = 0;

        while (col >= 0 && row <= matrix.length - 1) {
            int value = matrix[row][col];
            if (value == target) return true;
            else if (value > target) col--;
            else row++;
        }
        return false;
    }
}

第四题 120. Triangle

题目描述

给定一个三角形结构的二维数组，求从上到下最短的路径

算法

动态规划

二维举证据进行存储

public class minimumTotal120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.isEmpty() || triangle.get(0).isEmpty()) return 0;
        int n = triangle.size();
        int[][] presum = new int[n][n];
        presum[0][0] = triangle.get(0).get(0);
        int min = Integer.MAX_VALUE;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                int num = triangle.get(i).get(j);
                if (j == 0) presum[i][j] = presum[i - 1][j] + num;
                else if (j == i) presum[i][j] = presum[i - 1][j - 1] + num;
                else {
                    presum[i][j] = Math.min(presum[i - 1][j - 1], presum[i - 1][j]) + num;
                }
            }
        }
        for (int j = 0; j < n; j++) {
            min = Math.min(min, presum[n - 1][j]);
        }
        return min;
    }
}

利用一维矩阵

public class minimumTotal120 {
    public int minimumTotal2(List<List<Integer>> triangle) {
        if (triangle.isEmpty() || triangle.get(0).isEmpty()) return 0;
        int n = triangle.size();
        int[] presum = new int[n];
        int min = Integer.MAX_VALUE;
        presum[0] = triangle.get(0).get(0);

        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                int num = triangle.get(i).get(j);
                if (j == i) presum[j] = presum[j - 1] + num;
                else if (j == 0) presum[j] = presum[j] + num;
                else {
                    presum[j] = Math.min(presum[j], presum[j - 1]) + num;
                }
            }
        }

        for (int i = 0; i < n; i++) min = Math.min(min, presum[i]);
        return min;
    }
}

第五题 548. Split Array with Equal Sum

题目描述

给定包含n个整数的数组，判断是否存在三元组(i, j, k)满足下列条件：

1. 0 < i, i + 1 < j, j + 1 < k < n - 1
2. 子数组和 (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) 以及 (k + 1, n - 1) 相等
   我们定义子数组(L, R)为原始数组从L到R的切片，包含边界。

注意：

1 <= n <= 2000.
给定数组元素范围 [-1,000,000, 1,000,000].

算法

由于题目要求用3个点把一个数组分割成四段，如果四段的和相同，就回复true如果没有这样的3个点，回复false. 我们可以先将这个数组切为两段，在这两段中分别找看是否有相同的值，然后再看另外一个Array中是否有相同的切分方法

public class splitArray548 {
    public boolean splitArray(int[] nums) {
        if (nums.length < 7) return false;
        int[] sum = new int[nums.length];
        sum[0] = nums[0];

        for (int i = 1; i < nums.length; i++) sum[i] = sum[i - 1] + nums[i];

        for (int j = 3; j < nums.length - 3; j++) {
            Set<Integer> sliceSum = new HashSet<>();

            for (int i = 1; i < j - 2; i++) {
                if (sum[i - 1] == sum[j - 1] - sum[i]) sliceSum.add(sum[i - 1]);
            }

            for (int k = j + 2; k < nums.length - 1; k++) {
                if ((sum[k - 1] - sum[j] == sum[nums.length - 1] - sum[k]) && sliceSum.contains(sum[k - 1] - sum[j])) {
                    return true;
                }
            }
        }
        return false;
    }
}

第六题 105. Construct Binary Tree from Preorder and Inorder Traversal

题目描述

给定一个preorder和inorder遍历的数组，要求重构出二叉树

算法

如果preorder[0] 的数实在inorder[5]的位置，说明 0 - 4 是其左子树，6 - n-1是其右子树。

这样，我们就可以通过回溯的方法建造出整棵树

public class buildTree105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.length || preorder.length == 0) return null;
        TreeNode root = backtrack(preorder, inorder, 0 , 0, preorder.length - 1);
        return root;
    }

    public TreeNode backtrack(int[] preorder, int[] inorder, int prestart, int inorderstart, int inorderend) {
        if (inorderstart > inorderend || prestart > preorder.length - 1) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[prestart]);

        int index = 0;
        for (int i = inorderstart; i <= inorderend; i++) {
            if (root.val == inorder[i]) index = i;
        }

        root.left = backtrack(preorder, inorder, prestart + 1, inorderstart, index - 1);
        // (index - inorderstart) how many nodes in this root left part
        root.right = backtrack(preorder, inorder, prestart + (index - inorderstart) + 1, index + 1, inorderend);
        return root;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

第七题 106. Construct Binary Tree from Inorder and Postorder Traversal

题目描述

知道中序和后序遍历的情况下，建出整个二叉树

算法

思路与上一题相似

public class buildTree106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length != inorder.length || postorder.length == 0) return null;
        HashMap <Integer, Integer> position = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            position.put(inorder[i], i);
        }
        TreeNode root = backtrack(inorder, 0 , inorder.length - 1, postorder, 0, inorder.length - 1, position);
        return root;
    }

    public TreeNode backtrack(int[] inorder, int is, int ie, int[] postorder, int ps, int pe,
                              HashMap<Integer, Integer> position) {
        if (is > ie || ps > pe) return null;

        TreeNode root = new TreeNode(postorder[pe]);
        int po = position.get(postorder[pe]);

        //(po - is) the left size of the root
        root.left = backtrack(inorder, is, po - 1, postorder, ps, ps + (po - is) - 1, position);
        root.right = backtrack(inorder, po + 1, ie, postorder, ps + (po - is), pe - 1, position);
        return root;
    }
}

第八题 34. Search for a Range

题目描述

在Array中，找到目标值的[begin, end]区间，其中可能包含重复的数字。

算法

分别向左和向右趋近与targe的值。

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        if (nums.length <= 0 || target < nums[0] || target > nums[nums.length - 1]) return result;

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

第九题 624. Maximum Distance in Arrays

题目描述

给定一组数组arrays，各数组递增有序，求不同数组之间最小值、最大值之间差值绝对值的最大值。

算法

由于需要在不同的数组间挑选最大和最小，我们每次都用当前的数组的最小和最大和原始的最大和最小进行对比，这样就不会出现问题。

public class maxDistance624 {
    public int maxDistance(List<List<Integer>> arrays) {
        if (arrays.isEmpty()) return 0;

        int result = Integer.MIN_VALUE;
        int max = arrays.get(0).get(arrays.get(0).size() - 1);
        int min = arrays.get(0).get(0);

        for (int i = 1; i < arrays.size(); i++) {
            result = Math.max(result, Math.abs(arrays.get(i).get(0) - max));
            result = Math.max(result, Math.abs(min - arrays.get(i).get(arrays.get(i).size() - 1)));
            max = Math.max(arrays.get(i).get(arrays.get(i).size() - 1), max);
            min = Math.min(arrays.get(i).get(0), min);
        }

        return result;
    }
}

第十题 605. Can Place Flowers

题目描述

给定数组flowerbed表示一个花床，0表示位置为空，1表示位置非空。花不能相邻种植，即不能出现相邻的1。

给定想要种植的花朵数目n，判断是否可以满足要求。

算法

将可以种花的地方种上花，如果满足就return true

public class canPlaceFlowers605 {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (flowerbed.length <= 0) return false;

        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                if (i == 0) {
                    if (flowerbed.length > 1 && flowerbed[i + 1] == 0) {
                        flowerbed[i] = 1;
                        count++;
                    }
                    if (flowerbed.length == 1) {
                        count++;
                    }
                } else if (i < flowerbed.length - 1) {
                    if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                        flowerbed[i] = 1;
                        count++;
                    }
                } else if (i == flowerbed.length - 1) {
                    if (flowerbed[i - 1] == 0) {
                        flowerbed[i - 1] = 1;
                        count++;
                    }
                }
            }
            if (count >= n) return true;
        }
        return false;
    }
}