贪心、模拟(牛客)
题目来自牛客题目库 算法篇面试必刷TOP101。
贪心
BM95 分糖果问题(较难)
题目
一群孩子做游戏,现在请你根据游戏得分来发糖果,要求如下:
-
每个孩子不管得分多少,起码分到一个糖果。
-
任意两个相邻的孩子之间,得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组 arr 代表得分数组,请返回最少需要多少糖果。
要求: 时间复杂度为 O(n) 空间复杂度为 O(n)
数据范围: 1≤n≤100000 ,1≤a~i~≤1000
示例:
示例1:
输入:[1,1,2]
返回值:4
说明:最优分配方案为1,1,2
示例2:
输入:[1,1,1]
返回值:3
说明:最优分配方案是1,1,1
解法 贪心
- step 1:使用一个辅助数组记录每个位置的孩子分到的糖果,全部初始化为1.
- step 2:从左到右遍历数组,如果右边元素比相邻左边元素大,意味着在递增,糖果数就是前一个加1,否则保持1不变。
- step 3:从右到左遍历数组,如果左边元素比相邻右边元素大, 意味着在原数组中是递减部分,如果左边在上一轮中分到的糖果数更小,则更新为右边的糖果数+1,否则保持不变。
- step 4:将辅助数组中的元素累加求和。
import java.util.*;
public class Solution {
public int candy (int[] arr) {
int n = arr.length;
if(n <= 1)
return n;
int[] nums = new int[n];
//初始化
for(int i = 0; i < n; i++)
nums[i] = 1;
//从左到右遍历
for(int i = 1; i < arr.length; i++){
//如果右边在递增,每次增加一个
if(arr[i] > arr[i - 1])
nums[i] = nums[i - 1] + 1;
}
//记录总糖果数
int res = nums[arr.length - 1];
//从右到左遍历
for(int i = arr.length - 2; i >= 0; i--){
//如果左边更大但是糖果数更小
if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1])
nums[i] = nums[i + 1] + 1;
//累加和
res += nums[i];
}
return res;
}
}
BM96 主持人调度(二)(中等)
题目
有 n 个活动即将举办,每个活动都有开始时间与活动的结束时间,第 i 个活动的开始时间是 start~i~ ,第 i 个活动的结束时间是 end~i~ ,举办某个活动就需要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动,换句话说,一个主持人参与了第 i 个活动,那么该主持人在 (start~i~,end~i~) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动,最少需要多少名主持人。
数据范围: 1≤n≤10~5~ , −2~32~≤start~i~≤end~i~≤2~31~−1
复杂度要求:时间复杂度 O(nlogn) ,空间复杂度 O(n)
示例:
示例1:
输入:2,[[1,2],[2,3]]
返回值:1
说明:只需要一个主持人就能成功举办这两个活动
示例2:
输入:2,[[1,3],[2,4]]
返回值:2
说明:需要两个主持人才能成功举办这两个活动
解法 贪心
- step 1: 利用辅助数组获取单独各个活动开始的时间和结束时间,然后分别开始时间和结束时间进行排序,方便后面判断是否相交。
- step 2: 遍历n个活动,如果某个活动开始的时间大于之前活动结束的时候,当前主持人就够了,活动结束时间往后一个。
- step 3: 若是出现之前活动结束时间晚于当前活动开始时间的,则需要增加主持人。
import java.util.*;
public class Solution {
public int minmumNumberOfHost (int n, int[][] startEnd) {
int[] start = new int[n];
int[] end = new int[n];
//分别得到活动起始时间
for(int i = 0; i < n; i++){
start[i] = startEnd[i][0];
end[i] = startEnd[i][1];
}
//单独排序
Arrays.sort(start);
Arrays.sort(end);
int res = 0;
int j = 0;
for(int i = 0; i < n; i++){
//新开始的节目大于上一轮结束的时间,主持人不变
if(start[i] >= end[j])
j++;
else
//主持人增加
res++;
}
return res;
}
}
模拟
BM97 旋转数组(中等)
题目
一个数组A中存有 n 个整数,在不允许使用另外数组的前提下,将每个整数循环向右移 M( M >=0)个位置,即将A中的数据由(A0 A1 ……AN-1 )变换为(AN-M …… AN-1 A0 A1 ……AN-M-1 )(最后 M 个数循环移至最前面的 M 个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?
数据范围:0<n≤100,0≤m≤1000
进阶:空间复杂度 O(1),时间复杂度 O(n)
示例:
示例1:
输入:6,2,[1,2,3,4,5,6]
返回值:[5,6,1,2,3,4]
示例2:
输入:4,0,[1,2,3,4]
返回值:[1,2,3,4]
解法
public class Solution {
public int[] solve (int n, int m, int[] a) {
//取余,因为每次长度为n的旋转数组相当于没有变化
m = m % n;
//第一次逆转全部数组元素
reverse(a, 0, n - 1);
//第二次只逆转开头m个
reverse(a, 0, m - 1);
//第三次只逆转结尾m个
reverse(a, m, n - 1);
return a;
}
//反转函数
public void reverse(int[] nums, int start, int end){
while(start < end){
swap(nums, start++, end--);
}
}
//交换函数
public void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
BM98 螺旋矩阵(简单)
题目
给定一个m x n大小的矩阵(m行,n列),按螺旋的顺序返回矩阵中的所有元素。
数据范围:0≤n,m≤10,矩阵中任意元素都满足 ∣val∣≤100
要求:空间复杂度 O(n*m) ,时间复杂度 O(n*m)
示例:
示例1:
输入:[[1,2,3],[4,5,6],[7,8,9]]
返回值:[1,2,3,6,9,8,7,4,5]
示例2:
输入:[]
返回值:[]
解法
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
//先排除特殊情况
if(matrix.length == 0) {
return res;
}
//左边界
int left = 0;
//右边界
int right = matrix[0].length - 1;
//上边界
int up = 0;
//下边界
int down = matrix.length - 1;
//直到边界重合
while(left <= right && up <= down){
//上边界的从左到右
for(int i = left; i <= right; i++)
res.add(matrix[up][i]);
//上边界向下
up++;
if(up > down)
break;
//右边界的从上到下
for(int i = up; i <= down; i++)
res.add(matrix[i][right]);
//右边界向左
right--;
if(left > right)
break;
//下边界的从右到左
for(int i = right; i >= left; i--)
res.add(matrix[down][i]);
//下边界向上
down--;
if(up > down)
break;
//左边界的从下到上
for(int i = down; i >= up; i--)
res.add(matrix[i][left]);
//左边界向右
left++;
if(left > right)
break;
}
return res;
}
}
BM99 顺时针旋转矩阵(中等)
题目
有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度。
给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵。
数据范围:0<n<300,矩阵中的值满足 0≤val≤1000
要求:空间复杂度 O(N^2^),时间复杂度 O(N^2^)
进阶:空间复杂度 O(1),时间复杂度 O(N^2^)
示例:
输入:[[1,2,3],[4,5,6],[7,8,9]],3
返回值:[[7,4,1],[8,5,2],[9,6,3]]
解法
先转置,再每行翻转。
import java.util.*;
public class Solution {
public int[][] rotateMatrix(int[][] mat, int n) {
int length = mat.length;
//矩阵转置
for(int i = 0; i < length; ++i){
for(int j = 0; j < i; ++j){
//交换上三角与下三角对应的元素
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
}
//每行翻转
for (int i = 0; i < length; i++) {
for (int j = 0; j < length/2; j++){
int temp = mat[i][j];
mat[i][j] = mat[i][length - j - 1];
mat[i][length - j - 1] = temp;
}
}
return mat;
}
}