力扣名企直通车-学习计划-网易-刷题记录

发布于:2023-01-21 ⋅ 阅读:(533) ⋅ 点赞:(0)

一、买卖股票的最佳时机

 思路:

        遍历数组,用 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<Integer, Integer> 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';
        }
    }

五、分发糖果

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