首先我在這里先介紹下演算法對于我們個人的意義，在實際專案中，演算法的使用場景有很多，如“Java8中Hashmap使用紅黑樹來實作”、“Redis底層使用LRU來進做淘汰策略”、“大資料領域很多問題都基于TopK”、“JS原型鏈里使了類似鏈表的成環檢測”、“特別復雜的業務邏輯經常涉及到DAG”、“MySql為什么索引要用B+樹”、“Oracle里的開窗函式如何實作” 等等等等，總之，正是因為演算法題目中只保留了必備的要素，舍棄了其他無關緊要的部分，所以可以對每一位做題人都構建一個學習解決問題的最佳環境，而在這個環境中的成長與提高，將對一個軟體工程師的生涯產生深遠影響，乃至一世，所以，請大家能有一顆匠心，你可以選擇不去了解學習掌握演算法，但是請不要耽誤他人進步，山高水長，江湖路遠，珍重萬千，有緣再見！
一、LeetCode 350題 求兩個集合中的差值
1.1 題目分析
我們先來看一道題目： 第350題：兩個陣列的交集
需求：給定兩個陣列，撰寫一個函式來計算它們的交集，
實體代碼
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
根據實體代碼分析：
- 輸出的結果應該與給定的兩個集合共同出現的次數是相同的，
- 我們這里不考了排序的問題
- 首先拿著這個題目的時候，我們首先應該想到使用map的方式進行映射，為什么可以這樣看那，因為我們需要找出兩個陣列中交集的元素，同時應與兩個陣列中出現的次數一直，這樣導致我們需要制每個值串的次數，所以映射關系就成了<元素，元素出現的次數>
1.2 題目講解
根據分析，假設我們有兩個陣列分別為； nums1=[1,2,2,2] ， nums2=[2,2]
首先我們定義一個map用來存其中一個陣列中的資料，進行回圈向陣列中輸入資料
第一次map中沒有這個元素所以value為1
第二、三次map中如有這個元素value+1后面依次類推，就像使用map計算wordCount
首先我們需要進行判斷map中是否這個資料，如果有則進行相加(后面的邏輯就是一樣的了)
第二階段
首先定義一個空的陣列，我們現在獲取到了map之后，map中就存盤了我們每個元素及他們出現的個數，接下來我們在遍歷nums2這個陣列，拿著每個元素去map中get資料如果get到了資料value次數減1,將這個key復制給空的陣列，
1.3 代碼分析
public static int[] intersect(int[] nums1, int[] nums2) {
// 判空操作
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
//1.定義一個map用來存盤一個陣列中的出現的值 value存盤出現的個數
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
Integer integer = map.get(nums1[i]);
if (integer == null) {
map.put(nums1[i], 1);
} else {
map.put(nums1[i], integer + 1);
}
}
int k = 0;
for (int i = 0; i < nums2.length; i++) {
Integer integer = map.get(nums2[i]);
if (integer != null) {
if (integer > 0) {
nums2[k] = nums2[i];
map.put(nums2[i], integer - 1);
k++;
}
}
}
return Arrays.copyOfRange(nums2, 0, k);
}
1.4 題目進階（優化）
前提:我們首先我們需要將兩個陣列進行排序
如果給定的陣列已經排好序呢？你將如何優化你的演算法？我們分析一下，假如兩個陣列都是有序的，分別為： nums1=[1,2,2,2] ， nums2=[2,2]
解題步驟：
<1>如果兩個指標的元素不相同，我們將小的指標往后一然后在進行判斷
<2>如果兩個元素相同，則兩個指標同時后移
<3> 直到任意一個陣列終止，
1.5 代碼分析
public static int[] intersect2(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
int i = 0, j = 0, k = 0;
Arrays.sort(nums1);
Arrays.sort(nums2);
while (i < nums1.length && j < nums2.length) {
if (nums1[i] > nums2[j]) {
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
nums2[k] = nums1[i];
i++;
j++;
k++;
}
}
return Arrays.copyOfRange(nums2, 0, k);
}
二、LeetCode 14 最長公共前綴
2.1 題目分析
我們先來看一道題目： 第14: 最長公共前綴
需求：撰寫一個函式來查找字串陣列中的最長公共前綴，如果不存在公共前綴，則回傳""
實體代碼
輸入: ["flower","flow","flight"]
輸出: "fl"
輸入: ["dog","racecar","car"]
輸出: ""
題目分析：
我們要想尋找最長的公共前綴，那么首先這個前綴是公共的，我們可以從任意一個元素中找到他，假定我們現在就從一個陣列中尋找最長公共前綴，那么首先，我們可以將第一個元素設定為基準元素x0，假如陣列為[“flow”,“flower”,“flight”]，flow就是我們的基準元素x0，
然后我們只需要依次將基準元素和后面的元素進行比較（假定后面的元素依次為x1,x2,x3…），不斷更新基準元素，直到基準元素和所有元素都滿足最長公共前綴的條件，就可以得到最長公共前綴，
對比流程：
- 如果strs[i].indexOf(x0,x) == 0，則直接跳過（因為此時x就是x1的最長公共前綴），對比下一個元素，（如flower和flow進行比較）
- 如果strs[i].indexOf(x0,x) != 0, 則截取掉基準元素x的最后一個元素，再次和x1進行比較，直至滿足strs[i].indexOf(x0,x) == 0，此時截取后的x為x和x1的最長公共前綴，（如flight和flow進行比較，依次截取出flow-flo-fl，直到fl被截取出，此時fl為flight和flow的最長公共前綴）
2.2 圖解分析
2.3 代碼分析
public static String longestCommonPrefix(String[] strs) {
if (strs.length==0 || strs[0].length()==0){
return "";
}
String mondel = strs[0].substring(0, strs[0].length() - 1);
for (int i = 0; i < strs.length; i++) {
if (mondel.length()==0){
return "";
}
if (strs[i].indexOf(mondel)!=0){
while (true){
mondel=mondel.substring(0,mondel.length()-1);
if (mondel.length()==0){
break;
}
if (strs[i].indexOf(mondel)==0){
break;
}
}
}
}
return mondel==null? "":mondel;
}
三、LeetCode 買賣股票的最佳時機（I、II）
面試時出現的頻率非常的高，稍微改一改條件，就讓我們防不勝防，那我們如何攻克這一類的問題那？我們從最賤的一道開始看起，
3.1 121題 買賣股票的最佳時機 I
3.1.1 題目分析
我們先來看一道題目： 第121題：買賣股票的最佳時機 I
需求：給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，
如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設計一個演算法來計算你所能獲取的最大利潤，
注意：你不能在買入股票前賣出股票，
示例1：
輸入: [7,1,5,3,6,4]
輸出: 5
解釋： 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 ，
注意：注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票，
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋： 在這種情況下, 沒有交易完成, 所以最大利潤為 0，
3.2.2 圖解分析
假設我們是第二天買入，在收益在多的那一天賣出
執行流程
第二次執行
第三次執行… 以此類推，當我們整個回圈遍歷完成后maxV就獲取到了整個陣列中的最大收益，
3.1.3 代碼分析
public static int maxProfit(int[] prices) {
int maxProfit = 0, fi = 0, maxV = 0;
for (int i = 1; i < prices.length; i++) {
fi = Math.max(maxProfit + prices[i] - prices[i - 1], 0);
maxV = Math.max(fi, maxV);
maxProfit = fi;
}
return maxV;
}
3.2 122題 買賣股票的最佳時機 II
3.2.1 題目分析
我們先來看一道題目： 第122題：買賣股票的最佳時機 II
需求：給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，
設計一個演算法來計算你所能獲取的最大利潤，你可以盡可能地完成更多的交易（多次買賣一支股票），
注意： 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）
示例1
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 ，
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 ，
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 ，
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出，
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票，
示例三
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0，
3.2.2 圖解分析
假設我們的資料是：[7, 1, 5, 3, 6, 4]
從上圖中，我們可以觀察到 A+B+C的和等于差值 DD 所對應的連續峰和谷的高度之差，
3.2.3 代碼分析
public int maxProfit(int[] prices) {
int maxProfit=0;
for (int i = 1; i < prices.length ; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
四、LeetCode 189 旋轉陣列
4.1 題目分析
我們先來看一道題目： 第189 題：旋轉陣列
需求：給定一個陣列，將陣列中的元素向右移動 k 個位置，其中 k 是非負數
示例 1:
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉 1 步: [7,1,2,3,4,5,6]
向右旋轉 2 步: [6,7,1,2,3,4,5]
向右旋轉 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋:
向右旋轉 1 步: [99,-1,-100,3]
向右旋轉 2 步: [3,99,-1,-100]
注意：
盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題，
要求使用空間復雜度為 O(1) 的 原地 演算法，
4.2 圖解分析
假設我們的陣列為[1,2,3,4,5,6],I=6 且 k=3
通過觀察我們可以得到，我們要得到最終的結果，我們只需要將所有元素反轉，然后反轉前 k 個元素，再反轉后面l-k個元素，就能得到想要的結果，
4.3代碼分析
public static void rotate(int[] nums, int k) {
revers(nums, 0, nums.length);
revers(nums, 0, k % nums.length);
revers(nums, k % nums.length, nums.length);
}
public static void revers(int[] nums, int start, int end) {
int length = end - start;
for (int i = 0; i < length / 2; i++) {
int num = nums[start + i];
nums[start + i] = nums[start + length - i - 1];
nums[start + length - i - 1] = num;
}
System.out.println(Arrays.toString(nums));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/85709.html
標籤：其他