前言
上周去朋友去某公司面試沾乘，結(jié)果在被面試官問到算法時怜奖，直接給整不會了，于是我特意整理出來一套大廠高頻面試算法題翅阵，于是朋友拿著我這套題庫刷了一星期的力扣算法題終于如愿拿到offer歪玲，事后朋友說好像算法也沒那么難，主要是多理解就好掷匠，看到能幫助到朋友我也很高興滥崩，現(xiàn)在分享給大家，廢話不多說讹语，下面給大家看看力扣算法題及答案钙皮，需要的同學可以在文末領(lǐng)取
一、反轉(zhuǎn)鏈表
反轉(zhuǎn)一個單鏈表顽决。
輸入: 1->2->3->4->5
輸出: 5->4->3->2->1
解法1：迭代短条，重復某一過程，每一次處理結(jié)果作為下一次處理的初始值才菠，這些初始值類似于狀態(tài)茸时、每 次處理都會改變狀態(tài)、直至到達最終狀態(tài)
從前往后遍歷鏈表赋访，將當前節(jié)點的next指向上一個節(jié)點可都，因此需要一個變量存儲上一個節(jié)點prev，當前節(jié)點處理完需要尋找下一個節(jié)點蚓耽，因此需要一個變量保存當前節(jié)點curr渠牲，處理完后要將當前節(jié)點賦值給
prev，并將next指針賦值給curr田晚，因此需要一個變量提前保存下一個節(jié)點的指針next
1嘱兼、將下一個節(jié)點指針保存到next變量 next = curr.next
2国葬、將下一個節(jié)點的指針指向prev贤徒，curr.next = prev
3、準備處理下一個節(jié)點汇四，將curr賦值給prev
4接奈、將下一個節(jié)點賦值為curr，處理一個節(jié)點
解法2：遞歸：略
二通孽、統(tǒng)計N以內(nèi)的素數(shù)
素數(shù)：只能被1和自身整除的數(shù)序宦，0、1除外
解法一：暴力算法
直接從2開始遍歷背苦，判斷是否能被2到自身之間的數(shù)整除
public int countPrimes(int n)
{ int ans = 0;
for (int i = 2; i < n; ++i)
{ ans += isPrime(i) ? 1 :
0;
}
return ans;
}
//i如果能被x整除互捌，則x/i肯定能被x整除潘明，因此只需判斷i和根號x之中較小的即可
public boolean isPrime(int x) {
for (int i = 2; i * i <= x; ++i)
{ if (x % i == 0) {
return false;
}
}
return true;
}
解法2：埃氏篩
略
三、尋找數(shù)組的中心索引
數(shù)組中某一個下標秕噪，左右兩邊的元素之后相等钳降，該下標即為中心索引思路：先統(tǒng)計出整個數(shù)組的總和，然后從第一個元素開始疊加
總和遞減當前元素腌巾，疊加遞增當前元素遂填，知道兩個值相等
public static int pivotIndex(int[] nums)
{ int sum1 =
Arrays.stream(nums).sum(); int sum2 =
0;
for(int i = 0; i<nums.length;
? i++){ sum2 += nums[i];
if(sum1 ==
sum2){ return
i;
}
sum1 = sum1 - nums[i];
}
return -1;
}
四、刪除排序數(shù)組中的重復項
一個有序數(shù)組 nums 澈蝙，原地刪除重復出現(xiàn)的元素吓坚，使每個元素只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度灯荧。
不要使用額外的數(shù)組空間礁击，必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
雙指針算法：
數(shù)組完成排序后逗载，我們可以放置兩個指針 i 和 j客税，其中 i 是慢指針，而 j 是快指針撕贞。只要
nums[i]=nums[j]更耻，我們就增加 j 以跳過重復項。
當遇到 nums[j] 捏膨！= nums[i]時秧均，跳過重復項的運行已經(jīng)結(jié)束，必須把nums[j]）的值復制到 nums[i +
1]号涯。然后遞增 i目胡，接著將再次重復相同的過程，直到 j 到達數(shù)組的末尾為止链快。
public int removeDuplicates(int[] nums)
{ if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++)
{ if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
五誉己、x的平方根
在不使用 sqrt(x) 函數(shù)的情況下，得到 x的平方根的整數(shù)部分解法一：二分查找
x的平方根肯定在0到x之間域蜗，使用二分查找定位該數(shù)字巨双，該數(shù)字的平方一定是最接近x的，m平方值如果大于x霉祸、則往左邊找筑累，如果小于等于x則往右邊找
找到0和X的最中間的數(shù)m，
如果m * m > x丝蹭，則m取x/2到x的中間數(shù)字慢宗，直到m * m < x，m則為平方根的整數(shù)部分
如果m * m <= x，則取0到x/2的中間值镜沽，知道兩邊的界限重合敏晤，找到最大的整數(shù)，則為x平方根的整數(shù)部分
時間復雜度：O(logN)
public static int binarySearch(int x)
{ int l = 0, r = x, index = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
index = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return index;
}
解法二：牛頓迭代
略
六缅茉、 三個數(shù)的最大乘積
一個整型數(shù)組乘積不會越界茵典，在數(shù)組中找出由三個數(shù)字組成的最大乘積，并輸出這個乘積宾舅。
如果數(shù)組中全是非負數(shù)统阿，則排序后最大的三個數(shù)相乘即為最大乘積；如果全是非正數(shù)筹我，則最大的三個數(shù) 相乘同樣也為最大乘積扶平。
如果數(shù)組中有正數(shù)有負數(shù)，則最大乘積既可能是三個最大正數(shù)的乘積蔬蕊，也可能是兩個最小負數(shù)（即絕對 值最大）與最大正數(shù)的乘積结澄。
分別求出三個最大正數(shù)的乘積，以及兩個最小負數(shù)與最大正數(shù)的乘積岸夯，二者之間的最大值即為所求答案麻献。
解法一：排序
public static int sort(int[] nums)
{ Arrays.sort(nums);
int n = nums.length;
return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
}
解法二：線性掃描
public static int getMaxMin(int[] nums) {
// 最小的和第二小的
int min1 = 0, min2 = 0;
// 最大的、第二大的和第三大的
int max1 = 0, max2 = 0, max3 = 0;
for (int x : nums)
{ if (x < min1) {
min2 = min1;
? min1 = x;
} else if (x < min2)
{ min2 = x;
}
if (x > max1)
{ max3 =?
max2; max2 =
max1; max1 =?
? x;
} else if (x > max2)
{ max3 = max2;
max2 = x;
} else if (x > max3)
? { max3 = x;
? ? }
? }
}
七猜扮、兩數(shù)之和
給定一個升序排列的整數(shù)數(shù)組 numbers 勉吻，從數(shù)組中找出兩個數(shù)滿足相加之和等于目標數(shù) target 。假設(shè)每個輸入只對應(yīng)唯一的答案旅赢，而且不可以重復使用相同的元素齿桃。
返回兩數(shù)的下標值，以數(shù)組形式返回
暴力解法
public int[] twoSum(int[] nums, int target)
{ int n = nums.length;
for (int i = 0; i < n; ++i) {
? for (int j = i + 1; j < n; ++j) {
? ? ? if (nums[i] + nums[j] == target)
? ? ? ? { return new int[]{i, j};
? ? ? }
? ? }
? }
? ? return new int[0];
}
時間復雜度：O(N的平方) 空間復雜度：O(1)
哈希表：將數(shù)組的值作為key存入map煮盼，target - num作為key
? public int[] twoSum(int[] nums, int target) {
? ? Map<Integer, Integer> map = new HashMap<Integer, Integer>();
? ? for (int i = 0; i < nums.length; ++i) {
? ? ? if (map.containsKey(target - nums[i])) {
? ? ? ? ? return new int[]{map.get(target - nums[i]), i};
? ? ? }
? ? ? map.put(nums[i], i);
? ? ? }
? ? ? return new int[0];
}
時間復雜度：O(N)
空間復雜度：O(N)
解法一：二分查找
先固定一個值(從下標0開始)短纵，再用二分查找查另外一個值，找不到則固定值向右移動僵控，繼續(xù)二分查找
? public int[] twoSearch(int[] numbers, int target)
? ? { for (int i = 0; i < numbers.length; ++i) {
? ? ? ? int low = i, high = numbers.length -1;
? ? ? ? ? while (low <= high) {
? ? ? ? ? int mid = (high - low) / 2 + low;
? ? ? ? ? ? if (numbers[mid] == target - numbers[i])
? ? ? ? ? ? ? { return new int[]{i, mid};
? ? ? ? ? } else if (numbers[mid] > target - numbers[i])
? ? ? ? ? { high = mid - 1;
? ? ? ? ? } else {
? ? ? ? low = mid + 1;
? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? }
? ? ? }
時間復雜度：O(N * logN)
空間復雜度：O(1)
解法二：雙指針
左指針指向數(shù)組head香到，右指針指向數(shù)組tail，head+tail > target 則tail 左移报破，否則head右移
? public int[] twoPoint(int[] numbers, int target)
? ? { int low = 0, high = numbers.length - 1;
? ? ? while (low < high) {
? ? ? ? int sum = numbers[low] + numbers[high];
? ? ? if (sum == target) {
? ? ? ? return new int[]{low + 1, high + 1};
? ? ? ? ? } else if (sum < target) {
? ? ? ? ? ++low;
? ? ? ? ? } else {
? ? ? ? ? ? ? ? --high;
? ? ? ? ? }
? ? ? ? }
? ? ? ? return new int[]{-1, -1};
? }
時間復雜度：O(N) 空間復雜度：O(1)
八悠就、斐波那契數(shù)列
求取斐波那契數(shù)列第N位的值。
斐波那契數(shù)列：每一位的值等于他前兩位數(shù)字之和泛烙。前兩位固定 0理卑，1,1,2,3,5,8翘紊。蔽氨。。。解法一：暴力遞歸
public static int calculate(int
? num){ if(num == 0 ){
? return 0;
? }
? if(num == 1){
? ? return 1;
? ? }
? ? return calculate(num-1) + calculate(num-2);
}
解法二：去重遞歸
遞歸得出具體數(shù)值之后鹉究、存儲到一個集合(下標與數(shù)列下標一致)宇立，后面遞歸之前先到該集合查詢一次， 如果查到則無需遞歸自赔、直接取值妈嘹。查不到再進行遞歸計算
public static int calculate2(int
num){ int[] arr = new int[num+1];
return recurse(arr,num);
}
private static int recurse(int[] arr, int num)
{ if(num == 0 ){
return 0;
}
if(num == 1){
return 1;
}
if(arr[num] !=
0){ return
arr[num];
}
arr[num] = recurse(arr,num-1) + recurse(arr,num-2);
return arr[num];
}
解法三：雙指針迭代
略
九、 環(huán)形鏈表
給定一個鏈表绍妨，判斷鏈表中是否有環(huán)润脸。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達該節(jié)點他去，則鏈表中存在環(huán)如果鏈表中存在環(huán)毙驯，則返回 true 。 否則灾测，返回 false 爆价。
解法一：哈希表
public static boolean hasCycle(ListNode head)
{ Set<ListNode> seen = new
HashSet<ListNode>(); while (head != null) {
if (!seen.add(head))
{ return true;
}
head = head.next;
}
return false;
}
解法二：雙指針
? public static boolean hasCycle2(ListNode head) {
? ? if (head == null || head.next == null)
? ? ? { return false;
? }
? ? ? ListNode slow = head;
? ? ? ListNode fast = head.next;
? ? ? while (slow != fast) {
? ? ? ? if (fast == null || fast.next == null)
? ? ? ? ? { return false;
? ? ? ? }
? ? ? ? slow = slow.next;
? ? ? ? fast = fast.next.next;
? ? }
? ? return true;
? }
十、排列硬幣
總共有 n 枚硬幣媳搪，將它們擺成一個階梯形狀铭段，第 k 行就必須正好有 k 枚硬幣。給定一個數(shù)字 n秦爆，找出可形成完整階梯行的總行數(shù)序愚。
n 是一個非負整數(shù)，并且在32位有符號整型的范圍內(nèi)
解法一：迭代
從第一行開始排列等限，排完一列展运、計算剩余硬幣數(shù)，排第二列精刷，直至剩余硬幣數(shù)小于或等于行數(shù)
public static int arrangeCoins(int n)
? ? { for(int i=1; i<=n; i++){
? ? ? n = n-i;
? ? ? if (n <= i){
? ? ? return i;
? ? ? }
? ? }
? return 0;
? }
解法二：二分查找
略
十一拗胜、合并兩個有序數(shù)組
兩個有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中怒允，使 nums1 成為一個有序數(shù)組埂软。
初始化 nums1 和 nums2 的元素數(shù)量分別為 m 和 n 。假設(shè) nums1 的空間大小等于 m + n纫事，這樣它就有足夠的空間保存來自 nums2 的元素勘畔。
解法一：合并后排序
public void merge(int[] nums1, int m, int[] nums2, int n)
? { System.arraycopy(nums2, 0, nums1, m, n);
? Arrays.sort(nums1);
? }
時間復雜度 : O((n+m)log(n+m))±龌蹋空間復雜度 : O(1)炫七。
解法二：雙指針 從前往后
略
十二、子數(shù)組最大平均數(shù)
給一個整數(shù)數(shù)組钾唬，找出平均數(shù)最大且長度為滑動窗口：
窗口移動時万哪，窗口內(nèi)的和等于sum加上新加進來的值侠驯，減去出去的值
? public double findMaxAverage(int[] nums, int k)
? ? ? { int sum = 0;
? ? ? int n = nums.length;
? ? ? for (int i = 0; i < k; i++)
? ? ? ? ? { sum += nums[i];
? ? ? }
? ? int maxSum = sum;
? ? for (int i = k; i < n; i++) {
? ? ? sum = sum - nums[i - k] + nums[i];
? ? ? maxSum = Math.max(maxSum, sum);
? ? }
? return 1.0 * maxSum / k;
}
十三、二叉樹的最小深度
給定一個二叉樹奕巍，找出其最小深度吟策。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。解法一：深度優(yōu)先
遍歷整顆數(shù)的止，找到每一個葉子節(jié)點檩坚，從葉子節(jié)點往上開始計算，左右子節(jié)點都為空則記錄深度為1
左右子節(jié)點只有一邊诅福，深度記錄為子節(jié)點深度+1
左右兩邊都有子節(jié)點匾委，則記錄左右子節(jié)點的深度較小值+1
? public int minDepth(TreeNode root)
? ? ? { if (root == null) {
? ? ? ? return 0;
? ? }
? ? ? if (root.left == null && root.right == null)
{ return 1;
? }
? ? ? ? int min_depth = Integer.MAX_VALUE;
? ? ? ? if (root.left != null) {
? ? min_depth = Math.min(minDepth(root.left), min_depth);
? ? }
? ? if (root.right != null) {
? min_depth = Math.min(minDepth(root.right), min_depth);
}
return min_depth + 1;
}
時間復雜度：O(N)
空間復雜度：O(logN) 取決于樹的高度
解法二：廣度優(yōu)先
略
十四、最長連續(xù)遞增序列
給定一個未經(jīng)排序的整數(shù)數(shù)組氓润，找到最長且連續(xù)遞增的子序列剩檀，并返回該序列的長度。 序列的下標是連續(xù)的
貪心算法
從0開始尋找遞增序列旺芽，并將長度記錄沪猴，記錄遞增序列的最后一個下標，然后從該下標繼續(xù)尋找采章，記錄 長度运嗜，取長度最大的即可
public static int findLength(int[] nums)
{ int ans = 0;
int start = 0;
for (int i = 0; i < nums.length; i++)
? { if (i > 0 && nums[i] <= nums[i -
? ? 1]) {
start = i;
}
? ans = Math.max(ans, i - start + 1);
? }
? return ans;
}
十五、檸檬水找零
在檸檬水攤上悯舟，每一杯檸檬水的售價為 5 美元担租。顧客排隊購買你的產(chǎn)品，一次購買一杯抵怎。
每位顧客只買一杯檸檬水奋救，然后向你付 5 美元、10 美元或 20 美元反惕。必須給每個顧客正確找零注意尝艘，一開始你手頭沒有任何零錢。
如果你能給每位顧客正確找零姿染，返回 true 背亥，否則返回 false 。
輸入：[5,5,5,10,20]
輸出：true
輸入：[10,10]
輸出：false
貪心：
public boolean lemonadeChange(int[] bills)
{ int five = 0, ten = 0;
for (int bill : bills)
{ if (bill == 5) {
? five++;
? } else if (bill == 10)
? { if (five == 0) {
? return false;
}
? five--;
? ten++;
} else {
? ? if (five > 0 && ten > 0)
{ five--;
? ? ten--;
} else if (five >= 3)
? { five -= 3;
} else {
? ? ? return false;
? }
? }
}
return true;
}
十六悬赏、三角形的最大周長
給定由一些正數(shù)（代表長度）組成的數(shù)組 A 狡汉，返回由其中三個長度組成的、面積不為零的三角形的最大周長闽颇。
如果不能形成任何面積不為零的三角形盾戴，返回 0 。貪心：
先小到大排序兵多，假設(shè)最長邊是最后下標尖啡，另外兩條邊是倒數(shù)第二和第三下標橄仆，則此時三角形周長最大
n < (n-1) + (n-2)，如果不成立可婶，意味著該數(shù)組中不可能有另外兩個值之和大于n沿癞，此時將n左移援雇，重新計算
public int largestPerimeter(int[] A)
{ Arrays.sort(A);
? for (int i = A.length - 1; i >= 2; --i)
? { if (A[i - 2] + A[i - 1] > A[i]) {
? return A[i - 2] + A[i - 1] + A[i];
}
}
return 0;
}
十七矛渴、省份數(shù)量
有 n 個城市，其中一些彼此相連惫搏，另一些沒有相連具温。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c
直接相連筐赔，那么城市 a 與城市 c 間接相連铣猩。
省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市茴丰。
給你一個 n x n 的矩陣 isConnected 达皿，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連贿肩。
返回矩陣中 省份 的數(shù)量峦椰。親戚問題、朋友圈問題
解法一：深度優(yōu)先
獲取一個城市汰规，通過遞歸找到離該城市最遠的城市汤功，標記為已訪問，然后逐個向內(nèi)進行標記
public int findCircleNum(int[][] isConnected)
{ int provinces = isConnected.length;
boolean[] visited = new boolean[provinces];
int circles = 0;
for (int i = 0; i < provinces; i++)
{ if (!visited[i]) {
? dfs(isConnected, visited, provinces, i);
circles++;
}
}
return circles;
}
? public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i)
? { for (int j = 0; j < provinces; j++) {
if (isConnected[i][j] == 1 && !visited[j])
{ visited[j] = true;
dfs(isConnected, visited, provinces, j);
}
}
}
解法二：廣度優(yōu)先
略
十八溜哮、香檳塔
我們把玻璃杯擺成金字塔的形狀滔金，其中第一層有1個玻璃杯，第二層有2個茂嗓，依次類推到第100層餐茵，每個玻璃杯(250ml)將盛有香檳。
從頂層的第一個玻璃杯開始傾倒一些香檳述吸，當頂層的杯子滿了钟病，任何溢出的香檳都會立刻等流量的流向 左右兩側(cè)的玻璃杯。當左右兩邊的杯子也滿了刚梭，就會等流量的流向它們左右兩邊的杯子肠阱，依次類推。
（當最底層的玻璃杯滿了朴读，香檳會流到地板上）
例如屹徘，在傾倒一杯香檳后，最頂層的玻璃杯滿了衅金。傾倒了兩杯香檳后噪伊，第二層的兩個玻璃杯各自盛放一 半的香檳簿煌。在倒三杯香檳后，第二層的香檳滿了 - 此時總共有三個滿的玻璃杯鉴吹。在倒第四杯后姨伟，第三層中間的玻璃杯盛放了一半的香檳，他兩邊的玻璃杯各自盛放了四分之一的香檳
現(xiàn)在當傾倒了非負整數(shù)杯香檳后豆励，返回第 i 行 j 個玻璃杯所盛放的香檳占玻璃杯容積的比例（i 和 j都從0開始）夺荒。
public double champagneTower(int poured, int query_row, int query_glass)
{ double[][] A = new double[102][102];
? ? A[0][0] = (double) poured;
? for (int r = 0; r <= query_row; ++r)
? { for (int c = 0; c <= r; ++c) {
? double q = (A[r][c] - 1.0) / 2.0;
? if (q > 0) {
? ? A[r+1][c] += q;
? A[r+1][c+1] += q;
? ? }
? }
? }
return Math.min(1, A[query_row][query_glass]);
}
十九、Dota2參議院
Dota2 的世界里有兩個陣營：Radiant(天輝)和 Dire(夜魘)
Dota2 參議院由來自兩派的參議員組成×颊簦現(xiàn)在參議院希望對一個 Dota2 游戲里的改變作出決定技扼。他們以一個基于輪為過程的投票進行。在每一輪中嫩痰，每一位參議員都可以行使兩項權(quán)利中的一項：
禁止一名參議員的權(quán)利：參議員可以讓另一位參議員在這一輪和隨后的幾輪中喪失所有的權(quán)利剿吻。
宣布勝利： 如果參議員發(fā)現(xiàn)有權(quán)利投票的參議員都是同一個陣營的，他可以宣布勝利并決定在游戲中的有關(guān)變化串纺。
給定一個字符串代表每個參議員的陣營旷祸。字母 “R” 和 “D” 分別代表了 Radiant（天輝）和 Dire（夜魘）涧黄。然后奔坟，如果有 n 個參議員姻乓，給定字符串的大小將是 n。
以輪為基礎(chǔ)的過程從給定順序的第一個參議員開始到最后一個參議員結(jié)束五辽。這一過程將持續(xù)到投票結(jié) 束办斑。所有失去權(quán)利的參議員將在過程中被跳過。
假設(shè)每一位參議員都足夠聰明杆逗，會為自己的政黨做出最好的策略乡翅，你需要預(yù)測哪一方最終會宣布勝利并 在 Dota2 游戲中決定改變。輸出應(yīng)該是 Radiant 或 Dire罪郊。
public String predictPartyVictory(String senate)
{ int n = senate.length();
Queue<Integer> radiant = new LinkedList<Integer>();
Queue<Integer> dire = new LinkedList<Integer>();
for (int i = 0; i < n; ++i) {
if (senate.charAt(i) == 'R')
{ radiant.offer(i);
} else {
dire.offer(i);
}
}
while (!radiant.isEmpty() && !dire.isEmpty()) {
int radiantIndex = radiant.poll(), direIndex = dire.poll();
if (radiantIndex < direIndex) {
radiant.offer(radiantIndex + n);
} else {
dire.offer(direIndex + n);
}
}
return !radiant.isEmpty() ? "Radiant" : "Dire";
}
時間和空間：O(n)
二十蠕蚜、優(yōu)勢洗牌
給定兩個大小相等的數(shù)組 A 和 B，A 相對于 B 的優(yōu)勢可以用滿足 A[i] > B[i] 的索引 i 的數(shù)目來描述悔橄。返回 A 的任意排列靶累，使其相對于 B 的優(yōu)勢最大化。
public static int[] advantageCount(int[] A, int[] B)
{ int[] sortedA = A.clone();
Arrays.sort(sortedA);//找一個代價最小的去匹配B中的癣疟，比B大挣柬，在A中又是最小的
int[] sortedB = B.clone();
Arrays.sort(sortedB);//避免比較時，A每次都要重頭遍歷?
Map<Integer, Deque<Integer>> assigned = new HashMap();
for (int b: B)
assigned.put(b, new LinkedList());?
Deque<Integer> remaining = new LinkedList();
int j = 0;
for (int a: sortedA) {
if (a > sortedB[j])
{ assigned.get(sortedB[j++]).add(a);
} else {
remaining.add(a);
}
}
int[] ans = new int[B.length];
for (int i = 0; i < B.length; ++i)
{ if (assigned.get(B[i]).size() >
0)
ans[i] = assigned.get(B[i]).removeLast();
else
ans[i] = remaining.removeLast();
}
return ans;
}
時間復雜度：O(N log N)睛挚，其中 N 是A和B的長度
和空間復雜度：O(N)邪蛔。
總結(jié)
當然算法面試題還有很多，肯定遠遠不止這些扎狱。由于文章限制分享就只能到這里了侧到，創(chuàng)作不易勃教，如果對正在面試的你有所幫助的話記得點贊收藏加關(guān)注哦！
需要更多面試題和學習資料也都整理好了私信我即可領(lǐng)冉晨埂故源！我們下期在見！
