8.27刷题

发表于 | 分类于 | 0 comments

346. Moving Average from Data Stream

题目描述

求一个滑动窗口内的平均值

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MovingAverage {
    int[] store;
    double sum;
    int count;
    int index;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        sum = 0;
        count = 0;
        index = 0;
        store = new int[size];
    }
    
    public double next(int val) {
        if (count < store.length) count++;
        sum -= store[index];
        sum += val;
        store[index++] = val;
        index = index % store.length;
        return sum / count;
    }
}

374. Guess Number Higher or Lower

题目描述

我们来玩猜数字游戏。游戏规则如下：

我挑选一个1到n之间的数字。你来猜我选的是哪个数字。

每一次你猜错，我都会告诉你数字高了还是低了。

你可以调用一个预定义的API guess(int num)，返回3种结果 (-1, 1, 或 0)：

算法

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1, high = n;
        int middle = low + (high - low) / 2;
        while (guess(middle) != 0) {
            if (guess(middle) > 0) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
            middle = low + (high - low) / 2;
        }
        return middle;
    }
}

375. Guess Number Higher or Lower II

题目描述

我们玩猜数字游戏。游戏如下：

我从1到n中选择一个数字。你需要猜我选的是哪个数字。

每一次你猜错，我都会告诉你数字是高了还是低了。

然而，当你选择某个数字x并且猜错，你需要支付$x。当你猜到我选的数字时胜出。

测试用例如题目描述。

给定n ≥ 1，计算你需要多少钱才可以确保赢得游戏。

提示：

游戏的最佳策略是最小化你面临的最大可能损失。另一种策略是最小化期望损失。在这里，我们关注第一种策略。
以一个小的输入为例（n = 3）。最坏情况下你会支付多少金额？
如果还是一筹莫展，可以参考这篇文章。
单纯的minimax递归实现即使对于很小的n都是非常耗时的。你必须使用动态规划。
作为思考题，你怎样修改代码来实现最小化的期望损失，而不是最小化的最坏损失？

算法

注意DP的解法，首先可以使用回溯，暴力的写出所有的解，之后再利用DP存储中间的状态变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        return calculate(dp, 1, n);
    }
    
    public int calculate(int[][] dp, int start, int end) {
        if (start >= end)
            return 0;
        if (dp[start][end] != 0)
            return dp[start][end];
        int min = Integer.MAX_VALUE;
        for (int i = start; i <= end; i++) {
            int res = i + Math.max(calculate(dp, i + 1, end), calculate(dp, start, i - 1));
            min = Math.min(min, res);
        }
        dp[start][end] = min;
        return min;
    }
}

278. First Bad Version

题目描述

你是一名产品经理，正在领导团队开发一个新产品。不幸的是，产品的最新版本没有通过质量检测。由于每一个版本都是基于上一个版本开发的，某一个损坏的版本之后的所有版本全都是坏的。

假设有n个版本[1, 2, …, n]，你想要找出第一个损坏的版本，它导致所有后面的版本都坏掉了。

给你一个API bool isBadVersion(version)，返回某一个版本是否损坏。实现一个函数找出第一个损坏的版本。你应该最小化调用API的次数。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (isBadVersion(middle)) {
                if (middle == 1 || !isBadVersion(middle - 1))
                    return middle;
                else
                    high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }
}

658. Find K Closest Elements

题目描述

给定一个排序数组，两个整数k和x，求数组中距离x最近的k个数字。结果应该有序，距离相同时优先选择较小的数字。

算法

利用二分查找，之后确定两边的边界线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class findClosestElements658 {
    //Time O(log2(arr.size) + k + klog(k));
    public List<Integer> findClosestElementsBinary(List<Integer> arr, int k, int x) {
        int start = 0, end = arr.size() - 1;
        while (start <= end) {
            int middle = start + (end - start) / 2;
            if (arr.get(middle) == x) {
                start = middle;
                break;
            }
            else if (arr.get(middle) > x) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        start = start < 0 ? 0 : start;
        int left = start - 1, right = start;
        while (k-- > 0) {
            if (left < 0 || (right < arr.size() && Math.abs(x - arr.get(left)) > Math.abs(x - arr.get(right))))
                right++;
            else
                left--;
        }
        return arr.subList(left + 1, right);
    }
}

387. First Unique Character in a String

题目描述

给定一个字符串，寻找第一个不重复字符并返回其下标。如果不存在，返回-1。

注意：你可以假设字符串只包含小写字母。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class firstUniqChar387 {
    public int firstUniqChar(String s) {
        int[] map = new int[256];
        Arrays.fill(map, -1);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map[c] == -2) continue;
            else if (map[c] == -1) map[c] = i;
            else map[c] = -2;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < map.length; i++) {
            if (map[i] >= 0) min = Math.min(min, map[i]);
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}