上岸算法
死磕100%上岸率的精品小班課
關注我們，第一時間獲得大廠面試真題講解
應廣大同學們的需求，我們將定期整理各大廠最新的面試題題解，由我們【上岸算法】資深的老師給大家進行分析講解，幫助大家實時掌握最新的面試動態，早日上岸！
題目描述：Reconstruct Itinerary
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
One must use all the tickets once and only once.
Example 1:
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Example 2:
Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.
題解：
這題是一道歐拉路徑的題，歐拉路徑的含義：一個連通有向圖 G 有歐拉路徑，指存在一個頂點，從它出發，沿著有向邊的方向，可以不重複地遍歷圖中所有的邊。於是這題我們可以先 map 構建鄰接表，然後 dfs 起點 "JFK"，訪問過的邊從鄰接表中刪除， 當鄰接表中沒有節點時，把點加入結果集。
參考代碼
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
List<String> ans = new ArrayList<>();
//特殊條件判斷
if (tickets == null || tickets.size() < 1) return ans;
// 構造鄰接表
HashMap<String, List<String>> map = new HashMap<>();
for (List<String> e : tickets) {
//e的連結表存在獲取e的鄰接表，不存在就new一個List
List<String> edge = map.computeIfAbsent(e.get(0), k -> new ArrayList<>());
edge.add(e.get(1));
}
// 鄰接表排序
map.values().forEach(x -> x.sort(String::compareTo));
dfs(map,ans,"JFK");
return ans;
}
void dfs(HashMap<String, List<String>> map, List<String> ans, String start) {
List<String> edge = map.get(start);
//鄰接表中有節點繼續DFS
while (edge != null && edge.size() > 0) {
String p = edge.remove(0);
dfs(map, ans, p);
}
//沒有節點，把點加入ans
ans.add(0, start);
}
}
題目描述：Reorder Data in Log Files
You have an array of logs. Each log is a space delimited string of words.
For each log, the first word in each log is an alphanumeric identifier. Then, either:
Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.
We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.
Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.
Return the final order of the logs.
Example :
Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]題解：
根據題目意思，我們可以用兩個List存字母日誌和數字日誌，再用自定義排序對字母日誌進行排序，數字日誌順序保持不變，最後再合併兩個List。這題主要考察的是我們Comparator。
參考代碼
class Solution {
public String[] reorderLogFiles(String[] logs) {
List<String> letterLogs = new ArrayList<>();
List<String> numLogs = new ArrayList<>();
// 將字母日誌和數字日誌分開，分別放入兩個list
for (String log : logs) {
int i = log.indexOf(" ") + 1;
if (log.charAt(i) >= '0' && log.charAt(i) <= '9')
numLogs.add(log);
else
letterLogs.add(log);
}
Collections.sort(letterLogs, new Comparator<String>() {
@Override
public int compare(String a, String b) {
// 取字母a日誌的標識符及內容
int ai = a.indexOf(" ");
String ida = a.substring(0, ai);
String loga = a.substring(ai + 1);
// 取字母b日誌的標識符及內容
int bi = b.indexOf(" ");
String idb = b.substring(0, bi);
String logb = b.substring(bi + 1);
// 對比二者內容，如果相同則對比標識符
int cmp = loga.compareTo(logb);
if (cmp == 0)
return ida.compareTo(idb);
return cmp;
}
});
letterLogs.addAll(numLogs);
return letterLogs.toArray(new String[letterLogs.size()]);
}
}
題目描述：Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]Output: [[1,6],[8,10],[15,18]]Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].Example 2:
Input: intervals = [[1,4],[4,5]]Explanation: Intervals [1,4] and [4,5] are considered overlapping.
1.首先根據二維數組中每個一維數組的[0]進行升序排序，即根據start進行排序；
2.排序好的區間，從左到右進行合併區間
3.合併條件是前一個的結束 大於等於 後一個的開始（區間重複）
4.左邊一定是當前區間的左邊界
5.若區間有重疊，右邊界進行比較打擂臺
參考代碼
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
//特殊條件判斷
if (intervals == null || intervals.length == 0) return res.toArray(new int[0][]);
//根據區間的start進行排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int i = 0;
//從排序好的區間從左到右合併區間
while (i < intervals.length) {
//左邊一定是當前區間的左邊界
int left = intervals[i][0];
int right = intervals[i][1];
//若區間有重疊，右邊界進行比較打擂臺
while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
i++;
right = Math.max(right, intervals[i][1]);
}
//直到沒有重複，合併區間完畢
res.add(new int[]{left, right});
i++;
}
return res.toArray(new int[0][]);
}
}
題目描述：Kth Largest Element in a Stream
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.
Example :
KthLargest kthLargest = new KthLargest(3, arr);kthLargest.add(3); // returns 4kthLargest.add(5); // returns 5kthLargest.add(10); // returns 5kthLargest.add(9); // returns 8kthLargest.add(4); // returns 8題解：
因為是kth問題，平常kth問題可以用快排，也可以用heap來解決，這題主要注意的是in stream，所以第k大是動態更新的，我們並不能一次拿到所有數據，用heap來解決，代碼簡潔明。
參考代碼
public class KthLargest {
private PriorityQueue<Integer> queue;
private int limit;
public KthLargest(int k, int[] nums) {
limit = k;
queue = new PriorityQueue<>(k);
for (int num : nums) {
add(num);
}
}
public int add(int val) {
if (queue.size() < limit) {
queue.add(val);
} else if (val > queue.peek()) {
queue.poll();
queue.add(val);
}
return queue.peek();
}
}
杭州上岸算法網絡科技有限公司
上岸算法網絡科技有限公司是一家致力於用高質量，高互動性小班課程來幫助學生更好的在就業市場中定位以及求職的公司。我們以頂級的課程質量，高互動性的教學方式以及獨特的小班教學模式來幫助學生更快的跨過求職的鴻溝，用最高效，經濟，合理的方式幫助更多學生快速找到夢寐以求的工作。