??博客主頁(yè)：?【小扳_-CSDN博客】
?感謝大家點(diǎn)贊??收藏?評(píng)論??
?
?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-752173.html
文章目錄
????????1.0 輪轉(zhuǎn)數(shù)組
????????1.1 使用移位的方式
????????1.2 使用三次數(shù)組逆轉(zhuǎn)法
? ? ? ? 2.0 消失的數(shù)字
????????2.1 使用相減法
????????2.2 使用異或的方式
? ? ? ? 3.0 合并兩個(gè)有序數(shù)組
????????3.1 使用三指針?lè)绞?/strong>
????????3.2 使用合并排序方式
? ? ? ? 4.0 刪除有序數(shù)組中的重復(fù)項(xiàng)
????????4.1 使用雙指針?lè)绞?/strong>
? ? ? ? 5.0 移除元素
????????5.1 使用雙指針?lè)绞?/strong>
? ? ? ? 6.0 楊輝三角
????????6.1 使用二維數(shù)組的方式
?
????????1.0 輪轉(zhuǎn)數(shù)組
題目：
????????給定一個(gè)整數(shù)數(shù)組?
nums，將數(shù)組中的元素向右輪轉(zhuǎn)?k?個(gè)位置，其中?k?是非負(fù)數(shù)。示例 1:
輸入: nums = [1,2,3,4,5,6,7], k = 3 輸出:[5,6,7,1,2,3,4]解釋: 向右輪轉(zhuǎn) 1 步:[7,1,2,3,4,5,6]向右輪轉(zhuǎn) 2 步:[6,7,1,2,3,4,5]向右輪轉(zhuǎn) 3 步:[5,6,7,1,2,3,4]
????????1.1 使用移位的方式
????????先創(chuàng)建一個(gè)新的數(shù)組來(lái)記錄需要進(jìn)行右輪轉(zhuǎn)的元素，然后將數(shù)組前面剩余的元素進(jìn)行遍歷 "移" 到后面，即覆蓋。如例題1：先將 [5,6,7] 這 k 個(gè)元素使用新的數(shù)組來(lái)暫時(shí)存放，接著將 [1,2,3,4] 從后往前遍歷，即將 4 移到原來(lái) 7 的位置，3 移到 原來(lái) 6 的位置，2 移到原來(lái) 5 的位置......即? nums[nums.length - i ]? = nums[ nums.length - k - i ]? ，i? 從 1?開(kāi)始直到 i == nums.length - k 時(shí)，則結(jié)束循環(huán)。最后，將需要輪轉(zhuǎn)的元素進(jìn)行數(shù)組 temp[] 下標(biāo)一個(gè)個(gè)對(duì)應(yīng)賦值到 nums[] 數(shù)組中即可。
代碼如下：
public static void rotate(int[] nums,int k) { if(nums.length == 1 || nums.length == 0) { return; } k %= nums.length; int[] temp = new int[k]; System.arraycopy(nums,nums.length - k, temp, 0,k); System.arraycopy(nums,0,nums,k,nums.length - k); for(int i = 0;i < temp.length ; i++) { nums[i] = temp[i]; } }? ? ? ?這里使用了相關(guān)的 API ，總體上來(lái)說(shuō)思路是一樣的。一般來(lái)說(shuō)，這種算法時(shí)間復(fù)雜度會(huì)較高。????????
????????1.2 使用三次數(shù)組逆轉(zhuǎn)法
????????使用三次逆轉(zhuǎn)法，讓數(shù)組旋轉(zhuǎn)k次 ????
????????????????????????1.?整體逆置
????????????????????????2.?逆轉(zhuǎn)子數(shù)組[0,?k?-?1]
????????????????????????3.?逆轉(zhuǎn)子數(shù)組[k,?size?-?1]
代碼如下：
public static void fun(int[] arr, int k) { k %= arr.length; rotate(arr,0,arr.length - 1); rotate(arr,0,k-1); rotate(arr,k, arr.length-1); } public static void rotate(int[] arr,int left, int right) { while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } }流程圖如下：
????????
? ? ? ? 2.0 消失的數(shù)字
題目：
????????數(shù)組?
nums?包含從?0?到?n?的所有整數(shù)，但其中缺了一個(gè)。請(qǐng)編寫(xiě)代碼找出那個(gè)缺失的整數(shù)。你有辦法在 O(n) 時(shí)間內(nèi)完成嗎？示例 1：
輸入：[3,0,1] 輸出：2示例 2：
輸入：[9,6,4,2,3,5,7,0,1] 輸出：8
? ? ? ?2.1 使用相減法
????????定義 int sum ，然后遍歷 0 到 n 的所有整數(shù)都加起來(lái)，接著再跟將 nums 的所以數(shù)字加起來(lái)進(jìn)行比較，兩者相減即可得出 nums 數(shù)組中 "消失的數(shù)字" 。如例題：numsSum = 3 + 0 + 1 , nSum = 0 +?1 + 2 + 3，再接著 nSum - numsSum == 2 ，兩者相減即可得到消失的數(shù)字為:?2 。
代碼如下：
public static int disappearing1(int[] arr) { int sum1 = 0; int sum2 = 0; for (int i = 0; i < arr.length; i++) { sum1 += i; sum2 += arr[i]; } return (sum1 += arr.length) - sum2; }????????缺陷：如果數(shù)組中元素比較多，相加完成之后容易溢出。
? ? ? ?2.2 使用異或的方式
????????采用異或的方式解決，因?yàn)閮蓚€(gè)相同的數(shù)字異或的結(jié)果是 0，因此：將 0~N 之間的數(shù)字，與數(shù)組中的每個(gè)數(shù)字異或，最終的結(jié)果就是丟失的數(shù)字。
代碼如下：
public static int disappearing(int[] arr) { int data = 0; for (int i = 0; i < arr.length; i++) { data ^= arr[i]; data ^= i; } data ^= arr.length; return data; }? ? ? ? 分析：可以將將其理解為 “消消樂(lè)” ，即若兩個(gè)數(shù)相同就抵消為 0 ，那么現(xiàn)在目前有兩個(gè)袋子，一個(gè)袋子裝滿了 0?到 n 張卡片，其中每一種只有一片，也就是說(shuō)，該袋子里面就有 n + 1 張卡片，在另一個(gè)袋子里面裝有 0 到 n 張中缺少了一張卡片，即該袋子中有 n 張卡片，接著進(jìn)行每一次將分別從兩個(gè)袋子拿出不同的卡片進(jìn)行對(duì)比，如果相同的話則抵消掉了，不相同的話，得保存起來(lái)。就這樣一直對(duì)比下去，最終會(huì)發(fā)現(xiàn)留下來(lái)的就是另一個(gè)袋子所缺少的卡片了。
? ? ? ? 3.0 合并兩個(gè)有序數(shù)組
????????給你兩個(gè)按?非遞減順序?排列的整數(shù)數(shù)組?
nums1?和?nums2，另有兩個(gè)整數(shù)?m?和?n?，分別表示?nums1?和?nums2?中的元素?cái)?shù)目。請(qǐng)你?合并?
nums2?到?nums1?中，使合并后的數(shù)組同樣按?非遞減順序?排列。示例 1：
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 輸出：[1,2,2,3,5,6] 解釋：需要合并 [1,2,3] 和 [2,5,6] 。 合并結(jié)果是 [1,2,2,3,5,6] ，其中斜體加粗標(biāo)注的為 nums1 中的元素。
? ? ? ? 3.1 使用三指針?lè)绞?/h3>
????????定義三個(gè)指針?lè)謩e為：i 指向 nums1 中的最后一個(gè)有效元素，j 指向 nums2 中最后一個(gè)有效元素，k 指向 nums1 中最后一個(gè)索引位置。接著 nums[i] 與 nums[j] 進(jìn)行比較大小，得出較大的元素就放到 nums[k] 中，以此類推，直到 i < 0 或者 j < 0 時(shí)，則循環(huán)停止。最后來(lái)判斷，若 i?>?0 ，本來(lái)剩余的元素就在 nums1 中，則不用再繼續(xù)下去了，任務(wù)結(jié)束了；若 j > 0 ，需要將 nums2 中的元素進(jìn)行遍歷拷貝到 nums1 中。
代碼如下：
public void merge(int[] nums1, int m, int[] nums2, int n) { int k = nums1.length - 1; int i = m - 1; int j = n - 1; while(i >= 0 && j >= 0) { if(nums1[i] > nums2[j]) { nums1[k] = nums1[i]; k--; i--; }else if(nums1[i] <= nums2[j]) { nums1[k] = nums2[j]; k--; j--; } } if(j >= 0) { System.arraycopy(nums2,0,nums1,0,j+1); } }
? ? ? ? 3.2 使用合并排序方式
? ? ? ? 這個(gè)思路很簡(jiǎn)單，可以直接將 nums2 中的元素拷貝到 nums1 中，然后直接排序即可。這里就不過(guò)多贅述了。
? ? ? ? 4.0 刪除有序數(shù)組中的重復(fù)項(xiàng)
題目：
????????給你一個(gè)?非嚴(yán)格遞增排列?的數(shù)組?
nums?，請(qǐng)你?原地?刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素?只出現(xiàn)一次?，返回刪除后數(shù)組的新長(zhǎng)度。元素的?相對(duì)順序?應(yīng)該保持?一致?。然后返回?nums?中唯一元素的個(gè)數(shù)。示例 1：
輸入：nums = [1,1,2] 輸出：2, nums = [1,2,_] 解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 2，并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2。不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4] 輸出：5, nums = [0,1,2,3,4] 解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 5， 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4。不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
? ? ? ? 4.1 使用雙指針?lè)绞?/h3>
? ? ? ? 先定義兩個(gè)指針?lè)謩e指向，一個(gè)指針： i = 0 ，一開(kāi)始時(shí)指向數(shù)組中第一個(gè)元素；另一個(gè)指針：j = 1。分兩種情況來(lái)解決，第一種情況是，當(dāng) nums[i] == nums[j] 時(shí)，繼續(xù)讓 j 走下去，直到 j == nums.length 時(shí)，則結(jié)束循環(huán)；第二種情況是，當(dāng) nums[i] != nums[j] 時(shí)，讓 nums[i + 1] = nums[j] ，i++，j++ ，同樣直到 j == nums.length 時(shí)，則結(jié)束循環(huán)。最后返回 i+1 即可。
代碼如下：
public int removeDuplicates(int[] nums) { int i = 0; int j = i + 1; while (j < nums.length) { if (nums[i] == nums[j]) { j++; } else if (nums[i] != nums[j]) { nums[i+1] = nums[j]; i++; j++; } } return i + 1; }
? ? ? ? 5.0 移除元素
題目：
????????給你一個(gè)數(shù)組?
nums?和一個(gè)值?val，你需要?原地?移除所有數(shù)值等于?val?的元素，并返回移除后數(shù)組的新長(zhǎng)度。????????不要使用額外的數(shù)組空間，你必須僅使用?
O(1)?額外空間并?原地?修改輸入數(shù)組。元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
示例 1：
輸入：nums = [3,2,2,3], val = 3 輸出：2, nums = [2,2] 解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。例如，函數(shù)返回的新長(zhǎng)度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會(huì)被視作正確答案。示例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2 輸出：5, nums = [0,1,3,0,4] 解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4。注意這五個(gè)元素可為任意順序。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
? ? ? ? 5.1 使用雙指針?lè)绞?/h3>
? ? ? ? 先定義兩個(gè)指針，對(duì)于 left 這個(gè)指針來(lái)說(shuō)，一開(kāi)始指向數(shù)組下標(biāo)為 0 ；對(duì)于 right 這個(gè)指針來(lái)說(shuō)，一開(kāi)始指向數(shù)組下標(biāo)也為 0 處，然后 rigth 一直 right++ 自加，在這個(gè)過(guò)程中，需要先判斷，若 nums[right]? != val 時(shí)，則需要將這個(gè)值拷貝到 nums[left] 中?，left++ ，right++ ;若 nums[right] == val 時(shí)，right++ 即可，直到 right == nums.length 時(shí)，則結(jié)束循環(huán)。
代碼如下：
public int removeElement(int[] nums, int val) { int n = nums.length; int left = 0; for (int i = 0; i < n; i++) { if (nums[i] != val) { nums[left] = nums[i]; left++; } } return left; }? ? ? ?
? ? ? ? 6.0 楊輝三角
題目：
????????給定一個(gè)非負(fù)整數(shù)?
numRows，生成「楊輝三角」的前?numRows?行。在「楊輝三角」中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。
????????
示例 1:
輸入: numRows = 5 輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例?2:
輸入: numRows = 1 輸出: [[1]]
? ? ? ? 6.1 使用二維數(shù)組的方式
? ? ? ? 可以把這個(gè)問(wèn)題看成是一個(gè)二維數(shù)組，外層循環(huán)為 k?行數(shù)(層數(shù))，內(nèi)層為 l?列數(shù)。當(dāng) l == 0 或者 k == l 時(shí)，該二維數(shù)組中存放的是 1 ；其他情況則為當(dāng)前的數(shù)值為：上一層行數(shù)同一列的 data1 + 上一層行數(shù)少一列的 data2 。
?代碼如下：
public List<List<Integer>> generate(int numRows) { List<List<Integer>> i = new ArrayList<>(); for (int k = 0; k < numRows; k++) { List<Integer> j = new ArrayList<>(); for (int l = 0; l <= k ; l++) { if ( l == 0 || k == l) { j.add(1); } else { j.add(i.get(k-1).get(l) + i.get(k-1).get(l-1)); } } i.add(j); } return i; }? ? ? ? 需要注意的是，實(shí)現(xiàn)集合來(lái)實(shí)現(xiàn)，而不是數(shù)組。
需要了解相關(guān)集合的內(nèi)容可以點(diǎn)擊該鏈接：進(jìn)階JAVA篇-深入了解 List 系列集合-CSDN博客
?
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-752173.html
到了這里，關(guān)于Java LeetCode篇-深入了解關(guān)于數(shù)組的經(jīng)典解法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
