算法知识点
包含树，数组，字符串，回溯，遍历等算法知识点巩固
第一题算法题目描述
对给定的两个日期之间的日期进行遍历,比如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;
}
}
