算法】字符串复原IP地址，从前序与中序编辑序列构造二叉树

算法学习有些时候是枯燥的，一点一点学习算法

第一题算法题目描述

对给定的两个日期之间的日期进行遍历,比如startTime 是 2014-07-11；endTime 是 2014-08-11 如何把他们之间的日期获取并遍历出来。

java解题参考代码

private static List<Date> dateSplit(Date startDate, Date endDate) throws Exception { if (!startDate.before(endDate)) throw new Exception("开始时间应该在结束时间之后"); Long spi = endDate.getTime() - startDate.getTime(); Long step = spi / (24 * 60 * 60 * 1000); List<Date> dateList = new ArrayList<Date>(); dateList.add(endDate); for (int i = 1; i <= step; i++) { dateList.add(new Date(dateList.get(i - 1).getTime() - (24 * 60 * 60 * 1000))); } return dateList; } public static void main(String[] args) throws ParseException { try { SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd"); Date start = sdf.parse("2015-4-20"); Date end = sdf.parse("2015-5-2"); List<Date> lists = dateSplit(start, end); if (!lists.isEmpty()) { for (Date date : lists) { System.out.println(sdf.format(date)); } } } catch (Exception e) { } }

第二题算法题目描述

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

示例 1：

输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000" 输出：["0.0.0.0"]

示例 3：

输入：s = "1111" 输出：["1.1.1.1"]

示例 4：

输入：s = "010010" 输出：["0.10.0.10","0.100.1.0"]

示例 5：

：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

0 <= s.length <= 3000 s 仅由数字组成

java解题参考代码

public static void main(String[] args) throws ParseException { List<String> s= restoreIpAddresses("0000"); System.out.println(s); } private static List<String> res = new ArrayList<>(); public static List<String> restoreIpAddresses(String s) { if (s.length() < 4) return res; backtrack(s, 0, new StringBuilder(), 0); return res; } private static void backtrack(String s, int start, StringBuilder sb, int pointNumOfSb) { if (pointNumOfSb > 4) return; if (start == s.length() && pointNumOfSb == 4) { res.add(sb.toString().substring(1)); return; } for (int i = start; i < s.length() && i - start < 3; i++) { String x = s.substring(start, i + 1); if (x.charAt(0) == '0' && x.length() > 1) return; if (Integer.parseInt(x) <= 255) { sb.append("." + x); backtrack(s, i + 1, sb, pointNumOfSb + 1); sb.delete(sb.lastIndexOf("."), sb.length()); } } }

第三题算法题目描述

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1] Output: [-1]

提示:

1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 均无重复元素 inorder 均出现在 preorder preorder 保证为二叉树的前序遍历序列 inorder 保证为二叉树的中序遍历序列

java解题参考代码

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length != inorder.length) return null; if (preorder.length == 0) return null; if (preorder.length == 1) return new TreeNode(preorder[0]); return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1); } private TreeNode buildTree(int[] preorder, int[] inorder, int prei, int prej, int ini, int inj) { if (prei > prej || ini > inj || prei < 0 || prej >= preorder.length || ini < 0 || inj >= inorder.length) return null; if (prej - prei < 0) return null; if (prei == prej) return new TreeNode(preorder[prei]); TreeNode root = new TreeNode(preorder[prei]); int inFlag = 0; for (int i = ini; i <= inj; i++) { if (inorder[i] == root.val) { inFlag = i; break; } } int num_left = inFlag - ini; int num_right = inj - inFlag; root.left = buildTree(preorder, inorder, prei + 1, prei + num_left, ini, inFlag - 1); root.right = buildTree(preorder, inorder, prej - num_right + 1, prej, inFlag + 1, inj); return root; } }