Amazon高频练习

973. 最接近原点的K个点 K Closest Points to Origin

We have a list of points on the plane. Find the K closest points to the origin (0, 0)
Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]]

思路

遍历点，用一个数组记录每个点距离原点的距离
给这个数组排序，取出这个数组里第k个数值
再次遍历点，取出所有小于这个value的值，存入结果数组

java

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int n = points.length;
        int[] distance = new int[n];
        int[][] result = new int[K][2];
        for(int i=0;i<n;i++) {
            distance[i] = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        }
        Arrays.sort(distance);
        int value = distance[K-1];
        int t=0;
        for(int j=0;j<n;j++) {
            if(points[j][0] * points[j][0] + points[j][1] * points[j][1] <= value) {
                result[t++] = points[j];
            }
        }
        return result;
    }
}

js

var kClosest = function(points, K) {
    let distance = [];
    points.forEach((p, index) => {
        distance.push(p[0] * p[0] + p[1] * p[1])
    })
    distance.sort((a,b)=>a-b);
    const value = distance[K-1];
    const result = [];
    points.forEach((p) => {
        if(p[0] * p[0] + p[1] * p[1] <= value) {
            result.push(p);
        }
    })
    return result;
};

409. 最长回文串 Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Input: s = “abccccdd” Output: 7（”dccaccd”）

思路

计算每个字符出现的次数
出现v次，可以使用v/2*2次，在回文串的左右分别放置v/2个字符
如果v是奇数，可以将这个字符作为回文中心，只能有一个回文中心

java

class Solution {
  public int longestPalindrome(String s) {
    int[] count = new int[128];
    for (char c: s.toCharArray()) {
      count[c] ++;
    }
    int ans = 0;
    for (int v: count) {
      ans += v / 2 * 2;
      if (v % 2 == 1 && ans % 2 == 0) {
        ans ++;
      }
    }
    return ans;
  }
}

js

var longestPalindrome = function(s) {
    const map = {}
    const array = s.split("");
    array.forEach(e=>{
        if(map[e]) {
            map[e]++;
        }
        else {
            map[e] = 1;
        }
    })
    let result = 0;
    Object.keys(map).forEach(e=>{
        result += Math.floor(map[e] / 2) * 2;
        if (map[e] % 2 === 1 && result % 2 === 0) {
            result ++;
        }
    })
    return result;
};

836. 矩形重叠 Rectangle Overlap

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.
Given two (axis-aligned) rectangles, return whether they overlap.
Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3] Output: true
Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1] Output: false

思路

如果存在下面任意一种情况，就不会重叠

左侧： rec1[2] <= rec2[0]
右侧：rec1[0] >= rec2[2]
上方：rec1[1] >= rec2[3]
下方：rec1[3] <= rec2[1]

java

class Solution {
  public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    return !(rec1[2] <= rec2[0] || 
             rec1[3] <= rec2[1] ||
             rec1[0] >= rec2[2] ||  
             rec1[1] >= rec2[3]); 
  }
}

js

var isRectangleOverlap = function(rec1, rec2) {
    return !(rec1[2] <= rec2[0] || 
             rec1[3] <= rec2[1] ||
             rec1[0] >= rec2[2] ||  
             rec1[1] >= rec2[3]); 
};

210. 课程表2

There are a total of n courses you have to take labelled from 0 to n - 1.
Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.
Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.
Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1]
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3]

思路：拓扑排序

图的拓扑排序：对于一个有向无环图，对于所访问的顺序进行排序，形成一个线性序列。
图的周游问题的解决：通过递归实现深度优先，通过队列实现广度优先

深度优先，用栈记录访问过的节点。假设搜索到一个节点u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中，此时就可以把u入栈。这样如果从栈顶往栈底的顺序，由于u处于栈顶的位置，那么u出现在所有u相邻节点的前面。因此，满足拓扑顺序。这样对图进行一边深度优先搜索，最终从栈顶到栈底就是一种拓扑顺序。
对于图中的任意一个节点，在搜索的过程中有三种状态，即：未搜索，搜索中（还没回溯回来），已完成。
每一轮搜索开始时候，任取一个未搜索的节点开始深度优先搜索，将当前节点记为搜索中，遍历这个节点的每一个相邻节点v，如果v为未搜索，开始搜索，搜索完成后回溯到u；如果v为搜索中，那么就找到了图中的一个环，因此不存在拓扑排序；如果v是已完成，说明v已经在栈中，不用进行任何操作。当u的所有相邻节点都为已完成时，将u放入栈中，并将其标记为已完成。

java

class Solution {
  List<List<Integer>> edges;  //存储有向图
  int[] visited;  //标记每个节点的状态，0未搜索，1搜索中，2已完成
  int[] result; //栈
  boolean valid = true;
  int index;
  public int[] findOrder(int numCourses, int[][] prerequisites) {
    edges = new ArrayList<List<Integer>>();
    for(int i=0; i < numCourses; ++i) {
      edges.add(new ArrayList<Integer>());
    }
    visited = new int[numCourses];
    result = new int[numCourses];
    index = numCourses - 1;
    for (int[] info : prerequisites) {
      edges.get(info[1]).add(info[0]);
    }
    for (int i = 0; i < numCourses && valid ; ++i) {
      if (visited[i] == 0) {
        dfs(i);
      }
    }
    if(!valid) {
      return new int[0];
    }
    return result;
  }
  public void dfs(int u) {
    visited[u] = 1; //搜索中
    //搜索相邻接点
    for (int v: edges.get(u)) {
      if (visited[v] == 0) {
        dfs(v);
        if(!valid) {
          return;
        }
      }
      //找到了环
      else if (visited[v] == 1) {
        valid = false;
        return;
      }
    }
    visited[u] = 2;
    result[index--] = u;
  }
}

1120. 子树的最大平均值

Given the root of a binary tree, find the maximum average value of any subtree of that tree.
Input: [5,6,1] Output: 6.00000

思路

从底向上遍历，每次遍历返回当前子树的元素和节点个数
使用数组arr储存，arr[0]为元素和，arr[1]为节点个数，然后更新包括当前根节点在内的平均值。

java

class Solution {
  double res = 0;
  public double maximumAverageSubtree(TreeNode root) {
    if (root == null) return 0;
    helper(root);
    return res;
  }
  private int[] helper(TreeNode root) {
    int[] arr = new int[2];
    if (root==null) return arr;
    int[] left = helper(root.left);
    int[] right = helper(root.right);
    arr[0] = left[0] + right[0] + root.val;
    arr[1] = left[1] + right[1] + 1;
    res = Math.max(res, (double) arr[0] / arr[1]);
    return arr; //每次返回一个只有两位的数组
  }
}