终于可以往后赶赶进度了，这周开始写下周的笔记，美滋滋~~嘿嘿
香槟塔
题目：我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。
现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（i 和 j都从0开始）。
示例 1:
输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.0
解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。
示例 2:
输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.5
解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。
注意:
poured 的范围[0, 10 ^ 9]。
query_glass 和query_row 的范围 [0, 99]。
思路：这个题其实做起来应该不难。首先我的想法是用数组来表示。i+1层数组。然后数组的数目是从1到i+1。然后有一点是其实每一个上面的数组都会流向下一行的同等下标和+1下标。这个确定了之后只要顺序走数字变化就行了，我去写下代码。
第一版本代码：
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[][] d = new double[query_row+1][];
d[0] = new double[]{poured};
for(int i = 1;i<=query_row;i++) {
d[i] = new double[i+1];
for(int j = 0;j<d[i].length-1;j++) {
double cur = d[i-1][j]-1;//只有满了才有溢出
if(cur<0) continue;
d[i][j] += cur/2;
d[i][j+1] += cur/2;
}
}
return d[query_row][query_glass]>1?1.0:d[query_row][query_glass];
}
}
性能比较不错，思路也很顺。没啥难点。就是从上往下判断。然后溢出了才往左右流。重点是如果当前杯子没溢出则不操作，第一遍我把这个判断漏掉了，结果测试发现有负数才补上的，当然了这个也是因为我的马虎大意。我去瞅一眼性能第一的代码，不出意外这个题就过了：
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[] wine = new double[query_row+1];
wine[0] = poured;
for (int i = 1;i <= query_row;i++) {
for (int j = i;j >= 0;j--) {
if (wine[j] > 1.0) {
double out = (wine[j]-1.0)/2.0;
wine[j+1]+=out;
wine[j] = out;
}
else {
wine[j] = 0.;
}
}
}
return Math.min(1, wine[query_glass]);
}
}
这个应该算是状态压缩了吧。我是用二维数组一层一层表示，人家是一个数组直接压缩展示，而思路上没什么不同，直接过了。
使序列递增的最少交换次数
题目：我们有两个长度相等且不为空的整型数组 A 和 B 。我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
示例:
输入: A = [1,3,5,4], B = [1,2,3,7]
输出: 1
解释:
交换 A[3] 和 B[3] 后，两个数组如下:
A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
两个数组均为严格递增的。
注意:
A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
A[i], B[i] 均为 [0, 2000]区间内的整数。
思路：这个题的标签是动态规划，但是具体怎么用dp实现呢，我去寻思寻思递推公式。
在群友的指点下有了大概的思路：那就是每一个值都有两个状态：换，不换。也就是01背包问题。然後继这两个状态，其中有必须交换的节点和非必须交换的节点。而且因为条件一定满足，所以所有的数据满足下面二者之一的规律（也可能两个都满足）：
- A[i]>A[i-1] && B[i]>B[i-1] 这种情况是两者都递增
- A[i]>B[i-1] && B[i]>A[i-1] 这种情况发生在某列不递增，需要交换
首先两者都满足的话，则可换可不换，换不换看情况。（因为可能当前两列都满足，但是后面的3列不满足，所以为了最佳换这两列）
其次如果满足条件1，仍然是可换可不换，原因和上面一样
最后如果只满足条件2，说明某列不递增，要么当前要么上一个，必须换一个！
有了以上两点和三种情况，有了如下代码：
第一版本代码:
class Solution {
public int minSwap(int[] A, int[] B) {
int len = A.length;
//dp0代表換，dp1代表不換
int[][] dp = new int[len][2];
dp[0][0] = 1;//如果第一个元素就换，则dp[0][0] == 1
//因为一定满足可交换的情况，所以所有元素必然满足一下两种条件或者两种都满足：
//1. A[i]>A[i-1] && B[i]>B[i-1] 这种情况是两者都递增
//2. A[i]>B[i-1] && B[i]>A[i-1] 这种情况发生在某列不递增，需要交换了
for(int i = 1;i<len;i++){
if(A[i]>A[i-1] && B[i]>B[i-1] && A[i]>B[i-1] && B[i]>A[i-1]){
dp[i][0] = Math.min(dp[i-1][0],dp[i-1][1])+1;
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]);
}else if(A[i]>B[i-1] && B[i]>A[i-1]){//到这说明必然交换，只不过是交换上一个还是当前
dp[i][0] = dp[i-1][1]+1;//交换当前
dp[i][1] = dp[i-1][0];//交换上一个
}else{//到这说明可换可不换，随便找个
dp[i][0] = dp[i-1][0]+1;
dp[i][1] = dp[i-1][1];
}
}
return Math.min(dp[len-1][0],dp[len-1][1]);
}
}
其实这个题怎么说呢，我一直都觉得dp简直不是我这个小脑瓜能看明白的。做过的题目还有点头绪，遇到不认识的就一脸懵比。尤其是只要涉及到二维dp（这个题目也是分状态，也可以算是二维dp）就掉头发。。01背包当年（也就是去年）看过教程和视频，结果硬生生的套不到题目上。除了多练练还能怎么办呢~哎。我这个虽然做出来了但是性能不是很好，而且我个人也觉得可以优化，起码可以压缩成两个量而不是数组。因为本质上只用到了上一个的两个状态值。我优化试一下:
class Solution {
public int minSwap(int[] A, int[] B) {
int len = A.length;
int h = 1;//第一个元素换是1
int bh = 0;//不换则0
//因为一定满足可交换的情况，所以所有元素必然满足一下两种条件或者两种都满足：
//1. A[i]>A[i-1] && B[i]>B[i-1] 这种情况是两者都递增
//2. A[i]>B[i-1] && B[i]>A[i-1] 这种情况发生在某列不递增，需要交换了
for(int i = 1;i<len;i++){
if(A[i]>A[i-1] && B[i]>B[i-1] && A[i]>B[i-1] && B[i]>A[i-1]){
bh = Math.min(h,bh);
h = bh+1;
}else if(A[i]>B[i-1] && B[i]>A[i-1]){//到这说明必然交换，只不过是交换上一个还是当前
int temp = h;//这里要绕圈
h = bh+1;//交换当前
bh = temp;//交换上一个
}else{//到这说明可换可不换，随便找个
h += 1;
}
}
return Math.min(h,bh);
}
}
2ms,性能超过百分之九十三。自我满足了。我直接去看看题解吧。
class Solution {
//801. 使序列递增的最小交换次数
public int minSwap(int[] A, int[] B) {
int aMax=0;
int aMin=0;
int lastMax=-1;
for(int i=0;i<A.length;i++){
if(A[i]>B[i]){
if(B[i]>lastMax){//两种
aMax=Math.min(aMax, aMin);
aMin=1+aMax;
}else{//一种，aMax
aMin=1+aMin;
}
lastMax=A[i];
}else if(A[i]<B[i]){
if(A[i]>lastMax){
aMin=Math.min(aMax, aMin);
aMax=1+aMin;
}else{
aMax=1+aMax;
}
lastMax=B[i];
}else{
lastMax=A[i];
}
}
return Math.min(aMax, aMin);
}
}
性能第一的代码。怎么说呢，我感觉可能是因为上两种方法是我自己写的，所以思路贼清晰。但是这个代码是人家写的，而且大大优化过，所以勉强看懂了，但是觉得易读性来说还是我的好，哈哈。其实本来当前A元素，B元素，上一个A元素，上一个B元素。四个值来判断是哪种情况。但是这里是可以稍微简化一点的。比如上面的代码，只用了三个量来判断。总而言之精致的很但是没那么直观。这个题也就这样了，下一题。
找到最终的安全状态
题目：在有向图中，从某个节点和每个转向处开始出发，沿着图的有向边走。如果到达的节点是终点（即它没有连出的有向边），则停止。如果从起始节点出发，最后必然能走到终点，就认为起始节点是 最终安全 的。更具体地说，对于最终安全的起始节点而言，存在一个自然数 k ，无论选择沿哪条有向边行走 ，走了不到 k 步后必能停止在一个终点上。返回一个由图中所有最终安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
示例 2：
输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]
提示：
n == graph.length
1 <= n <= 104
0 <= graph[i].legnth <= n
graph[i] 按严格递增顺序排列。
图中可能包含自环。
图中边的数目在范围 [1, 4 * 104] 内。
思路：这个题咋说呢。我目前的想法就是一个元素一个元素过，这个一定要标记。比如哪个元素成环了，那么下一个元素遇到他就直接pass。大概思路就这样，我去代码实现下试试。
第一版代码ac是ac了，但是我觉得我可能做的反而复杂了。先贴上代码：
class Solution {
Boolean[] d;
public List<Integer> eventualSafeNodes(int[][] graph) {
d = new Boolean[graph.length];
List<Integer> ans = new ArrayList<>();
for(int i = 0;i<graph.length;i++){
if(graph[i].length == 0) d[i] = true;
}
for(int i = 0;i<graph.length;i++){
if(d[i] == null) dfs(graph,new HashSet<>(),i);
if(d[i] == true) ans.add(i);
}
return ans;
}
public void dfs(int[][] graph,Set<Integer> set,Integer temp){
if(set.contains(temp)) {
d[temp] = false;
return;
}
set.add(temp);
for(int i:graph[temp]){
if(d[i] == null) dfs(graph,new HashSet<>(set),i);
if(d[i] == false) {
d[temp] = false;
return;
}
}
d[temp] = true;
return;
}
}
这个题思路上大差不差，就是一个dfs和标记。我这里用了数组表示不同状态、Boolean数组，初始值null表示未知。false表示此元素无法全部到末尾。true不表示此元素可以。遍历的时候一个元素下一个中有false直接false。一个元素下一个有true不管，有未知去判断未知是什么。只有当一个元素的所有下一个元素都是true它本身才能是true。其实这个题随着做我随着发现可以换种写法。比如用hash来表示。当前元素是Key，下一个是Value。然后顺着路往下走。依然可以标记、主要就是构图的方法来实现应该也可以。不过我觉得再怎么也没这么直观的性能好吧。
这个题暂时真的没啥好思路了，我去看看性能第一的代码：
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
int N = graph.length;
int[] color = new int[N];
List<Integer> ans = new ArrayList();
for (int i = 0; i < N; ++i)
if (dfs(i, color, graph))
ans.add(i);
return ans;
}
// colors: WHITE 0, GRAY 1, BLACK 2;
public boolean dfs(int node, int[] color, int[][] graph) {
if (color[node] > 0)
return color[node] == 2;
color[node] = 1;
for (int nei: graph[node]) {
if (color[node] == 2)
continue;
if (color[nei] == 1 || !dfs(nei, color, graph))
return false;
}
color[node] = 2;
return true;
}
}
我可能是细节处理上的问题，或者说我用Boolean包装类导致性能不好的？其实这个确实数组中元素表示三个状态，确实用int也可以搞定。不过我觉得还是要挣扎意思，照着差不多的思路我取用Boolean试试。
修改版代码：
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
Boolean[] d = new Boolean[graph.length];
List<Integer> ans = new ArrayList<>();
for(int i=0;i<graph.length;i++) if(dfs(graph,d,i)) ans.add(i);
return ans;
}
public boolean dfs(int[][] graph,Boolean[] d,Integer temp){
if(d[temp] != null) return d[temp];
int[] cur = graph[temp];
d[temp] = false;//先假装当前值false。下次遇到这个就说明是环了
for(int i : cur){
if((d[i] != null && d[i] == false) || !dfs(graph,d,i)) return false;
}
d[temp] = true;
return true;
}
}
除了人家是int数组我是Boolean数组，别的差不多一样一样的，性能就硬生生是人家的2倍。果然最开始就寻思错了。哎
不过这个题起码是很明确了。需要表示多个状态的时候染色是一个很好的选择。下一题。
保持城市天际线
题目：在二维数组grid中，grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。 高度 0 也被认为是建筑物。最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。建筑物高度可以增加的最大总和是多少？
例子：
输入： grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出： 35
解释：
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
从数组竖直方向（即顶部，底部）看“天际线”是：[9, 4, 8, 7]
从水平水平方向（即左侧，右侧）看“天际线”是：[8, 7, 9, 3]
在不影响天际线的情况下对建筑物进行增高后，新数组如下：
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
说明:
1 < grid.length = grid[0].length <= 50。
grid[i][j] 的高度范围是： [0, 100]。
一座建筑物占据一个grid[i][j]：换言之，它们是 1 x 1 x grid[i][j] 的长方体。
思路：讲真，看完这个题目我只想说：medium和medium是不一样的。看前两道题，又是dp状态压缩，又是染色一个值表示三种状态。再看看这道题。简单来说就是当前行列的最大值中的最小值。思路很清晰。我去实现了。
直接贴代码：
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int len = grid.length;
int[] r = new int[len];
int[] c = new int[len];
for(int i = 0;i<len;i++){
for(int j = 0;j<len;j++){
r[i] = Math.max(r[i],grid[i][j]);
c[i] = Math.max(c[i],grid[j][i]);
}
}
int ans = 0;
for(int i = 0;i<len;i++){
for(int j = 0;j<len;j++){
ans += Math.min(r[i],c[j])-grid[i][j];
}
}
return ans;
}
}
因为这个性能超过百分百了，所以我也不看题解了，感觉思路没问题，处理上因为比较简单也没啥好说的。这个题就这样了。下一题。
情感丰富的文字
题目：有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 S = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = S。输入一组查询单词，输出其中可扩张的单词数量。
示例：
输入：
S = "heeellooo"
words = ["hello", "hi", "helo"]
输出：1
解释：
我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。
我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3 。
提示：
0 <= len(S) <= 100。
0 <= len(words) <= 100。
0 <= len(words[i]) <= 100。
S 和所有在 words 中的单词都只由小写字母组成。
思路：这个题怎么说呢，因为S和words的长度都才100.所以其实我觉得暴力法应该可能也许大概就不会超时。一个个单词来看就行。当然了也可以先进行一场遍历。就是看字母合不合适。比如测试案例中的hi。这个i都在s中不存在，所以肯定不行。。题目感觉不是很难，具体怎么实现我去写代码试试。
...怎么说呢，这个屌代码，我一边写一遍觉得有问题，但是写完了居然ac了。而且性能还很不错。。。所以说直觉果然不靠谱，直接贴代码：
class Solution {
int n;
public int expressiveWords(String S, String[] words) {
if("".equals(S)) return 0;
int ans = 0;
int[] temp = new int[100];
char[] c = new char[100];
int count = 1;
int idx = 0;
char[] arr = S.toCharArray();
char cur = arr[0];
for(int i = 1;i<arr.length;i++) {
if(arr[i] == arr[i-1]) {
count++;
}else {
temp[idx] = count;
c[idx] = cur;
idx++;
count = 1;
cur = arr[i];
}
}
temp[idx] = count;
c[idx] = cur;
n = idx;
for(String s:words) {
if(isOk(s, temp,c)) ans++;
}
return ans;
}
public boolean isOk(String s,int[] temp,char[] c) {
int count = 1;
char[] arr = s.toCharArray();
char cur = arr[0];
int idx = 0;
for(int i = 1;i<arr.length;i++) {
if(arr[i] == arr[i-1]) {
count++;
}else {
//三种false：1.字母都不一样。2.S的个数少于s的（只能扩不能缩）。3.S中个数小于3个，但是数目不同
if(cur != c[idx] || temp[idx]<count ||(temp[idx]<3&&temp[idx] != count)) return false;
idx++;
count = 1;
cur = arr[i];
}
}
if(cur != c[idx] || temp[idx]<count ||(temp[idx]<3&&temp[idx] != count)|| idx != n) return false;
return true;
}
}
不知道是不是我个人问题，代码写的贼墨迹。。大概思路就是首先把S作为一个模板。其中每一个出现的元素和元素的个数都记录出来。我这里是用了两个数组。关于这里两个数组我想了好多。一开始是打算用二维数组，后来发现不知道长度比较不容易实现。后来我又打算用List型Map，单纯的Map没有顺序，肯定不行。但是我又觉得List底层还是数组，所以最终如上方式实现的。
记录好模板的每一个元素出现顺序和个数。接下来用所有的可选项去一一比较。
这里需要注意的就是不满足的条件：
- 字符不一样直接false。
- 字符一样的前提下。子串比S的数目都多了，直接false。因为只能扩不能缩
- 字符一样，也是S的多，但是S的都不满3个。所以不能进行扩，两个不相等就false。
最主要的是最后一个字符的判断，要看两者出现的字符个数是不是相等的。比如S是hheeel，子串hhe。看似上面三点都满足了，但是实际上S中最后一个l丢了，一看也是不合格。
以上的判断都过了就是合格的，结果+1.
然后写法上我去看看性能第一的代码吧
我就简单看了下，也一大串一点没看出简单，所以就不复制了。这个题可能思路也就这样了。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
