记录一次力扣的模拟在线笔试[字节跳动]
一共三道算法题，共计一个半小时
1. 按奇偶排序数组
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。你可以返回满足此条件的任何数组作为答案。
示例：
输入：[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记录进程，index往前的数都是交换过来的偶数
只要找到了偶数，就将它与index下标对应的数进行交换，这样最终偶数都会在奇数的前面
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. 供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。
所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明:
- 给出的房屋和供暖器的数目是非负数且不会超过 25000。
- 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
- 只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
- 所有供暖器都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:
输入: [1,2,3,4],[1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
思路:找到每个房屋离加热器的最短距离（即找出离房屋最近的加热器），然后在所有距离中选出最大的一个即为结果。
class Solution {
// 找到每个房屋离加热器的最短距离（即找出离房屋最近的加热器），然后在所有距离中选出最大的一个即为结果。
// 即：所有最短距离中的最长值
public int findRadius(int[] houses, int[] heaters) {
//进行排序
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;
}
}
//记录当前选中的这个加热器距离目标房屋的距离（可正可负）
int len = heaters[start] - houses[i];
//如果是负的，则说明这是在房屋的左边的第一个加热器
if (len < 0) {
max = Math.max(max, -len);
} else if (len > 0) {
//分两种情况讨论
//如果start左边还有start-1，则说明start是右边第一个，start-1是左边最接近的，讨论两个中最近的那个返回
//如果start是第一个数，则直接让他与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. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 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.
思路：
运用动态规划的思想
使用一个二维数组记录可能的情况，第一维为天数，第二维分为两个情况，持有股票或者不持有股票
最终，遍历所有的情况，找到最好值
class Solution {
public int maxProfit(int[] prices, int fee) {
int len=prices.length;
//使用一个二维数组记录可能的情况，第一维为天数，第二维分为两个情况，持有股票或者不持有股票
int[][] books = new int[len][2];
//第一天要么不买，利润为0
books[0][0]=0;
//要么买进股票，利润为股票价格+手续费的负值
books[0][1]=-prices[0]-fee;
for(int i=1;i<len;i++){
//当天的不持有股票利润最大为max（不持有不变，前一天的卖掉）
books[i][0]=Math.max(books[i-1][0],books[i-1][1]+prices[i]);
//当天的持有股票利润最大为max（持有不变，前一天的买进）
books[i][1]=Math.max(books[i-1][1],books[i-1][0]-prices[i]-fee);
}
//最终天肯定是不持有的利润最大，因为有就卖掉，多少有点钱
return books[len-1][0];
}
}
自己算法水平还是不行，要多多练习
