題目

做項目的最大收益問題

• 鏈接 做項目的最大收益問題

• 題目描述

給定兩個整數W和K，W代表你擁有的初始資金，K代表你最多可以做K個項目。再給定兩個長度為N的正數數組costs[]和profits[]，代表一共有N個項目，costs[i]和profits[i]分別表示第i號項目的啟動資金與做完后的利潤(注意是利潤，如果一個項目的啟動資金為10，利潤為4，代表該項目最終的收入為14)。你不能并行只能串行地做項目，并且手里擁有的資金大于或等于某個項目的啟動資金時，你才能做這個項目。該如何選擇做項目，能讓你最終的收益最大？返回最后能獲得的最大資金。
[要求] 時間復雜度為 O(klogn)，空間復雜度為 O(n)。
和原題不一樣的是，這里返回值是 long 類型。

• 輸入與輸出

第一行三個整數N, W, K。表示總的項目數量，初始資金，最多可以做的項目數量 第二行有N個正整數，表示costs數組
第三行有N個正整數，表示profits數組。
輸入：
4 3 2
5 4 1 2
3 5 3 2
輸出：
11
解釋：
初始資金為3，最多做兩個項目，每個項目的啟動資金與利潤見costs和profits。最優選擇為：先做2號項目，做完之后資金增長到6。然后做1號項目，做完之后資金增長到11。其他的任何選擇都不會比這種選擇好，所以返回11。

最長無重復數組

• 鏈接 最長無重復數組
• 題目描述

給定一個數組arr，返回arr的最長無重復元素子數組的長度，無重復指的是所有數字都不相同。
子數組是連續的，比如[1,3,5,7,9]的子數組有[1,3]，[3,5,7]等等，但是[1,3,7]不是子數組

• 輸入與輸出

輸入：
[2,3,4,5]
輸出：
4
解釋：
[2,3,4,5]是最長子數組

思路

做項目的最大收益問題

1. 建立節點，記錄每個項目的 cost 和 profits；
2. 生成比較器，小根堆保存每個節點，大根堆根據情況（K 的取值、當前資金）保存值；
3. 判斷當前資金是否滿足條件；
4. 返回結果。

最長無重復子串

暴力解法

1. 雙層循環遍歷數組，如果有重復的，就打破循環，判斷長度。

滑動窗口

1. 定義 Map，key = arr[i] ，value = arr[i] 的下標；
2. 遍歷數組，如果當前出現過，那么更新左窗口的最大值；
3. 每次循環更新長度；
4. 返回結果。

代碼

做項目的最大收益問題

import java.util.Comparator;
import java.util.PriorityQueue;

public class Slution{
    /**
     * return the max money
     * @param costs int整型一維數組 the costs
     * @param profits int整型一維數組 the profits
     * @param W int整型 the money you have first
     * @param K int整型 max projects
     * @return long長整型
     */
    public static long maxMoney (int[] costs, int[] profits, int W, int K) {
        // write code here

        // 返回結果是 long 如果不定義 long res 的話結果可能會錯誤
        long res = W;

        // 將項目的花費與收益存在 nodes 數組中
        Node[] nodes = new Node[profits.length];
        for (int i = 0; i < profits.length; i++) {
            nodes[i] = new Node(profits[i], costs[i]);
        }

        PriorityQueue<Node> minQueue = new PriorityQueue<>(new MinHeapCom());
        PriorityQueue<Node> maxQueue = new PriorityQueue<>(new MaxHeapCom());

        // 建立小根堆, 按照 cost(花費) 排序
        for (int i = 0; i < profits.length; i++) {
            minQueue.add(nodes[i]);
        }

        // K 代表最多可做項目數量, 因此有了這個循環
        for (int i = 0; i < K; i++) {

            // 當 minQueue 不為空 并且 花費小于 W(初始資金) 時, 大根堆添加節點
            while (!minQueue.isEmpty() && minQueue.peek().cost <= res) {
                maxQueue.add(minQueue.poll());
            }

            // 如果資金不夠做下一個項目, 那么返回收益 res
            if (maxQueue.isEmpty()) {
                return res;
            }

            // 如果夠, 那么 res += 當前項目的收益
            res += maxQueue.poll().profit;
        }
        return res;
    }

    // 小根堆
    static class MinHeapCom implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.cost - o2.cost;
        }
    }

    // 大根堆
    static class MaxHeapCom implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            return o2.profit - o1.profit;
        }
    }


    // 定義節點
    static class Node {
        int profit;
        int cost;

        public Node(int profit, int cost) {
            this.profit = profit;
            this.cost = cost;
        }
    }
}

最長無重復子串

暴力

    public int maxLength (int[] arr) {
        // write code here

        // 定義結果
        int res = -1;
        for (int i = 0; i < arr.length; i++) {
            // 每次使用 set 保存
            Set<Integer> set = new HashSet<>();
            // 添加當前元素
            set.add(arr[i]);
            for (int j = i+1; j < arr.length; j++) {
                // 如果添加失敗, 那么說明有重復的元素,打破循環
                if (!set.add(arr[j])) {
                    break;
                }
            }
            // 比較當前長度與原來記錄的長度
            res = Math.max(res,set.size());
        }
        return res;
    }

滑動窗口

    public static int maxLength (int[] arr) {
        // 如果 arr.length < 2 直接返回結果
        if (arr.length < 2) {
            return arr.length;
        }

        // 定義結果
        int res = -1;

        // 使用 map 保存信息
        // key 代表當前元素, value 代表當前元素的下標
        Map<Integer, Integer> map = new HashMap<>();

        // 遍歷數組
        for (int i = 0, begin = 0; i < arr.length; i++) {
            // 如果 map 中含有當前元素, 說明重復了
            if (map.containsKey(arr[i])) {
                // 此時需要判斷左邊界與原來的左邊界的值, 如果
                begin = Math.max(map.get(arr[i]+1), begin);
            }
            res = Math.max(i - begin+1, res);
            map.put(arr[i],i);
        }
        return res;
    }