Leetcode-860-柠檬水找零

思路：贪心算法

题目描述

• 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

• 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

• 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

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

示例 1：

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
    
示例 2：

输入：[5,5,10]
输出：true
    
示例 3：

输入：[10,10]
输出：false
    
示例 4：

输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

图像学-伽马修正

计算机图形学-伽马修正

起因： [][][一个伽马矫正的视频][https://v.youku.com/v_show/id_XMTQwMjg5NzM4OA==.html]

答案 ： [一个知乎答案][https://www.zhihu.com/question/27467127]

参考博客 ： [博客地址][http://hanshilin.com/blog/gamma-and-linear-workflow/]

Leetcode-897-递增顺序查找树

题目描述

给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

示例 ：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

      5
      /     \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9  

Leetcode-861-翻转矩阵后的得分

思路：贪心算法

题目描述

• 有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

• 移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

• 在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。

• 返回尽可能高的分数。

1
2
3
4
5
6
7

示例：

输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：
转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Leetcode-204-计数质数

题目描述

• 统计所有小于非负整数 n 的质数的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0


提示：
0 <= n <= 5 * 106

方法一：枚举

• 很直观的思路是我们枚举每个数判断其是不是质数。

• 考虑质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

• 因此对于每个数 x，我们可以从小到大枚举[2,x-1]中的每个数 y，判断 y 是否为 x 的因数。但这样判断一个数是否为质数的时间复杂度最差情况下会到 O(n)，无法通过所有测试数据。

注意：

举例子 ：

• x = 6 y = 2 x/y =3
• min(y,x/y)= 2

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
30
31
32
33
34
35
36

public class MainClass {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        // 初始化数据
        String line;

        while ((line = in.readLine()) != null){
            int n = Integer.parseInt(line);
            int ret = new Solution().countPrimes(n);
            String out = String.valueOf(ret);
            System.out.println(out);
        }
    }
}

class Solution{
    public int countPrimes(int n) {
        int ans = 0;
        // O(n)
        for(int i = 2;i < n;++i){
            ans += isPrime(i)?1:0;
        }
        return ans;
    }

    // O(sqrt(n))
    public boolean isPrime(int x){
        for(int i = 2;i*i <= x;++i){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
}

Leetcode-134-加油站

思路：一次遍历

题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

• 如果题目有解，该答案即为唯一答案。
• 输入数组均为非空数组，且长度相同。
• 输入数组中的元素均为非负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

示例 1:

输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

示例 2:

输入: 
gas  = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

Leetcode-1030-距离顺序排列矩阵单元格

题目描述

• 给出 R 行 C 列的矩阵，其中的单元格的整数坐标为(r, c)，满足 0 <= r < R且0 <= c < C。

  另外，我们在该矩阵中给出了一个坐标为(r0, c0) 的单元格。

  返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

示例 1：

输入：R = 1, C = 2, r0 = 0, c0 = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

输入：R = 2, C = 2, r0 = 0, c0 = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

输入：R = 2, C = 3, r0 = 1, c0 = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

Leecode-409-移掉K位数字

题目描述：

• 给定一个以字符串表示的非负整数 num*，移除这个数中的 *k 位数字，使得剩下的数字最小。

注意:

• num 的长度小于 10002 且 ≥ k。
• num 不会包含任何前导零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例 1 :

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

Leecode-1122-数组的相对排序https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/)

题目描述

1
2
3
4
5

给你两个数组，arr1 和 arr2，

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

1
2
3
4

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

1
2
3
4
5
6

提示：

arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中

设计模式-模板方法模式

模板方法模式（Template Method）

• 动机：对于一项任务，常常有稳定的整体操作结构，但各个子步骤却又很多改变的需求，或者需要子步骤的晚期实现（延迟到子类去实现）。
• Template Method使得子类可以复用一个算法的结构（Override 重写）该算法的某些特定步骤。
• 不要调用我，让我来调用你，实现晚绑定机制，这也就是控制反转的思想。
• 声明成 protected ,因为具体步骤在流程中才有意义。

• AbstractClass : 稳定的骨架（里面有具体的方法和需要被重写的方法）
• ContreteClass : 具体的重写方法

模板方法模式定义（特别的常用）：

• 定义一个操作中的算法的骨架（稳定） ,而将一些步骤（变化）延迟到子类中。
• Template Method 使得子类可以不改变（复用）一个算法的结构即可（Override 重写）该算法某些特定的步骤