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]
 
🚀 答案
classSolution{publicint[]twoSum(int[] nums,int target){int[] res =newint[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
题目数据保证列表表示的数字不含前导零

🚀 答案
classSolution{publicListNodeaddTwoNumbers(ListNode l1,ListNode l2){//结果链表虚拟头结点ListNode dummyNode =newListNode(-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 =newListNode(sum);//指针后移到新结点上
            cur = cur.next;//两个工作指针后移if(l1 !=null) l1 = l1.next;if(l2 !=null) l2 = l2.next;}//难点：最后的进位是特殊情况，需要增加新结点并赋val值为1if(carry ==1){
            cur.next =newListNode(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" 是一个子序列，不是子串。
 
🚀 答案
classSolution{publicintlengthOfLongestSubstring(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 =newArrayList<>();//临时的字串存储空间ArrayList<String> tempStr =newArrayList<>();//循环for(int i=0; i<strChar.length; i++){//char -> StringString str =newString(newchar[]{strChar[i]});//判断str是否存在于tempStr中if(tempStr.contains(str)){//先判断tempStr的长度是否大于等于maxStr的长度,大于，才能将最长字串覆盖if(tempStr.size()> maxStr.size()){
                        maxStr =newArrayList<>(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();}return0;}}

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

🚀 答案
classSolution{publicdoublefindMedianSortedArrays(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"

🚀 答案
本题利用了中心扩展法
classSolution{publicStringlongestPalindrome(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 + 1return s.substring(start, end +1);}}

6. Z字形变换

难度系数：🚩🚩

🚀 题目
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
PAHNAPLSIIGYIR
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s,int numRows);
 

示例 1：
输入：s ="PAYPALISHIRING", numRows =4
输出："PINALSIGYAHRPI"
解释：
PINALSIGYAHRPI

示例 2：

输入：s ="A", numRows =1
输出："A"

🚀 答案

每行初始值为i;
第1行和第n行，每次加a =(2n-1)；
中间其余行，每次加b，b初始值为a-2i，其余b = a - b

classSolution{publicStringconvert(String s,int numRows){if(numRows==1){return s;}StringBuilder sb =newStringBuilder();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

🚀 答案
classSolution{publicintreverse(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 。

🚀 答案
publicclassSolution{publicintmyAtoi(String str){char[] chars = str.toCharArray();int n = chars.length;int idx =0;while(idx < n && chars[idx]==' '){// 去掉前导空格
            idx++;}if(idx == n){//去掉前导空格以后到了末尾了return0;}boolean negative =false;if(chars[idx]=='-'){//遇到负号
            negative =true;
            idx++;}elseif(chars[idx]=='+'){// 遇到正号
            idx++;}elseif(!Character.isDigit(chars[idx])){// 其他符号return0;}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 <=30
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

🚀 答案

本次使用了动态规划的方法

classSolution{publicbooleanisMatch(String s,String p){int sl = s.length();int pl = p.length();if(sl !=0&& pl ==0){returnfalse;}//dp[i][j]：s[i...]和p[j...]（从0开始）是否匹配boolean[][] dp =newboolean[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]或者.elseif(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]是*，还能做最后的挣扎elseif(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

🚀 答案
双指针 第一次不看题解有思路 看来多刷题真的很有用
classSolution{publicintmaxArea(int[] height){if(null== height){return0;}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;}}