网站建设公司宣传范文,什么是网络营销产生的技术原因,个人有限公司注册流程,专业网站建设费用怎么算274. H 指数
题目
给你一个整数数组 citations #xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义#xff1a;h 代表“高引用次数” #xff0c;一名科研人员的 h 指数 是指他#xff08;…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(i0 hcitations[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 {MapInteger,Integer map;ListInteger 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 i1;ilen;i){left[i] nums[i-1] * left[i-1];}right[len-1] 1;for(int ilen-2;i0;i--){right[i] right[i1] * nums[i1];}int[] res new int[len];for(int i0;ilen;i){res[i] left[i] * right[i];}return res;}
}134. 加油站
题目
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 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 i0;igas.length;i){totalSum gas[i] - cost[i];currSum gas[i] - cost[i];if(currSum0){currSum 0;index (i1)%gas.length;}}return totalSum0 ? -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 i1;ilen;i){if(ratings[i]ratings[i-1]){res[i] res[i-1] 1;}else{res[i] 1;}}for(int ilen-2;i0;i--){if(ratings[i]ratings[i1]){res[i] Math.max(res[i],res[i1]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(leftright){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 LCD 和 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 {MapCharacter,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 i0;is.length();i){int val map.get(s.charAt(i));if(is.length()-1 valmap.get(s.charAt(i1))){res - val;}else{res val;}}return res;}
}12. 整数转罗马数字
题目
罗马数字包含以下七种字符 I V X LCD 和 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 i0;ivalues.length;i){while(numvalues[i]){num - values[i];sb.append(strs[i]);}if(num0){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 is.length()-1;i0;i--){while(i0 s.charAt(i) ) i--;right i;while(i0 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();}
}
