本章節的主要内容是圍繞數組、排序的相關學習。本部分使用了部分排序算法，下篇文章将更新更多排序算法詳解及代碼
字元串部分傳送門：
愛吃咖喱的皮特：Leetcode-探索位元組跳動（官方題庫）-思路與解法分析-字元串（持續更新）zhuanlan.zhihu.com
Question 1: 3-Sum(Leetcode-15)
題目描述
給你一個包含 n 個整數的數組
nums
，判斷
nums
中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重複的三元組。
注意：答案中不可以包含重複的三元組。
示例：給定數組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路
單純的暴力解法包含大量的重複運算（重複的求和計算），我們通過對數組的排序，減少這種重複計算；具體來講：我們首先将數組排序，然後周遊數組的每一個index=i，對于每個值（我們記這個指為a），我們需要找到另外找到數組中的兩個數，使得他們的和等于一個定值（sum-a）。為了尋找這個定值和，我們從數組的其餘部分尋找，我們初始化左指針為index=i+1，右指針為index=length-1；由于數組是排序過的，是以如果nums[i+1]+nums[length-1]<sum-a，我們可以知道，nums[i+1]和index=i+2~length-1區間内的任何數的和都不可能等于sum-a。由此我們可以大大簡化計算。
代碼
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> lists = new ArrayList<>();
int length = nums.length;
if (length<=2){
return lists;
}
Arrays.sort(nums);
for (int i=0;i<length-2;i++){
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i+1;
int right = length-1;
while (left<right){
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0){
lists.add(Arrays.asList(nums[i],nums[left],nums[right]));
left++;
right--;
while (left<right&&nums[right]==nums[right+1]){
right--;
}
while (left<right&&nums[left]==nums[left-1]){
left++;
}
}else if (sum > 0){
right--;
}else {
left++;
}
}
}
return lists;
}
}
Question 2: Maximum Area of Island(Leetcode-695)
題目描述
給定一個包含了一些
和
1
的非空二維數組
grid
。
一個
島嶼是由一些相鄰的
1
(代表土地) 構成的組合，這裡的「相鄰」要求兩個
1
必須在水準或者豎直方向上相鄰。你可以假設
grid
的四個邊緣都被
（代表水）包圍着。
找到給定的二維數組中最大的島嶼面積。(如果沒有島嶼，則傳回面積為
。)
示例 1:[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
對于上面這個給定矩陣應傳回
6
。注意答案不應該是
11
，因為島嶼隻能包含水準或垂直的四個方向的
1
。
示例 2:[[0,0,0,0,0,0,0,0]]
對于上面這個給定的矩陣, 傳回
。
注意:給定的矩陣
grid
的長度和寬度都不超過 50。
思路
用visit數組記錄各個節點是否已經被周遊過。用深度優先周遊并且記錄最大島嶼面積即可
代碼
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[][] visit = new int[rows][cols];
int count = 0;
for (int i=0;i<rows;i++){
for (int j=0;j<cols;j++){
if (visit[i][j]==1){
continue;
}
if (grid[i][j]==1){
visit[i][j] = 1;
count=Math.max(count,calArea(i,j,grid,visit));
}
}
}
return count;
}
private int calArea(int i, int j,int[][] grid,int[][] visit) {
int output = 1;
if (i-1>=0&&grid[i-1][j]==1&&visit[i-1][j]==0){
visit[i-1][j] = 1;
grid[i-1][j] = 0;
output+=calArea(i-1,j,grid,visit);
}
if (i+1<grid.length&&grid[i+1][j]==1&&visit[i+1][j]==0){
visit[i+1][j] = 1;
grid[i+1][j] = 0;
output+=calArea(i+1,j,grid,visit);
}
if (j-1>=0&&grid[i][j-1]==1&&visit[i][j-1]==0){
visit[i][j-1] = 1;
grid[i][j-1] = 0;
output+=calArea(i,j-1,grid,visit);
}
if (j+1<grid[0].length&&grid[i][j+1]==1&&visit[i][j+1]==0){
visit[i][j+1] = 1;
grid[i][j+1] = 0;
output+=calArea(i,j+1,grid,visit);
}
return output;
}
}
Question 3: Search in Rotated Sorted Array(Leetcode-33)
題目描述
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組
[0,1,2,4,5,6,7]
可能變為
[4,5,6,7,0,1,2]
)。
搜尋一個給定的目标值，如果數組中存在這個目标值，則傳回它的索引，否則傳回
-1
。
你可以假設數組中不存在重複的元素。
你的算法時間複雜度必須是 O(log n) 級别。
示例 1:輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1
思路
周遊數組，找到旋轉點。旋轉點兩側為有序數組，用二分查找即可
代碼
class Solution {
public int search(int[] nums, int target) {
int length = nums.length;
int output = -1;
if (length==0){
return -1;
}
int index = 0;
for (int i=0;i<length-1;i++){
if (nums[i]>nums[i+1]){
index=i;
}
}
output = biSearch(0,index,nums,target);
if (output!=-1){
return output;
}else {
output = biSearch(index + 1,length-1,nums,target);
}
return output;
}
private int biSearch(int i, int index,int[] nums,int target) {
int left = i;
int right = index;
while (left<=right){
int mid = (left + right)/2;
if (nums[mid]==target){
return mid;
}else if (nums[mid]>target){
right = mid-1;
}else {
left = mid+1;
}
}
return -1;
}
}
Question 4: Longest Continuous Increasing Subsequence(Leetcode-674)
題目描述
給定一個未經排序的整數數組，找到最長且
連續的的遞增序列。
示例 1:輸入: [1,3,5,4,7]
輸出: 3
解釋: 最長連續遞增序列是 [1,3,5], 長度為3。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續的，因為5和7在原數組裡被4隔開。
輸入: [2,2,2,2,2]
輸出: 1
解釋: 最長連續遞增序列是 [2], 長度為1。
數組長度不會超過10000。
思路
滑動視窗法；在視窗右外側的數字如果比視窗的最右側元素大，則擴充視窗。否則則将視窗移動到此處并且将視窗長度初始化為0；這期間記錄産生的視窗的最大長度
代碼
class Solution {
public int findLengthOfLCIS(int[] nums) {
int output = 1;
int length = nums.length;
if (length==0){
return 0;
}
int left = 0;
int right = 0;
int local = 0;
while (right<length){
System.out.println("right="+right);
if (right==left||nums[right]>nums[right-1]){
local++;
right++;
output=Math.max(local,output);
}else {
left=right;
right=left;
local=0;
}
}
return output;
}
}
Question 5: Kth Largest Element in an Array(Leetcode-215)
題目描述
在未排序的數組中找到第
k個最大的元素。請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。
示例 1:輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
你可以假設 k 總是有效的，且 1 ≤ k ≤ 數組的長度。
思路
堆排序進行K次即可，典型的最大K個數或者第K大數問題。
堆排序的思路為，通過每次建構最大或最小堆，在logn時間内得到最大或最小值。詳見下篇排序專題文章。
代碼
class Solution {
public int findKthLargest(int[] nums, int k) {
int output = 0;
for (int i=0;i<k;i++){
output=makeHeap(nums,nums.length-i-1);
}
return output;
}
private int makeHeap(int[] input, int index) {
for (int i=index;i>=0;i--){
int rootIndex = 0;
if (i%2==0){
rootIndex = (i-2)/2;
}else {
rootIndex = (i-1)/2;
}
if ((rootIndex>=0&&input[rootIndex]<input[i])){
exchange(i,rootIndex,input);
}
}
exchange(0,index,input);
return input[index];
}
private void exchange(int i, int i1, int[] input) {
int mid=input[i];
input[i]=input[i1];
input[i1]=mid;
}
}
Question 6: Longest Consecutive Sequence(Leetcode-128)
題目描述
給定一個未排序的整數數組，找出最長連續序列的長度。
要求算法的時間複雜度為 O(n)。
示例:輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長連續序列是 [1, 2, 3, 4]。它的長度為 4。
思路
HashSet記錄所有出現過的數字，再次周遊并尋找連續序列；注意，由于我們不想被重複的序列幹擾，比如{1，2，3，4}中，我們可能周遊到1和2時都會發現遞增序列，是以我們指定，隻有在周遊到遞增序列某一端（最大的數或者最小的數）時才開始計算序列長度
代碼
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length==0){
return 0;
}
int output = 1;
HashSet<Integer> hashSet = new HashSet<>();
for (int i:nums){
hashSet.add(i);
}
for (int i:nums){
System.out.println("For number:"+i);
if (hashSet.contains(i+1)){
continue;
}else if (hashSet.contains(i-1)){
// System.out.println("Begin to count elements");
//Counting Elements
int local = i;
int count = 1;
while (hashSet.contains(local-1)){
// System.out.println("Count++");
count++;
local--;
}
output = Math.max(count,output);
}
}
return output;
}
}
Question 7: Permutation Sequence(Leetcode-60)
題目描述
給出集合
[1,2,3,…,*n*]
，其所有元素共有 n! 種排列。
按大小順序列出所有排列情況，并一一标記，當 n = 3 時, 所有排列如下：
-
"123"
-
"132"
-
"213"
-
"231"
-
"312"
-
"321"
給定 n 和 k，傳回第 k 個排列。
說明：- 給定 n 的範圍是 [1, 9]。
- 給定 k 的範圍是[1, n!]。
輸入: n = 3, k = 3
輸出: "213"
輸入: n = 4, k = 9
輸出: "2314"
思路
由于最高位的數字的選擇是與(n-1)!數值有關的。是以我們可以遞歸解決“首位數字是幾”的問題，進而得出最終的排列字元串。具體來講，首位數字選幾的問題，例如n=3時，每個首位數字（1或2或者3）可以分别産生2*1=2=2！個排列，是以我們可以通過k的值，推斷出首位數字是多少。
代碼
class Solution {
StringBuilder stringBuilder;
public String getPermutation(int n, int k) {
stringBuilder = new StringBuilder();
LinkedList<Integer> arrayList = new LinkedList<>();
for (int i=1;i<=n;i++){
arrayList.add(i);
}
buildString(arrayList,k);
return stringBuilder.toString();
}
private void buildString(LinkedList<Integer> arrayList, int k) {
if (k==0){
return;
}
if (k>cal(arrayList.size())){
return;
}
if (arrayList.size()==0){
return;
}
int length = arrayList.size();
if (length==2){
if (k==1){
stringBuilder.append(arrayList.get(0));
arrayList.remove(0);
}else if (k==2){
stringBuilder.append(arrayList.get(1));
arrayList.remove(1);
}
buildString(arrayList,1);
return;
}
if (length==1){
stringBuilder.append(arrayList.get(0));
arrayList.remove(0);
return;
}
int index = ((k-1)/cal(length-1));
stringBuilder.append(arrayList.get(index));
arrayList.remove(index);
buildString(arrayList,k-(index)*cal(length-1));
}
private int cal(int i) {
int output = 1;
while (i>0){
output*=i;
i--;
}
return output;
}
}
Question 8: Friend Circles(Leetcode-547)
題目描述
班上有
N名學生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那麼我們可以認為 A 也是 C 的朋友。所謂的朋友圈，是指所有朋友的集合。
給定一個
N * N的矩陣
M，表示班級中學生之間的朋友關系。如果Mi = 1，表示已知第 i 個和 j 個學生
互為朋友關系，否則為不知道。你必須輸出所有學生中的已知的朋友圈總數。
示例 1:輸入:
[[1,1,0],
[1,1,0],
[0,0,1]]
輸出: 2
說明：已知學生0和學生1互為朋友，他們在一個朋友圈。
第2個學生自己在一個朋友圈。是以傳回2。
輸入:
[[1,1,0],
[1,1,1],
[0,1,1]]
輸出: 1
說明：已知學生0和學生1互為朋友，學生1和學生2互為朋友，是以學生0和學生2也是朋友，是以他們三個在一個朋友圈，傳回1。
- N 在[1,200]的範圍内。
- 對于所有學生，有Mi = 1。
- 如果有Mi = 1，則有Mj = 1。
思路
DFS并且記錄朋友圈個數即可
代碼
class Solution {
int count;
public int findCircleNum(int[][] M) {
count = 0;
int n = M.length;
int[] visited = new int[n];
for (int i=0;i<n;i++){
if (visited[i]==1){
continue;
}else {
count++;
visited[i]=1;
dfs(i,M,visited);
}
}
return count;
}
private void dfs(int i, int[][] m, int[] visited) {
for (int j=0;j<m.length;j++){
if (i==j||visited[j]==1||m[i][j]==0){
continue;
}else {
visited[j]=1;
dfs(j,m,visited);
}
}
}
}
Question 9: Merge Intervals(Leetcode-56)
題目描述
給出一個區間的集合，請合并所有重疊的區間。
示例 1:輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區間 [1,3] 和 [2,6] 重疊, 将它們合并為 [1,6].
輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。
思路
先按照區間左端點的值進行排序，我們使用歸并排序。然後按順序進行歸并的判斷和結果記錄即可。
代碼
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length==0){
return new int[0][0];
}
mergeSort(intervals,0,intervals.length-1);
for (int[] inter:intervals){
// System.out.println(Arrays.toString(inter));
// System.out.println("###########");
}
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i=0;i<intervals.length;i++){
arrayList.add(i);
int local = i;
// System.out.println("add:"+i);
while (i<intervals.length-1&&intervals[local][1]>=intervals[i+1][0]){
intervals[local][1] = Math.max(intervals[local][1],intervals[i+1][1]);
i++;
}
}
int[][] output = new int[arrayList.size()][2];
for (int i =0;i<arrayList.size();i++){
output[i][0] = intervals[arrayList.get(i)][0];
output[i][1] = intervals[arrayList.get(i)][1];
}
return output;
}
private void mergeSort(int[][] intervals, int left, int right) {
if (left==right){
return;
}else {
int M = (right+left)/2;
mergeSort(intervals,left,M);
mergeSort(intervals,M+1,right);
mergeAll(intervals,left,M+1,right);
}
}
private void mergeAll(int[][] intervals, int left, int m, int right) {
int[][] leftNums = new int[m-left][2];
int[][] rightNums = new int[right-m+1][2];
for (int i=left;i<m;i++){
leftNums[i-left][0] = intervals[i][0];
leftNums[i-left][1] = intervals[i][1];
}
for (int i=m;i<=right;i++){
rightNums[i-m][0] = intervals[i][0];
rightNums[i-m][1] = intervals[i][1];
}
int i = 0;
int j = 0;
int k = left;
while (i<leftNums.length&&j<rightNums.length){
if (leftNums[i][0]<rightNums[j][0]){
intervals[k][0] = leftNums[i][0];
intervals[k][1] = leftNums[i][1];
i++;
}else {
intervals[k][0] = rightNums[j][0];
intervals[k][1] = rightNums[j][1];
j++;
}
k++;
}
while (i<leftNums.length){
intervals[k][0] = leftNums[i][0];
intervals[k][1] = leftNums[i][1];
i++;
k++;
}
while (j<rightNums.length){
intervals[k][0] = rightNums[j][0];
intervals[k][1] = rightNums[j][1];
k++;
j++;
}
}
}
Question 10: Trapping Rain Water(Leetcode-42)
題目描述
給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。
上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個機關的雨水（藍色部分表示雨水）。
感謝 Marcos貢獻此圖。
示例:輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
思路
根據對接水這個動作的分析，我們發現，儲存水的地方能儲存多少的水與此處的左側右側高度有關；注意，這裡說的“左側右側”高度是指目前index下左側的最高的高度和右側的最高的高度。是以我們計算每個節點對應的左側高度最大值和右側高度最大值，這樣通過計算可以得知每一個節點上方能存儲多少水。
代碼
class Solution {
public int trap(int[] height) {
int count = 0;
int length = height.length;
if (length<=2){
return 0;
}
int[] left = new int[length];
int[] right = new int[length];
left[0] = height[0];
for (int i=1;i<length;i++){
left[i] = Math.max(left[i-1],height[i]);
}
right[length-1] = height[length-1];
for (int i=length-2;i>=0;i--){
right[i] = Math.max(right[i+1],height[i]);
}
for (int i=1;i<length-1;i++){
count+=Math.min(left[i],right[i])-height[i];
}
return count;
}
}