350 Intersection of Two Arrays II intersection of two arrays 2

subject

attempt

First attempt:

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] nums3 = new int[nums1.length + nums2.length];
        int size = 0;
        for( int i = 0; i < nums1.length; i++){
            for ( int j = 0; j < nums2.length; j++){
                if (nums1[i] == nums2[j]){
                    nums3[j] = nums2[j];
                    nums1[i] = -1;
                    nums2[j] = -1;
                    size++;
                }
            }
        }
        /*
        int zero = 0;
        for (int k = 0; k < nums3.length; k++){
            if (nums3[k] == 0){
                zero++;
            }
        }
        int[] nums4 = new int[nums3.length - zero];
        int n = 0; 
        for ( int m = 0; m < nums3.length; m++){
            if (nums3[m] != 0){
                nums4[n] = nums3[m];
                n++;
            }
        }
        */
        //return nums4;
        int[] nums5 = new int[size];
        for (int x = 0; x < size; x++){
            nums5[x] = nums3[x];
        }
        return nums5;
    }
}

The comment in the middle is to remove 0, because the new array will automatically fill in 0, but the two arrays in the title also contain 0, so let's do it. The method used later is to transfer the array without the last 0 part to the new array (according to the size length, that is, the answer length). However, the following strange example reports an error:

Input:
[4,9,5]
[9,4,9,8,4]
Output:
[4,0]
Expected results:
[4,9]

Because I don't know what's wrong, let's do it...

Method 1, set

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list1 = new ArrayList<>();
        for (int num : nums1) {
            list1.add(num);
        }
        List<Integer> list2 = new ArrayList<>();
        for (int num : nums2) {
            if (list1.contains(num)) {
                list2.add(num);
                // Remove matched values from list1
                list1.remove(Integer.valueOf(num));
            }
        }
        int[] res = new int[list2.size()];
        int i = 0;
        for (int num : list2) {
            res[i++] = num;
        }
        return res;
    }
}

Method 2, hash table

Problem solution
Idea:

• Since the same number may appear more than once in both arrays, you need to use a hash table to store the number of occurrences of each number. For a number, the number of occurrences in the intersection is equal to the minimum number of occurrences of the number in two arrays.

• First, traverse the first array and record each number in the first array and the corresponding number of occurrences in the hash table, and then traverse the second array. For each number in the second array, if there is this number in the hash table, add the number to the answer and reduce the number of occurrences of this number in the hash table.

• In order to reduce the space complexity, first traverse the shorter array and record each number and the corresponding number of occurrences in the hash table, and then traverse the longer array to get the intersection.

Time complexity: O(m+n)O(m+n), where mm and nn are the lengths of the two arrays respectively. It is necessary to traverse two arrays and operate the hash table. The time complexity of hash table operation is O(1)O(1), so the total time complexity is linear with the sum of the lengths of the two arrays.

Spatial complexity: O(\min(m,n))O(min(m,n)), where mm and nn are the lengths of the two arrays respectively. Perform hash table operation on a shorter array. The size of the hash table will not exceed the length of the shorter array. Create an array intersection for the return value, whose length is the length of the shorter array.

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);
    }
}

121 Best Time to Buy and Sell Stock

subject

attempt

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

The result was that 200 / 211 test cases passed the time limit
Obviously, a violent search is not advisable.

Normal moving gauge

Idea:
Maximum revenue of the first i day = max {maximum revenue of the first i-1 day, price of the first i day - minimum price of the first i-1 day}

Law II greed

// dynamic programming
public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        int[] have = new int[len];  // Represents the maximum cash received from holding shares on day i
        int[] no = new int[len];    // Indicates the maximum cash received from not holding shares on day i
        have[0] = -prices[0]; // Holding stocks at this time must be buying stocks
        no[0] = 0;            // If you don't hold stocks, cash is 0

        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i-1], -prices[i]);
            no[i] = Math.max(no[i-1], prices[i] + have[i-1]);
        }
        return no[len - 1];
    }
}

// Greedy 
class Solution {
    public int maxProfit(int[] prices) {
        int low = Integer.MAX_VALUE;
        int result = 0;
        for (int i = 0; i < prices.length; i++) {
            low = Math.min(low, prices[i]);  // Take the leftmost minimum price
            result = Math.max(result, prices[i] - low); // Take the maximum interval profit directly
        }
        return result;
    }
}