LeetCode精选算法100题,从入门到入赘
文章目录
- 前言
前言
算法是程序员的内功，掌握算法不仅能帮助你在面试中过关斩将，赢取 Dream Offer，更能充分锻炼你的逻辑思维与底层能力，我是一名忠实的 Leetcode 用户，积累的一些个人经验，尽可能地帮助大家少走弯路。
1.两数之和
难度系数：🚩
🚀 题目给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例 1：输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：输入：nums = [3,2,4], target = 6输出：[1,2]示例 3：输入：nums = [3,3], target = 6输出：[0,1] 🚀 答案class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; for(int i=0;i<nums.length;i++){ for(int j=i+1;j<nums.length;j++){ if(nums[i]+nums[j]==target){ res[0]=i; res[1]=j; break; } } } return res; }}
2.两数相加
难度系数：🚩
🚀 题目给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例 1：输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807.示例 2：输入：l1 = [0], l2 = [0]输出：[0]提示：每个链表中的节点数在范围 [1, 100] 内0 <= Node.val <= 9题目数据保证列表表示的数字不含前导零🚀 答案class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //结果链表虚拟头结点 ListNode dummyNode = new ListNode(-1); //结果链表工作指针 ListNode cur = dummyNode; //定义进位 int carry = 0; //模拟两数相加 while(l1 != null || l2 != null){ //本题难点：如果l1为空，l2不为空，则将l1的空对应值置为0，否则置为l1.val。l2亦然。 //此处需要画图理解。 int x = (l1 == null) ? 0 : l1.val; int y = (l2 == null) ? 0 : l2.val; //两数原始和（0-18） int sum = x + y + carry; //进位 carry = sum / 10; //两数和（0-9） sum = sum % 10; //sum = sum / 10; 这里第一次搞错了，记录。 //新建链表结点，将val赋值为sum cur.next = new ListNode(sum); //指针后移到新结点上 cur = cur.next; //两个工作指针后移 if(l1 != null) l1 = l1.next; if(l2 != null) l2 = l2.next; } //难点：最后的进位是特殊情况，需要增加新结点并赋val值为1 if(carry == 1){ cur.next = new ListNode(1); } //返回结果链表的头结点 return dummyNode.next; }}
3.无重复字符的最长子串
难度系数：🚩🚩🚀 题目给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 🚀 答案class Solution { public int lengthOfLongestSubstring(String s) {//如果s为空，length不大于0，是一个空串，就没有向下执行的必要了 if(s != null && s.length() > 0 && s != ""){ //String -> char[] char[] strChar = s.toCharArray(); // 存储最长字串 key:char值，value:index下标 ArrayList<String> maxStr = new ArrayList<>(); //临时的字串存储空间 ArrayList<String> tempStr = new ArrayList<>(); //循环 for(int i=0; i<strChar.length; i++){ //char -> String String str = new String(new char[]{strChar[i]}); //判断str是否存在于tempStr中 if(tempStr.contains(str)){ //先判断tempStr的长度是否大于等于maxStr的长度,大于，才能将最长字串覆盖 if(tempStr.size() > maxStr.size()){ maxStr = new ArrayList<>(tempStr); } //存储重复字符 int reIndex = tempStr.indexOf(str); // 删除tempStr中的重复字节及其之前的字符 for(int j=0;j<=reIndex;j++){ tempStr.remove(0); } } //将当前字符存入tempStr中 tempStr.add(str); } //最终判断 if(tempStr.size() > maxStr.size()){ maxStr = tempStr; } //返回最长字串的长度 return maxStr.size(); } return 0; }}
4.寻找两个正序数组的中位数
难度系数：🚩🚩🚩🚀 题目给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。示例 1：输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2示例 2：输入：nums1 = [1,2], nums2 = [3,4]输出：2.50000解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5🚀 答案class Solution { public double findMedianSortedArrays(int[] a, int[] b) { int n1=a.length,n2=b.length,n3=n1+n2,aindex=0,bindex=0;boolean ds=n3%2==0;int end = n3/2+1;int ne=0,ne1=0,ne2=0; for(int i=0;i<end;i++) { ne = bindex==n2 || ( aindex<n1 &&a[aindex]<=b[bindex] )? a[aindex++]:b[bindex++]; if(i==end-2) ne1=ne; if(i==end-1) ne2=ne; }return ds?(double)(ne1+ne2)/2:ne2; }}
5.最长回文子串
难度系数：🚩🚩🚀 题目给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。示例 2：输入：s = "cbbd"输出："bb"🚀 答案本题利用了中心扩展法class Solution { public String longestPalindrome(String s) { char[] cs = s.toCharArray(); int res = 0; int max = 0; int start = 0, end = 0; String ans = ""; for(int i = 0;i < cs.length; i++){ int left = i - 1, right = i + 1; while(left >= 0 && cs[left] == cs[i]) left--; while(right < cs.length && cs[right] == cs[i]) right++; while(left >= 0 && right < cs.length && cs[left] == cs[right]){ left--; right++; } max = Math.max(max, right - left - 1); res = right - left - 1; //System.out.println(" i = " + i + " l = " + left + " r = " + right); if(res == max){ //left和right退出循环的话会多移动一位，所以要移动回去 start = left + 1; end = right - 1; //System.out.println(start + " " + end); } } //左闭右开区间，所以end + 1 return s.substring(start, end + 1); }}
6. Z字形变换
难度系数：🚩🚩🚀 题目将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：P A H NA P L S I I GY I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows); 示例 1：输入：s = "PAYPALISHIRING", numRows = 4输出："PINALSIGYAHRPI"解释：P I NA L S I GY A H RP I示例 2：输入：s = "A", numRows = 1输出："A"🚀 答案每行初始值为i;第1行和第n行，每次加a = (2n-1)；中间其余行，每次加b，b初始值为a-2i，其余b = a - bclass Solution { public String convert(String s, int numRows) { if(numRows==1){ return s; } StringBuilder sb = new StringBuilder(); int a = 2 * (numRows - 1); for (int i = 0; i < numRows; i++) { int c = i; if(i==0||i==numRows-1){ while (c<s.length()){ sb.append(s.charAt(c)); c = c + a; } }else { int b = a-2*i; while (c < s.length()) { sb.append(s.charAt(c)); c = c + b; b = a - b; } } } return sb.toString(); }}
7.整数反转
难度系数：🚩🚀 题目给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。假设环境不允许存储 64 位整数（有符号或无符号）。 示例 1：输入：x = 123输出：321示例 2：输入：x = -123输出：-321示例 3：输入：x = 120输出：21示例 4：输入：x = 0输出：0🚀 答案class Solution { public int reverse(int x) { long n = 0; while(x != 0) { n = n*10 + x%10; x = x/10; } return (int)n==n? (int)n:0; }}
8.字符串转换整数 (atoi)
难度系数：🚩🚩🚀 题目请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。函数 myAtoi(string s) 的算法如下：读入字符串并丢弃无用的前导空格检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。返回整数作为最终结果。注意：本题中的空白字符只包括空格字符 ' ' 。除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。 示例 1：输入：s = "42"输出：42解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。第 1 步："42"（当前没有读入字符，因为没有前导空格） ^第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'） ^第 3 步："42"（读入 "42"） ^解析得到整数 42 。由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。示例 2：输入：s = " -42"输出：-42解释：第 1 步：" -42"（读入前导空格，但忽视掉） ^第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数） ^第 3 步：" -42"（读入 "42"） ^解析得到整数 -42 。由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。示例 3：、输入：s = "4193 with words"输出：4193解释：第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格） ^第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'） ^第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止） ^解析得到整数 4193 。由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。🚀 答案public class Solution { public int myAtoi(String str) { char[] chars = str.toCharArray(); int n = chars.length; int idx = 0; while (idx < n && chars[idx] == ' ') { // 去掉前导空格 idx++; } if (idx == n) { //去掉前导空格以后到了末尾了 return 0; } boolean negative = false; if (chars[idx] == '-') { //遇到负号 negative = true; idx++; } else if (chars[idx] == '+') { // 遇到正号 idx++; } else if (!Character.isDigit(chars[idx])) { // 其他符号 return 0; } int ans = 0; while (idx < n && Character.isDigit(chars[idx])) { int digit = chars[idx] - '0'; if (ans > (Integer.MAX_VALUE - digit) / 10) { // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。 return negative? Integer.MIN_VALUE : Integer.MAX_VALUE; } ans = ans * 10 + digit; idx++; } return negative? -ans : ans; }}
9.正则表达式匹配
难度系数：🚩🚩🚩🚀 题目给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。'.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 示例 1：输入：s = "aa", p = "a"输出：false解释："a" 无法匹配 "aa" 整个字符串。示例 2:输入：s = "aa", p = "a*"输出：true解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：输入：s = "ab", p = ".*"输出：true解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。 提示：1 <= s.length <= 201 <= p.length <= 30s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母，以及字符 . 和 *。保证每次出现字符 * 时，前面都匹配到有效的字符🚀 答案本次使用了动态规划的方法class Solution { public boolean isMatch(String s, String p) { int sl = s.length(); int pl = p.length(); if(sl != 0 && pl == 0){ return false; } //dp[i][j]：s[i...]和p[j...]（从0开始）是否匹配 boolean[][] dp = new boolean[sl+1][pl+1]; //base case dp[sl][pl] = true;//两个空字符串肯定是匹配的 //s是空时，p可能也可以匹配空字符串 for(int i = pl-1; i >= 0; i--){ if(p.charAt(i) == '*'){ dp[sl][i] = dp[sl][i + 1]; }else{ if(i+1 < pl && p.charAt(i + 1) == '*'){ dp[sl][i] = dp[sl][i+1]; } } } for(int i = sl-1; i >= 0; i--){ for(int j = pl-1; j >= 0; j--){ //1.若p[j]是* if(p.charAt(j) == '*'){ //1.1若p[j-1]=s[i]或. ，那这个*可能把p[j-1]多匹配几个来，也可能匹配成0个 if(p.charAt(j-1) == s.charAt(i) || p.charAt(j-1) == '.'){ dp[i][j] = dp[i+1][j] || dp[i][j+1]; }else{//1.2 若p[j-1]啥也不是，那*只能把p[j-1]匹配为0个，然后看后面了 dp[i][j] = dp[i][j+1]; } }//2.若p[j]=s[i]或者. else if(p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)){ if(j+1 < pl && p.charAt(j+1) == '*'){ //2.1 p[j+1]为*,又有匹配成0个或多个的情况 dp[i][j] = dp[i+1][j] || dp[i][j+1]; }else{//2.2 p[j+1]不是*，那就直接都加1了 dp[i][j] = dp[i+1][j+1]; } }//3. 若p[j]既不是*也不是.和s[i]，但是p[j+1]是*，还能做最后的挣扎 else if(j+1 < pl && p.charAt(j+1) == '*'){ dp[i][j] = dp[i][j+1]; } } } return dp[0][0]; }}
10.盛最多水的容器
难度系数：🚩🚩🚩🚀 题目给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。示例 1：输入：[1,8,6,2,5,4,8,3,7]输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1]输出：1🚀 答案双指针 第一次不看题解有思路 看来多刷题真的很有用class Solution { public int maxArea(int[] height) { if (null == height) { return 0; } int res = 0; // 双指针 int l = 0, r = height.length - 1; while (l < r) { // 记住较短的柱子 int lower = 0; if (height[l] < height[r]) { // 左边短，左边移动 lower = height[l++]; } else { // 右边短，右边移动 lower = height[r--]; } // 用较短的柱子乘上距离得容量 res = Math.max(res, (r + 1 - l) * lower); } return res; }}
