Leetcode 热门百题斩(第三天)

2024-02-27 00:30

本文主要是介绍Leetcode 热门百题斩(第三天),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

介绍

针对leetcode的热门一百题,解决大多数实习生面试的基本算法题。通过我自己的思路和多种方法,供大家参考。 

1.两数之和(题号:1)

方法一 

最先想到的就是两个for去遍历匹配。

class Solution {public int[] twoSum(int[] nums, int target) {for(int i = 0; i < nums.length; i++)for(int j = i + 1; j < nums.length; j++) {if(nums[i] + nums[j] == target) {return new int[] {i, j};}}return null;}
}

效率低下。

尝试其他方法。

 方法二

 使用Hash表进行匹配。也是先进行一次遍历,任何直接使用containKey匹配符合条件的值。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> numMap = new HashMap<>();//在为map赋值的时候顺便进行判断//判断当前map中是否存在其他key2可以得到当前key1相加等于targetfor(int i = 0; i < nums.length; i++) {if(numMap.containsKey(target - nums[i])) {//存在直接返回数据即可,此时是没有包含本身值 + 本身值是否=targetreturn new int[] {i, numMap.get(target - nums[i])};}numMap.put(nums[i], i);}return new int[2];}
}

效率马上就高了。

2. 字符异位词分组(题号:49)

方法一(暴力法,超时)

创建标记数组(标记数组是否被使用),通过二次遍历,将符合添加的数据存储到一个list中,最终返回数据。 

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//创建一个标记数组int[] sign = new int[strs.length];List<List<String>> result = new LinkedList<>();//遍历列表并将重排序后相同的字符串存放在一个list中for(int i = 0; i < strs.length; i++) {//直接跳过if(sign[i] == 1) {continue;}//创建异位listList<String> tempList = new LinkedList<>();tempList.add(strs[i]);//对当前的字符串进行重排序char[] firstArray = strs[i].toCharArray();//直接对引用数组进行排序Arrays.sort(firstArray);String firstSortTemp = new String(firstArray);//将当前字符串标记为已使用(0为未使用,1为已使用)sign[i] = 1;for(int j = i + 1; j < strs.length; j++) {//对后续的字符串进行重排序if(sign[j] == 1) {//直接跳过continue;}char[] secondArray = strs[j].toCharArray();Arrays.sort(secondArray);String secondSortTemp = new String(secondArray);if(firstSortTemp.equals(secondSortTemp)) {//符合条件放入list中tempList.add(strs[j]);//标记为已使用sign[j] = 1;}}result.add(tempList);}return result;}
}

超时。

 方法二(使用hash表进行匹配)

使用hash表,对每个字符串重新排序,key存储排序后的字符串,value存储的就是符合异位的字符串的集合,最终返回values的集合。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//使用hash表进行匹配,key存储排序后的字符串,vlaue存储的就是异位字符串的list //(有点类似插入排序, 将对应的字符串存储到对应的键值对上)Map<String, List<String>> resultMap = new HashMap<>();for(int i = 0; i < strs.length; i++) {char[] tempStr = strs[i].toCharArray();Arrays.sort(tempStr);//排序好的字符串String sortTemp = new String(tempStr);List<String> tempList = resultMap.getOrDefault(sortTemp, new LinkedList<String>());//插入自己,并修改对应listtempList.add(strs[i]);resultMap.put(sortTemp, tempList);}//直接返回value集合return new LinkedList<List<String>>(resultMap.values());}
}

通过。

3.最长连续序列(题号:128)

最开始的时候题目要求将时间复杂度控制在O(N),就没有想到使用双重循环(主要是怕超时)。

主要的思路就是使用set去重,然后遍历,从每个连续序列的排头进行遍历判断,求出最长的序列长度。(要注意的就是,去除多余循环的次数,防超时)

class Solution {public int longestConsecutive(int[] nums) {//使用HashSet去重Set<Integer> set = new HashSet<Integer>();for(int i = 0; i < nums.length; i++) {set.add(nums[i]);}int maxSize = 0;for(int i = 0; i < nums.length; i++) {//判断当前数值是否为排头,如果是排头就将长度设置为1,反之直接跳过int currentSize = 0;int tempNum = nums[i];//判断是否存在前值,如果存在直接跳过,防止超时if(!set.contains(tempNum - 1)) {//不存在,就说明是排头currentSize = 1;//循环判断后续长度while(set.contains(tempNum + 1)) {currentSize++;tempNum++;}maxSize = Math.max(currentSize, maxSize);}}return maxSize;}
}

 执行通过。

4.移动零(题号:283)

第一时间想到的是使用双指针进行数值的移动,当时涉及到大量的移动操作,效率非常低下,因此直接新建一个数组进行操作。

class Solution {public void moveZeroes(int[] nums) {int[] result = new int[nums.length];int point = 0;for(int i = 0; i < nums.length; i++) if(nums[i] != 0) result[point++] = nums[i];for(int i = 0; i < nums.length; i++) nums[i] = result[i];}
}

 运行通过。

5.盛最多水的容器(题号:11)

在开始的时候就是想到使用两重遍历来解决,但是最后发现会超时。

class Solution {public int maxArea(int[] height) {int maxSize = 0;for(int i = 0; i < height.length; i++) {//对每条边进行遍历for(int j = i + 1; j < height.length; j++) {int len = Math.min(height[i], height[j]);int currentSize = len * (j - i);maxSize = (maxSize < currentSize) ? currentSize : maxSize;}}return maxSize;}
}

执行超时。

接着开始考虑其他方法,使用双指针来解决,左右向中间进行遍历,小的一侧向内移动。成功解决。 
 

class Solution {public int maxArea(int[] height) {int maxSize = 0;//使用双指针,两个指针分别左右进行压缩int first = 0, second = height.length - 1;while(first < second) {int currentLen = Math.min(height[first], height[second]);int currentSize = currentLen * (second - first);maxSize = (currentSize > maxSize) ? currentSize : maxSize;//小的一方就往内移一格if(height[first] > height[second]) {second--;} else {first++;}}return maxSize;}
}

执行通过。

6.三数之和(题号:15)

最开始的时候想到使用深度优先搜索,但是运行超时了。

class Solution {Set<List<Integer>> result = new HashSet<>();public List<List<Integer>> threeSum(int[] nums) {for(int mid = 0; mid < nums.length; mid++) {check(0, mid, nums.length - 1, nums);}return new LinkedList<List<Integer>>(result);}public void check(int i, int j, int k, int[] nums) {if(i == j || i == k || j == k || i >= nums.length || k < 0) {return ;}if(nums[i] + nums[j] + nums[k] == 0) {List<Integer> newSum = new LinkedList<>();newSum.add(nums[i]);newSum.add(nums[j]);newSum.add(nums[k]);Collections.sort(newSum);result.add(newSum);}//向下遍历check(i + 1, j, k, nums);check(i, j, k - 1, nums);}
}

运行超时。

 所以我们还是需要使用双指针,通过对一个数值作为target,其他两个来凑这个target,从而找到三数,通过双指针来控制和的大小,注意要进行去重。

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> result = new LinkedList<>();//第一位数值作为目标值,且要小于0,这样才存在三数和for(int targetIndex = 0; targetIndex < nums.length - 2; targetIndex++) {if(nums[targetIndex] > 0) {break;}if(targetIndex > 0  && nums[targetIndex] == nums[targetIndex - 1]) {continue;}int i = targetIndex + 1, j = nums.length - 1;while(i < j) {int tempSum = nums[i] + nums[j] + nums[targetIndex];if(tempSum > 0) {//j后退一个,且要去重while(i < j && nums[j] == nums[--j]);} else if(tempSum < 0) {//i前进一个,且要去重while(i < j && nums[i] == nums[++i]);} else {result.add(new LinkedList<Integer>(Arrays.asList(nums[targetIndex], nums[i], nums[j])));//j后退一个,且要去重while(i < j && nums[j] == nums[--j]);//i前进一个,且要去重while(i < j && nums[i] == nums[++i]);}}}return result;}
}

运行通过。

这篇关于Leetcode 热门百题斩(第三天)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/750652

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

AI Toolkit + H100 GPU,一小时内微调最新热门文生图模型 FLUX

上个月,FLUX 席卷了互联网,这并非没有原因。他们声称优于 DALLE 3、Ideogram 和 Stable Diffusion 3 等模型,而这一点已被证明是有依据的。随着越来越多的流行图像生成工具(如 Stable Diffusion Web UI Forge 和 ComyUI)开始支持这些模型,FLUX 在 Stable Diffusion 领域的扩展将会持续下去。 自 FLU

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

Java基础回顾系列-第三天-Lambda表达式

Java基础回顾系列-第三天-Lambda表达式 Lambda表达式方法引用引用静态方法引用实例化对象的方法引用特定类型的方法引用构造方法 内建函数式接口Function基础接口DoubleToIntFunction 类型转换接口Consumer消费型函数式接口Supplier供给型函数式接口Predicate断言型函数式接口 Stream API 该篇博文需重点了解:内建函数式

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划