写点什么

ARTS 打卡 Week 09

用户头像
teoking
关注
发布于: 2020 年 07 月 31 日
ARTS打卡Week 09

每周完成一个 ARTS:

Algorithm: 每周至少做一个 LeetCode 的算法题

Review: 阅读并点评至少一篇英文技术文章

Tips: 学习至少一个技术技巧

Share: 分享一篇有观点和思考的技术文章



Algorithm

  1. Construct Binary Tree from Preorder and Inorder Traversal

import java.util.HashMap;
// LC 105: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class ConstructBinaryTreefromPreorderAndInorderTraversal {
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
/*
build([3, (9), (20, 15, 7)], [(9), 3, (15, 20, 7)])
root=3
/ \
/ \
build([9], [9]) build([20, (15, 7)], [(15), 20, (7)])
root=9 root=20
/ \
/ \
build([15], [15]) build([7], [7])
root=15 root=15
*/
// Runtime: 3 ms, faster than 67.96% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
// Memory Usage: 40.2 MB, less than 10.29% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
static class RecursiveSolution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, 0, 0, preorder.length);
}
TreeNode build(int[] preorder, int[] inorder, int preStart, int inStart, int len) {
if (len <= 0) return null;
TreeNode root = new TreeNode(preorder[preStart]);
if (len == 1) return root;
int k = inStart;
while (root.val != inorder[k]) {
k++;
}
int n = k - inStart;
root.left = build(preorder, inorder, preStart + 1, inStart, n);
root.right = build(preorder, inorder, preStart + n + 1, k + 1, len - n - 1);
return root;
}
}
// Runtime: 3 ms, faster than 67.96% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
// Memory Usage: 42.8 MB, less than 5.08% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
static class RecursiveHashMapOptSolution {
HashMap<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>(preorder.length * 2);
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, inorder, 0, 0, preorder.length);
}
TreeNode build(int[] preorder, int[] inorder, int preStart, int inStart, int len) {
if (len <= 0) return null;
TreeNode root = new TreeNode(preorder[preStart]);
if (len == 1) return root;
int k = map.get(root.val);
int n = k - inStart;
root.left = build(preorder, inorder, preStart + 1, inStart, n);
root.right = build(preorder, inorder, preStart + n + 1, k + 1, len - n - 1);
return root;
}
}
}



Review

Android Development 最佳实践



Tips

最近碰到一个UICollectionView的Cell动态高度的问题,尝试了很多方法都无法解决(包括使用view flowlayout delegate)。直到:

Note that in 99% of cases, to achieve full width cells + autolayout dynamic height, simply use a table view. It's that easy.

折腾了大半天后,尝试了将UICollectionView改写为UITableView(恰好我的场景可以改写)后,列表UI错乱问题终于解决了。

与同事沟通时,他认为iOS - CollectionViewCell 对应不同 flow layout 的实例所描述的方案有些复杂,会面临一些不可预知的坑。建议采用“child view controller”的方案,并对view controller做好内存管理,可以很好的解决我这个场景的问题。

Share

周末在古北水镇玩了一趟,第一次去,总体上还是值得去玩的。

但论好玩程度,跟乌镇还是差一些:吃的东西比较匮乏,逛吧,也没有明显有乐趣的点;唯一亮点是挨着司马台长城,古镇逛得无聊可以去爬个长城,全场5.7公里,路线比八达岭好且人少。



用户头像

teoking

关注

Monkey plays software. 2018.11.28 加入

程序员。目前主要从事Android和iOS开发。

评论

发布
暂无评论
ARTS打卡Week 09