做付费软件网站怎么做,机械网站建设公司推荐,基于安卓系统的app开发,地下城钓鱼网站怎么做55. 跳跃游戏
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示例 1 …55. 跳跃游戏
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。提示
1 nums.length 1040 nums[i] 105 思路贪心思想。非常巧妙。一个变量代表我们最远跳到哪里。另一个变量。用来更新我们在这个路程中间实际上能跳转到的最大距离。比如用2,3,1,1,4举例。一开始最大跳转是到下边2的位置。那么我更新从1到2区间最大的位置。然后到index2的时候我们就知道这一段区间我们所能跳转的最大位置然后更新维护这个变量。 class Solution {public boolean canJump(int[] nums) {int maxStep 0;int end 0;for(int i 0;inums.length;i){maxStep Math.max(maxStep,nums[i]i);if(iend){end maxStep;if(endnums.length-1){return true;}}}return false;}
}274 H指数 思路 class Solution {public int hIndex(int[] citations) {int[] temp new int[1000];for (int i 0; i citations.length; i) {temp[citations[i]];}int sum 0;for (int i temp.length -1 ; i 0; i--) {sum temp[i];if (sum i ) {return i ;}}return 1 ; }}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 可为起始索引。示例 2:
输入: gas [2,3,4], cost [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发可以获得 4 升汽油。 此时油箱有 0 4 4 升汽油
开往 0 号加油站此时油箱有 4 - 3 2 3 升汽油
开往 1 号加油站此时油箱有 3 - 3 3 3 升汽油
你无法返回 2 号加油站因为返程需要消耗 4 升汽油但是你的油箱只有 3 升汽油。
因此无论怎样你都不可能绕环路行驶一周。贪心思想gas[i]-cost[i]。最终gas-cost 0。如果小于0说明肯定回不来。class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int sum 0;int min Integer.MAX_VALUE;int minIndex -1;for(int i 0; i gas.length; i){sum sum gas[i] - cost[i];if(sum min sum 0){min sum;minIndex i;}}if(sum 0) return -1;return (minIndex 1 )%gas.length;}
} 135. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
示例 1
输入ratings [1,0,2]
输出5
解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2
输入ratings [1,2,2]
输出4
解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。class Solution {public int candy(int[] ratings) {int n ratings.length;int[] left new int[n];int[] right new int[n];left[0] right[n-1] 1;for(int i 1; i n; i){if(ratings[i] ratings[i - 1]){left[i] left[i - 1] 1;}else{left[i] 1;}}int count left[n - 1];for(int i n - 2; i 0; i--) {if(ratings[i] ratings[i 1]){right[i] right[i 1] 1;}else{right[i] 1;}count Math.max(left[i], right[i]);}return count;}
}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。
给定一个罗马数字将其转换成整数。 总结分析规律题目。观察IV这种。是下一个大于前一个。这个时候减去当前这个就可以了。下一个是V直接相加就可以了。 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 ans 0;int len s.length();for(int i 0;ilen;i){int value map.get(s.charAt(i));if(ilen-1 value map.get(s.charAt(i1))){ans - value;}else{ans value;}}return ans;}
}392. 判断子序列
给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
进阶
如果有大量输入的 S称作 S1, S2, … , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码
致谢
特别感谢 pbrother 添加此问题并且创建所有测试用例。
示例 1
输入s abc, t ahbgdc
输出true示例 2
输入s axc, t ahbgdc
输出false思路双指针 class Solution {public boolean isSubsequence(String s, String t) {int left 0,right 0;while(lefts.length() rightt.length()){if(s.charAt(left)(t.charAt(right))){left;right;}else{right;}}return left s.length();}
}
