## ethannnli 查看完整档案

_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

### 个人动态

ethannnli 发布了文章 · 2019-02-01

# Max Area of Island

### 最新更新请见：https://yanjia.me/zh/2019/02/...

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

``````[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]``````

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:

``[[0,0,0,0,0,0,0,0]]``

Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

## 深度优先搜索

### 代码

#### Go

``````func maxAreaOfIsland(grid [][]int) int {
maxArea := 0
for i := range grid {
for j := range grid[i] {
area := measureIsland(grid, i, j)
if area > maxArea {
maxArea = area
}
}
}
return maxArea
}

func measureIsland(grid [][]int, x, y int) int {
if grid[x][y] == 0 {
return 0
}
area := 1
grid[x][y] = 0
if x > 0 {
area += measureIsland(grid, x-1, y)
}
if x < len(grid)-1 {
area += measureIsland(grid, x+1, y)
}
if y > 0 {
area += measureIsland(grid, x, y-1)
}
if y < len(grid[0])-1 {
area += measureIsland(grid, x, y+1)
}
return area
}``````

ethannnli 发布了文章 · 2019-01-24

## [Leetcode] Cheapest Flights Within K Stops K次转机最便宜机票

### 最新更新请见：https://yanjia.me/zh/2019/01/...

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

## 广度优先搜索

### 代码

Go

``````func buildGraph(flights [][]int) map[int]map[int]int {
graph := map[int]map[int]int{}
for _, flight := range flights {
src, dst, cost := flight[0], flight[1], flight[2]
cmap, ok := graph[src]
if !ok {
cmap = map[int]int{}
}
// cmap is a map from destination to cost
cmap[dst] = cost
graph[src] = cmap
}
return graph
}

func findCheapestPrice(n int, flights [][]int, src int, dst int, K int) int {
// build the graph given edges first
graph := buildGraph(flights)
queue := [][]int{{src, 0}}
stops := -1
cheapest := math.MaxInt64
visited := map[int]int{}
// BFS
for len(queue) > 0 && stops <= K {
size := len(queue)
for i := 0; i < size; i++ {
curr := queue[i]
from, sum := curr[0], curr[1]
if from == dst && sum < cheapest {
cheapest = sum
continue
}
toMap := graph[from]
for to, cost := range toMap {
// if the total cost is higher than before, there's no need to keep looking
if min, ok := visited[to]; ok && sum+cost > min {
continue
}
queue = append(queue, []int{to, sum + cost})
visited[to] = sum + cost
}
}
queue = queue[size:len(queue)]
stops++
}
if cheapest == math.MaxInt64 {
return -1
}
return cheapest
}``````

ethannnli 发布了文章 · 2018-12-05

# Evaluate Division

## 原文请访问：https://yanjia.me/zh/2018/12/...

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: `vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries` , where `equations.size() == values.size()`, and the values are positive. This represents the equations. Return `vector<double>`.

According to the example above:

``````equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].``````
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

## 深度优先搜索

### 代码

``````func compute(graph map[string]map[string]float64, first, second string, visited map[string]bool, value float64) float64 {
nexts := graph[second]
for next, ratio := range nexts {
if _, ok := visited[next]; !ok {
// if the target is found, we return the final result
if next == first {
return value * ratio
} else {
// otherwise keep looking
// set visited to true to avoid circle
visited[next] = true
res := compute(graph, first, next, visited, value * ratio)
if res != -1 {
return res
}
delete(visited, next)
}
}
}
return -1
}

func buildGraph(equations [][]string, values []float64) map[string]map[string]float64 {
graph := map[string]map[string]float64{}
for i, equation := range equations {
first := equation[0]
second := equation[1]
value := values[i]
// initialize the map if not being created before
if _, ok := graph[first]; !ok {
graph[first] = map[string]float64{}
}
if _, ok := graph[second]; !ok {
graph[second] = map[string]float64{}
}
// record both direction for this edge
graph[first][second] = 1/value
graph[second][first] = value
}
return graph
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
graph := buildGraph(equations, values)
res := []float64{}
for _, query := range queries {
first := query[0]
second := query[1]
value := -1.0
visited := map[string]bool{}
// dfs and find the path from 'first' to 'second'
value = compute(graph, first, second, visited, 1)
res = append(res, value)
}
return res
}``````

## Floyd算法

### 代码

``````func buildGraph(equations [][]string, values []float64) map[string]map[string]float64 {
graph := map[string]map[string]float64{}
for i, equation := range equations {
first := equation[0]
second := equation[1]
value := values[i]
if _, ok := graph[first]; !ok {
graph[first] = map[string]float64{}
}
if _, ok := graph[second]; !ok {
graph[second] = map[string]float64{}
}
graph[first][second] = 1/value
graph[second][first] = value
}
return graph
}

func calcEquation2(equations [][]string, values []float64, queries [][]string) []float64 {
graph := buildGraph(equations, values)
for i := range graph {
graph[i][i] = 1.0
for j := range graph {
for k := range graph {
ratio1, ok1 := graph[j][i]
ratio2, ok2 := graph[i][k]
if ok1 && ok2 {
graph[j][k] = ratio2 * ratio1
}
}
}
}
res := []float64{}
for _, query := range queries {
first := query[0]
second := query[1]
value := -1.0
if _, ok := graph[second][first]; ok {
value = graph[second][first]
}
res = append(res, value)
}
return res
}``````

ethannnli 发布了文章 · 2018-11-06

# Bus Routes

## 详细解题思路请访问：https://yanjia.me/zh/2018/11/...

We have a list of bus routes. Each `routes[i]` is a bus route that the i-th bus repeats forever. For example if `routes[0] = [1, 5, 7]``, this means that the first bus (0-th indexed) travels in the sequence `1->5->7->1->5->7->1->...` forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input:
`routes = [[1, 2, 7], [3, 6, 7]]`
`S = 1`
`T = 6`
Output: 2
Explanation:
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Note:
`>1 <= routes.length <= 500.`
`1 <= routes[i].length <= 500.`
`0 <= routes[i][j] < 10 ^ 6.`

### 代码

``````func searchRoute2(routes [][]int, graph map[int]map[int]bool, src, dst int) int {
queue := []int{}
for routeNum := range graph[src] {
queue = append(queue, routeNum)
}
visited := map[int]bool{}
dstRoutes := map[int]bool{}
// once one of the route in this map get hit, we find the solution
for routeNum := range graph[dst] {
dstRoutes[routeNum] = true
}
times := 1
// start BFS
for len(queue) != 0 {
newQueue := []int{}
for _, routeNum := range queue {
if _, ok := dstRoutes[routeNum]; ok {
return times
}
for _, stop := range routes[routeNum] {
nextRouteNums := graph[stop]
for nextRouteNum := range nextRouteNums {
// only add route that has been visited before to avoid cycle
if _, ok := visited[nextRouteNum]; !ok {
newQueue = append(newQueue, nextRouteNum)
visited[nextRouteNum] = true
}
}
}
}
queue = newQueue
times++
}
return -1
}

// map bus stop number to bus route numbers
func buildGraph2(routes [][]int) map[int]map[int]bool {
// use a map of map because route could be like 1->2->1->2
graph := map[int]map[int]bool{}
for i, route := range routes {
for _, stop := range route {
if _, ok := graph[stop]; ok {
graph[stop][i] = true
} else {
graph[stop] = map[int]bool{
i: true,
}
}
}
}
return graph
}

func numBusesToDestination(routes [][]int, S int, T int) int {
if S == T {
return 0
}
graph := buildGraph2(routes)
return searchRoute2(routes, graph, S, T)
}``````

ethannnli 评论了文章 · 2018-10-31

# Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example, Given the following words in dictionary,

``````[
"wrt",
"wrf",
"er",
"ett",
"rftt"
] ``````

The correct order is: `"wertf"`.

Note: You may assume all letters are in lowercase. If the order is invalid, return an empty string. There may be multiple valid order of letters, return any one of them is fine.

## 拓扑排序

### 注意

• 因为这题代码很冗长，面试的时候最好都把几个大步骤都写成子函数，先完成主函数，再实现各个子函数，比如初始化图，建图，加边，排序，都可以分开
• 要先对字典里所有存在的字母初始化入度为0，否则之后建图可能会漏掉一些没有入度的字母
• `'a'+'b'+""``'a'+""+'b'`是不一样的，前者先算数字和，后者则是字符串拼接
• 因为字典里有重复的边，所有要先判断，已经添加过的边不要重复添加

### 代码

``````    public class Solution {
public String alienOrder(String[] words) {
// 节点构成的图
Map<Character, Set<Character>> graph = new HashMap<Character, Set<Character>>();
// 节点的计数器
Map<Character, Integer> indegree = new HashMap<Character, Integer>();
// 结果存在这个里面
StringBuilder order = new StringBuilder();
// 初始化图和计数器
initialize(words, graph, indegree);
// 建图并计数
buildGraphAndGetIndegree(words, graph, indegree);
// 拓扑排序的最后一步，根据计数器值广度优先搜索
topologicalSort(order, graph, indegree);
// 如果大小相等说明无环
return order.length() == indegree.size() ? order.toString() : "";
}

private void initialize(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
for(String word : words){
for(int i = 0; i < word.length(); i++){
char curr = word.charAt(i);
// 对每个单词的每个字母初始化计数器和图节点
if(graph.get(curr) == null){
graph.put(curr, new HashSet<Character>());
}
if(indegree.get(curr) == null){
indegree.put(curr, 0);
}
}
}
}

private void buildGraphAndGetIndegree(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
Set<String> edges = new HashSet<String>();
for(int i = 0; i < words.length - 1; i++){
// 每两个相邻的词进行比较
String word1 = words[i];
String word2 = words[i + 1];
for(int j = 0; j < word1.length() && j < word2.length(); j++){
char from = word1.charAt(j);
char to = word2.charAt(j);
// 如果相同则继续，找到两个单词第一个不相同的字母
if(from == to) continue;
// 如果这两个字母构成的边还没有使用过，则
if(!edges.contains(from+""+to)){
Set<Character> set = graph.get(from);
// 将后面的字母加入前面字母的Set中
graph.put(from, set);
Integer toin = indegree.get(to);
toin++;
// 更新后面字母的计数器，+1
indegree.put(to, toin);
// 记录这条边已经处理过了
break;
}
}
}
}

private void topologicalSort(StringBuilder order, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
// 广度优先搜索的队列
// 将有向图的根，即计数器为0的节点加入队列中
for(Character key : indegree.keySet()){
if(indegree.get(key) == 0){
queue.offer(key);
}
}
// 搜索
while(!queue.isEmpty()){
Character curr = queue.poll();
// 将队头节点加入结果中
order.append(curr);
Set<Character> set = graph.get(curr);
if(set != null){
// 对所有该节点指向的节点，更新其计数器，-1
for(Character c : set){
Integer val = indegree.get(c);
val--;
// 如果计数器归零，则加入队列中待处理
if(val == 0){
queue.offer(c);
}
indegree.put(c, val);
}
}
}
}
}``````

``````public class Solution {
public String alienOrder(String[] words) {
Map<Character, AlienChar> graph = new HashMap<Character, AlienChar>();
// 如果建图失败，比如有a->b和b->a这样的边，就返回false
boolean isBuildSucceed = buildGraph(words, graph);
if(!isBuildSucceed){
return "";
}
// 在建好的图中根据拓扑排序遍历
String order = findOrder(graph);
return order.length() == graph.size() ? order : "";
}

private boolean buildGraph(String[] words, Map<Character, AlienChar> graph){
HashSet<String> visited = new HashSet<String>();
// 初始化图，每个字母都初始化入度为0
initializeGraph(words, graph);
for(int wordIdx = 0; wordIdx < words.length - 1; wordIdx++){
String before = words[wordIdx];
String after = words[wordIdx + 1];
Character prev = null, next = null;
// 找到相邻两个单词第一个不一样的字母
for(int letterIdx = 0; letterIdx < before.length() && letterIdx < after.length(); letterIdx++){
if(before.charAt(letterIdx) != after.charAt(letterIdx)){
prev = before.charAt(letterIdx);
next = after.charAt(letterIdx);
break;
}
}
// 如果有环，则建图失败
if(prev != null && visited.contains(next + "" + prev)){
return false;
}
// 如果这条边没有添加过，则在图中加入这条边
if(prev != null && !visited.contains(prev + "" + next)){
}
}
return true;
}

private void initializeGraph(String[] words, Map<Character, AlienChar> graph){
for(String word : words){
for(int idx = 0; idx < word.length(); idx++){
if(!graph.containsKey(word.charAt(idx))){
graph.put(word.charAt(idx), new AlienChar(word.charAt(idx)));
}
}
}
}

private void addEdge(char prev, char next, Map<Character, AlienChar> graph){
AlienChar prevAlienChar = graph.get(prev);
AlienChar nextAlienChar = graph.get(next);
nextAlienChar.indegree += 1;
graph.put(prev, prevAlienChar);
graph.put(next, nextAlienChar);
}

private String findOrder(Map<Character, AlienChar> graph){
StringBuilder order = new StringBuilder();
for(Character c : graph.keySet()){
if(graph.get(c).indegree == 0){
queue.offer(graph.get(c));
}
}
while(!queue.isEmpty()){
AlienChar curr = queue.poll();
order.append(curr.val);
for(AlienChar next : curr.later){
if(--next.indegree == 0){
queue.offer(next);
}
}
}
return order.toString();
}
}

class AlienChar {
char val;
ArrayList<AlienChar> later;
int indegree;
public AlienChar(char c){
this.val = c;
this.later = new ArrayList<AlienChar>();
this.indegree = 0;
}
}``````

2018/10

``````func buildGraphAndIndegree(words []string) (map[byte][]byte, map[byte]int) {
graph := make(map[byte][]byte)
indegree := make(map[byte]int)
for i := 1; i < len(words); i++ {
prev := words[i-1]
curr := words[i]
for idx := range prev {
if idx >= len(prev) {
break
}
prevChar := prev[idx]
if _, ok := indegree[prevChar]; !ok {
indegree[prevChar] = 0
}
if idx >= len(curr) {
break
}
currChar := curr[idx]
if prevChar == currChar {
continue
}
targets := graph[prevChar]
found := false
for _, el := range targets {
if el == currChar {
found = true
}
}
if !found {
graph[prevChar] = append(targets, currChar)
indegree[currChar]++
}
}
}
return graph, indegree
}

func alienOrder(words []string) string {
graph, indegree := buildGraphAndIndegree(words)
// find the first batch of roots for topological sort
var roots []byte
sb := strings.Builder{}
for key, value := range indegree {
if value == 0 {
roots = append(roots, key)
sb.WriteByte(key)
}
}
// keep sorting
for len(roots) != 0 {
newRoots := []byte{}
for _, root := range roots {
targets := graph[root]
for _, target := range targets {
if indegree[target] > 0 {
indegree[target]--
}
if indegree[target] == 0 {
newRoots = append(newRoots, target)
}
}
}
for _, root := range newRoots {
sb.WriteByte(root)
}
roots = newRoots
}
if sb.Len() == len(indegree) {
return sb.String()
}
return ""
}``````

ethannnli 发布了文章 · 2018-10-23

# Self Dividing Numbers

## 请访问最新更新版本：https://yanjia.me/zh/2018/11/...

A self-dividing number is a number that is divisible by every digit it
contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1: Input: left = 1, right = 22

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:
The boundaries of each input argument are 1 <= left <= right <= 10000.

## 暴力法

### 代码

``````func selfDividingNumbers(left int, right int) []int {
var res []int
for ; left <= right; left++ {
curr := left
for curr > 0 {
rem := curr % 10
// the digit can't be zero and should be divisible
if rem == 0 || left%rem != 0 {
break
}
curr = curr / 10
}
if curr == 0 {
res = append(res, left)
}
}
return res
}``````

ethannnli 评论了文章 · 2018-10-16

# Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

## 模十法

### 思路

• 两个正数数相加得到负数，或者两个负数相加得到正数，但某些编译器溢出或优化的方式不一样
• 对于正数，如果最大整数减去一个数小于另一个数，或者对于负数，最小整数减去一个数大于另一个数，则溢出。这是用减法来避免加法的溢出。
• 使用long来保存可能溢出的结果，再与最大/最小整数相比较

### 代码

``````public class Solution {
public int reverse(int x) {
long result = 0;
int tmp = Math.abs(x);
while(tmp>0){
result *= 10;
result += tmp % 10;
if(result > Integer.MAX_VALUE){
return 0;
}
tmp /= 10;
}
return (int)(x>=0?result:-result);
}
}``````

2018/10

``````func reverse(x int) int {
// The reserse of MinInt32 will overflow
if x == math.MinInt32 {
return 0
}
sign := 1
// Handle negative numbers
if x < 0 {
x = -x
sign = -1
}
result := 0
for x > 0 {
rem := x % 10
// When the result == MaxInt32/10, the reminder has to be smaller than 7
// so that result*10 + rem won't overflow (MaxInt32 is 2147483647)
if math.MaxInt32/10 < result || (math.MaxInt32/10 == result && rem > 7) {
return 0
}
result = result*10 + rem
x = x / 10
}
return result * sign
}``````

Q：拿到反转整数题目后第一步是什么？
A：先问出题者尾部有0的数字反转后应该是什么形式，其次问清楚溢出时应该返回什么。

Q：除了检查溢出返回特定值以外，有没有别的方法处理溢出？
A：可以使用try-catch代码块排除异常。

ethannnli 发布了文章 · 2018-04-01

# 方案一：循环或递归（错误解法）

``````const setInterval1 = (func, interval) => {
let startTime = Date.now();
const config = { shouldStop: false };
while (!config.shouldStop) {
if (Date.now() - startTime >= interval) {
func();
startTime = Date.now();
}
}
return config;
}

const myClearInterval = config => { config.shouldStop = true; }``````

# 方案二：使用setTimeout

setTimeout的好处在于，它是在消息队列里面添加一个待执行的消息，所以并不会堵塞主线程。更方便的在于，由于setTimeout自带定时器功能，我们甚至不用自己去维护一个时间戳。我们可以通过不断递归调用setTimeout来实现setInterval的效果

``````const setInterval2 = (func, interval) => {
const config = { shouldStop: false }
const loop = () => {
if (!config.shouldStop) {
func();
setTimeout(loop, interval);
}
}
setTimeout(loop, interval);
return config;
}

const myClearInterval = config => { config.shouldStop = true; }``````

# 方案三：使用requestAnimationFrame

``````const setInterval3 = (func, interval) => {
let startTime = Date.now();
const config = { shouldStop: false }
const check = () => {
if (!config.shouldStop) {
if (Date.now() - startTime > interval) {
func();
startTime = Date.now();
}
if(typeof window === 'undefined') {
setImmediate(check);
} else {
window.requestAnimationFrame(check)
}
}
}
check();
return config;
}

const myClearInterval = config => { config.shouldStop = true; }``````

# 方案四：使用Web Worker

requestAnimationFrame能确保我们在每帧显示前被调用一次，从而检计时器是否到期，但是如果被执行的函数计算量极大，导致帧内无法完成时，该如何保证给定函数能按时执行呢？显然，此时只依靠主线程来确保计时程序和给定程序都能准确执行，有点困难，但是如果将计时程序放入另一线程中，而主程序只负责监听定时器事件和执行给定程序，是不是会好一些呢？所以我们这里利用浏览器提供的Web Worker API来实现多线程。请注意这里由于没有调用另一个脚本，我们通过blob和object url的方式将我们的定时器程序`check`传入Web Worker中。

``````const setInterval4 = (func, interval) => {
if (typeof window !== 'undefined' && window.Worker && window.Blob) {
const check = new Blob(["(", function(){
self.onmessage = function(e) {
const interval = e.data;
let startTime = Date.now();
while(true) {
if (Date.now() - startTime >= interval) {
startTime = Date.now();
self.postMessage(Date.now());
}
}
}
}.toString(), ")()"], { type: "text/javascript" });
const worker = new Worker(window.URL.createObjectURL(check));
worker.onmessage = func;
worker.postMessage(interval);
return worker;
} else {
}
}

const myClearInterval = config => { config.terminate() }``````

ethannnli 发布了文章 · 2018-02-24

# Cheapest Flights Within K Stops

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:
Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1
Output: 200 Explanation: The graph looks like this:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Note:

The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
The size of flights will be in range [0, n * (n - 1) / 2].
The format of each flight will be (src, dst, price).
The price of each flight will be in the range [1, 10000]
`k` is in the range of [0, n - 1]. There will not be any duplicated flights or self cycles.

## 深度优先搜索

### 思路

1. 通过visited集合，记录当前路径中已经访问过的城市，本条路径中将不再访问
2. 如果当前路径的距离已经大于之前发现的最短距离，则不用再继续向下搜索
3. 中转次数一旦超过也不需要再向下搜索
``````class GraphNode:
def __init__(self, name):
self.name = name
self.dsts = []

self.dsts.append((dst, price))

class Solution:
def findCheapestPrice(self, n, flights, src, dst, K):
"""
:type n: int
:type flights: List[List[int]]
:type src: int
:type dst: int
:type K: int
:rtype: int
"""
flightsMap = self.constructGraph(flights)
self.globalMin = float('inf')
self.findFlight(flightsMap, flightsMap.get(src), 0, dst, 0, K, set())
return -1 if self.globalMin == float('inf') else self.globalMin

def findFlight(self, flightsMap, node, totalPrice, finalDst, stops, stopLimit, visited):
if node is None or stops > stopLimit:
return
if self.globalMin < totalPrice:
return
for dst in node.dsts:
dstName, dstPrice = dst
nextTotalPrice = dstPrice + totalPrice
if dstName == finalDst: # 如果找到目的地，则计算当前的距离并和最小值比较
self.globalMin = min(self.globalMin, nextTotalPrice)
elif flightsMap.get(dstName) is not None and self.globalMin > nextTotalPrice and dstName not in visited: # 如果不是目的地，则继续向下找，这里中转次数要加一，并且本条路径中已经访问过的节点不用再访问
self.findFlight(flightsMap, flightsMap.get(dstName), nextTotalPrice, finalDst, stops + 1, stopLimit, visited)
visited.remove(dstName)

def constructGraph(self, flights):
flightsMap = {}
for flight in flights: # 将航线按照出发城市一一加入图中
src = flight[0]
dst = flight[1]
price = flight[2]
node = flightsMap.get(src, GraphNode(src))
flightsMap[src] = node
return flightsMap``````

ethannnli 发布了文章 · 2018-02-21

# Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what
matchsticks the little match girl has, please find out a way you can
make one square by using up all those matchsticks. You should not
break any stick, but you can link them up, and each matchstick must be
used exactly one time.

Your input will be several matchsticks the girl has, represented with
their stick length. Your output will either be true or false, to
represent whether you could make one square using all the matchsticks
the little match girl has.

Example 1: Input: `[1,1,2,2,2]` Output: true

Explanation: You can form a square with length 2, one side of the
square came two sticks with length 1.

## 代码

``````class Solution:
def makesquare(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
perimeter = sum(nums)
if perimeter == 0 or perimeter % 4 != 0:
return False
sides = [perimeter // 4 for i in range(0, 4)]
nums.sort(reverse=True) # 先试着拼较长的边，有助于减少搜索分叉
return self.findSolution(nums, sides, 0) # 从第一根开始尝试拼出边

def findSolution(self, nums, sides, pos):
if pos == len(nums):
return True
for index in range(0, 4): # 对于当前这个火柴，尝试拼入上下左右四个边
if sides[index] >= nums[pos]:
sides[index] -= nums[pos] # 用当前火柴拼第index个边
if self.findSolution(nums, sides, pos + 1): # 如果这个火柴被成功使用，就开始尝试拼下一根火柴
return True
sides[index] += nums[pos] # 把当前火柴从第index个边中拿出来，好尝试下一条边
return False``````

#### 认证与成就

• 获得 119 次点赞
• 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

(ﾟ∀ﾟ　)

(ﾟ∀ﾟ　)