一、买卖股票的最佳时机

 思路：

        遍历数组，用 minprice 记录历史最低价格买入，就假设股票是这一天买的，然后我们得到的利润就是 price[i] - minprice 。

    public int maxProfit(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int money = 0;
        for(int i : prices){
            money = Math.max(money, i - minprice);
            minprice = Math.min(minprice, i);
        }
        return money;
    }

二、链表随机节点

 我自己刚开始做这个题的时候都没读懂题意，一直没理解到底要干嘛，所以人家大公司到底是大公司，题难啊。真是应了那句话，简单题我重拳出击，中等题我唯唯诺诺，困难题直接看题解，哈哈哈。

本来我还想着去看看这个水塘抽样是怎样的算法啥的，突然反应过来，这个题不就是让我给链表随机放数据进去吗，我恍然大悟。

思路

首先我们需要知道随机函数的使用，我举一个栗子，如果是一个大小为n的数组，求随机元素其实很简单，随机函数 int m = new Random().newxtInt(n) 就可以了。然后链表的逻辑和这个差不多，只是需要我们在初始化的时候计算出链表的大小n，再随机获取链表元素的位置 int m = new Random().newxtInt(n)；再遍历链表的第m个元素。

class Solution {
    ListNode cur;
    int size;
    Random rand = new Random();
    public Solution(ListNode head) {
        cur = head;
        ListNode index = cur;
        int count = 0;
        while (index != null){
            count++;
            index = index.next;
        }
        size = count;
    }
    public int getRandom() {
        int m = rand.nextInt(size);
        ListNode index = cur;
        while (m > 0){
            index = index.next;
            m--;
        }
        return index.val;
    }
}

三、两数之和

 这个题比较简单，然后我给出了两种思路。

第一种思路

利用哈希的思想

我这里假设第一个数字是 a ，第二个数字是 b ，然后我们遍历数组直到见到数字 a 时，就用target 减去 a，就会得到 b，若 b 存在于哈希表中，我们就可以直接返回结果了。若 b 不存在，那么我们就将 a 存入哈希表，继续让后续遍历的数字来比。我这里是把两数的差值当作 value 存入的哈希表。就是算出当前数字减之后和 target 的差，然后检查哈希表。

    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

第二种思路

暴力求解，直接遍历数组

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

四、找出第 N 个二进制字符串中的第 K 位

思路

遇到这种查找某个字符的位置，我马上就想到了二分查找。但是我最开始是没想出代码到底该偶怎么写的，是看了官方的题解思路在写出来的，然后我现在的想法就是根据下面这个图来的

由上图可以得出：

1. Si 的长度是 2^i - 1。
2. Si的长度是奇数，中间位置 一定是 1。

所以中间位置 mid = (2^n - 1) / 2 + 1，注意：k是从1开始的，后面就分情况看k是否大于小于mid，去进行递归。

    public char findKthBit(int n, int k) {
        if (n == 1) {
            return '0';
        }
        int sLen = (1 << n) - 1;
        int mid = (sLen >> 1) + 1;
 
        if (k == mid) {
            return '1';
        } else if (k < mid) {
            // 左边是正常的
            return findKthBit(n - 1, k);
        } else {
            // 右边是镜像+翻转
            k = sLen + 1 - k;
            return findKthBit(n - 1, k) == '0' ? '1' : '0';
        }
    }

五、分发糖果

 说实话这个题读完题的时候感觉也没什么难度，就算不知道该怎么下手写代码，从哪个角度入手去写，我看题解都有点晕晕的，这里就没有写后续的代码了。呜呜