Leetcode

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k. Example 1: 1Input: [3, 1, 4, 1, 5], k = 2 2Output: 2 3Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). 4Although we have two 1s in the input, we should only return the number of unique pairs. Example 2:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6] 思路：由于元素大小有限制，是在1..n之间。

思路： 分治搞之。 实际上两个vector就够了。。。4个会MLE(在leetcode上。。。 代码实现 1/** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 TreeNode* res; 13 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { 14 int siz = pre.size(); 15 if (siz==0) return NULL; 16 int rt = pre[0]; 17 int pos=-1; 18 for ( int i = 0 ; i < siz; i++) 19 if (vin[i]==rt) 20 { 21 pos = i; 22 break; 23 } 24 vector<int>preL,preR,vinL,vinR; 25 for ( int i = 0 ; i < pos ; i++) 26 { 27 preL.push_back(pre[i+1]); 28 vinL.push_back(vin[i]); 29 } 30 for ( int i = pos + 1 ; i < siz ; i++) 31 { 32 preR.push_back(pre[i]); 33 vinR.push_back(vin[i]); 34 } 35 TreeNode *head = new TreeNode(rt); 36 head->left = reConstructBinaryTree(preL,vinL); 37 head->right = reConstructBinaryTree(preR,vinR); 38 return head; 39 40 41 } 42}; 43 44 45 46 47/* *********************************************** 48Author :111qqz 49Created Time :2017年04月05日 星期三 16时21分35秒 50File Name :105.cpp 51************************************************ */ 52/** 53 54 * Definition for a binary tree node. 55 56 * struct TreeNode { 57 58 * int val; 59 60 * TreeNode *left; 61 62 * TreeNode *right; 63 64 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 65 66 * }; 67 68 */ 69 70class Solution { 71 72public: 73 74 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 75 76 int siz = preorder.size(); 77 if (siz==0) return NULL; 78 int rt = preorder[0]; 79 int pos; 80 for ( int i = 0 ; i < siz ; i++) 81 { 82 if (inorder[i]==rt) 83 { 84 pos = i; 85 break; 86 } 87 } 88 vector<int>preL,inL; 89 TreeNode *head = new TreeNode(rt); 90 for ( int i = 0 ; i < pos ; i++) 91 { 92 preL.push_back(preorder[i+1]); 93 inL.push_back(inorder[i]); 94 } 95 head->left = buildTree(preL,inL); 96 97 preL.clear(); 98 inL.clear(); 99 for ( int i = pos + 1 ; i < siz; i++) 100 { 101 preL.push_back(preorder[i]); 102 inL.push_back(inorder[i]); 103 } 104 head->right = buildTree(preL,inL); 105 return head; 106 107 } 108 109};

题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。 思路：单调。。显然二分。。。唯一的技巧是从右上角开始搜。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年03月09日 星期四 19时03分07秒 4File Name :74.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 bool searchMatrix(vector<vector<int>>& matrix, int target) { 11 12 int n = matrix.size(); 13 if (n==0) return false; 14 int m = matrix[0].size(); 15 if (m==0) return false; 16 int row = 0 ; 17 int col = m-1; 18 while (col>=0&&row<n) 19 { 20 if (matrix[row][col]==target) return true; 21 else 22 if (matrix[row][col]>target) col--; 23 else row++; 24 } 25 return false; 26 27 } 28 29};

题目链接 题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。 思路：想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。

题目链接 题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好 1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 13 bool leaf(TreeNode* root) 14 { 15 if (root->left==NULL&&root->right==NULL) return true; 16 return false; 17 } 18 bool mirror(TreeNode* rt1,TreeNode* rt2) 19 { 20 21 if (rt1==NULL&&rt2==NULL) return true; 22 if (rt1==NULL||rt2==NULL) return false; 23 printf("%d %d\n",rt1->val,rt2->val); 24 if (leaf(rt1)&&leaf(rt2)&&rt1->val==rt2->val) return true; 25 if (leaf(rt1)||leaf(rt2)) return false; //包含了其中一个是叶子，或者两个都是叶子但是值不相等的情况。 26 if (rt1->val!=rt2->val) return false; //不是叶子，但是值不相等，没必要继续了。 27 bool res = true; 28 res = mirror(rt1->left,rt2->right); 29 if (!res) return false; 30 res = mirror(rt2->left,rt1->right); 31 if (!res) return false; 32 return true; 33 } 34 bool isSymmetric(TreeNode* root) { 35 if (root==NULL) return true; 36 return mirror(root,root); 37 38 } 39};

题目链接 题意：判断一颗二叉树是否平衡…. 思路：直接搞就好了。。。神TM又忘记dfs的时候忘记返回子调用的值。。。。我这是药丸啊。。。 1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { //错误原因：左右子树都平衡的树未必平衡！！！！ 11public: 12 bool leaf(TreeNode* root) 13 { 14 if (root->left==NULL&&root->right==NULL) return true; 15 return false; 16 } 17 int dep(TreeNode* root) 18 { 19 if (root==NULL) return 0; 20 return max(dep(root->left),dep(root->right))+1; 21 } 22 bool dfs(TreeNode* root) 23 { 24 bool res = true; 25 if (abs(dep(root->left)-dep(root->right))>1) return false; 26 if (root->left!=NULL) res = dfs(root->left); 27 if (!res) return false; 28 if (root->right!=NULL) res = dfs(root->right); 29 if (!res) return false; 30 return true; 31 } 32 bool isBalanced(TreeNode* root) { 33 if (root==NULL) return true; 34 bool res = dfs(root); 35 return res; 36 } 37};

题目链接 题意：求一个BST中某两个节点LCA…. 思路：卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。

题目链接 题意：求一棵树的深度。。。。 思路：。。。定义搞即可。。按照左右子树中大的算。。。因为据说是经典题（虽然并不觉得2333。。。所以记录下。。。 1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 13 int dfs(TreeNode* root) 14 { 15 if (root==NULL) return 0; 16 return max(dfs(root->left),dfs(root->right))+1; 17 } 18 19 int maxDepth(TreeNode* root){ 20 if (root==NULL) return 0; 21 int res = dfs(root); 22 return res; 23 24 25 } 26};

题目链接 题意：反转一棵二叉树。。。字面意思理解即可。。就是把每一棵子树的左右孩子交换。。。 思路：直接照着题意做就好了。。。没有坑。。记录的原因是听说这题比较经典（虽然毫无难度…

题目链接 题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的val之和等于给定的sum。 思路：。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。

leetcode108 题意：把一个有序的数组转化成一棵高度尽量小的bst(二叉搜索树) 思路：我竟然忘记了什么是bst……..我好傻啊…不过想想可能是因为…最朴素的二叉搜索树几乎用不到…所以很容易忘记吧2333

最近要准备面试…虽然leetcode的题目难度比较水..不过白板写代码还是要练下的。。。我所理解的白板写代码。。。大概就是。。。用记事本。。一遍写对代码的能力吧。。。所以我来记录一下。。思路想错的或者没有秒的题目。