devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode力扣热题一百·自我解法记录（JAVA版本·仅代码）_力扣直播课程 百度云

作者：IT小白 | 2024-02-26 19:03:18

赞

踩

力扣直播课程 百度云

1. 两数之和·哈希表

题目链接：力扣·两数之和·简单

  1. import java.util.HashMap;
  2.  
  3. class Solution {
  4.     public int[] twoSum(int[] nums, int target) {
  5.         //创建哈希表
  6.             HashMap<Integer,Integer> map = new HashMap<>();
  7.         //向哈希表中录入元素
  8.             for(int i=0;i<nums.length;i++)
  9.             {
  10.                 map.put(nums[i],i);
  11.             }
  12.         //寻找固定值
  13.             for(int j=0;j<nums.length;j++)
  14.             {
  15.                 if(map.containsKey(target-nums[j]))//找到了，返回两个下标
  16.                 {
  17.                     int index = map.get(target-nums[j]);
  18.                     if(j!=index) return new int[]{j,index};
  19.                 }
  20.             }  
  21.         //要有一个出口(返回空数组)
  22.         return new int[0];
  23.     }
  24. }

2. 两数之和

初始思路：把两个数读出来直接加，不行，太多错误，会导致无法进位（我他*&*（）*反正就是不能进位，改成long , double都不行）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; } //赋值
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }//链接函数
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  13.         //读数l1,存入x
  14.             int  i=1;
  15.             int  x=0;
  16.             while(l1 != null){
  17.                 x = x + l1.val*i;
  18.                 i = i*10;
  19.                 l1 = l1.next;
  20.             }
  21.         //读数l2,存入y
  22.             i=1;
  23.             int  y=0;
  24.             while(l2 != null){
  25.                  y= y + l2.val*i;
  26.                  i = i*10;
  27.                  l2 = l2.next;
  28.             }
  29.         //加和
  30.             int z = x+y;
  31.         //分离数位，尾插法建立链表
  32.             ListNode head = null;//建立头结点
  33.             ListNode tail = null;//建立尾结点
  34.         //特殊处理：如果和为0
  35.             if(z==0)
  36.             {
  37.                 head = new ListNode(0);
  38.             }
  39.         //正常情况
  40.             while(z!=0){
  41.                 if(head == null)
  42.                 {
  43.                     head = tail = new ListNode(z%10);
  44.                 }
  45.                 else{
  46.                     tail.next = new ListNode(z%10);
  47.                     tail = tail.next;
  48.                 }
  49.                 z = z/10; 
  50.             }
  51.         //返回头指针
  52.         return head;
  53.     }
  54. }

思路2·模拟进位

【个人超级复杂版进位操作（数字大的时候不行）】

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  13.         //建立和链表
  14.         ListNode head = null;
  15.         ListNode tail = null;
  16.         //设定一个计数器i,和一个代表乘以几个10的计数器，以及一个进位记录jin
  17.         int i = 0;
  18.         int jin = 0;
  19.         //同步从个位读取两个链表，直到其中一个停止
  20.         while(l1!=null || l2!=null)
  21.         {
  22.             int x = l1.val + l2.val;
  23.             int x0=x;
  24.  
  25.             //建立新链表
  26.             if(head==null)
  27.             {
  28.                 head = tail = new ListNode(x%10+jin);
  29.             }
  30.             else{
  31.                 tail.next = new ListNode(x%10+jin);
  32.                 tail = tail.next;
  33.             }
  34.             //计算下次是否需要进位
  35.             if(x0>9)//需要进位
  36.                 jin = 1;
  37.             else//不需要进位
  38.                 jin = 0;
  39.             //继续循环
  40.             l1 = l1.next;
  41.             l2 = l2.next;
  42.         }
  43.         //两个链表其中一个先终止了,把剩下的那个链表直接接入结果链表
  44.         if(l1!=null)
  45.         {
  46.         while(jin!=0 && l1!= null)
  47.         {
  48.             int x = l1.val + jin;
  49.             int x0=x;
  50.  
  51.             tail.next = new ListNode(x%10);
  52.             tail = tail.next;
  53.             //判断下一位需不需要进位
  54.  
  55.             //计算下次是否需要进位
  56.             if(x0>9)//需要进位
  57.                 jin = 1;
  58.             else//不需要进位
  59.                 jin = 0;
  60.             l1 = l1.next;
  61.         }
  62.         if(jin!=0 && l1==null)//进位进出多一位的情况
  63.         {
  64.             tail.next = new ListNode(1);
  65.             tail = tail.next;
  66.         }
  67.         if(jin==0 && l1!=null)//需要把后续连入的情况
  68.         {
  69.             tail.next = l1;
  70.         }
  71.         }
  72.  
  73.         if(l2!=null)
  74.         {
  75.         while(jin!=0 && l2!= null)
  76.         {
  77.             int x = l2.val + jin;
  78.             int x0=x;
  79.  
  80.             tail.next = new ListNode(x%10);
  81.             tail = tail.next;
  82.             //判断下一位需不需要进位
  83.  
  84.             //计算下次是否需要进位
  85.             if(x0>9)//需要进位
  86.                 jin = 1;
  87.             else//不需要进位
  88.                 jin = 0;
  89.             l2 = l2.next;
  90.         }
  91.         if(jin!=0 && l2==null)//进位进出多一位的情况
  92.         {
  93.             tail.next = new ListNode(1);
  94.             tail = tail.next;
  95.         }
  96.         if(jin==0 && l2!=null)//需要把后续连入的情况
  97.         {
  98.             tail.next = l2;
  99.         }
  100.         }
  101.  
  102.         return head;
  103.     }
  104. }

答案简洁版进位

重点就在于，先结束的链表用0补足

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  13.         //新建链表，给出头尾指针
  14.         ListNode head = null, tail = null;
  15.         //carry变量用来记录进位，需要进位则为1，否则为0
  16.         int carry = 0;
  17.         //两个链表只要还有一个非空，就继续操作
  18.         while (l1 != null || l2 != null) {
  19.             //这个方法里最重要的地方就在于，要用0补足先空了的链表
  20.             int n1 = l1 != null ? l1.val : 0;
  21.             int n2 = l2 != null ? l2.val : 0;
  22.             //计算新链表当前位的值，并建立链表
  23.             int sum = n1 + n2 + carry;
  24.             if (head == null) {
  25.                 head = tail = new ListNode(sum % 10);
  26.             } else {
  27.                 tail.next = new ListNode(sum % 10);
  28.                 tail = tail.next;
  29.             }
  30.             carry = sum / 10;//计算进位
  31.             //推动链表向下运算
  32.             if (l1 != null) {
  33.                 l1 = l1.next;
  34.             }
  35.             if (l2 != null) {
  36.                 l2 = l2.next;
  37.             }
  38.         }
  39.         //如果都算完了还有进位，则意味着要多出一位，因为是加法，所以多出来的一位肯定是1
  40.         if (carry > 0) {
  41.             tail.next = new ListNode(carry);
  42.         }
  43.         return head;
  44.     }
  45. }

3.最长不重复子串·队列问题·滑动窗口

题目链接：

力扣-最长不重复子串

自我解题方法（错）（语法虽然没有毛病了，思路也没毛病，但运算结果就是不对。呵。）

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3.  
  4. class Solution {
  5.     public int lengthOfLongestSubstring(String s) {
  6.         //建立一个队列
  7.             Queue<String> queue = new LinkedList();
  8.         //遍历字符串，送入队列并计数
  9.             int len = 1;
  10.             int max = len;
  11.             int first = 1;
  12.             for(int i=0;i<s.length();i++)
  13.             {
  14.                 //如果是第一个元素，直接入队
  15.                 if(first == 1)
  16.                 {
  17.                     first = 0;
  18.                     queue.offer(s.substring(i,i+1));//入队
  19.                 }
  20.                 //非首元素
  21.                 else{
  22.                     //如果和队首元素相同，得到当前不重复子串长度
  23.                     if(s.substring(i,i+1)==queue.element())
  24.                     //if(queue.element().equals(s.substring(i,i+1)))
  25.                     {
  26.                         //首先，进行不重复子串长度最大值比较
  27.                         if(len > max)
  28.                         {
  29.                             max = len;//更新max值
  30.                             len = 1; //len重新计数
  31.                         }
  32.                         //然后，弹出队首元素
  33.                         String del = queue.poll();
  34.                     }
  35.                     else{//不相同，则将该元素入队并计数
  36.                         queue.offer(s.substring(i,i+1));//入队
  37.                         len++;//不重复子串长度计数
  38.                     }
  39.                 }
  40.             }
  41.             if(len>max)//防止最大不重复子串在最后
  42.                 max = len;
  43.             //返回max值
  44.             return max;
  45.     }
  46. }

正解：

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         // 哈希集合，记录每个字符是否出现过
  4.         Set<Character> occ = new HashSet<Character>();
  5.         int n = s.length();
  6.         // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  7.         int rk = -1, ans = 0;
  8.         for (int i = 0; i < n; ++i) {
  9.             if (i != 0) {
  10.                 // 左指针向右移动一格，移除一个字符
  11.                 occ.remove(s.charAt(i - 1));
  12.             }
  13.             while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
  14.                 // 不断地移动右指针
  15.                 occ.add(s.charAt(rk + 1));
  16.                 ++rk;
  17.             }
  18.             // 第 i 到 rk 个字符是一个极长的无重复字符子串
  19.             ans = Math.max(ans, rk - i + 1);
  20.         }
  21.         return ans;
  22.     }
  23. }

6. 最长回文子串

用到的主要结构：哈希表

【主要思想】

遍历字符串，每出现一个没见过的字符，就将其加入哈希表；哈希表中只保存每个元素第一次出现的位置。

如果在遍历字符串时，发现该元素已经出现过了，那么就查找哈希表，将（第一次出现的位置下标，当前下标）这个子字符串提取出来，判断这个子字符串是不是回文串。

如果是，则判断是否需要更新max值（最长回文串长度值）；如果不是，则继续向下便利字符串。

（为了保证哈希表里只保存每个元素第一次出现的位置，只有当该元素不再哈希表中时才向内添加，否则不添加。）

【需要进行的特殊情况处理】

① 整个字符串无重复的情况——哈希表长度为零，返回第一个元素即可；

② 整个字符串全是重复的情况——哈希表为长度为1，直接返回整个字符串即可；

代码记录：

  1. import java.util.HashMap;
  2. class Solution {
  3.     public String longestPalindrome(String s) {
  4.         //建立哈希表，存储内容为字符元素及其下标
  5.         HashMap<Character,Integer> map = new HashMap<>();
  6.         int max = 0;
  7.         int[] res = {0,0};//保存最长字符串的两个下标
  8.  
  9.         //遍历字符串，并存入哈希表
  10.         int len = s.length();
  11.  
  12.         //特殊情况处理——如果该字符串中没有重复元素，那么就返回第一个字符值
  13.         boolean nosame = true;
  14.  
  15.         //遍历字符串
  16.         for(int i=0;i<len;i++)
  17.         {         
  18.             //判断哈希表中是否已经有该元素
  19.             if(map.containsKey(s.charAt(i))){
  20.                 nosame=false;
  21.                 //如果有该元素，则找到该元素第一次出现的位置
  22.                 int x=map.get(s.charAt(i));
  23.                 //判断该子字符串是否为回文串，如果是，则计数
  24.                     //首先截取该子串
  25.                     String s1 = s.substring(x,i+1);//因为是前闭后开
  26.                     //因为存在溢出问题，所以不截取该子串呢？
  27.  
  28.                     //判断是否是回文串
  29.                     int i1=x;//头指针
  30.                     int j1=i;//尾指针
  31.                     boolean hui = true;
  32.                     while(i1 < j1+1)
  33.                     {
  34.                         if(s.charAt(i1)!=s.charAt(j1))
  35.                         {
  36.                             hui = false;
  37.                             break;
  38.                         }
  39.                         else{
  40.                             i1++;
  41.                             j1--;
  42.                         }
  43.                     }
  44.                     //如果是回文串，更新max
  45.                     if(hui == true)
  46.                     {
  47.                     int lens1 = s1.length();
  48.                     if(lens1 > max)
  49.                     {
  50.                         max = lens1;
  51.                         res[0]=x;
  52.                         res[1]=i+1;
  53.                     }
  54.                     }
  55.                     
  56.                 //如果当前元素为重复元素，那么不存入当前元素，即可保证哈希表中记录的是该元素第一次出现的位置
  57.             }
  58.             //如果该元素未重复，则将元素当前位置插入哈希表；
  59.             map.put(s.charAt(i),i);
  60.         }
  61.         //无重复字符的特殊处理
  62.         if(nosame == true)
  63.         {
  64.             return s.substring(0,1);
  65.         }
  66.         //全重复字符的特殊处理
  67.         if(map.size()==1)
  68.         {
  69.             return s;
  70.         }
  71.         //返回最长回文子串
  72.         return s.substring(res[0],res[1]);
  73.     }
  74. }

此题力扣的官方解法是动态规划，动态规划上学的时候我就没学明白，放在这里供大家参考吧。

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         if (s == null || s.length() < 1) {
  4.             return "";
  5.         }
  6.         int start = 0, end = 0;
  7.         for (int i = 0; i < s.length(); i++) {
  8.             int len1 = expandAroundCenter(s, i, i);
  9.             int len2 = expandAroundCenter(s, i, i + 1);
  10.             int len = Math.max(len1, len2);
  11.             if (len > end - start) {
  12.                 start = i - (len - 1) / 2;
  13.                 end = i + len / 2;
  14.             }
  15.         }
  16.         return s.substring(start, end + 1);
  17.     }
  18.  
  19.     public int expandAroundCenter(String s, int left, int right) {
  20.         while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
  21.             --left;
  22.             ++right;
  23.         }
  24.         return right - left - 1;
  25.     }
  26. }
  27.  
  28.

11.盛最多水的容器

【原题地址】

力扣·盛最多水的容器·中等难度

【个人思路】

我的思路就是用双重循环进行暴力破解。每次遍历时，我只关心比我矮的垂线，因为这个比我矮的垂线会决定水位的高度，而我们之间下标差的绝对值就是水位的宽度。

故，暴力破解，高效完美。

但是力扣里面的输入例子里，非要给一个巨大的输入，你他喵的返回值就是个Int，整那么大谁能不溢出？！

哼。

在此记录一下我的暴力破解代码：

  1. import java.lang.Math;
  2.  
  3. class Solution {
  4.     public int maxArea(int[] height) {
  5.         //暴力破解法
  6.  
  7.         //遍历数组，每次只关心值比当前值小的垂线，然后计算面积，不断更新迭代面积的最大值
  8.         int max = 0;
  9.         for(int i=0;i<height.length;i++)
  10.         {
  11.             for(int j=0;j<height.length;j++)
  12.             {
  13.                 if(height[j]<height[i]+1)//如果j的垂线比i矮（或相等），那么它将决定水位的高度
  14.                 {
  15.                     int size = height[j]*Math.abs(j-i); //计算面积
  16.                     if(size>max)
  17.                     {
  18.                         max = size;//更新max值
  19.                     }
  20.                 }
  21.             }
  22.         }
  23.  
  24.         //返回最大值
  25.         return max;
  26.     }
  27. }

力扣官方的思路是这样的：

设置两个指针，一个头一个尾，每次就算这两个指针组成的长方体的面积；每次只移动比较矮的那个垂线的指针。

emmm我打了一遍代码，这次倒是通过了。不得不说官方这个时间复杂度确实小的多，只进行一次遍历。

  1. import java.lang.Math;
  2.  
  3. class Solution {
  4.     public int maxArea(int[] height) {
  5.         int i=0;//设置头指针
  6.         int j=height.length-1;//设置尾指针
  7.  
  8.         int max = 0;
  9.         int size = 0;
  10.  
  11.         while(i<j) //两指针交汇即为遍历完整个链表
  12.         {
  13.             size = Math.min(height[i],height[j])*(j-i);//两个数里更小的那个决定水位高度
  14.             if(size > max)
  15.             {
  16.                 max = size;
  17.             }
  18.  
  19.             //只移动较小值的指针
  20.             if(Math.min(height[i],height[j])==height[i])
  21.             {
  22.                 i++;
  23.             }
  24.             else{
  25.                 j--;
  26.             }
  27.         }
  28.  
  29.         return max;
  30.     }
  31. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/146133
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号