暑期算法打卡----第二天

r囧r小猫 2023-09-28 13:18 14阅读 0赞

**目录**

1、二分查找

2.找出数组排序后的目标下标

3.寻找重复数

4.Binary Deque

说在最后✏️

--------------------

### 1、二分查找 ###

> 题目：[力扣][Link 1]
> 
> 给定一个 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
> 
> 提示：
> 
> 你可以假设 nums 中的所有元素是不重复的。  
> n 将在 \[1, 10000\]之间。  
> nums 的每个元素都将在 \[-9999, 9999\]之间。

**题解：**

Hash表法：

![96aca38bd0bb4adda3f2d86ef45a4abf.png][]

package 暑期特训__社区.day2;
    
    import java.util.HashMap;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2022-07-03 19:30
     */
    public class lc_704二分查找 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int i=scanner.nextInt();
            int[] nums=new int[i];
            HashMap<Integer,Integer>map=new HashMap<>();
            for (int j = 0; j < i; j++) {
                nums[j]=scanner.nextInt();
                map.put(nums[j],j);
            }
            int target=scanner.nextInt();
            System.out.println(map.get(target));
        }
    }

二分法：

![b0a9ee237bb844cabfac1abb9706ef07.png][]

package 暑期特训__社区.day2;
    
    import com.sun.org.apache.xml.internal.serializer.ElemDesc;
    
    import java.util.HashMap;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2022-07-03 19:30
     */
    public class lc_704二分查找 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int i=scanner.nextInt();
            int[] nums=new int[i];
            for (int j = 0; j <i ; j++) {
                nums[j]=scanner.nextInt();
            }
            int target=scanner.nextInt();
    //        System.out.println(hashmap_coding(nums,target));
    //        System.out.println(二分_coding(nums,target));
        }
        //hashMap
        static int hashmap_coding(int[] nums,int target){
            HashMap<Integer,Integer>map=new HashMap<>();
            for (int j = 0; j < nums.length; j++) {
                map.put(nums[j],j);
            }
            if(map.get(target)!=null){
                return map.get(target);
            }else {
                return -1;
            }
        }
    
        /**
         *二分板子   大于等于target的最小值
         */
        static int 二分_coding(int[] nums,int target) {
            int left = 0;//定义左指针
            int rigth = nums.length - 1;//定义右指针
            while (left < rigth) {
                int mid=left+rigth>>1;//移动位置
                if(nums[mid]>=target)rigth=mid;
                else left=mid+1;
            }
            return nums[rigth]==target?rigth:-1;
        }
    }

### 2.找出数组排序后的目标下标 ###

> 题目：[力扣][Link 2]
> 
> 给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。
> 
> 目标下标 是一个满足 nums\[i\] == target 的下标 i 。
> 
> 将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列。
> 
> 示例 1：
> 
> 输入：nums = \[1,2,5,2,3\], target = 2  
> 输出：\[1,2\]  
> 解释：排序后，nums 变为 \[1,2,2,3,5\] 。  
> 满足 nums\[i\] == 2 的下标是 1 和 2 。
> 
> 示例 2：
> 
> 输入：nums = \[1,2,5,2,3\], target = 3  
> 输出：\[3\]  
> 解释：排序后，nums 变为 \[1,2,2,3,5\] 。  
> 满足 nums\[i\] == 3 的下标是 3 。
> 
> 示例 3：
> 
> 输入：nums = \[1,2,5,2,3\], target = 5  
> 输出：\[4\]  
> 解释：排序后，nums 变为 \[1,2,2,3,5\] 。  
> 满足 nums\[i\] == 5 的下标是 4 。
> 
> 示例 4：
> 
> 输入：nums = \[1,2,5,2,3\], target = 4  
> 输出：\[\]  
> 解释：nums 中不含值为 4 的元素。
> 
> 提示：
> 
> 1 <= nums.length <= 100  
> 1 <= nums\[i\], target <= 100

**题解：**

暴力：

![efa28ec090124177a9bbc923753cc5e8.png][]

package 暑期特训__社区.day2;
    
    import java.util.*;
    
    /**
     * @author yx
     * @date 2022-07-03 21:46
     */
    public class lc_2089找出数组排序后的目标下标 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int i=scanner.nextInt();
            int[] nums=new int[i];
            for (int j = 0; j < i; j++) {
                nums[j]=scanner.nextInt();
            }
            int target=scanner.nextInt();
            List<Integer>T=targetIndices(nums,target);
            for (int j = 0; j < T.size(); j++) {
                System.out.print(T.get(j)+" ");
            }
        }
        static List<Integer> targetIndices(int[] nums, int target) {
            List<Integer> T=new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                if(nums[i]==target){
                    T.add(i);
                }
            }
            return T;
        }
    }

### 3.寻找重复数 ###

> 题目：[力扣][Link 3]
> 
> 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 \[1, n\] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
> 
> 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
> 
> 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
> 
> 示例 1：
> 
> 输入：nums = \[1,3,4,2,2\]  
> 输出：2
> 
> 示例 2：
> 
> 输入：nums = \[3,1,3,4,2\]  
> 输出：3
> 
> 提示：
> 
> 1 <= n <= 105  
> nums.length == n + 1  
> 1 <= nums\[i\] <= n  
> nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
> 
> 进阶：
> 
> 如何证明 nums 中至少存在一个重复的数字?  
> 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

**题解：**

![981d7a7e536242db8bb866bb1921c2db.png][]

package 暑期特训__社区.day2;
    
    import java.util.HashMap;
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2022-07-03 22:05
     */
    public class lc_287寻找重复数 {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n=scanner.nextInt();
            int[] nums=new int[n+1];
            for (int i = 0; i < n+1; i++) {
                nums[i]=scanner.nextInt();
            }
            System.out.println(findDuplicate(nums));
        }
        
        static int findDuplicate(int[] nums) {
            HashMap<Integer,Integer> map=new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                /*
                这个地方不知道为啥用containsVlue放在leetcode上会超时
                可能是时间复杂度有区别，到时候再看看
                 */
                if(map.containsKey(nums[i])){
                    return nums[i];
                }else {
                    map.put(nums[i],0);
                }
            }
            return -1;
        }
    }

### 4.Binary Deque ###

> **题目：**[Problem - 1692E - Codeforces (Unofficial mirror by Menci)][Problem - 1692E - Codeforces _Unofficial mirror by Menci]
> 
> E. Binary Deque  
> time limit per test  
> 2 seconds  
> memory limit per test  
> 256 megabytes  
> input  
> standard input  
> output  
> standard output
> 
> Slavic has an array of length
> 
> consisting only of zeroes and ones. In one operation, he removes either the first or the last element of the array.
> 
> What is the minimum number of operations Slavic has to perform such that the total sum of the array is equal to  
> after performing all the operations? In case the sum
> 
> can't be obtained after any amount of operations, you should output -1.  
> Input
> 
> The first line contains a single integer  
> (
> 
> ) — the number of test cases.
> 
> The first line of each test case contains two integers  
> and (
> 
> ) — the length of the array and the needed sum of elements.
> 
> The second line of each test case contains  
> integers (
> 
> ) — the elements of the array.
> 
> It is guaranteed that the sum of  
> over all test cases doesn't exceed
> 
> .  
> Output
> 
> For each test case, output a single integer — the minimum amount of operations required to have the total sum of the array equal to  
> , or -1 if obtaining an array with sum
> 
> isn't possible.  
> Example  
> Input  
> Copy
> 
> 7  
> 3 1  
> 1 0 0  
> 3 1  
> 1 1 0  
> 9 3  
> 0 1 0 1 1 1 0 0 1  
> 6 4  
> 1 1 1 1 1 1  
> 5 1  
> 0 0 1 1 0  
> 16 2  
> 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1  
> 6 3  
> 1 0 1 0 0 0
> 
> Output  
> Copy
> 
> 0  
> 1  
> 3  
> 2  
> 2  
> 7  
> \-1
> 
> Note
> 
> In the first test case, the sum of the whole array is
> 
> from the beginning, so we don't have to make any operations.
> 
> In the second test case, the sum of the array is  
> and we want it to be equal to , so we should remove the first element. The array turns into , which has a sum equal to
> 
> In the third test case, the sum of the array is  
> and we need it to be . We can obtain such a sum by removing the first two elements and the last element, doing a total of three operations. The array turns into , which has a sum equal to

**题解：**

![f827a205535a4c72b4b5945767244bef.png][]

package 暑期特训__社区.day2;
    
    import com.sun.xml.internal.bind.v2.runtime.reflect.Accessor;
    
    import java.util.Scanner;
    
    /**
     * @author yx
     * @date 2022-07-03 23:13
     */
    public class cf_E_BinaryDeque {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int t=scanner.nextInt();
            while (t-->0){
                int n=scanner.nextInt();
                int v=scanner.nextInt();
                int [] s=new int[n+1];
                for (int i = 1; i <=n ; i++) {
                    s[i]=scanner.nextInt();
                    s[i]+=s[i-1];
                }
                if(s[n]<v){
                    System.out.println(-1);
                    continue;
                }
                int res=0x3f3f3f3f;
                for (int i = 1; i <=n ; i++) {
                    int l=i,r=n;
                    while (l<r){
                        int mid=l+r+1>>1;
                        if(s[mid]-s[i-1]<=v)l=mid;
                        else {
                            r=mid-1;
                        }
                    }
                    if(s[r]-s[i-1]==v){
                        res=Math.min(res,n-(r-i+1));
                    }
                }
                System.out.println(res);
            }
        }
    }

### 说在最后✏️ ###

> **算法暑期打卡快乐每一天，如果觉得我的题解对您有帮助的话，欢迎一键三联！**
> 
> ![c0d8d5475c8e4638a7a1914cb0fcf90b.png][]

[Link 1]: https://leetcode.cn/problems/binary-search/
[96aca38bd0bb4adda3f2d86ef45a4abf.png]: https://img-blog.csdnimg.cn/96aca38bd0bb4adda3f2d86ef45a4abf.png
[b0a9ee237bb844cabfac1abb9706ef07.png]: https://img-blog.csdnimg.cn/b0a9ee237bb844cabfac1abb9706ef07.png
[Link 2]: https://leetcode.cn/problems/find-target-indices-after-sorting-array/
[efa28ec090124177a9bbc923753cc5e8.png]: https://img-blog.csdnimg.cn/efa28ec090124177a9bbc923753cc5e8.png
[Link 3]: https://leetcode.cn/problems/find-the-duplicate-number/
[981d7a7e536242db8bb866bb1921c2db.png]: https://img-blog.csdnimg.cn/981d7a7e536242db8bb866bb1921c2db.png
[Problem - 1692E - Codeforces _Unofficial mirror by Menci]: https://codeforc.es/problemset/problem/1692/E
[f827a205535a4c72b4b5945767244bef.png]: https://img-blog.csdnimg.cn/f827a205535a4c72b4b5945767244bef.png
[c0d8d5475c8e4638a7a1914cb0fcf90b.png]: https://img-blog.csdnimg.cn/c0d8d5475c8e4638a7a1914cb0fcf90b.png