0


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;}}

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

标签: leetcode 算法 java

本文转载自: https://blog.csdn.net/weixin_41645135/article/details/124899610
版权归原作者 IT邦德 所有, 如有侵权,请联系我们删除。

“LeetCode精选算法100题,从入门到入赘”的评论:

还没有评论