Commit ffd786c
authored
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,51 @@ | |||
| 1 | + package com.v0ex.leetcode; | ||
| 2 | + | ||
| 3 | + import java.util.ArrayList; | ||
| 4 | + import java.util.HashMap; | ||
| 5 | + import java.util.List; | ||
| 6 | + import java.util.Map; | ||
| 7 | + | ||
| 8 | + /** | ||
| 9 | + * Find Duplicate File in System | ||
| 10 | + * | ||
| 11 | + * @author bugcoder | ||
| 12 | + */ | ||
| 13 | + public class LeetCode_609_49 { | ||
| 14 | + | ||
| 15 | + /** | ||
| 16 | + * 用哈希表来处理，key就是文件的内容，value就是文件的路径 | ||
| 17 | + * @param paths | ||
| 18 | + * @return | ||
| 19 | + */ | ||
| 20 | + public List<List<String>> findDuplicate(String[] paths) { | ||
| 21 | + Map<String,List<String>> map = new HashMap<>(); | ||
| 22 | + for (String path : paths) { | ||
| 23 | + String[] split = path.split(" "); | ||
| 24 | + String rootPath = split[0]+"/"; | ||
| 25 | + for (int i = 1; i < split.length; i++) { | ||
| 26 | + String file = split[i]; | ||
| 27 | + String fileName = file.substring(0,file.indexOf("(")); | ||
| 28 | + //拆分字符串获取文件的内容 | ||
| 29 | + String fileContent = file.substring(file.indexOf("(")+1, file.lastIndexOf(")")); | ||
| 30 | + //获取文件的全部路径 | ||
| 31 | + String filePath = rootPath + fileName; | ||
| 32 | + if (map.containsKey(fileContent)){ | ||
| 33 | + List<String> list = map.get(fileContent); | ||
| 34 | + list.add(filePath); | ||
| 35 | + map.put(fileContent,list); | ||
| 36 | + }else { | ||
| 37 | + List<String> list = new ArrayList<>(); | ||
| 38 | + list.add(filePath); | ||
| 39 | + map.put(fileContent,list); | ||
| 40 | + } | ||
| 41 | + } | ||
| 42 | + } | ||
| 43 | + List<List<String>> result = new ArrayList<>(); | ||
| 44 | + for (Map.Entry<String,List<String>> entry : map.entrySet()){ | ||
| 45 | + if (entry.getValue().size()>1){ | ||
| 46 | + result.add(entry.getValue()); | ||
| 47 | + } | ||
| 48 | + } | ||
| 49 | + return result; | ||
| 50 | + } | ||
| 51 | + } | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,44 @@ | |||
| 1 | + package com.v0ex.leetcode; | ||
| 2 | + | ||
| 3 | + import java.util.HashSet; | ||
| 4 | + import java.util.Set; | ||
| 5 | + | ||
| 6 | + /** | ||
| 7 | + * Second Minimum Node In a Binary Tree | ||
| 8 | + * | ||
| 9 | + * @author bugcoder | ||
| 10 | + */ | ||
| 11 | + public class LeetCode_671_49 { | ||
| 12 | + | ||
| 13 | + public int findSecondMinimumValue(TreeNode root) { | ||
| 14 | + Set<Integer> set = new HashSet<Integer>(); | ||
| 15 | + inOrder(root,set); | ||
| 16 | + if(set.size() < 2){ | ||
| 17 | + return -1; | ||
| 18 | + } | ||
| 19 | + //根据题意，第一个值肯定是最小的值 | ||
| 20 | + int first = root.val; | ||
| 21 | + //先临时设置第二小的值是整数的最大值，后续会对这个值进行替换 | ||
| 22 | + int second = Integer.MAX_VALUE; | ||
| 23 | + for(int val : set){ | ||
| 24 | + if(first < val && val <= second){ | ||
| 25 | + second = val; | ||
| 26 | + } | ||
| 27 | + } | ||
| 28 | + return second <= Integer.MAX_VALUE ? second : -1; | ||
| 29 | + } | ||
| 30 | + | ||
| 31 | + /** | ||
| 32 | + * 中序遍历二叉树，把所有的值存放在Set集合中 | ||
| 33 | + * @param root | ||
| 34 | + * @param set | ||
| 35 | + */ | ||
| 36 | + private void inOrder(TreeNode root,Set<Integer> set){ | ||
| 37 | + if(root == null){ | ||
| 38 | + return; | ||
| 39 | + } | ||
| 40 | + inOrder(root.left,set); | ||
| 41 | + set.add(root.val); | ||
| 42 | + inOrder(root.right,set); | ||
| 43 | + } | ||
| 44 | + } | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -1 +1,46 @@ | |||
| 1 | - # 学习笔记 | ||
| 1 | + # 学习笔记 | ||
| 2 | + 之前对于二叉树的前中后遍历，一直停留在学生时代，给定一个二叉树，能够从ABCD中选出正确答案，但是要写出递归代码，总是把自己给递进去归不来，那种深深的挫败感一直停留在对算法的黑洞里。第二周的作业，在求解LeetCode671. Second Minimum Node In a Binary Tree时，忽然想到了王争老师第三章的课件中对于二叉树遍历的讲解，四五行代码，那种感觉，简单优雅，豁然开朗。于我个人而言，这是我这周最大的收获！ | ||
| 3 | + | ||
| 4 | + 二叉树的中遍历 | ||
| 5 | + | ||
| 6 | + void inOrder(TreeNode root){ | ||
| 7 | + if(null == root){ | ||
| 8 | + return; | ||
| 9 | + } | ||
| 10 | + //先-左节点 | ||
| 11 | + inOrder(root.left); | ||
| 12 | + //然后-根节点，得到当前节点的val，进行相关的逻辑处理 | ||
| 13 | + root.val; | ||
| 14 | + //最后-右节点 | ||
| 15 | + inOrder(root.right); | ||
| 16 | + } | ||
| 17 | + | ||
| 18 | + 二叉树的前序遍历 | ||
| 19 | + | ||
| 20 | + void preOrder(TreeNode root){ | ||
| 21 | + if(null == root){ | ||
| 22 | + return; | ||
| 23 | + } | ||
| 24 | + //先-根节点，得到当前节点的val，进行相关的逻辑处理 | ||
| 25 | + root.val; | ||
| 26 | + //然后-左节点 | ||
| 27 | + inOrder(root.left); | ||
| 28 | + //最后-右节点 | ||
| 29 | + inOrder(root.right); | ||
| 30 | + } | ||
| 31 | + | ||
| 32 | + 二叉树的后序遍历 | ||
| 33 | + | ||
| 34 | + void lastOrder(TreeNode root){ | ||
| 35 | + if(null == root){ | ||
| 36 | + return; | ||
| 37 | + } | ||
| 38 | + //先-左节点 | ||
| 39 | + inOrder(root.left); | ||
| 40 | + //然后-右节点 | ||
| 41 | + inOrder(root.right); | ||
| 42 | + //最后-根节点，得到当前节点的val，进行相关的逻辑处理 | ||
| 43 | + root.val; | ||
| 44 | + } | ||
| 45 | + | ||
| 46 | + 二叉树的前中后序遍历可以把二叉树表示为数组，那如果知道某个二叉树的前序数组和中序数据，如何还原二叉树? | ||
0 commit comments