贪心、模拟(牛客)

目录

贪心、模拟(牛客)

题目来自牛客题目库 算法篇面试必刷TOP101

贪心

BM95 分糖果问题(较难)

题目

题目链接

一群孩子做游戏,现在请你根据游戏得分来发糖果,要求如下:

  1. 每个孩子不管得分多少,起码分到一个糖果。

  2. 任意两个相邻的孩子之间,得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 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;
    }
}
-->