2022寒假算法题汇总

题目及示例 给定一个 n 整形数组有序(升序)元素 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值返回下标，否则返回 -1。

示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 并下标为 4

示例 2: 输入: nums = [-1，0，3，5，9，12]， target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

代码：

class Solution { 
             public int search(int[] nums, int target) { 
                int begin=0;        int end=nums.length-1;        int mid;         while(begin<=end){ 
                     mid=(begin end)/2;             if(target>nums[mid]){ 
                         begin=mid 1;             }else if(target<nums[mid]){ 
                         end=mid-1;             }else{ 
                         return mid;             }         }         return -1;     } } 

题解：

1. 二分搜索体现了分治法的思想，
2. 在题目中，数组是有序的，所以不需要排序，降低难度。
3. 设置起始下标为0，终止下标为数组长度-1（nums.length-从而得到mid=(begin end)/2
4. 把target与nums[mid]相比之下，如果target>nums[mid],则target在数组的上部，所以begin=mid 1；如果target<nums[mid]，则target在数组的下部；如果target=nums[mid],返回数组下标。
5. 一直循环，终止条件是begin>end,如果找不到，返回-1
6. 时间复杂度为O(log2n),空间复杂度为O(1)

题目及示例

您是产品经理，目前正在带领团队开发新产品。不幸的是，您的最新版本没有通过质量测试。因为每个版本都是基于以前的版本开发的，所以错误版本后的所有版本都是错误的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致所有版本错误的第一个错误版本。

可以调用 bool isBadVersion(version) 接口来判断版本号 version 单元测试是否有错误。实现一个数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4 输出：4 解释： 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。 示例 2：

输入：n = 1, bad = 1 输出：1

提示：1 <= bad <= n <= 231 - 1

错误代码（时间复杂度太高，超时）

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */

public class Solution extends VersionControl { 
        
    public int firstBadVersion(int n) { 
        
        int first=1;
        int last=n;
        int result=1;
        if(n==1){ 
        
            result=1;
        }else{ 
        
            while(first+1<=last){ 
        
                int mid=(first+last)/2;
                if(isBadVersion(mid)&&isBadVersion(mid+1)){ 
        
                    last=mid;
                }else if((!isBadVersion(mid))&&(!isBadVersion(mid+1))){ 
        
                    first=mid;
                }else if((!isBadVersion(mid))&&isBadVersion(mid+1)){ 
        
                    result=mid+1;
                    break;
                }
            }
        }
        return result;
    }
}

正确代码

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */

public class Solution extends VersionControl { 
        
    public int firstBadVersion(int n) { 
        
        int first=1;
        int last=n;
        while(first<last){ 
        //循环直至左右端点相同
            int mid=first+(last-first)/2;//防止计算时溢出
            if(isBadVersion(mid)){ 
        
                last=mid;//[first,mid]
            }else { 
        
                first=mid+1;//[mid+1,last]
            }
        }
        return first;//first==last
    }
}

题解：

1. 首先，题目中提到尽量减少对调用 API 的次数，即是少调用isBadVersion(version) 函数。但是错误代码中，我调用了六次此函数，会导致时间的增加。因为我一直认为必须要前一个版本是false，后一个版本是true才行。
2. 正确代码中并不在while循环中找到第一个错误版本，而是通过缩小区间，最后只剩一个（first=last）,first或者last就是第一个错误版本。
3. 最重要的一点，我提交了好几次，都是超时。原因在于n和bad都是很大的数字 （1 <= bad <= n <= 231 - 1）,mid不能直接等于(first+last)/2,要等于first+(last-first)/2，以防止计算时溢出。

题目及示例

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num 1：我选出的数字比你猜的数字大 pick > num 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num 返回我选出的数字。

示例 1：

输入：n = 10, pick = 6 输出：6

示例 2：

输入：n = 1, pick = 1 输出：1

提示：1 <= n <= 2^31 - 1 1 <= pick <= n

代码：

public class Solution extends GuessGame { 
        
    public int guessNumber(int n) { 
        
        int first=1;
        int last=n;
        while(first<last){ 
        
            int mid=first+(last-first)/2;
            if(guess(mid)<=0){ 
        
                last=mid;//[first,mid]
            }else{ 
        
                first=mid+1;//[mid+1,last]
            }
        }
        return first;//first=end
    }
}

题目及示例

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log2 n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2:

输入: nums = [1,3,5,6], target = 2 输出: 1 示例 3:

输入: nums = [1,3,5,6], target = 7 输出: 4 示例 4:

输入: nums = [1,3,5,6], target = 0 输出: 0

代码

class Solution { 
        
    public int searchInsert(int[] nums, int target) { 
        
       int begin=0;
       int end=nums.length-1;
       int mid;
        while(begin<=end){ 
        
            mid=(begin+end)/2;
            if(target>nums[mid]){ 
        
                begin=mid+1;
            }else if(target<nums[mid]){ 
        
                end=mid-1;
            }else{ 
        
                return mid;
            }
        }
        return begin;
    }
}

题解

1. 这一题和704二分查找差不多，不同的是没查到目标数字的话就输出应该插入的下标，正好是begin。
2. 时间复杂度为O(log2n) ，空间复杂度为O(1)

题目及示例

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

代码：

class Solution { 
        
    public int[] sortedSquares(int[] nums) { 
        
        int []a=new int[nums.length];
        for(int i=0;i<nums.length;i++){ 
        
            a[i]=nums[i]*nums[i];
        }
        Arrays.sort(a);
        return a;
    }
}

题解

1. 先进行平方，然后用java自带的Arrays.sort函数进行排序。
2. 时间复杂度为O(n),空间复杂度为O(n)

题目及示例 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]

提示： 1 <= nums.length <= 105 -2^31 <= nums[i] <= 2^31 - 1 0 <= k <= 105 代码

class Solution { 
        
    public void rotate(int[] nums, int k) { 
        
        int []a=new int[nums.length];
        int n=nums.length;
        for(int i=0;i<n;i++){ 
        
            a[(i+k)%n]=nums[i];
        }
         //for(int i=0;i<n;i++){ 
        
         // nums[i]=a[i];
        //}
        // System.out.print("[");
        // for(int j=0;j<n;j++){ 
        
        // System.out.print(nums[j]);
        // if(j!=n-1){ 
        
        // System.out.print(",");
        // }
        // }
        // System.out.print("]");
        System.arraycopy(a,0,nums,0,n);//浅度复制,把a数组赋值给nums数组
    }
}

题解：

1. 这题我犯了一个错误，以为只要a[(i+k)%n]=nums[i]，输入a数组即可，但是还要把a数组赋值给nums才行
2. 我用的是for循环输出，看到官方解法， System.arraycopy(a,0,nums,0,n);
3. System中提供了一个native静态方法arraycopy(),可以使用这个方法来实现数组之间的复制。对于一维数组来说，这种复制属性值传递，修改副本不会影响原来的值。对于二维或者一维数组中存放的是对象时，复制结果是一维的引用变量传递给副本的一维数组，修改副本时，会影响原来的数组。
4. public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length) src表示源数组，srcPos表示源数组要复制的起始位置，desc表示目标数组，destPos表示m目标数组要复制的起始位置,length表示要复制的长度。
5. 时间复杂度为O(n),空间复杂度为O(n)

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

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

说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

代码：

class Solution { 
        
    public void moveZeroes(int[] nums) { 
        
        for(int i=0;i<nums.length;i++){ 
        
            for(int j=i;j<nums.length;j++){ 
        
                if(nums[i]==0&&nums[j]!=0){ 
        
                    nums[i]=nums[j];
                    nums[j]=0;
                    break;
                }
            }
        }
    }
}

题解：

1. 双重for循环，遇到0，再遇到一个不是0的数，则交换。
2. 对于数组长度很大的不适用
3. 时间复杂度为O（n）,空间复杂度为O(1)

题目及示例

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,“e”,“l”,“l”,“o”] 输出：[“o”,“l”,“l”,“e”,“h”]

示例 2：

输入：s = [“H”,“a”,“n”,“n”,“a”,“h”] 输出：[“h”,“a”,“n”,“n”,“a”,“H”]

提示： 1 <= s.length <= 105 s[i] 都是 ASCII 码表中的可打印字符

代码：

class Solution { 
        
    public void reverseString(char[] s) { 
        
        for(int i=0;i<s.length/2;i++){ 
        
            char t;
            t=s[i];
            s[i]=s[s.length-i-1];
            s[s.length-i-1]=t;
        }
    }
}

题解：

1. 从中间分开，第一个与最后一个字符交换，依次递推。
2. 时间复杂度为O(n），空间复杂度为O(1)

题目及示例 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入：“Let’s take LeetCode contest” 输出：“s’teL ekat edoCteeL tsetnoc”

提示： 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

代码1：

class Solution { 
        
    public String reverseWords(String s) { 
        
        String []str=s.split(" ");
        String afterReverse="";
        for(int i=0;i<str.length;i++){ 
        
            StringBuffer sb = new StringBuffer(str[i]);
            if(i!=str.length-1){ 
        
                afterReverse+=sb.reverse().toString()+" ";
            }else{ 
        
                afterReverse+=sb.reverse().toString();
            }
            
        }
        return afterReverse;
    }
}

代码2:

class Solution { 
        
    public String reverseWords(String s) { 
        
        String []str=s.split(" ");
        StringBuffer sb = new StringBuffer();
        StringBuffer sb1 = new StringBuffer();
        for(int i=0;i<str.length;i++){ 
        
            sb = new StringBuffer(str[i]);
            if(i!=str.length-1){ 
        
                sb1.append(sb.reverse());
                sb1.append(" ");
            }else{ 
        
                sb1.append(sb.reverse());
            }
        }
        return sb1.toString();
    }
}

题解：

1. 首先把字符串以空格为分割，分成字符串数组；for循环，用reverse反转，toString转成字符串
2. 代码2和代码1不同之处在于，用了StringBuffer的append方法把反转后的字符串存在其中，这样比字符串相加所用的时间短。
3. 时间复杂度为O(n),空间复杂度为O(n)

题目及示例 给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。

示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2： 输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：给定链表的结点数介于 1 和 100 之间。

代码：

/** - 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 middleNode(ListNode head) { 
        
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){ 
        
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}

题解：

• 快慢指针法，slow是慢指针，一次走一步；fast是快指针，一次走两步。
• 当fast走到尽头的时候，slow正好走到中间结点位置

题目及示例

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2： 输入：head = [1], n = 1 输出：[]

示例 3： 输入：head = [1,2], n = 1 输出：[1]

提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz

代码：

/** - 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 removeNthFromEnd(ListNode head, int n) { 
        
       ListNode dummy=new ListNode(0,head);
       ListNode first=head;
       ListNode second=dummy;
       for(int i=0;i<n;i++){ 
        
           first=first.next;
       }
       while(first!=null){ 
        
           first=first.next;
           second=second.next;
       }
       second.next=second.next.next;
       ListNode ans=dummy.next;//头结点
       return ans;
    }
}

题解：

• first指向头指针，second指向哑指针（哑指针指向头指针）。两者相隔n，则当first指向末尾时，second的下一个就是要删除的结点。
• 删除节点：second指向删除节点的下一个结点（second.next=second.next.next;）
• 头结点是哑结点的下一个结点。

题目及示例 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3: 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

示例 4: 输入: s = “” 输出: 0

提示： 0 <= s.length <= 5 * 10⁴ s 由英文字母、数字、符号和空格组成

代码：

class Solution { 
        
    public int lengthOfLongestSubstring(String s) { 
        
        int n=s.length();
        Set<Character> set=new HashSet<>();
        int right=-1;
        int max=0;
        for(int left=0;left<n;left++){ 
        
            if(left!=0){ 
        
                set.remove(s.charAt(left-1));
            }
            while(right+1<n&&!set.contains(s.charAt(right+1)))
            { 
        
                set.add(s.charAt(right+1));
                right++;
            }
            max=Math.max(max,right-left+1);
        }
        return max;
    }
}

题解：