春季四个月刷题

2.4 做题

79. Word Search. 这个题目要在一个全是字母的矩阵当中，找到一条连续的路径（上下左右相连）使得这条路径按线性顺序能够组成给定的单词；方法就是，对于矩阵的每一个位置的元素，都进行一下dfs；dfs的逻辑就是，首先检查当前位置的元素是否和给定单词所需要检查位置的字母相同，如果不同马上return false；如果相同的话，再检查一下给定单词当前检查位置的字母是不是最后一个字母，如果是的话，说明检查到最后都还是相同的，那么就可以返回true了；在一般的情况下，如果确定了矩阵当前位置的元素和给定单词当前检查位置的字母相同，那么就上下左右四个方向进行dfs，也就是传入recursion方法的参数分别是往上往下往左往右各走一步，并且对于给定单词的要检查的index位置也需要在当前recursion的基础上加1；最后这四个dfs方法的结果，只要有一个是true，那么当前dfs就可以返回true了；这里要额外注意一个问题，就是同一个元素在同一次dfs的时候不能重复进行，也就是说比如当前点进行四个方向的发散，但是发散完了以后不能返回来重新使用这个位置的元素，而只能继续发散；因此在dfs函数内部，当需要进行四个方向的发散之前，需要把当前位置的元素进行变更，变成比如“ * ”这种标记元素，然后在所有recursion结束后，再变回来

200. Number of Islands. 这个题目仍然是在一个矩阵当中，进行上下左右方向的DFS；方法就是，遍历这个矩阵，对矩阵的每一个点都进行检查，如果当前点是1也就是陆地，那么就对当前点进行dfs；dfs的过程就是寻找和当前陆地的点所有直接接触的其他陆地位置，从而找到当前的整个“岛”；找岛的过程其实也是排除的过程，dfs遍历当前“岛”的时候，会把每次遍历的点设置为0也就是海洋，这样做的目的是避免重复查找；具体来说，对于每一个是1的陆地，都进行dfs；dfs内部的内容就是，首先把当前点设置为0（因为进入了dfs就确定了这个点本来是1），然后对该点的上下左右进行检查；如果上下左右的点有一些点是valid的（也就是说不越界）并且这些点也都是1，那么就可以对这些点进一步进行dfs检查；最后在结束对当前点的dfs后，要进行count累计，这是因为现在已经对当前点所在的“岛”进行完毕了统计，所以增加计数

130. Surrounded Regions. 这个题目要求给定一个矩阵，把那些矩阵内部的上下左右全部被“X”给包围住的“O”找到并且都反转为“X”；本质上来说，其实是要去寻找那些在边缘的O或者和边缘的O有链接的O，因为这些O肯定不是要反转的那些，而除此之外就需要反转了；那么对于这种问题，可以使用BFS或者DFS的方法，也就是从边缘O出发，看看有没有上下左右有相连的O，如果有的话就做标记，然后对于这些相连的O再继续进行搜索检查；标记以后，重新遍历整个矩阵，对于没有标记的O进行反转，而标记的O就变回O即可

2.5 做题

155. Min Stack. 这个题目要求实现一个Stack，同时这个stack有一个getMin方法可以获取该stack的整体最小值，这里采用的方法是完全自己实现一个stack，而非在Java的Stack数据结构上进行修改而实现getMin；首先希望实现一个Stack，用linkedlist的方法，只维护一个head节点；每次push的时候，都新建一个节点，然后这个节点的next指向原有的head节点，最后把这个新建的节点设置为head节点；而每次pop的时候，就直接把当前head节点往后指向它的next即可，这样原有的head节点就相当于扔掉了；每次top的时候，就直接获取到当前head节点的value即可；那么对于getMin这个功能，实际上需要总是可以获取到当前整个stack的最小值，那么思路就是，对于这个LinkedList当中的每一个节点，除了有自己的value和next之外，还需要维护一个min值，这个min值就是当该节点被push到整个linkedlist/stack当中的时候，当前stack的最小值；也就是说，每次push的时候，新建立的节点的value都要和原有的head节点中所储存的min值进行比较，如果新建立节点的value更小，那么新建立节点的min就应该是它自己的value，否则就仍然是原有head中的min值；这个的意思本质就是，在构建这个以Linked List为形式的Stack的同时，就在每一个节点上都记录下，以当前这个节点为head的stack的min是什么；这样，无论stack如何操作，都可以从当前head获取当前stack的整体最小值

225. Implement Stack using Queues. 这个题目需要使用Queue来实现一个Stack；Queue是先进先出，而Stack是后进先出，如果Queue是{1, 2, 3, 4}的话，就希望出来的顺序是4, 3, 2, 1；对于一个Queue来说，具体方法就是每push一个元素之前，都先记录下来这个Queue当前的size，然后push新元素进来；那么记录下当前size以后就可以进行除了新元素以外的所有之前元素的循环，使得之前所有元素都一个一个从queue里面pop出去，然后再按照先pop先push的顺序push回来；这样就实现了在push的过程中完成元素的逆序，那么在pop的时候，当然首先pop的就是新元素了，对于其他的方法，因为现在Queue中已经实现了逆序，所以调用其他方法以后，都显得像是Stack一样了

232. Implement Queue using Stacks. 让使用stack去实现Queue；这个题目需要两个stack，因为stack本身只有一个开口，所以就是后进先出；那么每次push的时候直接push到stack里面；而pop或者peek的时候，首先要把当前stack里面的所有元素，一个一个的pop出来，然后再按照先pop先push的顺序，push到另一个辅助stack当中；这样在结束之后，所有元素存在于另一个stack中，并且实现了逆序；然后如果希望peek或者pop的话，就直接从另一个辅助stack中pop或peek即可，这样就实现了Queue；当然在完成操作后，还要将辅助stack中的元素再一个个push回到主要的stack中

2.6 做题

150. Evaluate Reverse Polish Notation. 逆波兰表达式，这个题目只要搞清楚是什么意思就可以了；使用一个stack，每当遇到数字的话，就offer到stack当中；而如果遇到符号的话，就poll出stack的前两个元素进行运算；注意在减法和除法的时候，先poll出来的那个在运算顺序上应该在后面

71. Simplify Path. 这个题目是实际场景应用类型，需要给出一个path的String，让我们去进行简化；对于unix系统的path，一般来说每个文件夹或文件都是用/斜杠分隔的，然后斜杠和斜杠之间可能会出现一点.两点..和空；对于这些特殊情况，如果出现一点就说明仍然处于当前位置，如果是空就自动忽略，如果是两点的话就说明需要从当前位置往后退一个目录，也就是回到上级目录的意思；那么这里和逆波兰表达式很像；首先按照斜杠进行分隔，如果出现的是正常的单词表示文件或文件夹，那么就放到stack当中；如果出现的是两点那就相当于后退到上级目录因此就需要从stack中pop出来一个文件夹，也就是pop出来最上面的文件夹表示从这个文件夹后退回上级；最后留在stack中的就是结果，进行组合即可

215. Kth Largest Element in an Array. 找到array当中第K大的数字；这里用PQ，如果是maxHeap的话就先全部offer进去，然后一个一个poll出来，poll出来的第k个就是第K大的；如果是minHeap的话就一个一个offer进去，如果heap的size大于k的话，那么就poll一个出来，每次poll出来的都是最小的，因此poll出来n - k个就相当于把前n - k小的poll了出来，那么最后再poll一个的话就一定是第k大的

2.7 做题

347. Top K Frequent Elements. 这个题目是典型的Top K；首先统计给定数组的元素频率，用一个map去做；然后创建一个内部元素为Map.Entry的最大Heap，并且把map的entry都offer进去；最后从Heap里面不断poll出来k个元素到结果当中即可

218. The Skyline Problem. 这个题目用一个比较直观比较基础的方法来做；可以先收集好所有的点，也就是把给定的这个buildings拆分好，把start point和end point分隔开，然后统一放到一个list当中；这里注意start point和end point都是相当于一个坐标一样，横坐标是start或end，纵坐标是height，为了区分start或end，start的height就是负的，而end的height就是正的；接下来把他们统一进行排列，排列顺序是首先按照横坐标从小到大，然后如果横坐标相同的话就按照纵坐标从小到大（这样的话，start的height为负、end的height为正，start优先级总是比end优先级要高）；排列完毕优先级之后，建立一个PQ，是maxHeap，这是为了存放height的，因为天际线总是以当前最高建筑为标准的，并且当前最高建筑可能还总是在改变，这就相当于在PQ当中总是进行最大元素的更新一样；接下来的步骤就是，首先offer进PQ一个0作为基点，然后维护一个prev存储当前最高值；对存储坐标的已经排好顺序的list进行循环；对于每一个坐标，根据纵坐标正负判断，如果它是start那么就把height（正的）offer到PQ当中，说明现在进入到了这个building的范围，如果它是end那么就把height给remove出PQ中，因为现在已经离开了building的范围；然后对于每一个遍历到的坐标，都取PQ顶的元素，把当前元素和原有的高度prev进行比较，这是因为如果当前遍历到的坐标是start，那么就说明进入到了building范围内，那么也就可能这个building非常高已经达到了更高的高度，从而offer到PQ当中后，当前PQ顶的元素就正是这个更高的高度，因此就说明天际线改变了；同样，如果当前遍历到的坐标是end，那么就说明离开了这个building范围，而如果这个building的高度正好是当前最高，那么因为离开了building范围并且把它从PQ中remove了出来，当前最高高度就相应发生了改变；因此，如果当前PQ顶的元素不同于当前最高高度的prev，那么就说明天际线需要发生变化了，因此就需要把当前坐标的横坐标，与当前PQ顶元素，组成一个新的位置坐标，然后添加到结果当中；这个题目的思路其实就是说，对于天际线问题，其实就是从原点开始沿着building的start到end的方向走，遇到了start point就需要开始考虑这个start point所处的building的高度是否会发生影响，也就是说这个building的高度是否比当前的高度更高，如果更高的话天际线就需要进行改变，也就意味着在结果list当中需要新增一个点；那么继续往前走，可能下一次遇到的还是start point，也可能遇到的是一个end point，如果是end point的话，就意味着现在离开了某一个building，那么既然离开了这个building它的高度就不再产生影响，有可能发生的事情就是这个building是当前最高的，因此也就是当前的天际线，所以如果当前的点是end point，就要考虑是否当前的天际线会因为离开了最高建筑而变得更低，这也就意味着同样需要在结果list中新增一个点

389. Find the Difference. 这个题目可以用HashMap，对于每一个在s字符串中出现的字母统计词频记录，然后对于t中每一个字母进行删减，最后看看哪一个字母在t中出现但是在s中的词频已经为0，就找到了difference；也可以用XOR做，也就是用一个char变量，对每一个s中的字符进行XOR，这样就相当存储了s中的每一个字符了；然后再去对t中字符进行XOR，这样t中字符和s中相同的就会因为XOR的特性（相同为0）而被删除，那么剩下的当然就是多出来的那个

2.8 做题

136. Single Number. 这个题目使用XOR去做，XOR的意义就在于对应位置相同则为0，不同则为1；在这里的话使用0去和每一位数字进行XOR，结果就相当于是0 ^ 4 ^ 2 ^ 1 ^ 2 ^ 1就等于是0 ^ 4 ^ (2 ^ 2) ^ (1 ^ 1)就相当于是0 ^ 4 ^ 0 ^ 0，最后还是4，因为0和其他数字进行XOR结果一定是其他的数字，所以最后单个的数字肯定会留下了

70. Climbing Stairs. 这个题目使用DP的方法做，题目要求爬楼梯，每次从当前楼梯往上爬的话，能走一步或两步，看爬到第n级台阶能有多少不同的爬法；因此对于当前的某一级台阶来说，人可以从后一级台阶上、走一步爬上来，也可以从后两级台阶上，走两步爬上来；因此如果从底下爬到后一级台阶的方法是n种爬法，从底下爬到后两级台阶的方法是m种爬法，而这两个位置可以分别爬一步或爬两步走到当前台阶，因此当前台阶的爬法自然是这两种之和，也就是n + m；所以这里的induction rule就自然是dp[i] = dp[i - 1] + dp[i - 2]，base case就是dp[0] = 1和dp[1] = 1（因为不爬和爬一级都是只有一种方法）；dp[i]的物理意义就在于爬到i级台阶一共有多少种方法

62. Unique Paths. 这个题目和上一个爬楼梯的题目很类似；同样是到达某一个位置究竟有多少种走法，上一个爬楼梯的是当前位置可以从前一级或前两级位置抵达，因此当前位置的走法就是前一级的走法加上前两级的走法；而这个题目在一个矩阵当中，某一个位置可以从它上面的位置到达，也可以从它左边的位置到达，因此当前位置的走法就是上面位置的走法加上左边位置的走法，这样就可以有induction rule就是dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；此外，注意边界的位置，比如最上面的那一行只能从左边的位置到达，而最左边的那一列只能从上面的位置到达；dp[i][j]的物理意义当然是到达某个矩阵中的位置的途径一共有多少种

63. Unique Paths II. 这个题目在上一题的基础上添加了一个条件，也就是给定的矩阵可能有障碍点，而如果某一个点是障碍点的话，那么这个点就变得不可到达了，也就是到达的方式为0；因此，计算方法还是像原来一样，即某一点的到达方法等于它上面点的方法加上它左边点的方法，但是这里需要一个额外条件就是，如果这个点在给定矩阵上是1的话，就说明有障碍点，那么无论它上侧和左侧的点的到达方法是多少，该点都是不可到达的，因此到达方法为0

120. Triangle. 这个题目是给了一个金字塔型的二维list，希望找到一个从塔底爬上塔顶的最小路径（每个位置的元素加起来的和最小）；因此这个金字塔的每一个位置，包括它在内的最小路径，当然就是它本身的数值，加上它下面的紧挨着两个位置的最小路径（也就是以下面的那两个位置分别为定点的最小路径）中间的最小值，这很容易理解；所以最后随着金字塔的逐渐收拢，肯定会最终聚集到定点，而这样肯定就是最小的路径；这里的DP是从底往上的，每一个点都进行了比较

2.9 做题

279. Perfect Squares. 这是一个DP题目，要求给定一个数字，看看它最少可以由几个完全平方数相加而构成，完全平方数就是1，4，9，16，25这种；比如5这个数字，可以是1 + 1 + 1 + 1组成，这样就是5个，但是当然也可以是4 + 1组成，这样就是两个；又比如27这个数字，可以是1 + 1 + ... + 1组成，这样就是27个，当然也可以是16 + 9 + 1 + 1组成，这样就是4个，当然也可以是9 + 9 + 9组成，这样就是3个；所以一个数字可以有多种完全平方数组合的方式；那么具体来说使用DP的方法，其实就是dp就是可以组成i的最少方式，对于任意一个j来说，只要i >= j * j，那么都可以有dp = dp[i - j * j] + 1；这是因为，i - j * j肯定是一个比i小的数字，比如如果i是27的话，那么j是2，那么i - j * j就是23；如果现在知道了组成23的完全平方数最小数量，那么只要在这个基础上再加一个2 * 2 = 4就可以构成27了，也就是说dp[27] = dp[23] + 1，这代表着加“一个”4即可；当然这种情况还会有很多，因为比i小的、加上一个完全平方数就可以构成i的数不止这一个，而这些数的组成方式数量，只要再加1（加一个完全平方数）就可以构成i；所以对于j从1开始到i的平方根进行逐个递增，对于每一个dp[i - j * j] + 1都比较一下，找出最小的那个，就是最后确定的dp了；因此base case就是dp[0] = 0和dp[1] = 1，然后i从2开始一直循环到n；对于每一个i循环内部，都去循环j，j从1开始只要满足i >= j * j就一直递增，对于每一个j都去让dp和dp[i - j * j] + 1进行比较，谁小取谁，最后assign到dp上

139. Word Break. 这个题目使用DP的方法，对于整个word进行一步一步往上检查；假设dp表示对于给定String从0开始一直到i的这一段substring是否能够break成功，是由从0开始到j的这一段substring，和从j开始到i的这一段substring，是由这两段substring共同决定的；而(0, j)这一段其实就是dp[j]，而(j, i)这一段则可以在wordDict当中去寻找并检验；因此dp = dp[j] && set.contains(s.substring(j, i))；具体来说，首先对i从1开始到s的长度循环，然后内部就是对DP的构建过程；dp代表从0开始到i是否能够break成功，那么对于每一个dp，内部都要进行这种两段式拆分，也就是内部也要有一个循环，这个循环其实就是循环j了，这个j就是拆分0到i这一段，然后看看代表0到j的dp[j]和j到i这一段是否存在于wordDict当中；这里有一个小技巧，对于j的循环，如果从i往0循环的话，速度要比从0往i循环更快

375. Guess Number Higher or Lower II. 这个题目的理解方式是这样，对于从1到n的这个范围之内，target的数字是任意未知的，而每次如果猜错了的话，会有提示target是更大还是更小，从而缩小下一次猜的范围，同时要交纳猜错的数字相同的钱；那么如果猜的话，从1到n这范围内的数字每一个都有可能被猜到，如果猜到了一个数字x且1 <= x <= n的话，这个x如果猜错了，那么首先要缴纳x数值的钱，同时会提示是比x更大还是比x更小；如果target比x更大的话，下一个猜的范围自然就是从x + 1到n，而如果target比x更小的话，下一个猜的范围自然就是从1到x - 1；这样其实就完成了把一个大问题拆分成小问题的过程，也就是在i到j范围之内，如果猜了x的话，那么要交的钱实际上就是x + Max((i, x - 1), (x + 1, j))这样，因为并不确定到底是比x更大还是比x更小，因此如果这一次猜了x的话，那么必须要有足够的钱，去应付下一个范围，而现在有两个可能的范围，所以就必须准备好这两个范围所需要的钱的更多的那个；因为每个范围要求至少需要准备的钱其实是确定的，那么对于这两个范围来说，在不确定的究竟是哪个范围的时候，肯定要准备更多的那个才能保证万无一失；那么回到一开始的从1到n这个最终范围，其实1 <= x <= n的这个x可以从1取到n的，也就是说这里如何取这个x其实是有最优策略的，可以通过选择猜合适的x，使得后续不断缩小范围的过程中，所需要支付的钱是最少的；因此就把x从1到n全部都尝试一遍，需要钱最少的对应的x，就是从1到n所需要准备交纳的钱；这里取最小是因为这里是在选择最优的策略，而之前取最大是因为之前的范围是不可知的

322. Coin Change. 这个题目是给定了一个数组，数组内部包含了硬币的面值，假设每个面值的硬币可提供的数量有无限多个，而又给了一个target，看看能不能通过给定数组当中的硬币（只能使用给定面值的硬币，但是同一种面值的硬币可以使用多次）来组成target；这个题目很类似之前的combination sum，所以首先想到用DFS的方法，也就是对于排好序的给定数组进行循环，对于每一个面值，都调用recursion，然后把当前target扣除当前index对应的面值，然后记录count + 1，如果在recursion的过程中发现target正好等于0的话，就说明这个count是有效的，就可以和全局最小值进行比较；类似的recursion方法还有一种，也就是在函数中，直接对所有的coin面值数组进行循环，对于每一个面值，都进行recursive调用原本给定的函数，只不过传入的参数是原有amount减去当前的coin，如果这个recursion返回的数值不是-1（也就意味着amount减去当前的coin面值剩下的amount可以被这个数组内的面值硬币所组成），那么这个amount的组成硬币数量，就相当于返回的数值基础上再加1（就是加上一个当前面值）；那么只需要维护一个global的min，然后对于对coins循环当中的所有的这种组成硬币数量，取一个全局最小就可以了；但是这种方法额问题就在于重复计算太多了，因为在原本的coins循环时，可能amount减去某个coin面值后的recursion路径中已经算出来过了以后的值，因此就可以维护一个Map，对于每一次算出来的某个amount对应的硬币数值都put进去，这样就可以作为recursion提前终止的条件，避免重复计算；那么最简单的就是DP方法了，这里是bottom up的DP，也就是当算出来amount为i时的组成硬币数量以后，再去考虑amount为i + 1的时候的组成硬币数量应该怎么由更小的dp去组成；这里其实也很简单，首先对i循环，这就是构建DP的过程；而对于每一个i的循环内部，都去算对于这个i的组成硬币最小值是多少，那么在循环内部，再针对这个i去对coins数组进行循环；对于每一个面值coin，如果这个面值不比i大，并且i减去这个coin以后剩下的amount，在DP数组中检查后发现并不是-1（也就是说i - coin也是在之前的步骤中算出来是可行的），那么这个i其实就可以由dp[i - coin] + 1来表示dp；当然这里对coins数组进行循环，可能不止一个coin都满足这个条件，所以就在内循环中对min进行更新；循环结束以后，如果min有更新，就证明是可以组成的，从而dp就确定下来了，否则dp就是-1，说明不能由这些面值的硬币所组成

312. Burst Balloons. 这个题目我看的这个https://leetcode.com/problems/bu ... siest-Java-Solution；思路就是，对于一个范围start到end，内部的任何一个气球i，如果希望扎它的话，假设从start到i - 1和从i + 1到end这两个区间都扎完毕了，那么现在就只剩下了start - 1、i、end + 1这三个了，那么如果扎i的话，也就是他们三个的数组元素相乘，这样就相当于是扎完了；那么对i进行循环一下，找出最大的那个就可以了；而对于那两个已经扎完毕的区间，从start到i - 1和从i + 1到end，就可以用recursion方法进行求解；这里我没用来得及用DP，但是也同样是可以用DP进行bottom up求解的；那么对于recursion的方法，可以有一个dp数组，dp[start][end]去进行memory记录即可

2.10 做题

64. Minimum Path Sum. 这个题目比较典型的DP，思路和之前的那种在一个矩阵里、以矩阵作为平面然后走的题目一样；从左上角往右下角走，每一个位置只可能由上方和左侧的点到达；那么dp就代表从起始点到i j点的最短路径，因为只能由上方和左侧点到达，所以dp就应该是上方点的最短路径和左侧点的最短路径的更小的那个加上当前的数值，从而计算出dp i j

72. Edit Distance. 这个题目关键在于如何想出这三种操作方式究竟是如何映射到DP的推导上去的；这个题目的dp物理意义很简单，dp[i][j]就表示，s1的从0到i的substring，要通过多少次操作，可以变成s2的从0到j的substring；那么现在考虑dp[i][j]，和s1.substring(0, i)和s2.substring(0, j)；如果s1在i位置的char和s2在j位置的char完全相同，那么这里就并不需要任何操作，也就是说dp[i][j]可以完全继承自dp[i - 1][j - 1]，这是因为现在已经知道了s1.substring(0, i - 1)到s2.substring(0, j - 1)的操作次数，而s1.charAt(i)又等于s2.charAt(j)，因此对于这个新位置的两个字母就不需要任何额外操作直接放上来就可以了，所以dp[i][j] = dp[i - 1][j - 1]完全等于之前的操作次数；那么如果这两个位置的char不相同，就说明肯定需要一次操作次数了，比如可以把s1在这个位置的char删除掉，或者把s2在这个位置新增一个和s1这个位置的char相同的char，又或者把s2在这个位置的char替换为s1在这个位置的char，不管怎样，都是需要又一次操作，所以就需要+1；而对于这三种操作方式，把对s1的char删除的方式，就是dp[i - 1][j] + 1，也就是说把s1的当前字母位置回退一个，把s2新增char的方式，就是dp[i][j - 1] + 1，也就是相当于s2回退一个，把s2替换为s1的char，就相当与是dp[i - 1][j - 1] + 1，也就是两个都回退一个，然后长度不变；最后当前dp在这三个当中选一个最小的就可以了；这里仍然要思考一些究竟是如何映射的

97. Interleaving String. 这个题目和edit distance很类似；dp[i][j]的物理意义稍微难想到一些，它表示的是s1的前i个字母的substring，和s2的前j个字母的substring，是否可以组成s3的i + j个字母的substring，这也就是interleaving的意思，s1和s2的相对顺序都不能改变，就像s1和s2插入一样，看看能不能组成s3；那么dp的推断方式就是这样的，如果dp[i][j - 1]为true，也就是说s1的前i个字母的substring，和s2的前j - 1个字母的substring，能够组成s3的i + j - 1个字母的substring，那么现在因为interleaving顺序不变的原因，s2只能提供第j个字母，而现在对于s3来说，它需要被匹配的正好就是第i + j - 1个字母，所以就看看在dp[i][j - 1]的基础之上s2的第j个字母，是否能够和s3的第i + j个字母相同，如果相同的话，就说明dp[i][j]为true，也就是说可以组成；那么同样的，对于dp[i - 1][j]来说，这就轮到s1去提供第i个字母和s3的第i + j个字母判断相同了；只要这两种情况有一个符合，那么就说明dp[i][j]为true

2.11 做题

174. Dungeon Game. 这个题目是一个比较形象的2维DP题目，和之前的edit distance以及interleaving string不同，这里是真的给了一个矩阵，矩阵的每一个元素都有着实际意义；意思是说，这个矩阵中有加血的地方也有掉血的地方，要保证从左上角格子出发一直到右下角格子扣完血之后还是血量大于0才行，注意左上角的格子也可能掉血；所以希望给出一个血量，使得在进入矩阵之前拥有这个血量可以平安到达右下角并且不死，只能往右或者往下走；这里并不是按照一般的形式，从小到大进行推导dp，或者应该说是，这里的从小到大进行推导DP不是从矩阵的左上角开始，而是从矩阵的右下角开始；因为已经确定了右下角是目的地，那么这里就是在讨论，往左往上以(i, j)为起点的话，最少需要准备的初始血量是多少，所以就应该从右下角开始往左往上推导；base case就是，以右下角为起点，或者说矩阵只有右下角这一个点的话，应该准备的血量应该看当前的这个点究竟是加血点还是减血点还是不加不减点，如果是加血点或者不加不减点，那么只要保证到达这个点之前是活着的，也就是说到这个点之前血量是1即可，而这个血量其实就是题中要求的初始血量，所以这里就是1；如果这个点是减血点，那就要保证准备的初始血量，在到达这个点后减去相应的血之后，仍然至少是1才可以，所以初始血量就必须比这个减血点的数值多1才行；那么这里的induction rule，把上述情况进行合并就是，dp[i][j] = Math.max(1, 1 - dungeon[i][j])，意思就是说，初始血量要么是1（在加血点或不加不减点的情况）、要么是1 - dungeon[i][j]，具体情况依dungeon[i][j]是加血还是减血决定（这里注意，因为题目中的dungeon矩阵中，如果这是一个减血点的话数值会是一个负数，所以这里表现的初始血量就是1 - dungeon[i][j]，实际上是说把这个减血点的负数取反以后再加1保证至少为1的）；而对于一般的点来说(i, j)来说，要么可以去他下方的点、要么可以去他右侧的点，而他下方的点所需要的初始血量就是dp[i + 1][j]、他右侧的点所需要的初始血量就是dp[i][j + 1]，那么如果想从这个点出发去这两个点，就需要考虑当前这个点到底是加血点还是减血点，如果是加血点的话，就有“初始血量 + 加血点血量 == 它下方或右侧所需的初始血量”，初始血量必须满足这个条件；而如果是减血点的话，就有“初始血量 - 减血点血量 == 它下方或右侧所需的初始血量”，必须满足这个条件才能保证即通过了当前这个点、又保证了仍然拥有充足的初始血量给后面的两个点；那么具体来说，对于一个点来说，首先选定下一次是往下走还是往右走，这取决于下方和右侧的点哪一个所需要的初始血量最少；在选定之后，再考虑当前这个点是加血点还是减血点：如果是加血点，那么当前的初始血量就要保证“初始血量 + 加血点血量 == 它下方或右侧所需的初始血量”，也就是说这里的初始血量就是要尽量弥补加血点血量的不足、或者在加血点血量足以补充下一个点所需的血量的情况下至少为1；如果是不加不减点，那么当前初始血量就完全等于下一个点所需的初始血量；如果是减血点，那么自然当前初始血量在减去当前减血数量后，仍然要等于下一个点的初始血量；所以一般的induction rule就应该是dp[i][j] = Math.max(1, Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j])；这里一定要注意，由于这是top down，是从右下角推导到左上角的，所以会有这种看起来是用后面的推导前面的induction

169. Majority Element. 这个题目要求给定一个数组，让找出数组当中出现次数比其他所有元素出现次数之和都要多的元素，也就是说出现频率大于数组长度一半的元素；这里一般的想法就是，首先用Map进行统计频率，然后一个一个检查看看有没有哪个的频率是高于数组长度一半的；或者说在构建map的时候，就可以进行检查，因为构建的过程就是记录频次的过程，就可以提前发现频率超过一半的元素；更简单巧妙的方法是用moore voting算法，意思就是说，对于任意一个元素，都当作结果；如果后面遇到了与当前结果相同的元素，则计数增加，否则计数减少；如果计数减少到0的话，就更换结果为当前元素；最后剩下额结果就是整个的结果；这是因为如果又超过频率一半的元素的话，从全局来看，它的计数总是会为正的

229. Majority Element II. 这个题目直接用的HashMap进行频次统计，然后在构建Map的过程中检查是否已经有元素的出现次数大于给定数组长度的三分之一了

2.12 做题

274. H-Index. 这个题目太难想了，要求找到的这个h的意义在于，至少有h篇文章的引用数量大于等于h；题目的难想之处在于，如何在定位到某一文章的同时，获取引用数大于等于这篇文章的文章数；因为定位到某一文章的时候，就知道该篇文章的自己的引用数了，那么如果这篇文章的引用数是h的话，就希望看看引用数大于等于这篇文章的文章数是不是也是h？但是对于给定数组来说，遍历到任何一个位置，获取到的仅仅是这篇文章的引用数量，所以就希望对于这个位置所代表的文章，再去重新遍历一下其他的所有文章、统计一下其他的那些引用数量大于等于这篇文章的数量；也就是说，用一个双重循环，外循环遍历所有文章，内循环针对当前遍历到的文章，再去遍历其他文章，看看引用数大于当前外循环文章的引用数的文章的总体数量，这个总体数量是否大于外循环文章的引用数量；另一种更快的方法就是，如果能够把给定数组进行排序，排序完毕的话，对于遍历定位到某一个文章，除了可以获取这篇文章的引用数量之外，还可以通过这个文章在数组中的index，来获取所有引用数大于等于它的文章数量；因为这个数组已经按照引用数sort过了，那么某一篇文章在数组的位置，恰恰就代表了这篇文章的引用数量的排名，那么所有排在这篇文章之前的，就是引用数小于它的，排在这篇文章之后的，就是引用数大于它的；因此就可以通过数组长度减去当前文章的index，来获取所有引用数大于当前文章的文章总数量；这样就可以通过一次遍历，去比较每篇文章的引用数，和所有引用数大于等于这篇文章的文章总数；满足条件的最大的就是h了

275. H-Index II. 这个题目首先要明确一点，也就是当前文章的引用数量citaitons[i]，和比引用数量大于等于当前文章的文章总数n - i，这两个之前，如果citations[i] < n - i，就说明这个n - i是一个h，这里和上一题一样，希望找到满足citations[i] < n - i的最大的i，而正好这个给定数组已经排好序了，实际上就是希望找到满足这个表达式的最大的i，用binary search；定位mid之后，如果citations[mid] >= n - mid，说明这肯定不是h，mid取得太大，所以right = mid - 1；如果citations[mid] < n - mid，这个应该是一个h，但是可能mid取得有点小，希望找到尽可能大的，所以left = mid；但是这里出了一个问题，暂时不明白；这里的while循环条件是left <= right，而对于left的变化是left = mid + 1，暂时不太明白这里的物理意义是什么

217. Contains Duplicate. 这个问题用HashSet进行一个一个检查并add即可

2.13 做题

219. Contains Duplicate II. 这个题目要求检查给定数组中是否有重复元素，并且要求给定数组中的某一对重复元素nums[i]和nums[j]，它们的下标之差、也就是距离，要小于等于k才可以；那么这里就需要利用HashMap来做，key是当前元素，而value则是当前元素的下标index；那么每次检查的过程中，如果发现了重复元素，也就是发现了map中已经存在了的key，那么就去检查重复元素的index和map中已经存在的index，它们的下标之差是否小于等于k；如果是的话则返回true，否则就更新当前元素的下标，走到后面继续检查

55. Jump Game. 这个题目本应该想出来的；给定一个数组，每次能往后跳当前位置元素为长度的步数，问能不能跳到终点；那么从初始位置开始跳，在这个“0”位置上，最多能达到的距离就是nums[0]，并且在nums[0]范围之内的位置也都能跳得到；那么继续往后走，每到达一个位置，都可以获取到一个新的元素，而如果从这个位置往后跳的话，最远的距离就是这个位置本身“i”加上这个位置的元素的值“nums[i]”；所以随时对当前能够达到的最远距离进行更新，也就是随时对“i + nums[i]”进行更新，看看当前能够达到的最远距离是多少；另一方面，对这个数组进行遍历，总是要随着下标index往后走的，如果走到某一个位置，发现这个位置index已经大于当前能够达到的最远距离了，也就是说当前最远距离的更新并没有赶得上数组的遍历，这样就说明不可以最终跳到终点，因为当前这个大于最远距离的index就相当于是一个断点，在它之前的所有index加上它们的元素数值，都不比这个index大，也就是说在它之前的所有位置无论从哪一个位置开始跳都跳不到这个index，所以是false了

290. Word Pattern. 这个题目我就用了两个HashMap，本质上就是要检验，是不是每一个pattern中的字母都对应着同一个String，此外还需要注意，每一个String只能属于一个pattern的字母；这就可以使用两个HashMap，暂时想不出其他更好的方法；或许pattern作为key，string作为value的话，在通过检查发现这是一个新的pattern之后，能够检查出来当前的string是不是已经出现过了；如果对于一个新的pattern对应上了一个已经出现过的string的话，那么说明这个string肯定被已经属于了之前的pattern；这时就可以考虑使用set，或者说使用一个map.values()这样的set进行检验，从而没必要使用两个Map