記錄一次力扣的模擬在線筆試[字節(jié)跳動]
一共三道算法題，共計(jì)一個半小時
1. 按奇偶排序數(shù)組
給定一個非負(fù)整數(shù)數(shù)組 A，返回一個數(shù)組，在該數(shù)組中， A 的所有偶數(shù)元素之后跟著所有奇數(shù)元素。你可以返回滿足此條件的任何數(shù)組作為答案。
示例：
輸入：[3,1,2,4]
輸出：[2,4,3,1]
輸出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也會被接受。
提示：
1 <= A.length <= 5000
0 <= A[i] <= 5000
思路：
使用一個變量index記錄進(jìn)程，index往前的數(shù)都是交換過來的偶數(shù)
只要找到了偶數(shù)，就將它與index下標(biāo)對應(yīng)的數(shù)進(jìn)行交換，這樣最終偶數(shù)都會在奇數(shù)的前面
class Solution {
public int[] sortArrayByParity(int[] A) {
int index=0;
for(int i=0;i<A.length;i++){
if(A[i]%2==0){
int k=A[index];
A[index]=A[i];
A[i]=k;
index++;
}
}
return A;
}
}
2. 供暖器
冬季已經(jīng)來臨。 你的任務(wù)是設(shè)計(jì)一個有固定加熱半徑的供暖器向所有房屋供暖。
現(xiàn)在，給出位于一條水平線上的房屋和供暖器的位置，找到可以覆蓋所有房屋的最小加熱半徑。
所以，你的輸入將會是房屋和供暖器的位置。你將輸出供暖器的最小加熱半徑。
說明:
- 給出的房屋和供暖器的數(shù)目是非負(fù)數(shù)且不會超過 25000。
- 給出的房屋和供暖器的位置均是非負(fù)數(shù)且不會超過10^9。
- 只要房屋位于供暖器的半徑內(nèi)(包括在邊緣上)，它就可以得到供暖。
- 所有供暖器都遵循你的半徑標(biāo)準(zhǔn)，加熱的半徑也一樣。
示例 1:
輸入: [1,2,3],[2]
輸出: 1
解釋: 僅在位置2上有一個供暖器。如果我們將加熱半徑設(shè)為1，那么所有房屋就都能得到供暖。
示例 2:
輸入: [1,2,3,4],[1,4]
輸出: 1
解釋: 在位置1, 4上有兩個供暖器。我們需要將加熱半徑設(shè)為1，這樣所有房屋就都能得到供暖。
思路:找到每個房屋離加熱器的最短距離（即找出離房屋最近的加熱器），然后在所有距離中選出最大的一個即為結(jié)果。
class Solution {
// 找到每個房屋離加熱器的最短距離（即找出離房屋最近的加熱器），然后在所有距離中選出最大的一個即為結(jié)果。
// 即：所有最短距離中的最長值
public int findRadius(int[] houses, int[] heaters) {
//進(jìn)行排序
Arrays.sort(houses);
Arrays.sort(heaters);
//記錄最終的最短管道距離
int max = 0;
//尋找每一個房屋的最近加熱器的距離，然后記錄這些最短距離中的最大值
for (int i = 0; i < houses.length; i++) {
int start = 0;
int end = heaters.length - 1;
//二分查找，在heaters中尋找與房屋 c 最近的加熱器
while (start < end) {
int mid = (start + end) / 2;
if (houses[i] > heaters[mid]) {
start = mid+1;
} else {
end=mid;
}
}
//記錄當(dāng)前選中的這個加熱器距離目標(biāo)房屋的距離（可正可負(fù)）
int len = heaters[start] - houses[i];
//如果是負(fù)的，則說明這是在房屋的左邊的第一個加熱器
if (len < 0) {
max = Math.max(max, -len);
} else if (len > 0) {
//分兩種情況討論
//如果start左邊還有start-1，則說明start是右邊第一個，start-1是左邊最接近的，討論兩個中最近的那個返回
//如果start是第一個數(shù)，則直接讓他與max比較
if (start > 0) {
max = Math.max(Math.min(houses[i] - heaters[start - 1], len), max);
} else {
max = Math.max(max, len);
}
}
}
//max即為所求
return max;
}
}
3. 買賣股票的最佳時機(jī)含手續(xù)費(fèi)
給定一個整數(shù)數(shù)組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負(fù)整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用。
你可以無限次地完成交易，但是你每次交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。
返回獲得利潤的最大值。
示例 1:
輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達(dá)到的最大利潤:
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
思路：
運(yùn)用動態(tài)規(guī)劃的思想
使用一個二維數(shù)組記錄可能的情況，第一維為天數(shù)，第二維分為兩個情況，持有股票或者不持有股票
最終，遍歷所有的情況，找到最好值
class Solution {
public int maxProfit(int[] prices, int fee) {
int len=prices.length;
//使用一個二維數(shù)組記錄可能的情況，第一維為天數(shù)，第二維分為兩個情況，持有股票或者不持有股票
int[][] books = new int[len][2];
//第一天要么不買，利潤為0
books[0][0]=0;
//要么買進(jìn)股票，利潤為股票價格+手續(xù)費(fèi)的負(fù)值
books[0][1]=-prices[0]-fee;
for(int i=1;i<len;i++){
//當(dāng)天的不持有股票利潤最大為max（不持有不變，前一天的賣掉）
books[i][0]=Math.max(books[i-1][0],books[i-1][1]+prices[i]);
//當(dāng)天的持有股票利潤最大為max（持有不變，前一天的買進(jìn)）
books[i][1]=Math.max(books[i-1][1],books[i-1][0]-prices[i]-fee);
}
//最終天肯定是不持有的利潤最大，因?yàn)橛芯唾u掉，多少有點(diǎn)錢
return books[len-1][0];
}
}
自己算法水平還是不行，要多多練習(xí)
