1-力扣刷题笔记

力扣刷题

一、数组

①双指针

1.移动0

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

 

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：

class Solution {
    public void moveZeroes(int[] nums) {
         //使用双指针法，index1 ,index2 同时指向开头
        //index1， 遍历数组，遇到非0 的就将 index1上的放到 index2上，同时 index1和index2向前移动一位
        //执行完后，再把 index2 到末尾的全部改成0
        if (nums==null) return;
        int index1=0,index2=0;
        for (;index1<nums.length;index1++){
            if (nums[index1]!=0){
                nums[index2++]=nums[index1];
            }
        }
        //
        for (;index2< nums.length;index2++){
            nums[index2]=0;
        }   
    }
}

解析；

//使用双指针法，index1 ,index2 同时指向开头
//index1， 遍历数组，遇到非0 的就将 index1上的放到 index2上，同时 index1和index2向前移动一位
//执行完后，再把 index2 到末尾的全部改成0

原始

4 3 2 7 8 2 3 1

0 1 2 3 4 5 6 7

第一次执行

int x=(4-1)%8=3;

num[3]=7+8=15;

4 3 2 15 8 2 3 1

0 1 2 3 4 5 6 7

第二次执行

int x=(3-1)%8=2;

num[2]=2+8=10;

4 3 10 15 8 2 3 1

0 1 2 3 4 5 6 7

第三次执行

int x=(10-1)%8=1;

num[1]=4+8=12

4 12 10 15 8 2 3 1

0 1 2 3 4 5 6 7

第四次执行

int x=(15-1)%8=6;

num[6]=3+8=11;

4 9 18 11 8 2 11 1

0 1 2 3 4 5 6 7

第五次执行

int x=(8-1)%8=7;

num[7]=1+8=9;

4 9 18 11 8 2 11 9

0 1 2 3 4 5 6 7

第六次执行

int x=(2-1)%8=1;

num[1]=9+8=17;

4 17 18 11 8 2 11 9

0 1 2 3 4 5 6 7

第七次执行

int x=(3-1)%8=2;

num[2]=18+8=26;

4 17 26 11 8 2 11 9

0 1 2 3 4 5 6 7

第八次执行

int x=(9-1)%8=0;

num[0]=4+8=12;

12 17 26 11 8 2 11 9

0 1 2 3 4 5 6 7

4+8=12

11%8=3

2.查找消失的数字(448)

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]

//  查找消失的数字
   //numbs长度 为n ,每个值为 1~n。 遇到1 就让 nums[0]+=n;
   // 2 nums[2-1]+=n;
   //1.遍历 numbs ,每遇到一个x 就让 numbs[x-1] 增加 n，由于numbs 全部在 1~n 必定大于n 。
   //如果没有 i+1 的下标数，那该nums 中下表为 i+1的数则不会增加
   //2.遍历 numbs，若 nums[i] 小于 n，则说明 numbs 中没有 i+1的数。
   //3.还要注意取回修改后的原值。

   public List<Integer> findDisappearedNumbers(int[] nums) {
       int n=nums.length;
       List<Integer> integers = new ArrayList<>();
       for (int num:nums){
           int x=(num-1)%n;
           nums[x]+=n;
       }
       for (int i=0;i<n;i++){
           if (nums[i]<=n){
               integers.add(i+1);
           }
       }
   return integers;
   }

二、链表

1.合并两个有序列表(21)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

链表的合并与数组类似，都可以使用双指针方法进行快速的排序。

//合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    //使用循环+双指针
        //1.使用一个临时变量resultNode 进行储存结果。
        //2.1使用两个指针，同时从 list1 和list2 出发，如果 list1 >= list2，则把 list2 放在 resultNode 后，并将 list 2移动一位
        //2.2.反正则 把 list1 放在 resultNode 后 ，list1 移动一位。
        //3.resultNode移动
         if (list1==null) return  list2;
         if (list2==null) return  list1;
        ListNode resultNode = new ListNode(0);
        ListNode p=resultNode;
        while (list1!=null&&list2!=null){
            if (list1.val>= list2.val){
                p.next=list2;
                list2=list2.next;
            }else {
                p.next=list1;
                list1=list1.next;
            }
            p=p.next;
        }
        if (list1!=null) p.next=list1;
        if (list2!=null) p.next=list2;
        return resultNode.next;
    }