一、买卖股票的最佳时机
思路:
遍历数组,用 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 位
思路
遇到这种查找某个字符的位置,我马上就想到了二分查找。但是我最开始是没想出代码到底该偶怎么写的,是看了官方的题解思路在写出来的,然后我现在的想法就是根据下面这个图来的
由上图可以得出:
- Si 的长度是 2^i - 1。
- 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';
}
}
五、分发糖果
说实话这个题读完题的时候感觉也没什么难度,就算不知道该怎么下手写代码,从哪个角度入手去写,我看题解都有点晕晕的,这里就没有写后续的代码了。呜呜