Day03 数组

2022年快乐各位，1月1号，今天也是代码人码代码的一天呢，(′д｀ )…（题解均来自leetcode网站）。
1月份后明显累了,到今天（2022/2/8）才开始练leetcode，最近发生了一些事，让我决定不考研二战了，怎么说呢，从来没想过，再有半年，我就要走出学校进入社会了，内心感慨万千。

05 两个数组的交集Ⅱ

2022/1/1
2022/9/25 2022/10/9 复习

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

（java）
思路：用较小的数组去遍历较大的数组，进行比较，若相等则将该元素加入ArrayList，我写的代码问题很多：
（1）如何返回可变的长度的数组，这里使用ArrayList存储数据，最后还要将其转化为int数组；
（2）使用这样的方式，容易出现一个数组中存在过多重复元素；
（3）怎样确定两数组大小，并使用较小的数组去比较；

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
       //int minArr = nums1.length ? nums2.length : (nums1.length > nums2.length);
       int temp = 0;
       int[] tempArr = new int[maxArr];
       if(nums1.length > nums2.length){
           for(int i=0;i<nums2.length;i++)
            tempArr[i] = nums2[i];
       }else{
           for(int i=0;i<nums1.length;i++)
            tempArr[i] = nums1[i];
       }
       ArrayList<Integer> list = new ArrayList<>();
  
       for(int i=0;i<tempArr.length;i++){
        temp = tempArr[i];
        for(int j=0;j<nums1.length;j++){
            if(temp == nums1[j]){
                list.add(temp);
            }
         }
        }
        
        if(list.size() == 0)
            return new int[0];
        int[] arr = new int[list.size()];
        for(int i=0;i<list.size();i++)
            arr[i] = list.get(i);
        return arr;
    }
}

代码写了，问题很多，看题解怎么写吧

题解：
（1）哈希表
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

（2）排序＋双指针

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

题目知识点复习

HashMap常用方法

boolean containsKey(Object key); //判断集合中是否包含key键

boolean containsValue(Object value); //判断集合中是否包含vlaue值

V get(Object key); //返回指定键所映射的值，无该key值返回null

V put(Object key,V value); //向集合中添加新值，HashMap中不能包含重复元素，若添加重复元素，覆盖该键的值

V remove(Object key); //删除集合中键为key的键，返回删除键的值

06 买卖股票的最佳时机

2022/2/9
2022/10/11 复习
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

（java）
思路：单纯确定最大最小元素位置是错误的，对于price数组，头部取尽可能小的值，对于尾部取尽可能大的值，作为该数组的买入和卖出位置；应该是在该基础上遍历数组，取两个差值最大的情况；
确定头部值，依次遍历后面数组取差值最大的情况作为卖出的位置。

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit) {
                    maxprofit = profit;
                }
            }
        }
        return maxprofit;
    }
}

超出时间限制

题解：
动态规划问题，一次遍历求解；使用一个变量minprice记录历史最低价格，记录相对于当前日期的最低买入价格，在第i天卖出股票，计算获得的利润（prices[i] - minprice）。
$$dp[i]=min(dp[i-1],prices[i])$$

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

题目知识点疑惑

初识动态规划
（1）动态规划的两种形式：自顶向上的备忘录法、自底向上的动态规划
（2）动态规划的经典模型：线性模型、区间模型、背包模型
（使用动态规划前提，该问题是否具有最优子结构；该问题中是否包含重叠子问题）