上岸算法
任何只教知識的課程都是耍流氓
我們直擊上岸
關注我們，第一時間獲得大廠面試真題講解
應廣大同學們的需求，我們將定期整理各大廠最新的面試題題解，由我們【上岸算法】資深的老師給大家進行分析講解，幫助大家實時掌握最新的面試動態，早日上岸！
Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.
Example 1 :
Output: 2Example 2 :
Output: 3題解：
在歸併排序的時候計算翻轉對
歸併排序時：
注意：nums[j] * 2 計算得到的結果可能會大於Integer.MAX_VALUE,需要轉化成long
參考代碼
class Solution {
public int reversePairs(int[] nums) {
// 使用歸併排序，從小到大的進行排序
if(nums.length < 2) {
return 0;
}
return sort(nums,0,nums.length - 1);
}
public int sort(int[] nums,int left,int right) {
if(left >= right) {
return 0;
}
int mid = (left + right) / 2;
int leftRes = sort(nums,left,mid);
int rightRes = sort(nums,mid + 1,right);
return leftRes + rightRes + merge(nums,left,mid,right);
}
public int merge(int[] nums,int left,int mid,int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int res = 0;
int flag = 0;
// 計算翻轉對
while(i <= mid && j <= right) {
if(nums[i] > 2 * (long)nums[j]) {
res += mid - i + 1;
j++;
}else {
i++;
}
}
i = left;
j = mid + 1;
// 進行排序
while(i <= mid && j <= right) {
if(nums[i] < nums[j]) {
temp[flag++] = nums[i++];
}else {
temp[flag++] = nums[j++];
}
}
while(i <= mid) {
temp[flag++] = nums[i++];
}
while(j <= right) {
temp[flag++] = nums[j++];
}
for(int k = 0;k < temp.length;k++) {
nums[left + k] = temp[k];
}
return res;
}
}
題目描述：Random Pick with Weight
You are given an array of positive integers w where w[i] describes the weight of ith index (0-indexed).
We need to call the function pickIndex() which randomly returns an integer in the range [0, w.length - 1]. pickIndex() should return the integer proportional to its weight in the w array. For example, for w = [1, 3], the probability of picking the index 0 is 1 / (1 + 3) = 0.25 (i.e 25%) while the probability of picking the index 1 is 3 / (1 + 3) = 0.75 (i.e 75%).
More formally, the probability of picking index i is w[i] / sum(w).
Example 1 :
["Solution","pickIndex"][[[1]],[]]Output[null,0]ExplanationSolution solution = new Solution([1]);solution.pickIndex(); // return 0. Since there is only one single element on the array the only option is to return the first element.
題解：
這題採用前綴和和二分查找來解決。
參考代碼
class Solution {
int[] sum;
public Solution(int[] w) {
sum = new int[w.length + 1];
for (int i = 1;i <= w.length; i++){
sum[i] = sum[i - 1] + w[i - 1];
}
}
public int pickIndex() {
int n = sum.length;
int x = new Random().nextInt(sum[n - 1]) + 1;
int l = 0, r = n;
while (l < r){
int mid = l + r >> 1;
if (sum[mid] >= x) r = mid;
else l = mid + 1;
}
return l - 1;
}
}
題目描述：Continuous Subarray Sum
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:
Input: [23, 2, 4, 6, 7], k=6Output: TrueExplanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.Example 2:
Input: [23, 2, 6, 4, 7], k=6Output: TrueExplanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42參考代碼
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int N = nums.length, cache = 0;
int[] sum = new int[N+1];
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < N; i++) {
sum[i+1] = sum[i] + nums[i];
int res = k == 0 ? sum[i+1] : sum[i+1] % k;
if (set.contains(res)) return true;
set.add(cache);
cache = res;
}
return false;
}
}
題目描述：Paint House
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
Example 1:
Given costs = [[14,2,11],[11,14,5],[14,3,10]] return 10
house 0 is blue, house 1 is green, house 2 is blue, 2 + 5 + 3 = 10
Note:
All costs are positive integers.
y one island with area = 4.題解：
房子i的最小塗色開銷是房子i-1的最小塗色開銷，加上房子i本身的塗色開銷。但是房子i的塗色方式需要根據房子i-1的塗色方式來確定，所以我們對房子i-1要記錄塗三種顏色分別不同的開銷，這樣房子i在塗色的時候，我們就知道三種顏色各自的最小開銷是多少了。我們在原數組上修改，可以做到不用空間。
參考代碼
class Solution {
public int minCost(int[][] costs) {
if(costs != null && costs.length == 0) return 0;
// 直接用原數組
for(int i = 1; i < costs.length; i++){
// 塗第一種顏色的話，上一個房子就不能塗第一種顏色，這樣我們要在上一個房子的第二和第三個顏色的最小開銷中找最小的那個加上
costs[i][0] = costs[i][0] + Math.min(costs[i - 1][1], costs[i - 1][2]);
// 塗第二或者第三種顏色同理 costs[i][1] = costs[i][1] + Math.min(costs[i - 1][0], costs[i - 1][2]);
costs[i][2] = costs[i][2] + Math.min(costs[i - 1][0], costs[i - 1][1]);
}
// 返回塗三種顏色中開銷最小的那個
return Math.min(costs[costs.length - 1][0], Math.min(costs[costs.length - 1][1], costs[costs.length - 1][2]));
}
}