实验一 电子商务网站建设与维护,图片做网站,天津网站优化首页,莒南县网站建设leetcode 150道题 计划花两个月时候刷完#xff0c;今天#xff08;第四天#xff09;完成了4道(10-13)150#xff1a; 10. #xff08;45. 跳跃游戏 II#xff09;题目描述#xff1a;
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[…leetcode 150道题 计划花两个月时候刷完今天第四天完成了4道(10-13)150 10. 45. 跳跃游戏 II题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i]
i j n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。第一版这个和昨天是一样的就还是那样只是多加了一个计数器我没有看最优解这个我能记住。。最优解记不住
class Solution {public int jump(int[] nums) {// 和上一个跳跃 是一样的//如果跳不到终点就尽可能跳到最远int lennums.length;int index0;int res0;while(indexlen-1){int tempnums[index]index;if(templen-1){return res1;}int max0;for(int iindex1;itemp;i){if(nums[i]0){continue;}if(nums[i]imax){indexi;maxnums[i]i;}}// 这个应该可以不加判断题目应该会保证给的测试例子都可以跳到终点的。。if(max0)return 0;res;}return res;}
}274. H 指数题目描述
给你一个整数数组 citations 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义h 代表“高引用次数” 一名科研人员的 h 指数 是指他她至少发表了 h 篇论文并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值h 指数 是其中最大的那个。这个题我真的做了至少四遍了每次都做不出来是真的理解不了他说的然后我去查了维基百科上的上面就有算法我感觉这个好理解最优的二分法感觉记不住。。 可以按照如下方法确定某人的H指数 1、将其发表的所有SCI论文按被引次数从高到低排序 2、从前往后查找排序后的列表只要当前的引用量大于当前的索引值则H指数加1最后得到的结果即为最终的H指数 第一版按照这个维基百科算法去写的
class Solution {public int hIndex(int[] citations) {int hNum0;int lencitations.length;Arrays.sort(citations);for(int ilen-1;i0;i--){if(citations[i]len-i-1)hNum;}return hNum;}
}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 {ArrayListInteger list;Random random;MapInteger,Integer map;public RandomizedSet() {listnew ArrayListInteger();random new Random();mapnew HashMapInteger,Integer();}public boolean insert(int val) {if(map.keySet().contains(val))return false;list.add(val);map.put(val,list.size()-1);return true;}public boolean remove(int val) {if(!map.keySet().contains(val))return false;int indexmap.get(val);int lastValuelist.get(list.size()-1);map.put(lastValue,index);list.set(index,lastValue);list.remove(list.size()-1);map.remove(val);return true;}public int getRandom() {int sizelist.size();return list.get(random.nextInt(size));}
}238. 除自身以外数组的乘积题目描述
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法且在 O(n) 时间复杂度内完成此题。第一版当然是暴力求解了但是我加了一些优化以为是最优解没想到超时了。。
class Solution {public int[] productExceptSelf(int[] nums) {int lennums.length;int[] resnew int[len];for(int i0;ilen;i){if(nums[i]0){// 其他为 0 res[i]getNum(nums,i);return res;}}for(int i0;ilen;i){res[i]getNum(nums,i);}return res;}public int getNum(int[] nums,int i){int temp1;for(int j0;jnums.length;j){if(ji){continue;}if(nums[j]0){temp0;break;} temp*nums[j];}return temp;}
}第二版看的解析人家还是厉害啊
class Solution {public int[] productExceptSelf(int[] nums) {int lennums.length;int[] resnew int[len];int[] lAnswernew int[len];int[] rAnswernew int[len];lAnswer[0]1;for(int i1;ilen;i){lAnswer[i]nums[i-1]*lAnswer[i-1];}rAnswer[len-1]1;for(int ilen-2;i0;i--){rAnswer[i]nums[i1]*rAnswer[i1];}for(int i0;ilen;i){res[i]lAnswer[i]*rAnswer[i];}return res;}
}早日跳槽跳槽 真的现在待的公司感觉一点前途都没有。。看不到未来啊。
