Triangle

题目

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

> [ > [2], > [3,4], > [6,5,7], > [4,1,8,3] > ] > >

>

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

题目是说，从三角形的最上层走到最下层，每次只走到下一层的相邻元素，求从顶点走到最下层的最短路径长度。

方法1：DFS遍历

从上往下深度优先遍历搜索，记录所有情况之中最小值

public int best = Integer.MAX_VALUE;;
//sum为走到当前节点但不包含当前节点的路径和
public void dfs(List<List<Integer>> triangle,int i,int j,int sum){
  //搜索结束条件：走过了最下面一层
  int height = triangle.size();
  if(i==height){
    best = Math.min(best,sum);
    return;
  }
  dfs(triangle,i+1,j,sum+triangle.get(i).get(j));
  dfs(triangle,i+1,j+1,sum+triangle.get(i).get(j));
}
public int minimumTotal(List<List<Integer>> triangles) {
  dfs(triangles,0,0,0);
  return best;
}

时间复杂度$O(2^n)$

堆

基本性质

• 支持操作：Add $O(logN)$/Remove$O(logN)$/Min or Max$O(1)$

• heap可以用来求最大值或者最小值，不能同时求最大和最小值。

• Heap结构：

  一颗尽量填满的二叉树，每次插入节点时，插到最后一行的最左端的空余位置，如果本层没有空余位置了，另起一行。因此节点数目为N的堆对应的二叉树高度为$O(logN)$

• MaxHeap vs MinHeap

  • MaxHeap：父亲节点比左右孩子都大
  • MinHeap：父亲节点比左右孩子都小

  因此当取最大或最小时，将root值取出即可，因此getMin/Max的时间复杂度为$O(1)$

• 堆的存储

  由于我们需要频繁的对堆进行增加删除，所以一般堆的底层都是通过数组来实现（而不能用链表，因为链表需要频繁new 或 delete对象，非常慢）

  对于元素A[i]：

  • 父节点：A[i-2/2] (右移1)
  • 左孩子：A[2i+1] (左移1，可得到2i)
  • 右孩子：A[2i+2] (左移1，低位+1，可得到2i+1)

扫描线

lintcode391. 数飞机

题目

给出飞机的起飞和降落时间的列表，用 interval 序列表示. 请计算出天上同时最多有多少架飞机？

样例

对于每架飞机的起降时间列表：[[1,10],[2,3],[5,8],[4,7]], 返回3。

分析

计算空中的飞机个数，可以看成用一个线从左到右扫描的过程，计算每一时刻空中飞机的数量。

优化：只计算所有线段起始位置时天上的飞机即可，因为只有起始点是可能发生变化的点。遇到起点，天上的飞机数+1，遇到终点则-1。

因此，我们先将所有线段的起点、终点排序，并标记是起点还是终点，然后从小到大遍历这些点，遇到起点则+1，遇到终点-1，返回过程中最大的数值即为空中飞机数的最大值。

需要注意的是：在同一点上会同时有开始点和结尾点，此时应该把结尾点放在前面，否则会出现多计算的情况。

leetcode刷题总结

Trie树

leetcode相关题目

• Add and Search Word - Data structure design
• Map Sum Pairs
• Word Search II
• ​

Trie字典树

源自单词：retrieve

Trie树，即字典树/前缀树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

假设有[b，abc，abd，bcd，abcd，efg，hii ]这6个单词 , 查找abc 在不在字典里面

将单词插入Trie树，只在跟之前的字符串出现分歧时分裂，对最后一个字母做标记，这样查找的时候，根据最后一个字母的标记，即可判断出该单词是否出现过。

这里有一个巧妙的操作，可以让插入和查询操作同时完成，所以查询的时间复杂度简化为所要查询的单词的长度，即$O(1)$。

LR真的很基础而且也非常非常重要，算法面试必考，啃了好多遍，总结一下，希望能够经常复习。

暑假去头条面试，一面的面试官问到：

1. 推导一下LR吧
2. 为什么要用sigmod函数
3. 如何优化求解（梯度下降）
4. 代码实现一下

Union Find并查集

并查集

一种用来解决集合查询合并的数据结构

假如A、B、C三人在Microsoft工作，D、E、F、G四人在Linkedin工作，给七个人都分发一个工牌，上面写着自己的公司名字，告诉他们自己的老大是哪家公司，则可以表示成如下形式。

如果A遇到F，看一眼对方的工牌，跟自己是不是一个boss，就知道对方是不是跟自己是同一家公司的人了。

如果有一天M公司把L公司收购了，那么此时，需要对两个公司的员工进行合并操作，给员工分发新的工牌，为了减少重新分配的麻烦，就把L的boss指向M，此时L下面的员工最大的boss是M了，那么A和E就在一个阵营了。

如果在M公司三个员工和L公司四个员工中分别选出一个作为该公司的boss，可以表示成如下形式：

那么合并之后，J的boss设置为B，此时大家都是一个阵营的了。