public class better_Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
int[]re = new int[2];
HashMap<Integer,Integer>map = new HashMap<>();
for(int i = 0;i<n;i++){
map.put(i,nums[i]);
if(map.containsValue(target-nums[i])){
re[0] = map.getKey //根据value获取key好像有点困难……这样是会报错的!
//所以想到了把i和nums[i]交换一下,因为containsKey(key)和containsValue(Value)都有
}
}
}
}
改进:
public class better_Solution1 {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
int[]re = new int[2];
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<n;i++){
if(map.containsKey(target-nums[i])){
re[0] = map.get(target-nums[i]);
re[1] = i;
// 这里还能改进成直接返回数组,不提前建立:return new int[]{hashtable.get(target - nums[i]), i};
}
map.put(nums[i],i);
}
return re;
//这里改进成:return new int[0];
}
}
import java.util.*;
public class Solution {
public static int longestConsecutive(int[] nums) {
HashSet<Integer>set = new HashSet<Integer>();
for(int num:nums){
set.add(num);
}
int re = 0;
for(int num:set) {
int num0 = num;
if (set.contains(num0 - 1)) {
continue; //搞了半天。。是搞混了continue(下一个循环)和break(跳出循环)..
}
int now = 1;
while (set.contains(num0 + 1)) {
num0++;
now++;
}
re = Math.max(now, re);
}
return re;
}
}
public class Solution {
public int maxArea(int[] height) {
int n = height.length;
int max = 0;
if(n == 1||n == 0)return 0;
int i = 0,j = n-1;
while(i<j){
max = Math.max(max,(j-i)*(Math.min(height[i],height[j])));
if(height[i]<height[j]){
i++;
}
else{
j--;
}
}
return max;
}
}
还可以改进,不用单独列出0个或者1个的情况:
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j) {
res = height[i] < height[j] ?
Math.max(res, (j - i) * height[i++]):
Math.max(res, (j - i) * height[j--]);
}
return res;
}
}
哈希
两数之和
题目: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
思路: 我就是直接双层循环i,j。但是发现时间复杂度有点高O( $n^2$),题解用哈希表可以降低时间复杂度为插入哈希表的O(n),因为哈希表中可以调用函数直接判断target - i是否在表里,只需要常数的复杂度。
代码:(哈希表) 第一次自己写:
改进:
字母异位词分组(⚠)
题目:
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
思路: 自己想的很繁琐……先写一个方法判断两个字符串是不是字母异位词(这里用了哈希表),再用两层循环判断……超出时间限制了
简单的方法:(想不出) 排序后的字符串作为Key,原始字符串作为Value,存到哈希表,输出所有Value
代码:(简化版)
⚠解释
char[] charArray = str.toCharArray(); 将字符串 str 转换为一个字符数组 charArray。这个字符数组中的每个元素都是字符串中对应位置的字符。例如,如果 str 是 "cat",那么 charArray 就是一个包含字符 'c'、'a' 和 't' 的字符数组。
Arrays.sort(charArray); 使用 Arrays.sort() 方法对字符数组进行排序。这会将字符数组中的字符按照字母顺序重新排列。例如,如果 charArray 是 {'c', 'a', 't'},那么排序后它会变成 {'a', 'c', 't'}。
String sortedStr = new String(charArray); 这行代码使用字符数组中的字符创建了一个新的字符串 sortedStr。
⚠还有一点很关键,就是把哈希表的Value数据结构设置成ArrayList,这样最后return就可以直接输出了
最长连续序列
题目:
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路:(没想出来。。)
我只能想到先排序,再用max循环求(肯定复杂度太大)正确的思路: 将所有数存进哈希表,然后循环,挨个判断比自己大1的数在不在哈希表里-------优化一下,不用每个都判断,只要判断每个序列最小的那个,所以每次判断一下如果有比自己小1的元素存在,就跳过。代码:(因为搞混了continue和break卡了一节课……)
双指针
移动零
题目: 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。
思路:(我还以为我的方法就是双指针……) 我:
用冒泡的方法把0一个一个换到最后去(复杂度是 $n^2$ ),超出时间限制了双指针:可以相当于是选择排序?就不用n了,选择要换的那个只需要常数级别-------不对,还是超出时间限制居然是移动非0!不是移动0!!! 一个指针 j 从0开始遍历,当指向非0时移到另一个前面的指针 i 的位置,i ++,j 遍历完后,i 剩下的部分都改成0代码:(双指针)
再看看我自己写的伪双指针:
还是双层循环,复杂度还是平方项
乘最多水的容器
题目:
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。 说明:你不能倾斜容器。![乘最多水的容器](https://github.com/alittlepeara/leetcode_notes/assets/133872419/fcb533f5-8c43-4011-abf5-962ee2921a01)
思路:(只能想出最简单的,,超限) 真的想了好久啊,还是没想出来到底该怎样简化
简化,就是要跳过一些步骤,想出一些情况是不需要执行的,但是我一直在想i和j都是从左边向右,因为横向一定会增加,所以不管增加的长还是短,都有可能会使整个面积增加。 正确的思路: 双指针分别从左右两端开始 两板中的长板如果向内移动,一定变小了(短板还是原来的甚至更短,但是横向距离减少)
还把我的双层循环改进成了单层
代码:(我按题解的思路写的)
还可以改进,不用单独列出0个或者1个的情况: