栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法刷题集训第一天

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法刷题集训第一天

个人简介

⭐️个人主页:摸鱼の文酱博客主页‍♂️
博客领域:java编程基础,mysql
写作风格:干货,干货,还是tmd的干货
精选专栏:【Java】【mysql】 【算法刷题笔记】
博主的码云gitee,平常博主写的程序代码都在里面。
支持博主:点赞、收藏⭐、留言
作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!

今日学习内容:数组 练习题目:
题目链接难度
2016. 增量元素之间的最大差值easy
1588. 所有奇数长度子数组的和easy
2239. 找到最接近 0 的数字easy
1475. 商品折扣后的最终价格easy
496. 下一个更大元素 Ieasy
2248. 多个数组求交集easy
1848. 到目标元素的最小距离easy
1652. 拆炸弹easy
1640. 能否连接形成数组easy

文章目录
  • 今日学习内容:数组
  • 练习题目:
  • LeetCode2016. 增量元素之间的最大差值
    • 解题思路
      • 思路一:暴力(模拟)
      • 思路二:贪心
      • 思路三:辅助栈
  • 1588. 所有奇数长度子数组的和
    • 解题思路
      • 思路一:枚举
      • 思路二:前缀和
      • .思路三:数学
  • 2239. 找到最接近 0 的数字
    • 解题思路
      • 思路一:遍历
  • 1475. 商品折扣后的最终价格
    • 解题思路
      • 思路一:模拟
      • 思路二:栈
  • 496. 下一个更大元素 I
    • 解题思路
      • 思路一:暴力
      • 思路二:单调栈
  • 2248. 多个数组求交集
    • 解题思路
      • 思路一:用一个新数组统计每个数字出现次数
  • 1848. 到目标元素的最小距离
    • 解题思路
      • 思路一:暴力
  • 1652. 拆炸弹
    • 解题思路
      • 思路一:模拟
  • 1640. 能否连接形成数组
    • 解题思路
      • 思路一:模拟

LeetCode2016. 增量元素之间的最大差值 解题思路 思路一:暴力(模拟)

  1.思路一:很容易可以想到枚举两个数,符合条件nums[j] > nums[i] 时, 计算差值,最后返回最大差值.
但是这样解是一个for循环嵌套,时间复杂度很高.

public int maximumDifference(int[] nums) {
        int n = nums.length, ans = -1;
        for (int i = 0, min = nums[0]; i < n; i++) {
            if (nums[i] > min) ans = Math.max(ans, nums[i] - min);
            min = Math.min(min, nums[i]);
        }
        return ans;
    }
思路二:贪心

  2.思路二:我们尝试使用一次for循环解决来降低时间复杂度 – 贪心法
枚举每一个数字,在其中找出最小的数字作为min,同时,如果枚举的当前数字nums[j] > min, 就计算他们的差值, 最后返回最大的差值,如果nums[j] < min, 则返回-1

public int maximumDifference(int[] nums) {
        int n = nums.length;
        // 初始化没有找到的情况下的结果
        int max = -1;
        // 进行遍历 ,并且设置初始位置的最小nums[i] 为第一个元素
        for (int i = 0 ,min = nums[0]; i< n ;i++){
            // 如果满足 当前元素的值 大于了 当前所处位置的最小nums[i] 则进行更新我们的最大差值
            if (nums[i] > min) max = Math.max(nums[i] - min,max);
            // 更新我们 当前位置的最小nums[i]
            min = Math.min(min,nums[i]);
        }
        return max;
    }
思路三:辅助栈

  3.思路三:思路也可以参考最小栈,多维护一个辅助栈来进行求解答案数据,思路3和思路2本质相同,但是实现的情况有不同,这里可以进行参考。

public int maximumDifference(int[] nums) {
    	// 初始化辅助栈
        Stack helpStack = new Stack<>();
        helpStack.push(nums[0]);
        // 初始化数据栈
        Stack stack = new Stack<>();
        int max = -1;

        // 初始化
        for (int num : nums){
            stack.push(num);
            helpStack.push(Math.min(num,helpStack.peek()));
        }
		
        while (!stack.isEmpty() ){
        	// 获取判断差值
            max = Math.max(stack.pop() - helpStack.pop(),max);
        }
        // 这步是为了防止i < j 时将其赋值引起的最小差值
        if (max == 0)return -1;
        return max;
    }
1588. 所有奇数长度子数组的和 解题思路 思路一:枚举

  1.思路一:枚举
首先枚举起点,然后枚举终点,枚举终点时进行累加用一个临时变量sum记录
最后判断起点到终点的长度是否为奇数,长度为奇数(j-i+1)%2!=0 , 就将累加的临时变量sum加到结果ret中返回
或者:
遍历数组 arr 中的每个长度为奇数的子数组,计算这些子数组的和。由于只需要计算所有长度为奇数的子数组的和,不需要分别计算每个子数组的和,因此只需要维护一个变量 sum 存储总和即可。
实现方面,令数组 arr 的长度为 n,子数组的开始下标为start,长度为 length,结束下标为 end,则有 0 < n≤start≤end

public int sumOddLengthSubarrays(int[] arr) {
        int sum = 0, ret = 0;
        for(int i=0;i
            sum =0;
            for(int j=i;j
                sum+=arr[j];
                if( (j-i+1) % 2 != 0 ){
                    ret += sum;
                }
            }
        }
        return ret;
    }
    //或者
   public int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;
        int n = arr.length;
        for (int start = 0; start < n; start++) {
            for (int length = 1; start + length <= n; length += 2) {
                int end = start + length - 1;
                for (int i = start; i <= end; i++) {
                    sum += arr[i];
                }
            }
        }
        return sum;
    }
思路二:前缀和

  2.思路二:前缀和
方法一中,对于每个子数组需要使用 O(n) 的时间计算子数组的和。如果能将计算每个子数组的和的时间复杂度从 O(n) 降低到 O(1),则能将总时间复杂度从 O(n^3)降低到 O(n^2)
为了在 O(1)的时间内得到每个子数组的和,可以使用前缀和。创建长度为 n+1 的前缀和数组 prefixSums,其中 0prefixSums[0]=0,当 n1≤i≤n 时,prefixSums[i] 表示数组 arr 从下标 0 到下标 i−1 的元素和。
得到前缀和数组 prefixSums 之后,对于0≤start≤end

public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + arr[i];
        }
        int sum = 0;
        for (int start = 0; start < n; start++) {
            for (int length = 1; start + length <= n; length += 2) {
                int end = start + length - 1;
                sum += prefixSums[end + 1] - prefixSums[start];
            }
        }
        return sum;
    }
.思路三:数学

  3.思路三:数学
事实上,我们可以统计任意值 arr[i]arr[i] 在奇数子数组的出现次数。
对于原数组的任意位置 i 而言,其左边共有 i 个数,右边共有 n−i−1 个数。
arr[i] 作为某个奇数子数组的成员的充要条件为:其所在奇数子数组左右两边元素个数奇偶性相同。
于是问题转换为如何求得arr[i] 在原数组中两边连续一段元素个为奇数的方案数和arr[i] 在原数组两边连续一段元素个数为偶数的方案数。
由于我们已经知道 arr[i] 左边共有 i 个数,右边共有n−i−1 个数,因此可以算得组合数:
  位置 i 左边奇数个数的方案数为(i+1)/2,右边奇数个数的方案数为 (n−i)/2;
  位置 i 左边偶数(非零)个数的方案数为i/2,右边偶数(非零)个数的方案数为 (n−i−1)/2;
考虑左右两边不选也属于合法的偶数个数方案数,因此在上述分析基础上对偶数方案数自增 1。 至此,我们得到了位置 i 左右奇数和偶数的方案数个数,根据arr[i] 位于奇数子数组中, 其左右两边元素个数奇偶性相同 以及「乘法原理」,我们知道 arr[i]arr[i] 同出现在多少个奇数子数组中, 再乘上 arr[i] 即是 arr[i] 对答案的贡献

   public int sumOddLengthSubarrays3(int[] arr) {
        int n = arr.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l1 = (i + 1) / 2, r1 = (n - i) / 2; // 奇数
            int l2 = i / 2, r2 = (n - i - 1) / 2; // 偶数
            l2++; r2++;
            ans += (l1 * r1 + l2 * r2) * arr[i];
        }
        return ans;
    }
2239. 找到最接近 0 的数字 解题思路 思路一:遍历

  1.从 0 下标开始遍历整个数组,创建两个临时变量min(用来记录遇到过的距离0最短的距离),max(用来记录两个数距离相等情况下数值较大的那个数),遍历过程中,如果遇到一个数nums[i]到0的距离小于min,说明找到距离0更近的数,同时更新min和max的值. 如果找到一个数nums[i] = min,只需要将max设置为nums[i] 和 min中较大的那个数

    public int findClosestNumber(int[] nums) {
        int min = Math.abs(nums[0]);
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i]) == min) {
                //nums[i]距离与已知最短距离相等
                max = Math.max(max,nums[i]);   //更新max为 nums[i] 和 max 中较大的数
            }
            //nums[i]的距离不等于已知最短距离 -- nums[i]更近
            if (Math.abs(nums[i]) < min) {
                //更新 min 和 max 的相应值
                min = Math.abs(nums[i]);
                max = nums[i];
            }
        }
        return max;
    
    }
1475. 商品折扣后的最终价格 解题思路 思路一:模拟

  1.双循环,找到每一个元素之后的第一个比她小的数,更新该元素值为 prices[i] - prices[j]

    public int[] finalPrices(int[] prices) {
        for (int i=0;i
            for (int j=i+1;j
                if(prices[i] >= prices[j]){
                    prices[i] -= prices[j];
                    break;
                }
            }
        }
        return prices;
    }
思路二:栈

  2.单调栈

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        Deque deque = new LinkedList<>();
        //从后遍历,栈中保存的是j的数据
        for(int i = n - 1;i >= 0;i--){
            //栈为空,说明没有任何折扣
            if(deque.isEmpty()){
                deque.push(prices[i]);
                ans[i] = prices[i];
            }else{
                //prices[j] > prices[i]的数据都要从栈中弹出,直到prices[j] <= prices[i]
                while (!deque.isEmpty() && deque.peek() > prices[i]) deque.poll();
                if(deque.isEmpty()){
                    //说明没有折扣
                    ans[i] = prices[i];
                }else{
                    //说明有折扣
                    ans[i] = prices[i] - deque.peek();
                }
                deque.push(prices[i]);
            }
        }
        return ans;
    }
}

    public int[] finalPrices(int[] prices) {
         Stackstack=new Stack<>(); //单调栈
        int[]res=new int[prices.length];
        for (int i = 0; i 
            while (!stack.isEmpty()&&prices[stack.peek()]>=prices[i]){
                int index=stack.pop();
                res[index]=prices[index]-prices[i];
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            int index=stack.pop();
            res[index]=prices[index];
        }
        return res;
    }


496. 下一个更大元素 I 解题思路 思路一:暴力

  1.暴力解法。利用多重循环遍历两个数组

//三重for循环
 public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        boolean flag = true;
        for (int i=0;i
            flag = true;
            for (int j=0;j
                if(nums2[j] == nums1[i]) {
                    for (int k=j+1; k
                        if(nums2[k] > nums2[j]) {
                            ans[i] = nums2[k];
                            flag = false;
                            break;
                        }
                    }
                    if(flag) {
                        ans[i] = -1;
                    }
                }
            }
        }
        return ans;
    }
//双重for循环
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int res[]=new int[nums1.length]; //建立一个结果数组
        for (int i = 0; i < nums1.length ; i++) {
            int indexInNums2=-1;
            for (int j = 0; j < nums2.length; j++) {
                if(nums2[j]==nums1[i]){
                    indexInNums2=j;
                }
                if(indexInNums2!=-1&&nums2[j]>nums1[i]){
                    if(j>indexInNums2)
                    {
                        res[i]=nums2[j];
                        break;
                    }
                }
                res[i]=-1;
            }
        }
        return res;
    }
}

思路二:单调栈

  2.单调栈: 我们可以忽略数组nums1,先对将nums2中的每一个元素,求出其下一个更大的元素(单调栈解法)。随后对于将这些答案放入哈希映射(HashMap)中,再遍历数组 nums1,并直接找出答案。

//单调栈
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        Stack stack=new Stack<>();
        HashMap map=new HashMap<>();
        int res[]=new int[nums1.length];
        for (int i = 0; i < nums2.length ; i++) {
            while (!stack.isEmpty()&&nums2[i]>stack.peek()){
                map.put(stack.pop(),nums2[i]);
            }
            stack.push(nums2[i]);
        }
        while (!stack.isEmpty()){
            map.put(stack.pop(),-1);
        }
        for (int i = 0; i 
            res[i]=map.get(nums1[i]);
        }
        return res;
    }
2248. 多个数组求交集 解题思路 思路一:用一个新数组统计每个数字出现次数
    public List intersection(int[][] nums) {
        int[] num = new int[1001];
        List list = new LinkedList();
        for(int i=0;i
            for(int j=0;j
                num[nums[i][j]]++;
            }
        }
        for(int i=0;i
            if(num[i] == nums.length){
                list.add(i);
            }
        }
        return list;
    }
1848. 到目标元素的最小距离 解题思路 思路一:暴力

  1.从数组开头遍历,找到每一个和目标 t a r g e t target target相等的 n u m s [ i ] nums[i] nums[i],然后计算 a b s ( i − s t a r t ) abs(i-start) abs(i−start)的值,用一个变量 m i n min min记录最小的那个值返回

   public int getMinDistance(int[] nums, int target, int start) {
        int min = nums.length;
        for(int i=0;i
            if(nums[i] == target){
                min = min < Math.abs(i-start) ? min : Math.abs(i-start);
            }
        }
        return min;
    }
1652. 拆炸弹 解题思路 思路一:模拟

1.如果 k>0,当前数字 arr[i] 要用下标 i 接下来的 k 个数字之和代替: 由于是循环数组,只需要将用当前下标i+j(1<=j<=k),然后再和原数组长度取余即可得到要加的数的下标
2. 如果 k<0,我们是要向前找 k 个数,但是如果下标 i 所以,需要把当前下标 i+code.length 后,再减去j(1<=j<=k),由于前面加了code.length,还要再取余得到下标
3.如果 k=0,直接返回全为0的数组

	public int[] decrypt(int[] code, int k) {
        int[] arr = new int[code.length];
        if(k>0) {
            for (int i = 0; i < code.length; i++) {
                for (int j = 1; j <= k; j++) {
                //向后找k个数
                    arr[i] += code[(i+j)%code.length];
                }
            }
        } else if(k<0){
            for (int i = 0; i < code.length; i++) {
                for (int j = 1; j <= Math.abs(k); j++) {
                //向前找k个数
                    arr[i] += code[(i+code.length-j)%code.length];
                }
            }
        } else {
        //将数组全初始化为0
            Arrays.fill(arr,0);
        }
        return arr;
    }
1640. 能否连接形成数组 解题思路 思路一:模拟
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948853.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号