制作企业网站的新闻,手机版商城网站都有哪 些功能,东莞樟木头做网站哪家好,想要找个网站做环评公示LeetCode刷题日记
HashMap
第1题----两数之和 原题地址 [https://leetcode.cn/problems/two-sum/]: 解题思路#xff1a; 将数组中每个元素通过两次遍历使两数之差target#xff0c;最后由结果target得到对应数组下标。此时算法的时间复杂度为O(n^2)。故而放弃此方法。 由于…LeetCode刷题日记
HashMap
第1题----两数之和 原题地址 [https://leetcode.cn/problems/two-sum/]: 解题思路 将数组中每个元素通过两次遍历使两数之差target最后由结果target得到对应数组下标。此时算法的时间复杂度为O(n^2)。故而放弃此方法。 由于上种方法时间复杂度过大超出时间限制所以改为通过使用hashmap来存储nums中的元素。通过一次遍历来判断target-nums[i]是否已经存在于数组nums[i]中了如果已经存在于nums[i]中则满足该数组中两数之和target。此时的时间复杂度为O(n)。 代码如下
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger, Integer hashtable new HashMapInteger, Integer();int[] sumnew int[2];for (int i 0; i nums.length; i) {if (hashtable.containsKey(target - nums[i])) {sum[0]hashtable.get(target - nums[i]);sum[1]i;return sum;}hashtable.put(nums[i], i);}return sum;}
}双指针
第26题-----删除有序数组中的重复项
原题地址
[https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/]: 解题思路** 由题中原地删除重复出现的元素可知我们必须在原数组中完成重复元素的删除并在删除的同时减小数组的长度。 此处最好使用的是双指针算法 通过同向的快慢指针来实现在原地删除重复的元素。通过快指针来遍历数组判断是否有重复的元素而慢指针则在元素不重复时将不重复的元素存储下来其中慢指针所指位置的长度就是原地删除重复出现的元素之后的新的数组长度。 代码如下
class Solution {public int removeDuplicates(int[] nums) {int fast1;int slow1;int sizenums.length;if(size0){return 0;}while(fastsize){if(nums[fast]!nums[fast-1]){nums[slow]nums[fast];slow;}fast;}return slow;}
}排队插入
第27题----移除元素
原题地址
[https://leetcode.cn/problems/remove-element/description/]: 解题思路 同样地该题的要求为在原数组中移除指定值的元素。 对于该题则使用“排队插入算法”。使用count标记如果是目标元素则count如果不是目标元素则为了将删除的元素填补上使nums[i-count]nums[i]; 代码如下
class Solution {public int removeElement(int[] nums, int val) {int count0;int snums.length;if(s0){return 0;}for(int i0;is;i){if(nums[i]val){count;}else{nums[i-count]nums[i];}}return s-count;}
}第121题----买卖股票的最佳时机 原题地址 [https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/]: 解题思路 代码如下
class Solution {public int maxProfit(int[] prices) {int maxProfit 0;int minPrice prices[0]; for (int i 1; i prices.length; i) {if( prices[i] - minPrice maxProfit) {maxProfit prices[i] - minPrice;}if (prices[i] minPrice) {minPrice prices[i];}}return maxProfit;}}
