637. 二叉树的层平均值

//BFS
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null){
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            int n = queue.size();
            int count = n;
            double avg = 0;
            while(n>0){
                TreeNode node = queue.poll();
                avg += node.val;
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
                n--;
            }
            res.add(avg/count);
        }
        return res;
    }
}

// DFS
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Integer> counts = new ArrayList<Integer>();
        List<Double> sums = new ArrayList<Double>();
        dfs(root, 0, counts, sums);
        List<Double> averages = new ArrayList<Double>();
        int size = sums.size();
        for (int i = 0; i < size; i++) {
            averages.add(sums.get(i) / counts.get(i));
        }
        return averages;
    }

    public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
        if (root == null) {
            return;
        }
        if (level < sums.size()) {
            sums.set(level, sums.get(level) + root.val);
            counts.set(level, counts.get(level) + 1);
        } else {
            sums.add(1.0 * root.val);
            counts.add(1);
        }
        dfs(root.left, level + 1, counts, sums);
        dfs(root.right, level + 1, counts, sums);
    }
}

215. 数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums,0,nums.length-1);
        return nums[nums.length-k];
    }

    public void quickSort(int[] nums,int left,int right){
        if(left>=right) return;
        int l = left,r = right;
        int mid = (left+right)/2;
        int privot = nums[mid];
        while(l < r){
            while(nums[l]<privot){
                l++;
            }
            while(nums[r]>privot){
                r--;
            }
            if(l>=r){
                break;
            }
            swap(nums,l,r);
            if(nums[l]==privot){
                r--;
            }
            if(nums[r]==privot){
                l++;
            }
        }
        if(l==r){
            l++;
            r--;
        }
        if(left<r){
            quickSort(nums,left,r);
        }
        if(l<right){
            quickSort(nums,l,right);
        }
    }

    private static void swap(int[] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

64. 最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length,n = grid[0].length;
        for(int i = 1;i < m;i++){
            grid[i][0] += grid[i-1][0];
        }
        for(int i = 1;i < n;i++){
            grid[0][i] += grid[0][i-1];
        }

        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                grid[i][j] = grid[i][j] + Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(i == 0 && j == 0) continue;
                else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

你知道的越多，你不知道的越多。