C++ 编程练习题: 左子树叶节点之和 (深度优先搜索+广度优先搜索+递归算法)
题意: 找出所有左子树上的叶节点的值之和. 3 / \ 9 20 / \ 15 7 比如上面 9 和15是左子树上的子节点, 那么求和得 24. 一般来说, 遍历树有两种方式: 深度优先DFS和广度优先BFS. 解这题的关键就在需要知道叶子节点是从左边来的还是从右边来的. C++ 定义二叉树 struct TreeNode { int val; TreeNode *left; …
Tag: C#
C++ 编程练习题 – 最多水容器 (递归)
题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离. 上面的图的输入为 . 蓝色区域最可以装水为49. 最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈: class Solution { public: int f(vector<int>& height, int j) { if …
C++编程练习题: 对两单向链表求和
这题难度中等, 原因就是在实现的时候细节很多, 不容易一次性搞对. 还好这两个列表表示的整数是反过来的, 所以实现上可以边遍历边相加, 只需要在累加每一位的时候记得记住进位即可. C++单向列表定义如下: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 当然, 还有更笨的方法, 就是先把每个列表转换成数字, 然后想加再把结果换成列表. 我们需要创建一个dummy结点, 记住, 在函数返回的时候返回 dummy.next …
C++ 刷题坑: 二分查找也没有那么容易写出来
最近在刷题, 刷了一道比较简单的二分搜索, 但是却让我刷了好几次才过(果真是很久没刷 能力立马下降许多) 题意就是 不允许使用 sqrt 或者 pow 之类的函数来判断一个整数是否是平方数. 比如 4, 16, 64, 25 就是平方数而 3, 7, 11 不是. 很容易想到可以用二分搜索来解决, 算法复杂度是 O(log n), 答案如下: typedef unsigned long long …
ACM 解题报告 – O(n)找多数算法
给定一些整数, 请找出它们中的的”多数”. 一个数字如果超过了一半, 那么它就是多数. 假定这样的数是存在的. 比如, 给定 , 您的算法将给出 答案 1 因为1出现了4次超过了一半(3.5次) 最直接的算法就是通过 字典(或者HASHMAP)记录每个出现数字的次数, 然后只要判断其中一个出现超过一半了, 就返回它. class Solution { public: /* * @param nums: a list of integers * …
ACM题解系列之 – 最小堆栈 (Min Stack)
没事刷刷题能防止老年痴呆, 而且也能让你随时处于最佳状态, 随时都可以炒老板鱿鱼另谋高就. 题目: 设计一个堆栈(Stack)使 push, pop, 和取最小 min 操作时间复杂度都是 O(1). 这题的难点就是在于怎么样用O(1)常数时间复杂度来取得堆栈里的最小值. class MinStack { public: MinStack() { // write your code here } /* * @param number: An …
一顿饭与 一个 C++ 软件工程师的职位
今天晚上, 公司两大股东(其中一个是英国总公司的HR, 另一个是中国公司的总经理)请我吃饭. 我本来以为我犯了什么事呢, 提心吊胆, 结果原来是公司为了招人而犯愁呢. 我们公司(初创公司)最近在招一个 C++ 软件工程师 (C++ Software Technical Expert), 但是一直招不到合适的人选. 但项目启动迫在眉睫, 所以想听听的我意见. 客观来说, 我们公司的待遇还是不错的, 但是C++的牛人一直招不到有一大原因就是: 剑桥市有很多很牛的大公司, 比如苹果, 微软. 能力强的很多不会到剑桥郡的一个村庄里上班. 先说好处: 我们公司给办工作签证(五年英国绿卡), 所以如果你想来英国工作或生活, 这个机会难得, 因为据我所知, 英国并不是很多公司愿意给外国人发工签. …