LeetCode基礎(chǔ)算法-數(shù)組
算法 LeetCode 數(shù)組相關(guān)
1. 從排序數(shù)組中刪除重復(fù)項(xiàng)
描述：
給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成磷蜀。
解答思路：
- 雙指針法，index指針指向當(dāng)前已無重復(fù)數(shù)字?jǐn)?shù)組的最后一位百炬；i指針遍歷nums數(shù)組褐隆。
- i與index處值相同時，i指針繼續(xù)向后遍歷剖踊。
- i與index處值相同時庶弃，將i處值復(fù)制給++index處。
- 無重復(fù)數(shù)組的長度為index+1德澈。
代碼：
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// index從索引0開始
int index = 0;
// i從索引1開始遍歷
for (int i = 1; i < nums.length; i++) {
// 不相同則進(jìn)行擴(kuò)展歇攻，index永遠(yuǎn)指向符合條件數(shù)組的最后一個索引
if (nums[i] != nums[index]) {
nums[++index] = nums[i];
}
}
return index + 1;
}
2. 買賣股票的最佳時機(jī)
描述：
給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價(jià)格梆造。
設(shè)計(jì)一個算法來計(jì)算你所能獲取的最大利潤缴守。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）澳窑。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時候買入斧散，在第 3 天（股票價(jià)格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 供常。
隨后摊聋，在第 4 天（股票價(jià)格 = 3）的時候買入，在第 5 天（股票價(jià)格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 栈暇。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時候買入麻裁，在第 5 天 （股票價(jià)格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出煎源。
因?yàn)檫@樣屬于同時參與了多筆交易色迂，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0手销。
解答思路(貪心算法)：
- minPrice指向當(dāng)前的最低價(jià)(假設(shè)為買入)歇僧，sum記錄當(dāng)前盈利的最大值。
- minPrice初始化為數(shù)組第一個值锋拖。
- 當(dāng)前值<minPrice诈悍，此時賣出會賠錢，因此不能賣出兽埃，將當(dāng)前值賦值給minPrice侥钳。
- 當(dāng)前值>minPrice,此時賣出可以賺錢，因此賣出柄错，將當(dāng)前值賦值給minPrice舷夺。
代碼實(shí)現(xiàn):
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0){
return 0;
}
int sum = 0;
int minPrice = prices[0];
for(int i = 1;i<prices.length;i++){
if(prices[i]>minPrice){
// 此時賣出。
sum += prices[i] - minPrice;
minPrice = prices[i];
}else{
// 以當(dāng)前價(jià)格買入
minPrice = prices[i];
}
}
return sum;
}
3. 旋轉(zhuǎn)數(shù)組
描述：
給定一個數(shù)組售貌，將數(shù)組中的元素向右移動 k 個位置给猾，其中 k 是非負(fù)數(shù)。
示例 1:
輸入: [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]
解題思路：
- 如果K為數(shù)組長度的整倍數(shù)趁矾，那么無需做任何操作耙册。
- k = k%length
- 循環(huán)右移數(shù)組，將數(shù)組的最后一個值賦值給數(shù)組第一個值毫捣。
public void rotate(int[] nums, int k) {
if (null == nums || nums.length == 0) {
return;
}
if (k % nums.length == 0) {
return;
}
k = k % nums.length;
int last;
for (int i = 0; i < k; i++) {
last = nums[nums.length - 1];
for (int j = nums.length - 1; j > 0; j--) {
nums[j] = nums[j - 1];
}
nums[0] = last;
}
}
4. 只出現(xiàn)一次的數(shù)字
給定一個非空整數(shù)數(shù)組详拙，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次蔓同。找出那個只出現(xiàn)了一次的元素饶辙。
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎斑粱？
解題思路：
- 使用數(shù)學(xué)上的異或的特點(diǎn)弃揽，兩個相同的數(shù)字異或等于0；
- 11=0,11^2=2
代碼：
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int sigleNum = nums[0];
for (int i = 1; i < nums.length; i++) {
sigleNum ^= nums[i];
}
return sigleNum;
}
5. 兩個數(shù)組的交集
描述：
給定兩個數(shù)組则北，編寫一個函數(shù)來計(jì)算它們的交集矿微。
解題思路：
- 先排序，然后使用三個指針：i,j,z來遍歷保存數(shù)據(jù)尚揣。
// 兩個數(shù)組的交集
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return new int[0];
}
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] result;
if (nums1.length > nums2.length) {
result = new int[nums2.length];
} else {
result = new int[nums1.length];
}
int i = 0, j = 0, z = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
result[z++] = nums1[i];
i++;
j++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
i++;
}
}
int realResult[] = new int[z];
for (int index = 0; index < z; index++) {
realResult[index] = result[index];
}
return realResult;
}
6. 加1
給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)涌矢，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位快骗， 數(shù)組中每個元素只存儲一個數(shù)字娜庇。
你可以假設(shè)除了整數(shù) 0 之外塔次，這個整數(shù)不會以零開頭。
解題思路：
- 從數(shù)組尾部遍歷名秀，職要當(dāng)前位不為9励负，那么當(dāng)前位+1，循環(huán)結(jié)束匕得。
- 如果當(dāng)前位為9继榆，則當(dāng)前位設(shè)置為0，繼續(xù)向前遍歷汁掠。
public int[] plusOne(int[] digits) {
if (digits == null || digits.length == 0) {
return new int[0];
}
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] == 9) {
digits[i] = 0;
} else {
digits[i] += 1;
return digits;
}
}
int[] newDigits = new int[digits.length + 1];
for (int i = 0; i < digits.length; i++) {
newDigits[i] = digits[i];
}
newDigits[0] = 1;
return newDigits;
}
7. 移動零
給定一個數(shù)組 nums裕照，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序调塌。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:
必須在原數(shù)組上操作晋南，不能拷貝額外的數(shù)組。
盡量減少操作次數(shù)羔砾。
解題思路：
- 使用雙指針循環(huán)遍歷负间。
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int index = 0, start = 0;
while (start < nums.length) {
if (nums[start] != 0) {
nums[index++] = nums[start];
}
start++;
}
while (index < nums.length) {
nums[index] = 0;
index++;
}
}
8. 兩數(shù)之和
給定一個整數(shù)數(shù)組和一個目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個數(shù)姜凄。
你可以假設(shè)每個輸入只對應(yīng)一種答案政溃，且同樣的元素不能被重復(fù)利用。
解題思路：
- 使用Map态秧，遍歷放入時檢查map中是否已經(jīng)存在余數(shù)值董虱，存在立即返回；不存在繼續(xù)遍歷申鱼。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
if (map.get(target - nums[i]) != i) {
return new int[]{map.get(target - nums[i]), i};
}
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}
9. 有效的數(shù)獨(dú)
判斷一個 9x9 的數(shù)獨(dú)是否有效愤诱。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可捐友。
數(shù)字 1-9 在每一行只能出現(xiàn)一次淫半。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次匣砖。
解題思路：
使用三個數(shù)組來記錄是否已經(jīng)存在該值的信息科吭。
rowFlag[9][9]:rowFlag[i][c],第i行是否出現(xiàn)了值c。
colFlag[9][9]:rowFlag[c][j],c出現(xiàn)在第j列猴鲫。
cellFalg[9][9]:cell[3(i/3)+j/3],第3(i/3)+j/3個單元中出現(xiàn)了c对人。
public boolean isValidSudoku(char[][] board) {
boolean rowFlag[][] = new boolean[9][9];
boolean colFlag[][] = new boolean[9][9];
boolean cellFlag[][] = new boolean[9][9];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; i++) {
if (board[i][j] >= '1' && board[i][j] <= '9'){
int c = board[i][j] - '1';
if (rowFlag[i][c] || colFlag[j][c] || cellFlag[3 * (i / 3) + j / 3][c]) {
return false;
}
rowFlag[i][c] = true;
colFlag[j][c] = true;
cellFlag[3 * (i / 3) + j / 3][c] = true;
}
}
}
return true;
}
10. 旋轉(zhuǎn)數(shù)組
給定一個 n × n 的二維矩陣表示一個圖像。
將圖像順時針旋轉(zhuǎn) 90 度拂共。
說明：
你必須在原地旋轉(zhuǎn)圖像牺弄，這意味著你需要直接修改輸入的二維矩陣。請不要使用另一個矩陣來旋轉(zhuǎn)圖像匣缘。
給定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋轉(zhuǎn)輸入矩陣猖闪，使其變?yōu)?
[
[7,4,1],
[8,5,2],
[9,6,3]
]
public void rotate(int[][] matrix) {
// 首先沿著對角線旋轉(zhuǎn)
for (int i = 0; i < matrix.length; i++) {
for (int j = i + 1; j < matrix.length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 再沿著數(shù)組垂直中線進(jìn)行旋轉(zhuǎn)
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - 1 - j];
matrix[i][matrix.length - 1 - j] = temp;
}
}
}
11. 三數(shù)之和
給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a肌厨，b培慌，c ，使得 a + b + c = 0 柑爸？找出所有滿足條件且不重復(fù)的三元組吵护。
注意：答案中不可以包含重復(fù)的三元組。
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]表鳍，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
解題思路：
- 首先對數(shù)組進(jìn)行排序馅而，逐個遍歷數(shù)組，以index上的數(shù)據(jù)nums[index]為例分析：
- 如果nums[index]>0,結(jié)束循環(huán)譬圣，因?yàn)榇撕蟮臄?shù)組值必大于0瓮恭。
- 如果nums[index]<=0,定義target = 0-nums[index],兩數(shù)之和等于target的過程。
- 我們使用雙指針來解決兩數(shù)之和為target的求解過程厘熟。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> re = new ArrayList<>();
if (nums == null || nums.length < 3) {
return re;
}
// 1. 首先排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 選取第一個值
if (nums[i] > 0) break;
// 去除重復(fù)
if (i >= 1) if (nums[i] == nums[i - 1]) continue;
int target = 0 - nums[i];
int low = i + 1;
int high = nums.length - 1;
while (low < high) {
if (nums[low] + nums[high] == target) {
List<Integer> list = new ArrayList();
list.add(nums[i]);
list.add(nums[low]);
list.add(nums[high]);
re.add(list);
// 為了去重復(fù)屯蹦。
while (low + 1 < high && nums[low] == nums[low + 1]) {
low++;
}
// 為了去重復(fù)。
while (high - 1 > low && nums[high] == nums[high - 1]) {
high--;
}
low++;
high--;
} else if (nums[low] + nums[high] < target) {
low++;
} else {
high--;
}
}
}
return re;
}
12. 矩陣置零
給定一個 m x n 的矩陣绳姨，如果一個元素為 0登澜，則將其所在行和列的所有元素都設(shè)為 0。請使用原地算法飘庄。
示例 1:
輸入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
輸出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
輸入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
輸出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
進(jìn)階:
一個直接的解決方案是使用 O(mn) 的額外空間脑蠕，但這并不是一個好的解決方案。
一個簡單的改進(jìn)方案是使用 O(m + n) 的額外空間跪削，但這仍然不是最好的解決方案谴仙。
你能想出一個常數(shù)空間的解決方案嗎？
解題思路：
- 我們直接使用常數(shù)空間來解決問題碾盐。
- 首先我們借助s0行和0列來存儲哪些行和類稍后需要置為0狞甚。
- 其次我們定義兩個遍歷來分別記錄0行0列原來是否出現(xiàn)過0。
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean firstRowIsZero = false;
boolean firstColIsZero = false;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
if (i != 0 && j != 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
} else {
firstColIsZero = j == 0 ? true : firstColIsZero;
firstRowIsZero = i == 0 ? true : firstRowIsZero;
}
}
}
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
//第一列含0
if(firstColIsZero){
for(int i=0;i<matrix.length;i++){
matrix[i][0] = 0;
}
}
//第一行含0
if(firstRowIsZero){
for(int j=0;j<matrix[0].length;j++){
matrix[0][j] = 0;
}
}
}
13. 字謎分組
給定一個字符串?dāng)?shù)組廓旬，將字母異位詞組合在一起哼审。字母異位詞指字母相同，但排列不同的字符串孕豹。
示例:
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"],
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
說明：
所有輸入均為小寫字母涩盾。
不考慮答案輸出的順序。
解題思路：
- 怎樣判斷異位詞呢励背？我們之前做過判斷兩個詞是否為異位詞的題目春霍，如果按照暴力搜索比對的話，肯定是要超時的叶眉。
- 怎樣判斷兩個詞為異位詞呢址儒？我們采用對字符串的字節(jié)數(shù)組進(jìn)行排序的方式來判斷兩個字符串是否為異位詞芹枷。
- 使用Mapl來完成分組存儲異位詞。
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) {
return new ArrayList<List<String>>();
}
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
if (map.containsKey(key) == false) {
map.put(key, new ArrayList<String>());
}
map.get(key).add(strs[i]);
}
return new ArrayList<>(map.values());
}
14. 無重復(fù)字符的最長子串
給定一個字符串莲趣，找出不含有重復(fù)字符的最長子串的長度鸳慈。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 無重復(fù)字符的最長子串是 "abc"，其長度為 3喧伞。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 無重復(fù)字符的最長子串是 "b"走芋，其長度為 1。
解題思路：
- 核心問題是如果出現(xiàn)了重復(fù)潘鲫，我們的start位置從何處計(jì)算翁逞。
- 因?yàn)樽址拈L度不固定，因此我們使用數(shù)組來存儲字符最近一次出現(xiàn)的下一個位置溉仑。
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
// current index of character
int[] index = new int[128];
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
14. 遞增的三元子序列
給定一個未排序的數(shù)組挖函，判斷這個數(shù)組中是否存在長度為 3 的遞增子序列。
數(shù)學(xué)表達(dá)式如下:
如果存在這樣的 i, j, k, 且滿足 0 ≤ i < j < k ≤ n-1浊竟，
使得 arr[i] < arr[j] < arr[k] 挪圾，返回 true ; 否則返回 false 。
說明: 要求算法的時間復(fù)雜度為 O(n)逐沙，空間復(fù)雜度為 O(1) 哲思。
解題思路：
- 使用兩個指針來解決問題，first代表三元子序列的第一個值吩案，second代表三元子序列的第二個值棚赔。
- first<second<第三個值。
- 只要出現(xiàn)比first小的值徘郭，我們就更新first的值靠益。
- 出現(xiàn)比first大比second小的值，我們更新second.
- 出現(xiàn)比second大的值時残揉，三元子序列就找到了胧后。
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length < 3) {
return false;
}
if (nums == null || nums.length < 3) {
return false;
}
int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
for (int num : nums) {
if (first > num) {
first = num;
} else if (first < num && second > num) {
second = num;
} else if (num > second) {
return true;
}
}
return false;
}
