java算法题每日多道
274. H 指数
题目
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。
示例 1：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
示例 2：
输入：citations = [1,3,1]
输出：1
答案
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int i = citations.length - 1;
int h = 0;
while(i>=0 && h<citations[i]){
i--;
h++;
}
return h;
}
}
380. O(1) 时间插入、删除和获取随机元素
题目
实现RandomizedSet 类：
RandomizedSet()初始化RandomizedSet对象bool insert(int val)当元素val不存在时，向集合中插入该项，并返回true；否则，返回false。bool remove(int val)当元素val存在时，从集合中移除该项，并返回true；否则，返回false。int getRandom()随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
答案
class RandomizedSet {
Map<Integer,Integer> map;
List<Integer> list;
Random random;
public RandomizedSet() {
map = new HashMap();
list = new ArrayList();
random = new Random();
}
public boolean insert(int val) {
if(map.containsKey(val)){
return false;
}
int index = list.size();
list.add(val);
map.put(val,index);
return true;
}
public boolean remove(int val) {
if(!map.containsKey(val)){
return false;
}
//让最后一个填补删除的位置，保持list的索引映射
int index = map.get(val);
int last = list.get(list.size()-1);
list.set(index,last);
map.put(last,index);
list.remove(list.size()-1);
map.remove(val);
return true;
}
public int getRandom() {
int index = random.nextInt(list.size());
return list.get(index);
}
}
238. 除自身以外数组的乘积
题目
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(*n*) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
答案
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
int[] left = new int[len];
int[] right = new int[len];
left[0] = 1;
for(int i=1;i<len;i++){
left[i] = nums[i-1] * left[i-1];
}
right[len-1] = 1;
for(int i=len-2;i>=0;i--){
right[i] = right[i+1] * nums[i+1];
}
int[] res = new int[len];
for(int i=0;i<len;i++){
res[i] = left[i] * right[i];
}
return res;
}
}
134. 加油站
题目
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
答案
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int currSum = 0;
int totalSum = 0;
int index = 0;
for(int i=0;i<gas.length;i++){
totalSum += gas[i] - cost[i];
currSum += gas[i] - cost[i];
if(currSum<0){
currSum = 0;
index = (i+1)%gas.length;
}
}
return totalSum<0 ? -1 : index;
}
}
135. 分发糖果
题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
答案
class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
int[] res = new int[len];
res[0] = 1;
for(int i=1;i<len;i++){
if(ratings[i]>ratings[i-1]){
res[i] = res[i-1] + 1;
}else{
res[i] = 1;
}
}
for(int i=len-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
res[i] = Math.max(res[i],res[i+1]+1);
}
}
int sum = 0;
for(int num : res){
sum += num;
}
return sum;
}
}
42. 接雨水
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
答案
class Solution {
public int trap(int[] height) {
int len = height.length;
int left = 0,right = len - 1;
int leftMax = 0,rightMax = 0;
int res = 0;
while(left<right){
leftMax = Math.max(leftMax,height[left]);
rightMax = Math.max(rightMax,height[right]);
if(height[left]<height[right]){
res += leftMax - height[left++];
}else{
res += rightMax - height[right--];
}
}
return res;
}
}
13. 罗马数字转整数
题目
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
示例 1:
输入: s = "III"
输出: 3
答案
class Solution {
Map<Character,Integer> map = new HashMap(){
{ put('I',1);
put('V',5);
put('X',10);
put('L',50);
put('C',100);
put('D',500);
put('M',1000);
}
};
public int romanToInt(String s) {
int res = 0;
for(int i=0;i<s.length();i++){
int val = map.get(s.charAt(i));
if(i<s.length()-1 && val<map.get(s.charAt(i+1))){
res -= val;
}else{
res += val;
}
}
return res;
}
}
12. 整数转罗马数字
题目
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
示例 1:
输入: num = 3
输出: "III"
示例 2:
输入: num = 4
输出: "IV"
答案
class Solution {
public String intToRoman(int num) {
int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuilder sb = new StringBuilder();
for(int i=0;i<values.length;i++){
while(num>=values[i]){
num -= values[i];
sb.append(strs[i]);
}
if(num==0){
break;
}
}
return sb.toString();
}
}
58. 最后一个单词的长度
题目
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大
子字符串
示例 1：
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为5。
示例 2：
输入：s = " fly me to the moon "
输出：4
解释：最后一个单词是“moon”，长度为4。
答案
class Solution {
public int lengthOfLastWord(String s) {
int right = 0,left = 0;
for(int i=s.length()-1;i>=0;i--){
while(i>=0 && s.charAt(i)==' ') i--;
right = i;
while(i>=0 && s.charAt(i)!=' ') i--;
left = i;
break;
}
return right - left;
}
}
class Solution {
public int lengthOfLastWord(String s) {
String[] strs = s.split(" ");
return strs[strs.length-1].length();
}
}