LeetCode

2.两数之和

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

• 示例1：

​ ·

​ 输入：l1 = [2,4,3], l2 = [5,6,4]
​ 输出：[7,0,8]
​ 解释：342 + 465 = 807

• 示例2：

  ​ 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  ​ 输出：[8,9,9,9,0,0,0,1]

• 代码实现

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode() {}
   *     ListNode(int val) { this.val = val; }
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
  class Solution {
      public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
          ListNode head1 = l1.next,head2 = l2.next;
          ListNode ret = new ListNode((l1.val + l2.val)%10);
          ListNode temp = ret;//最后返回的结果，指向ret链表的头部
          int outNum = (l1.val + l2.val) / 10; //保留进位
          while(head1 != null || head2 != null){
              if((head1 != null)&&(head2 != null)){//当l1和l2都没被遍历完
                  ret.next = new ListNode((head1.val + head2.val + outNum) % 10);
                  outNum = ((head1.val + head2.val + outNum) / 10);
                  head1 = head1.next;
                  head2 = head2.next;
                  ret = ret.next;
              }else if(head1 != null){//当l1没遍历完
                  ret.next = new ListNode((head1.val + outNum) % 10);
                  outNum = ((head1.val + outNum) / 10);
                  head1 = head1.next;
                  ret = ret.next;
              }else if(head2 != null){
                  ret.next = new ListNode((head2.val + outNum) % 10);
                  outNum = ((head2.val + outNum) / 10);
                  head2 = head2.next;
                  ret = ret.next;
              }
          }
          if(outNum != 0){
                  ret.next = new ListNode(1); //若最后进位不为零，则需要在结果的链表中增加一个值为1 的新节点
          }
          return temp;
      }
  }
  

27.移除元素

 * 给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
   例：输入：nums = [3,2,2,3], val = 3
      输出：2。且数组变为nums = [2,2]（长度之外忽略）

/**
 * @author muchen
 * @create 2023 - 02 - 2023/2/18 16:28
 */
思路：使用循环判断数组中的值是否与val相等，若相等则用异或换位将其放置数组最后，数组长度变量减小（数组长度赋值给可变变量），返回数组长度。
public class LeetCode27 {
    public static void main(String[] args) {
        System.out.println(demo(new int[]{2,3, 2, 2, 4}, 3));
    }
    public static int demo(int[] ints,int val){
        int intLength = ints.length;
        for (int i = 0;i < intLength;)&#123;
            if (ints[i] == val)&#123;
                ints[i] = ints[intLength - 1] ^ ints[i];
                ints[intLength - 1] = ints[intLength - 1] ^ ints[i];
                ints[i] = ints[intLength - 1] ^ ints[i];
                intLength--;
            &#125;else &#123;
                i++;
            &#125;
        &#125;
        return intLength;
    &#125;
&#125;

209.长度最小的子数组

• 题目

  给定一个含有 n 个正整数的数组和一个正整数 target 。
  找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
      示例：输入：target = 7, nums = [2,3,1,2,4,3]
           输出：2
           解释：子数组 [4,3] 是该条件下的长度最小的子数组。
  

• 思路

  1. 使用暴力解法：暴力解法是使用两个for，不断地寻找符合条件的子数组(因为子数组必须是连续的)，外层循环是更新子数组，内层循环是寻找符合条件的子数组。时间复杂度为O(n^2)
  2. 滑动窗口解法：根据前子数组和的大小，不断调节子数组的起始位置，复杂度将为O(n)

• 代码实现滑动窗口解法

  class Solution {
      public int minSubArrayLen(int target, int[] nums) {
          //数组滑动窗口解决问题：时间复杂度O(n)
          int count = 0;//存放数组元素的和，判断是否大于target
          int minsize = Integer.MAX_VALUE;//初始化符合条件的子数组长度，将其置为最大
          int arraySize;
          for(int i = 0,j = 0;i < nums.length;)&#123;
              count += nums[i++];
              while(count >= target)&#123;
                  arraySize = (i - j);
                  minsize = arraySize > minsize ? minsize : arraySize;
                  //这里体现了滑动窗口的精髓之处，不断变更i(子数组的起始位置)
                  count -= nums[j++];
              &#125;
          &#125;
          return minsize == Integer.MAX_VALUE ? 0 : minsize;  //如果值未发生变化则说明没有符合条件的子数组，即返回0；
      &#125;
  &#125;
  

454.四数相加2

• 题目

  给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
  0 <= i, j, k, l < n
  nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
  
  输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
  输出：2
  解释：两个元组如下：
  1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
  

• 思路

  1.使用hash表解法，因为只需要寻找元组个数，所以使用hash表解法更直接简单。
  2.先创建一个hashMap将num1和num2(即数组1和数组2)遍历之后的各种相加结果存入map中(map的value对应两个数组相加的结果，value对应结果出现的次2.数)。
  3.然后再遍历num3和num4同时使用map中的map.containsKey()，查看map中是否含有[-(a+b)],如果存在，则取得key对应的value是多少，将其加到最终需要返回的结果中去。
  

• 实现

  class Solution {
      public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
             //hash表解法
          HashMap<Integer, Integer> map1 = new HashMap<>();
          int count = 0;//存放答案的个数
          for (int n1 : nums1)&#123;
              for (int n2 : nums2)&#123;
                  map1.put(n1 + n2, map1.get(n1+n2) != null ? map1.get(n1+n2)+1:1);
              &#125;
          &#125;
          for (int n3 : nums3)&#123;
              for (int n4 : nums4)&#123;
                  if (map1.containsKey(-(n3+n4)))&#123;
                      count+=map1.get((-n3-n4));
                  &#125;
              &#125;
          &#125;
          return count;
      &#125;
  &#125;
  

541.反转字符串

• 题目

  给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
  
  如果剩余字符少于 k 个，则将剩余字符全部反转。
  如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
  
      示例1：
          输入：s = "abcdefg", k = 2
          输出："bacdfeg"
  

• 思路

  每次让 i += (2 * k)，i 每次移动 2 * k 
  

• 实现

  class Solution {
      public String reverseStr(String s, int k) {
          char[] chars = s.toCharArray();
          char temp;
          int i = 0,j = 0;
          for (;j<=chars.length-1;)&#123;
              j = (i+k-1) > (chars.length-1) ? (chars.length-1) :(i+k-1);
              int temp1 = i,temp2 = j;
              while(temp1<temp2)&#123;
                  temp = chars[temp1];
                  chars[temp1++] = chars[temp2];
                  chars[temp2--] = temp;
              &#125;
              i+=(2*k);
              if(i >= chars.length)&#123;
                  return String.copyValueOf(chars);//将数组转化为字符串并返回
              &#125;
          &#125;
          return String.copyValueOf(chars);
      &#125;
  &#125;