{"id":288,"date":"2018-12-20T00:55:43","date_gmt":"2018-12-19T16:55:43","guid":{"rendered":"http:\/\/kaispace.cn\/?p=288"},"modified":"2018-12-20T00:55:43","modified_gmt":"2018-12-19T16:55:43","slug":"leetcode%e5%ad%a6%e4%b9%a0%e8%ae%b0%e5%bd%95","status":"publish","type":"post","link":"https:\/\/blog.kaispace.cn\/?p=288","title":{"rendered":"LeetCode\u5b66\u4e60\u8bb0\u5f55"},"content":{"rendered":"

\u53ea\u8bb0\u5f55\u611f\u89c9\u6bd4\u8f83\u6709\u8da3\u7684\u9898<\/h3>\n

1.\u4e8c\u53c9\u6811\u5408\u5e76<\/h2>\n

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.<\/p>\n

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.<\/p>\n

INPUT:[1,3,2,5][2,1,3,null,4,null,7]
\nOUTPUT:[3,4,5,5,4,null,7]<\/p>\n

\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode(int x) { val = x; }\n * }\n *\/\nclass Solution {\n    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {\n        \/* Current Node have 4 Condition\n        *   \u3010NotNull && NotNull\u3011 \u3010Null && NotNull\u3011 \u3010NotNull && Null\u3011 \u3010Null && Null\u3011\n        *   If return t1 means you only concern about condition 1 and 2,3,4 are not matter\n        *\/\n        if(t1!=null&&t2!=null){\n            t1.val += t2.val;\n            if(t1.left==null&&t2.left!=null){\n                t1.left = t2.left;\n            }else if(t1.left!=null&&t2.left!=null){\n                mergeTrees(t1.left,t2.left);\n            }\n            if(t1.right==null&&t2.right!=null){\n                t1.right = t2.right;\n            }else if(t1.right!=null&&t2.right!=null){\n                mergeTrees(t1.right,t2.right);\n            }\n        }else if(t1==null&&t2!=null){\n            t1 = t2;\n        }\n        return t1;\n    }\n}\n<\/code><\/pre>\n
Result:85\/85 Time:6ms<\/p>\n
2.\u8ba1\u7b97\u6c49\u660e\u8ddd\u79bb<\/h2>\n
\u6c49\u660e\u8ddd\u79bb<\/a>
\nbetween two integers is the number of positions at which the corresponding bits are different.<\/p>\n
Given two integers\u00a0x\u00a0and\u00a0y, calculate the Hamming distance.<\/p>\n
INPUT:1,4
\nOUTPUT:2<\/p>\n
\/*\n* \u539f\u672c\u6211\u662f\u7528\u96642\u53d6\u4f59\u53f3\u79fb\uff0c\u4f46\u76f8\u6bd4\u76f4\u63a5\u6216\u8fd0\u7b97\uff0c\u6162\u592a\u591a\u4e86\uff0c\u6ca1\u60f3\u5230\u554a\n*\/\nclass Solution {\n    public int hammingDistance(int x, int y) {\n        int n = x^y;\n        int setBits = 0;\n        while(n>0){\n            setBits += n&1;\n            n >>= 1;\n        }\n\n        return setBits;\n    }\n}\n<\/code><\/pre>\n
3.DI\u5b57\u7b26\u4e32\u5339\u914d<\/h2>\n
Given a string\u00a0S\u00a0that\u00a0only<\/strong>\u00a0contains “I” (increase) or “D” (decrease), let\u00a0N = S.length.
\nReturn\u00a0any<\/strong> permutation\u00a0A\u00a0of\u00a0[0, 1, …, N]\u00a0such that for all\u00a0i = 0,\u00a0…, N-1:<\/p>\n
If\u00a0S[i] == “I”, then\u00a0A[i] < A[i+1]
\nIf\u00a0S[i] == “D”, then\u00a0A[i] > A[i+1]<\/p>\n
INPUT:”IDID”
\nOUTPUT:[0,4,1,3,2]<\/p>\n
\/*\n* \u51e0\u4e4e\u662f\u6700\u4f18\u7684\u529e\u6cd5\n*\/\nclass Solution {\n    public int[] diStringMatch(String S) {\n        int len = S.length();\n        int[] result = new int[len+1];\n        int min=0,max=len;\n        for(int i = 0;i<len;i++){\n            result[i] = S.charAt(i) == 'I' ? min++:max--;\n        }\n        result[len] =  max;\n        return result;\n    }\n}\n<\/code><\/pre>\n
4.\u4e8c\u53c9\u6811\u6700\u5927\u6df1\u5ea6<\/h2>\n
\/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode(int x) { val = x; }\n * }\n *\/\nclass Solution {\n    public int maxDepth(TreeNode root) {\n        int i = 0;\n        return searchTreeNode(root,i);\n    }\n\n    public int searchTreeNode(TreeNode node,int depth){\n        int leftDepth,rightDepth;\n        if(node!=null){\n            depth++;\n            leftDepth = searchTreeNode(node.left,depth);\n            rightDepth = searchTreeNode(node.right,depth);\n            depth = leftDepth > rightDepth ? leftDepth : rightDepth;\n        }\n        return depth;\n    }\n}\n<\/code><\/pre>\n
5.\u6c42\u5355\u6b21\u51fa\u73b0\u7684\u6570\u5b57<\/h2>\n
Given a\u00a0non-empty<\/strong>\u00a0array of integers, every element appears\u00a0twice\u00a0except for one. Find that single one.<\/p>\n
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?\u8981\u6c42\u7a7a\u95f4\u8981\u6781\u5ea6\u5c0f<\/p>\n
class Solution {\n    public int singleNumber(int[] nums) {\n        int a = 0;\n        \/\/\u601d\u60f3\u5c31\u662f\u7528\u5f02\u6216\uff0c\u5f02\u6216\u4e24\u6b21\u8fd8\u662f\u4f1a\u6062\u590d\u539f\u6765\u7684\u503c\u8fd9\u4e2a\u601d\u60f3\uff0c\u4fdd\u8bc1\u4f1a\u6062\u590d\uff0c\u5999\u554a\n        for (int n : nums) a ^= n;\n        return a ;\n    }\n}\n<\/code><\/pre>\n
\u539f\u6765\u6211\u662f\u7528HashSet\u5728\u7b2c\u4e8c\u6b21\u51fa\u73b0\u5c31\u79fb\u9664\u90a3\u4e2a\u70b9\uff0c\u5230\u6700\u7ec8HashSet\u4e2d\u53ea\u6709\u4e00\u4e2a\u6570\u5b57\u5c31\u662f\u90a3\u4e2aSingleNum,\u4f46\u662f\u5bf9\u6bd4\u8fd9\u79cd\u65b9\u6cd5\u8fd8\u662f\u592a\u7b28\u4e86\uff0c\u4f4d\u8fd0\u7b97\u662f\u771f\u6ef46<\/p>\n
6.\u79fb\u52a80<\/h2>\n
Given an array\u00a0nums, write a function to move all\u00a00’s to the end of it while maintaining the relative order of the non-zero elements.<\/p>\n
class Solution {\n    public void moveZeroes(int[] nums) {\n    if(nums == null || nums.length == 0) return;\n        int k = -1;\n        for(int i = 0; i < nums.length; i++) {\n            if(nums[i] != 0) {\n            \/\/k\u4e3a\u975e0\u7684\u7d22\u5f15,\u4e00\u6b65\u5230\u4f4d\u76f4\u63a5\u628a\u975e\u6570\u5b57\u79fb\u52a8\u5230\u5e94\u8be5\u5728\u7684\u4f4d\u7f6e\n                nums[++k] = nums[i];\n            }\n        }\n        \/\/\u6700\u7ec80-k\u5219\u4e3a\u6240\u6709\u975e0\u7684\u5185\u5bb9,k+1\u5230length\u518d\u8865\u4e0a0\n        for(int i = k + 1; i < nums.length; i++) {\n            nums[i] = 0;\n        }\n    }\n}\n<\/code><\/pre>\n
\u628a\u91cd\u70b9\u653e\u5728\u975e0\u800c\u4e0d\u662f0\uff0c\u7528\u4e00\u4e2a\u7d22\u5f15\u4f5c\u4e3a\u7ef4\u62a4\u975e0\u7684\u4f4d\u7f6e\uff0c\u8fbe\u5230\u65e0\u8bba\u4e2d\u95f4\u591a\u5c11\u4e2a0\u90fd\u80fd\u4e00\u6b65\u5230\u4f4d\u5230\u8fbe\u975e0\u7684\u6700\u5927\u4f4d\u7f6e\uff0c\u6700\u7ec8\u624d\u586b\u51450\uff0c\u8fd9\u662f\u6700\u4f18\u7684\u529e\u6cd5\u4e86(\u81ea\u5df1\u6709\u60f3\u5230\u8fd9\u4e2a\u601d\u8def\uff0c\u4f46\u662f\u590d\u6742\u5316\u4e86\uff0c\u628a\u91cd\u70b9\u6ce8\u91cd\u57280\u7684\u4f4d\u7f6e\uff0c\u7528k\u7ef4\u62a4\u662f\u6700\u7b80\u5355\u76f4\u63a5\u7684\u65b9\u6cd5)<\/p>\n
7.\u4e0d\u7528+-\u5b9e\u73b0\u4e24\u6570\u4e4b\u548c<\/h2>\n
class Solution {\n    public int getSum(int a, int b) {\n        return (a&b)==0 ? a^b : getSum( (a&b)<<1, a^b );\n    }\n}\n<\/code><\/pre>\n
8. Shortest Distance to a Character<\/h2>\n
\u53cc\u5411\u524d\u8fdb\u6c42\u8ddd\u79bb\uff0c\u5f53\u5f53\u524d\u6700\u8fd1\u4e00\u4e2aC\u7684\u4f4d\u7f6e\u662f\u672a\u77e5\u65f6\uff0c\u5148\u628a\u8ddd\u79bb\u8bbe\u4e3aMAXVALUE\uff0c\u56e0\u4e3a\u53cd\u5411\u904d\u5386\u65f6\u4f1a\u586b\u6ee1\u3002\u53ea\u8bb0\u5f55\u524d\u8fdb\u4e2d\u6700\u540e\u4e00\u4e2a\u67e5\u5230\u7684C\u7684\u8ddd\u79bb\uff0c\u8fbe\u5230\u81ea\u52a8\u6700\u8fd1\u7684\u4f5c\u7528\u3002<\/p>\n
class Solution {\n    public int[] shortestToChar(String S, char C) {\n        int[] res = new int[S.length()];\n\n        if(S == null || S.length() == 0) return res;\n        char[] c = S.toCharArray();\n\n        int prev = -1;\n        for(int i = 0; i < c.length; i++) {\n            if(c[i] == C) {\n                prev = i;\n            }\n            res[i] = prev == -1 ? Integer.MAX_VALUE : i - prev;\n        }\n\n        prev = Integer.MAX_VALUE;\n        for(int i = c.length-1; i >= 0; i--) {\n            if(c[i] == C) {\n                prev = i;\n            }\n            res[i] = Math.min(res[i], prev - i);\n        }\n        return res;\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u53ea\u8bb0\u5f55\u611f\u89c9\u6bd4\u8f83\u6709\u8da3\u7684\u9898 1.\u4e8c\u53c9\u6811\u5408\u5e76 Given two binary trees and imagine …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[3],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=\/wp\/v2\/posts\/288"}],"collection":[{"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=288"}],"version-history":[{"count":0,"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=\/wp\/v2\/posts\/288\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=288"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=288"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kaispace.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=288"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}