数据结构刷题训练营3

简介: 数据结构刷题训练营3

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。


示例 1:


输入:nums1 = [1,2,2,1], nums2 = [2,2]


输出:[2,2]


示例 2:


输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]


输出:[4,9]


提示:


1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000


进阶:


如果给定的数组已经排好序呢?你将如何优化你的算法?


如果 nums1 的大小比 nums2 小,哪种方法更优?


如果 nums2 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?


根据题意,我们可以进行一下思考:


第一步,进行排序


申请一个新的数组(最后可以返回这个数组)可以用来存储两个数组中相同的数据!!


将排序好的两个数组进行比较!


经过上面三步的具体分析,我们可以有:一下的代码:


<code class="kdocs-plaintext hljs">class Solution {
   public int[] intersect(int[] nums1, int[] nums2) {
        //先对数组进行排序
        //将排好序的数组进行双指针比较!!
        //首先对两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //求出两个数组的最小值(此时申请的数组,可能是最有效的)
        int length1 = nums1.length;
        int length2 = nums2.length;
        //比较大小
        int max_length = length1 > length2 ? length1 :length2 ;
        //申请一个(相对)有效的数组,最后可以返回这个数组!
        int[] array = new int[max_length];
        int index1 =0;
        int index2 =0;
        int index =0;
         while(index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            }else if (nums1[index1] > nums2[index2]) {
                index2++;
            }else  {
                array[index] =nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(array, 0, index);
    }
}</code>


在上面的代码中:注释都已经标注的很清楚了!所以,笔者不在进行详解了!!毕竟代码很简单!!


121. 买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。


你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。


返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。


示例 1:


输入:[7,1,5,3,6,4]


输出:5


解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。


注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。


示例 2:


输入:prices = [7,6,4,3,1]


输出:0


解释:在这种情况下, 没有交易完成, 所以最大利润为 0。


提示:


1 <= prices.length <= 105
0 <= prices[i] <= 104


对于该题目,笔者有着一下的思考:


在这个测试用列中:[7,1,5,3,6,4],我们可以看出来:最小的数据为:1,在数据1之后的最大数据为6,所以差值为5!!


我们可以有着一下的思路:


第一次遍历的时候,找到最小的价格!记录此时的最小价格及其对应的下标!!


通过判断最小价格位置处的下标与数组总长度!来确定是否继续往下走!


第二次遍历,是从最小下标的位置处开始遍历!然后找到最大的数据!


因此,有着一下的代码:


<code class="kdocs-plaintext hljs">public class Solution {
    public static int maxProfit(int[] prices) {
        //第一步,遍历一遍数组,找到最小位置
        //min:最小的数据
        //index:记录最小数据处的下标
        int min =prices[0];
        int index =0;
        for (int i = 0; i < prices.length; i++) {
            if (min > prices[i]) {
                min = prices[i];
                index =i;
            }
        }
        //此时已经拿到最小数据min,及其最小数据所在的位置index了!
        //判断:index是否是最后一个元素??
        if (index == prices.length-1) {
            return  0;
        }
        //从index位置处开始遍历,寻找最大的数据!
        int max =prices[index];//记录最大的数据
        for (int i = index; i < prices.length; i++) {
            if (max < prices[i]) {
                max = prices[i];
            }
        }
        //此时拿到最大的数据
        return max-min;
    }
    // public static void main(String[] args) {
    //     int[] array ={2,4,1};
    //     int ret = maxProfit(array);
    //     System.out.println(ret);
    // }
}</code>


不过,此代码在IDEA上面可以跑过,但是,在力扣上面显示:[2,4,1]这个测试用列没有跑过!!不知道为什么!!我也不知道为什么!!尴尬了!!但是在IDEA中来进行调试,也没有任何的问题!!等待大佬救援!!


在力扣上面的情况:


0a2653c851af460fa595bd959398a8f1.png


在IDEA中的用列:


2d65d23f6d4748949b924e4057485923.png

等待大佬指教!


相关文章
|
编译器 C语言
【数据结构刷题】消失的数字和轮转数组(下)
【数据结构刷题】消失的数字和轮转数组(下)
【数据结构刷题】消失的数字和轮转数组(上)
【数据结构刷题】消失的数字和轮转数组(上)
|
算法
数据结构刷题训练:用栈实现队列(力扣OJ)
数据结构刷题训练:用栈实现队列(力扣OJ)
61 0
|
5月前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
5月前
|
算法
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
|
5月前
|
算法
【数据结构与算法 刷题系列】移除链表元素
【数据结构与算法 刷题系列】移除链表元素