淄博市建设业协会网站,网站开发一般都有系统,织梦cms可以做淘宝客网站么,动漫制作工资一般多少473. Matchsticks to Square
思路#xff1a;有n根长度不一的火柴#xff0c;这些火柴可以拼接在一起#xff0c;但不能被折断。这些火柴能够围城一个正方形吗#xff1f;每个火柴可以并且必须使用一次。分析得到每个边的长度应该是所有火柴长度和的1/4。接下来就是将火柴…473. Matchsticks to Square
思路有n根长度不一的火柴这些火柴可以拼接在一起但不能被折断。这些火柴能够围城一个正方形吗每个火柴可以并且必须使用一次。分析得到每个边的长度应该是所有火柴长度和的1/4。接下来就是将火柴分组。可以用4个变量或者一个数组记录每组火柴目前已经分配的长度。如果正好分配完成就返回true否则返回false。 这里的一个小技巧是对输入nums排序。先分配火柴长度长的火柴。这样可以更早地找到不合理分配的情况。 代码
743. Network Delay Time
思路这是一道关于在图中找从一个顶点到其他顶点的最短路径的问题。我的错误在于忽略了最短路径。 思路1普通的dfs。只是要注意遍历的时候先访问距离短的边。 思路2Dijkstra’s Algorithm。但是我比较了dfs版本的代码与堆实现版本的代码认为思路是一样的。只是代码书写结构不同。排序位置不同。它们的耗时确实不同。前者耗时101ms后者耗时51ms。 public int networkDelayTime(int[][] times, int N, int K) {int[] costs new int[N1];Arrays.fill(costs,-1);MapInteger, Listint[] map new HashMapInteger, Listint[]();for(int[] a : times){if( map.get(a[0])null){map.put(a[0],new ArrayListint[]());}map.get(a[0]).add(new int[]{a[1],a[2]});}//按dist排序可以优先选择距离短的边for (int node: map.keySet()) {//(a, b) - a[0] - b[0]Collections.sort(map.get(node), new Comparatorint[](){public int compare(int[] o1, int[] o2) {return o1[1]-o2[1];}});}visitNode(map,costs,K,0);int max 0;for(int i1;iN;i){if(costs[i] -1) return -1;max Math.max(max, costs[i]);}return max;}public void visitNode(MapInteger,Listint[] timeMap,int[] costs,int node,int cost){if(costs[node]!-1){if(cost costs[node]){return;}}costs[node] cost;if(timeMap.get(node)!null){for(int[] edge :timeMap.get(node)){visitNode(timeMap,costs,edge[0],edge[1]cost);}}} public int networkDelayTimeV2(int[][] times, int N, int k) {MapInteger, Listint[] graph new HashMapInteger, Listint[]();for(int[] a : times){if( graph.get(a[0])null){graph.put(a[0],new ArrayListint[]());}graph.get(a[0]).add(new int[]{a[1],a[2]});}PriorityQueueint[] heap new PriorityQueueint[](N,new Comparatorint[](){public int compare(int[] o1, int[] o2) {return o1[1]-o2[1];}});heap.offer(new int[]{k,0});int[] dist new int[N1];Arrays.fill(dist,Integer.MAX_VALUE);while(!heap.isEmpty()){int[] info heap.poll();int d info[1];int node info[0];if(dist[node]!Integer.MAX_VALUE) continue;dist[node] d;if(graph.containsKey(node)){for(int[] edge :graph.get(node)){if(dist[edge[0]]Integer.MAX_VALUE){heap.offer(new int[]{edge[0],edge[1]d});}}}}int max 0;for(int i1;iN;i){if(dist[i] Integer.MAX_VALUE) return -1;max Math.max(max, dist[i]);}return max;}
思路3也是Dijkstra’s算法。但是是用数组实现的。快很多耗时13ms。代码 代码
417. Pacific Atlantic Water Flow
思路这道题目不难。难的是理解题目含义。红色框的所有位置相当于都是Pacific的入口。能到达这些位置的点都能流入Pacific。同理对于Atlantic也一样。标记哪些位置是能流入二者的点就是需要返回的点。 代码
207. Course Schedule
思路检测有向图上是否有环。 思路1BFS。1、构建图2 找到入度为0的点加入到队列3 从队列中弹出一个元素count1找到这个元素可以达到的点课程将这些课程的入度减14 如果发现有新的入度为0的点继续加入到队列5 重复步骤3,4直到队列为空6 判断count是否等于课程数。如果等于返回true。 思路2DFS。1、构建图2 参考802. Find Eventual Safe States我们设计节点的访问有三种状态还没有开始访问节点是白(0)开始访问一个节点是灰(1)访问一个节点结束是黑(2)3 我们依次访问所有课程如果节点状态是1则表示有环返回false如果节点状态是2则表示已经访问成功直接返回true如果节点状态是0则进入访问状态修改为1接着dfs访问这个节点的邻接节点。 代码
721. Accounts Merge
思路这题目初看上去很简单。map吧。把email和用户名做映射。但实际上没这么简单。 学习DFS。这是一个图。图的链接技巧是将第一个email和同一个list内的其他email双向相连。连通的email就是在同一个组内。 DFS思路代码 AccountsMergeV2 union-find代码思路 AccountsMergeV3 AccountsMergeV4 我自己写的union-find超时了。
542. 01 Matrix
思路这道题目DFS思路可以解决。但有一个细节需要解决。如果matrix[i][j]1计算最近0距离的时候。1 先判断周围是否有0如果有则距离为1直接退出。2 不满足条件1继续搜索周围相邻节点。这个过程中没有把相邻节点的计算保留下来所以会有重复计算.在整个dfs过程中并没有对r的有效修改所以会有重复的。 例如在计算(0,4)的最近0距离的时候会计算(1,4)点的最近0距离但是结果并没有保存下来。 这个问题的解决在别人文章中学到了。在从左到右从上到下的遍历中dist[i][j] Min(dist[i][j],min(dist[i-1][j]1,dist[i][j-1]1))。因为在这样的遍历中(i-1,j)和(i,j-1)节点是计算过的。在从下到上从右到左的遍历中dist[i][j] Min(dist[i][j],min(dist[i1][j]1,dist[i][j1]1))。因为在这样的遍历中,(i,j1)和(i1,j)节点是计算过的。 这是一种DP的思想。但是这样的思维就确定整个计算过程不会出错。要不我总会想是应该先计算(1,4)还是先计算(0,4)。究竟是(0,4)点的距离影响(1,4)还是(1,4)点的距离影响(0,4)。而这种从上到下从左到右遍历一次从下到上从右到左再遍历一次就好多了。 学习BFS思路考虑从matrix[i][j]0的点开始扩散查找更有意思了。 代码
