ethannnli

ethannnli 查看完整档案

填写现居城市重庆大学  |  通信工程 编辑Snapchat  |  Software Engineer 编辑填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

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

[Leetcode] Max Area of Island 最大岛屿面积

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.

深度优先搜索

思路

该题基本上就是Number of Islands的变形题,唯一的区别是在Number of Islands中我们只需要将搜索到的陆地置为0,保证其不会再被下次探索所用就行了。但这题多了一要求就是要同时返回岛屿的面积。那么最简单的方式就是在递归的时候,每个搜索到的格子都将自身的面积1,加上四个方向搜索出来的延伸面积都加上,再返回给调用递归的那个格子作为延伸面积使用,这样一直返回到岛屿的起始格子时,面积之和就是岛屿的总面积了。

代码

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
}
查看原文

赞 0 收藏 0 评论 0

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.

广度优先搜索

思路

本题给定起始点和重点,还给定各个点之间的连接,一看就知道是要搜索。另外由于给定了最大深度K,使用广度优先搜索会比较方便,因为每一层的深度都是一样的,不用像DFS那样来回修改深度值。这题OJ的难点在于如何剪枝来满足对时间和空间的优化,对于某一个航线,在什么样的情况下可以确认不用再往下寻找了呢?自然地想到用一个visited的map来记录哪些访问过,可是即使访问过,也不能完全说明不用继续寻找了,因为可能某种方案虽然中转多后面才遇到,但是总价却少。所以对于每个访问过的节点,我们要记录当前最低的总价,只有当到达该地新的总价更低时,才继续寻找,如果该方案到达该地的总价已经高于之前的方案的话,就没有必要继续寻找了,从该地到终点的最优线路反正都是一样的。

代码

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
}
查看原文

赞 0 收藏 0 评论 0

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

[Leetcode] Evaluate Division 计算除法

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.

深度优先搜索

思路

这道题抽象之后可以理解为,给定一系列图中的边,边的值表示其两端节点的比例,现在给定一系列图中节点对,求每对节点的比例。那无论如何,首先我们要先根据给定的equations和values把图先建出来。由于是无向图,不分前后,所以我们不仅要记下a到b的边,也要记下b到a的边,即倒数。图建好以后,如果给定的query并不是很多,那么最简单的就是从节点a开始,深度搜索寻找节点b,并同时记录下路径上的比例并乘起来,一旦找到节点b就返回这个乘积。这里代码使用了递归来实现DFS。

代码

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算法

思路

但是如果query很多,甚至要求图中每个节点对两两之间的比例时,深度搜索就显得不是那么有效了。因为这时搜索会重复走很多次相同的路径。这种求两两之间最短路径有一个现成的算法:Floyd–Warshall 。基本上该算法就是通过三层循环,一层是中间节点,两层是开始和结束节点,穷举所有的可能性看是否开始和结束节点能否通过这个中间节点串联起来,如果可以的话就给图中加一条直接从开始节点到结束节点的边。这样虽然建图会花掉O(N^3)的时间,但是对每个query就成了一个O(1)的操作。

注意

使用该算法的时候要记得给每个节点到自身也加一条值为1的边(自己对自己的比例是1),这样当中间节点和开始节点是一个节点时,不会把0乘进去

代码

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
}
查看原文

赞 0 收藏 0 评论 1

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

[Leetcode] Bus Routes 公交线路

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)
}
查看原文

赞 0 收藏 0 评论 0

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

[Leetcode] Alien Dictionary 外文字典

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.

拓扑排序

复杂度

时间 O(N) 空间 O(N)

思路

首先简单介绍一下拓扑排序,这是一个能够找出有向无环图顺序的一个方法

假设我们有3条边:A->C, B->C, C->D,先将每个节点的计数器初始化为0。然后我们对遍历边时,每遇到一个边,把目的节点的计数器都加1。然后,我们再遍历一遍,找出所有计数器值还是0的节点,这些节点就是有向无环图的“根”。然后我们从根开始广度优先搜索。具体来说,搜索到某个节点时,将该节点加入结果中,然后所有被该节点指向的节点的计数器减1,在减1之后,如果某个被指向节点的计数器变成0了,那这个被指向的节点就是该节点下轮搜索的子节点。在实现的角度来看,我们可以用一个队列,这样每次从队列头拿出来一个加入结果中,同时把被这个节点指向的节点中计数器值减到0的节点也都加入队列尾中。需要注意的是,如果图是有环的,则计数器会产生断层,即某个节点的计数器永远无法清零(有环意味着有的节点被多加了1,然而遍历的时候一次只减一个1,所以导致无法归零),这样该节点也无法加入到结果中。所以我们只要判断这个结果的节点数和实际图中节点数相等,就代表无环,不相等,则代表有环。

对于这题来说,我们首先要初始化所有节点(即字母),一个是该字母指向的字母的集合(被指向的字母在字母表中处于较后的位置),一个是该字母的计数器。然后我们根据字典开始建图,但是字典中并没有显示给出边的情况,如何根据字典建图呢?其实边都暗藏在相邻两个词之间,比如abcabd,我们比较两个词的每一位,直到第一个不一样的字母cd,因为abd这个词在后面,所以d在字母表中应该是在c的后面。所以每两个相邻的词都能蕴含一条边的信息。在建图的同时,实际上我们也可以计数了,对于每条边,将较后的字母的计数器加1。计数时需要注意的是,我们不能将同样一条边计数两次,所以要用一个集合来排除已经计数过的边。最后,我们开始拓扑排序,从计数器为0的字母开始广度优先搜索。为了找到这些计数器为0的字母,我们还需要先遍历一遍所有的计数器。

最后,根据结果的字母个数和图中所有字母的个数,判断时候有环即可。无环直接返回结果。

注意

  • 因为这题代码很冗长,面试的时候最好都把几个大步骤都写成子函数,先完成主函数,再实现各个子函数,比如初始化图,建图,加边,排序,都可以分开
  • 要先对字典里所有存在的字母初始化入度为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.add(to);
                        // 将后面的字母加入前面字母的Set中
                        graph.put(from, set);
                        Integer toin = indegree.get(to);
                        toin++;
                        // 更新后面字母的计数器,+1
                        indegree.put(to, toin);
                        // 记录这条边已经处理过了
                        edges.add(from+""+to);
                        break;
                    }
                }
            }
        }
        
        private void topologicalSort(StringBuilder order, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
            // 广度优先搜索的队列
            Queue<Character> queue = new LinkedList<Character>();
            // 将有向图的根,即计数器为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);
                    }
                }
            }
        }
    }

新建一个AlienChar数据结构重写,只用一个Map作为Graph自身

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)){
                addEdge(prev, next, graph);
                visited.add(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;
        prevAlienChar.later.add(nextAlienChar);
        graph.put(prev, prevAlienChar);
        graph.put(next, nextAlienChar);
    }
    
    private String findOrder(Map<Character, AlienChar> graph){
        StringBuilder order = new StringBuilder();
        Queue<AlienChar> queue = new LinkedList<AlienChar>();
        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

[Leetcode] Self Dividing Numbers 自除数

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.

暴力法

复杂度

时间 O(NM)

思路

从左到右,对每个数字依次取出其各个位的数字,然后判断是否能整除。

代码

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
}
查看原文

赞 0 收藏 0 评论 0

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

[Leetcode] Reverse Integer 反转整数

Reverse Integer

Reverse digits of an integer.

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

字符串法

复杂度

时间 O(n) 空间 O(n)

思路

先将数字转化为字符串,然后将字符串倒序输出,并转回数字。记得需要去除首部多余的0。

模十法

复杂度

时间 O(n) 空间 O(1)

思路

通过对数字模十取余得到它的最低位。其实本题考查的是整数相加的溢出处理,检查溢出有这么几种办法:

  • 两个正数数相加得到负数,或者两个负数相加得到正数,但某些编译器溢出或优化的方式不一样
  • 对于正数,如果最大整数减去一个数小于另一个数,或者对于负数,最小整数减去一个数大于另一个数,则溢出。这是用减法来避免加法的溢出。
  • 使用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
}

后续 Follow Up

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

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

查看原文

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

[Javascript] 实现setInterval函数

问题

经常使用Javascript的同学一定对setInterval非常熟悉,当使用setInterval(callback, timer)时,每经过timer毫秒时间,系统都将调用一次callback。请问全局如果没有提供setInterval函数,该如何自己实现这一功能?

方案一:循环或递归(错误解法)

最简单的思路便是通过简单的循环或者递归,每次检查时间戳是否已经超过上次触发给定函数的时间加上间隔时间,如果已经超过便再次触发函数,并重置计时器至当前时间。

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; }

然而这样的解法有一个致命问题,我们将setInterval1变成一个阻塞函数,主线程会卡死在这个无限循环或者递归中,导致之后的代码或者事件无法执行。想了解详细原因的请戳: 并发模型与事件循环JavaScript:彻底理解同步、异步和事件循环(Event Loop)

方案二:使用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

然而使用setTimeout有违这道题的初衷,因为setTimeout在本质上和setInterval是类似的,多少有些作弊的嫌疑。那有没有别的非阻塞方案呢?在浏览器环境中,我们有requestAnimationFrame(),而在nodejs环境中,我们有setImmediate()。以requestAnimationFrame为例,这将保证我们的代码只会在每一帧render之前被递归一次,从而避免了阻塞其他代码。

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 {
        console.log('Your environment is not supported');
    }
}

const myClearInterval = config => { config.terminate() }
查看原文

赞 1 收藏 3 评论 0

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

[Leetcode] Cheapest Flights Within K Stops 计算最便宜票价

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:
https://s3-lc-upload.s3.amazo...
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.

给定一个数组,其中每个元素代表着从[出发城市,目的城市,飞机票价],现在再给定任意一对不一定有直飞航线的出发城市和目的城市,和最大允许的中转次数K,求具有最便宜总价的航线组合。

深度优先搜索

思路

想知道从A到B最便宜的机票组合,只要将所有从A到B在K个中转之内的所有路径组合都遍历一遍,就能找到最低的价格。然而本题的输入是城市之间的航线,所以我们还要先根据这些航线构建一个航线图。由于题中说明了不会产生环路,也不会有重复的航线,所以在遍历图时不需要检测环路。

这里需要剪枝减少搜索分叉才能通过OJ,剪枝的要点包括:

  1. 通过visited集合,记录当前路径中已经访问过的城市,本条路径中将不再访问
  2. 如果当前路径的距离已经大于之前发现的最短距离,则不用再继续向下搜索
  3. 中转次数一旦超过也不需要再向下搜索
class GraphNode:
    def __init__(self, name):
        self.name = name
        self.dsts = []
    
    def addFlight(self, dst, price):
        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: # 如果不是目的地,则继续向下找,这里中转次数要加一,并且本条路径中已经访问过的节点不用再访问
                visited.add(dstName)
                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))
            node.addFlight(dst, price)
            flightsMap[src] = node
        return flightsMap
查看原文

赞 0 收藏 0 评论 1

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

[Leetcode] Matchsticks to Square 火柴拼方形

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.

给定一个数组,其中每个数字是火柴长度。求是否能够用且只用一次每一根火柴,通过首尾相连来拼出一个正方形。

深度优先搜索

思路

由于正方形有四条边,该搜索其实要满足四个目标才能算成功,即四条边都用能够用火柴拼出来。想象此时我们有个火柴队列,我们拿出一支火柴,先尝试将它放入第一条边上,如果第一条边放得下,再拿出第二根火柴,尝试继续放在第一条边上,如果此时发现已经放不下了,就试着把它放在第二条边上,以此类推。细心的同学可能会发现,如果第一根火柴在第一条边上都放不进去的话,后面也都不用试了,因为每条边长都一样,一个放不进去的话其他也放不进去。其实不只是第一根火柴,由于较长的火柴较不容易放入边中,所以如果我们先把较长的火柴放完再放较短的火柴,能帮助减少很多分叉的情况。所以这里一个优化的方法就是先将火柴排序,将长的放在前面。

到这里你可能会疑惑,为什么用完所有火柴就意味着四条边都拼完了呢?因为我们规定了边长的目标为总长除以4,而所火柴用完时总长已经确定即为边长的4倍,那么肯定就是有四条边被拼出来了。

代码

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
查看原文

赞 0 收藏 0 评论 0

认证与成就

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

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2015-07-13
个人主页被 7k 人浏览