ACM

2257: [Jsoi2009]瓶子和燃料 # Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1246 Solved: 756 [Submit][Status][Discuss] Description # jyy就一直想着尽快回地球，可惜他飞船的燃料不够了。 有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy 的飞船上共有 N个瓶子(1<=N<=1000) ，经过协商，火星人只要其中的K 个 。 jyy 将 K个瓶子交给火星人之后，火星人用它们装一些燃料给 jyy。所有的瓶子都没有刻度，只 在瓶口标注了容量，第i个瓶子的容量为Vi（Vi 为整数，并且满足1<=Vi<=1000000000 ） 。 火星人比较吝啬，他们并不会把所有的瓶子都装满燃料。他们拿到瓶子后，会跑到燃料 库里鼓捣一通，弄出一小点燃料来交差。jyy当然知道他们会来这一手，于是事先了解了火 星人鼓捣的具体内容。火星人在燃料库里只会做如下的3种操作：1、将某个瓶子装满燃料； 2、将某个瓶子中的燃料全部倒回燃料库；3、将燃料从瓶子a倒向瓶子b，直到瓶子b满 或者瓶子a空。燃料倾倒过程中的损耗可以忽略。火星人拿出的燃料，当然是这些操作能 得到的最小正体积。 jyy知道，对于不同的瓶子组合，火星人可能会被迫给出不同体积的燃料。jyy希望找 到最优的瓶子组合，使得火星人给出尽量多的燃料。

1012: [JSOI2008]最大数maxnumber # Time Limit: 3 Sec Memory Limit: 162 MB Submit: 9717 Solved: 4244 [Submit][Status][Discuss] Description # 现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加 上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取 模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个 数。

#1197 : Give My Text Back # 时间限制：10000ms 单点时限：1000ms 内存限制：256MB 描述 # To prepare for the English exam Little Ho collected many digital reading materials. Unfortunately the materials are messed up by a malware.

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。 比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。

转自：http://blog.csdn.net/v_july_v/article/details/6279498 第一部分、十道海量数据处理面试题 1、海量日志数据，提取出某日访问百度次数最多的那个IP。

思路： 分治搞之。 实际上两个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};

前言： # hash这种东西人人都会用的东西还有必要说？ 起因是…本问了hash中的一个细节…然后…我知道怎么做… 结果描述的不够清楚？如果知道那个做法的名字也许就不用费劲描述了呢。。。所以来复习一下吧2333

面京东被这个问题卡了QAQ，来补补这方面的课。 转自：链接 蓄水池抽样算法是随机算法的一种，用来从 N 个样本中随机选择 K 个样本，其中 N 非常大（以至于 N 个样本不能同时放入内存）或者 N 是一个未知数。其时间复杂度为 O(N)，包含下列步骤 (假设有一维数组 S, 长度未知，需要从中随机选择 k 个元素， 数组下标从 1 开始), 伪代码如下：

题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个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的题目难度比较水..不过白板写代码还是要练下的。。。我所理解的白板写代码。。。大概就是。。。用记事本。。一遍写对代码的能力吧。。。所以我来记录一下。。思路想错的或者没有秒的题目。

1303: [CQOI2009]中位数图 # Time Limit: 1 Sec Memory Limit: 162 MB Submit: 2480 Solved: 1529 [Submit][Status][Discuss] Description # 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

1800: [Ahoi2009]fly 飞行棋 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1530 Solved: 1220 [Submit][Status][Discuss] Description # 给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。