Duplicate Zeros
往后加一个0，然后移动其他数 看到讨论里有个o(1) time, o(n) space的, 利用queue作为结果的预存储:
Leetcode
Shortest Word Distance
给一个字符串数组, 并给出两个words, 求最短距离. 直接用map
Happy Number
public boolean isHappy(int n) { // Write your code here if(n <= 0) return false; long nn = (long)n; Set<Long> set = new HashSet<Long>(); while(true) { if(nn == 1) return true; if(set.contains(nn)) return false; else set.add(nn); long tmp = 0; while(nn != 0){ tmp+= (nn % 10)*(nn % 10); nn/=10; } nn = tmp; […]
Binary Tree Paths
打印所有的从root到leaf的path. 开始用的queue做的..后来看了下别的人的答案, 感觉都很简练.po一个别人的答案 public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<String>(); if(root == null) return res; if(root.left == null && root.right == null) res.add(root.val + “”); else{ if(root.left != null) res.addAll(binaryTreePaths(root.left)); if(root.right != null) res.addAll(binaryTreePaths(root.right)); for(int i = 0 ; i < res.size(); i++) res.set(i,root.val + “->” + res.get(i)); } return res; […]
Verify Preorder Array for Binary Search Tree
给一个int的array, 问你这个array是不是一个bst的preorder. 用stack做preorder遍历” 如果当前元素大于stack里的元素, 证明我们在遍历一个node的右节点, 这时,因为是preorder, 说明左节点已经遍历过了, 所以我们要把stack中所有小于当前元素的节点pop出来,并且用low记录最后的一个. 如果当前元素比low小, 证明循序有错误, 因为low是左子树中最小的元素. 然后每次把当前node放入stack, 最后stack中有元素也不影响判断是不是preorder public boolean verifyPreorder(int[] preorder) { int low = Integer.MIN_VALUE; Stack<Integer> st = new Stack<>(); for(int p : preorder){ if (p < low) return false; while (!st.empty()&& st.peek() < p) low = st.pop(); st.push(p); } return true; }
关于Integer越界的处理
刚才刷题, Leetcode中, Reverse Integer 和 String to Integer (atoi), 都要对结果进行越界处理. 什么是越界处理? 越界处理就是当整形数据超过最大/最小值的时候, 需要对数据进行判断, 避免程序出错. 可以用以下code进行对Integer的越界处理: if(Math.abs(res) > (Integer.MAX_VALUE – Math.abs(update_value)) / 10) return 0; 这里的res就是以上两题中, 每次需要做 res = res*10 + update_value的结果值, 我们在更新res前判断下次更新会不会越界(超过Integer.MAX_VALUE).
Count Complete Tree Nodes
算一个完全树的节点个数 答案是抄的 public class Solution { public int countNodes(TreeNode root) { int leftDepth = leftDepth(root); int rightDepth = rightDepth(root); if (leftDepth == rightDepth) return (1 << leftDepth) – 1; else return 1+countNodes(root.left) + countNodes(root.right); } private int rightDepth(TreeNode root) { // TODO Auto-generated method stub int dep = 0; while (root != null) { root […]
Binary Tree Maximum Path Sum
给一个二叉树, 问你path sum最大是多少, 返回最大值 遍历所有node, 如果当前的path sum小于0, 那么是对sum没帮助的, 只关心大于0的. 然后找到最大就行了 int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { if(root == null) return 0; helper(root); return max; } public int helper(TreeNode root) { if (root == null) return 0; int left = Math.max(helper(root.left), 0); int right = Math.max(helper(root.right), 0); max = Math.max(max, root.val + left […]
Group Shifted Strings
给一组string, 定义一下shift “abc” – >; “bcd” ->; … ->; “xyz” 让你找这组string中,能互相shift的几组. 可以看出, 当一个string的字符之间的距离决定了shift后的string. 所以对字符之间的距离进行记录, 当做key, 就可以找到. 这里先取一下string首字母当做offset, 然后算距离. 最后记录在一个key(string)中. public List<List<String>> groupStrings(String[] strings) { List<List<String>> res = new ArrayList<List<String>>(); HashMap<String, List<String>> maps = new HashMap<>(); for(int i = 0 ; i < strings.length; i++) { String key = “”; int offset = strings[i].charAt(0) – ‘a’; […]
Closest Binary Search Tree Value
给一个 bst和一个double, 问你能不能找到一个值,和target的值最相近. 很naive的解法.在二叉遍历的同时, 记录当前节点值合给的值的差. public int closestValue(TreeNode root, double target) { int res = root.val; while(root != null){ if(Math.abs(root.val – target) < Math.abs(res – target)) res = root.val; if(root.val < target) root = root.right; else root = root.left; } return res; }