上岸算法
任何只教知識的課程都是耍流氓
我們直擊上岸
關注我們，第一時間獲得大廠面試真題講解
應廣大同學們的需求，我們將定期整理各大廠最新的面試題題解，由我們【上岸算法】資深的老師給大家進行分析講解，幫助大家實時掌握最新的面試動態，早日上岸！
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Example 1 :
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]Explanation: [4,-1,2,1] has the largest sum = 6.題解：
動態規劃方法：判斷以第 i - 1 個元素結尾的子序列的最大值能不能給當前第 i 個元素結尾的序列提供增益，即dp[i - 1] > 0 ，dp[i] = dp[i - 1] + nums[i]。
參考代碼
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null) {
return 0;
}
int max = nums[0]; // 全局最大值
int subMax = nums[0]; // 前一個子組合的最大值,狀態壓縮
for (int i = 1; i < nums.length; i++) {
if (subMax > 0) {
// 前一個子組合最大值大於0，正增益
subMax = subMax + nums[i];
} else {
// 前一個子組合最大值小於0，拋棄前面的結果
subMax = nums[i];
}
// 計算全局最大值
max = Math.max(max, subMax);
}
return max;
}
}
題目描述：Maximum Product of Word Lengths
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1 :
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]Explanation: The two words can be "abcw", "xtfn".
Example 2 :
Input: ["a","ab","abc","d","cd","bcd","abcd"]Explanation: The two words can be "ab", "cd".
題解：
用二進位的一位表示某一個字母是否出現過，0表示沒出現，1表示出現。當兩個字符串沒有相同的字母時，二進位數與的結果為0。
參考代碼
class Solution {
public int maxProduct(String[] words) {
int wlength = words.length;
int[] arr = new int[wlength];
for(int i = 0; i < wlength; ++i){
int length = words[i].length();
for(int j = 0; j < length; ++j){
arr[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
int ans = 0;
for(int i = 0; i < wlength; ++i){
for(int j = i + 1; j < wlength; ++j){
if((arr[i] & arr[j]) == 0){
int k = words[i].length() * words[j].length();
ans = ans < k ? k : ans;
}
}
}
return ans;
}
}
題目描述：Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Follow up: Could you implement the O(n) solution?
Example 1:
Input: nums = [100,4,200,1,3,2]Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]題解：
先找出最大最小值，創建長度為 max-min+1的輔助空間，將原數組的元素映射到[0,max-min]區間，順序統計該區間最長連續子序列。
參考代碼
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
//先找出最大最小值
int min = nums[0],max = nums[0];
for (int e:nums){
max = Math.max(max, e);
min = Math.min(min, e);
}
//將nums中的每個數字映射到 [0,max-min]
boolean[] arr = new boolean[max-min+1];
for (int e:nums){
arr[e-min] = true;
}
//一次遍歷
int cnt = 0,res = 0;
for (int i = 0; i < arr.length; i++){
if (arr[i]){
cnt++;
}else{
res = Math.max(cnt, res);
cnt = 0;
}
}
res = Math.max(cnt, res);
return res;
}
}
題目描述：Alien Dictionary
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Example 2:
"zx"
題解：
先由輸入構造出一張有向圖，圖的節點是字符，邊指示字符順序。考察相鄰兩字符串的每個字符來構造全圖。假設當前考察的字符是c1, c2（c1是前面單詞某位置的字符，c2是後面單詞同位置處的字符），若c1和c2不等，則在圖中加入一條c1指向c2的邊。
然後進行拓撲排序，並記錄拓撲排序依次遍歷到的字符，若排序後所得字符和圖中節點數一致說明該圖無圈，也即給定的字典合法，拓撲排序所得結果即為字典規則。
參考代碼
public class Solution {
public String alienOrder(String[] words) {
if (words == null || words.length == 0)
return "";
if (words.length == 1)
return words[0];
Map<Character, Set<Character>> graph = buildGraph(words);
Map<Character, Integer> indegree = computeIndegree(graph);
StringBuilder order = new StringBuilder();
LinkedList<Character> queue = new LinkedList<Character>();
for (Character c : indegree.keySet()) {
if (indegree.get(c) == 0)
queue.offer(c);
}
while (!queue.isEmpty()) {
char c = queue.poll();
order.append(c);
for (Character adj : graph.get(c)) {
if (indegree.get(adj) - 1 == 0)
queue.offer(adj);
else
indegree.put(adj, indegree.get(adj) - 1);
}
}
return order.length() == indegree.size() ? order.toString() : "";
}
public Map<Character, Set<Character>> buildGraph(String[] words) {
Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
int N = words.length;
for (int i = 1; i < N; i++) {
String word1 = words[i - 1];
String word2 = words[i];
int len1 = word1.length(), len2 = word2.length(), maxLen = Math.max(len1, len2);
boolean found = false;
for (int j = 0; j < maxLen; j++) {
char c1 = j < len1 ? word1.charAt(j) : ' ';
char c2 = j < len2 ? word2.charAt(j) : ' ';
if (c1 != ' ' && !map.containsKey(c1))
map.put(c1, new HashSet<Character>());
if (c2 != ' ' && !map.containsKey(c2))
map.put(c2, new HashSet<Character>());
if (c1 != ' ' && c2 != ' ' && c1 != c2 && !found) {
map.get(c1).add(c2);
found = true;
}
}
}
return map;
}
public Map<Character, Integer> computeIndegree(Map<Character, Set<Character>> graph) {
Map<Character, Integer> indegree = new HashMap<Character, Integer>();
for (Character prev : graph.keySet()) {
if (!indegree.containsKey(prev))
indegree.put(prev, 0);
for (Character succ : graph.get(prev)) {
if (!indegree.containsKey(succ))
indegree.put(succ, 1);
else
indegree.put(succ, indegree.get(succ) + 1);
}
}
return indegree;
}
}