上岸算法
死磕100%上岸率的精品小班課
關注我們，第一時間獲得大廠面試真題講解
應廣大同學們的需求，我們將定期整理各大廠最新的面試題題解，由我們【上岸算法】資深的老師給大家進行分析講解，幫助大家實時掌握最新的面試動態，早日上岸！
題目描述：K Closest Points to Origin
We have a list of points on the plane. Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1 :
Input: points = [[1,3],[-2,2]], K = 1The distance between (1, 3) and the origin is sqrt(10).The distance between (-2, 2) and the origin is sqrt(8).Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].Example 2 :
Input: points = [[3,3],[5,-1],[-2,4]], K = 2(The answer [[-2,4],[3,3]] would also be accepted.)題解：
這個問題的本質其實就是對於點到原點的距離，求 Top K 元素。Top K元素的題型可以用快排思想，也可以用堆。堆的這題需要自定義排序方法，因為比較距離長短，我們可以用歐幾裡得計算距離。
參考代碼
class Solution {
public int[][] kClosest(int[][] points, int K) {
//構造一個大頂堆自定義堆排序方法
//以歐幾裡得距離作為判定優先級的標準
PriorityQueue<int[]> max = new PriorityQueue<>( (a, b) -> (count(b) - count(a)) );
int[][] res = new int[K][2];
for(int[] point : points){
//先往裡面添加K個元素
if(max.size() < K){
max.add(point);
continue;
}
//始終保持最小的K的元素
if(count(point) < count(max.peek())){
max.poll();
max.add(point);
}
}
for(int i = 0; i < K; ++i){
res[i] = max.poll();
}
return res;
}
//歐幾裡得距離計算
private int count(int[] num){
int res = num[0] * num[0] + num[1] * num[1];
return res;
}
}
題目描述：Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1 :
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .
Example 2 :
Input: 4, [[1,0],[2,0],[3,1],[3,2]]Output: [0,1,2,3] or [0,2,1,3]Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
題解：
這題考的是拓撲排序，可以用BFS來做。
1.建立入度表，入度為 0 的節點先入隊
2.當隊列不為空，節點出隊，標記學完課程數量的變量加 1，並記錄該課程
3.將課程的鄰居入度減 1
4.若鄰居課程入度為 0，加入隊列
用一個變量記錄學完的課程數量，一個數組記錄最終結果，簡潔好理解。
參考代碼
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses == 0) return new int[0];
int[] inDegrees = new int[numCourses];
// 建立入度表
for (int[] p : prerequisites) { // 對於有先修課的課程，計算有幾門先修課
inDegrees[p[0]]++;
}
// 入度為0的節點入隊列（即不需要先修其他課的課程加入隊列）
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegrees.length; i++) {
if (inDegrees[i] == 0) queue.offer(i);
}
// 記錄當前已經學完課程數量
int count = 0;
// 已經學完的課程
int[] res = new int[numCourses];
// 根據提供的先修課列表，刪除入度為 0 的節點
while (!queue.isEmpty()){
int curr = queue.poll();
// 將可以學完的課程加入結果當中
res[count++] = curr;
//把先修課是curr的鄰居課程的入度減1
for (int[] p : prerequisites) {
if (p[1] == curr){
inDegrees[p[0]]--;
if (inDegrees[p[0]] == 0) queue.offer(p[0]);
}
}
}
//當課程數量與要學的課程數量相等時，直接返回
if (count == numCourses) return res;
return new int[0];
}
}
題目描述：Maximum Points You Can Obtain from Cards
There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.
In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.
Your score is the sum of the points of the cards you have taken.
Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
Example 1:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.Example 2:
Input: cardPoints = [2,2,2], k = 2Explanation: Regardless of which two cards you take, your score will always be 4.這題求取的點數最大值，可以思路反一反，取剩餘數的最小值，因為剩餘數是連續的，等於這題是考長度len - k的連續子數組的最小值。這樣理解後就可以很快想出用滑動窗口來解答。
參考代碼
class Solution {
public int maxScore(int[] cardPoints, int k) {
int len = cardPoints.length, sum = 0;
for (int cardPoint: cardPoints) {
sum += cardPoint;
}
int min = Integer.MAX_VALUE, temp = 0;
int length = len - k;
for (int i = 0; i < len; i++) {
temp += cardPoints[i];
if (i >= length) {
temp -= cardPoints[i - length];
}
if (i >= length - 1)
min = Math.min(min, temp);
}
return sum - min;
}
}
題目描述：Minimum Number of K Consecutive Bit Flips
In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.
Example 1:
Input: A = [0,1,0], K = 1Explanation: Flip A[0], then flip A[2].Example 2:
Input: A = [1,1,0], K = 2Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].題解：
這題可以用滑動窗口來解答，我們可以通過維護長度為k的翻轉隊列，來計算最後最少翻轉結果。因為當前位置 i 是否翻轉的情況是：
1）前k個數字一共翻轉了偶數次（i位置其實等於沒翻轉），並且當前 i 原數字是0
2）前k個數字一共翻轉了奇數次（i位置其實等於翻轉了），並且當前 i 原數字是1
可以用一個統一的表達式 翻轉次數 time % 2 == A[i].
參考代碼
class Solution {
public int minKBitFlips(int[] A, int K) {
Queue<Integer> q = new LinkedList<Integer>();
int res = 0;
for(int i = 0; i < A.length; i++){
// 維護長度為K的窗口
if(!q.isEmpty() && q.element() + K == i)
q.poll();
//判斷當前位置 i 是否需要翻轉
if(q.size() % 2 == A[i]){
if(i + K > A.length) return -1;
res ++;
q.offer(i);
}
}
return res;
}
}