C++ 编程练习题: 左子树叶节点之和 (深度优先搜索+广度优先搜索+递归算法)
题意: 找出所有左子树上的叶节点的值之和. 3 / \ 9 20 / \ 15 7 比如上面 9 和15是左子树上的子节点, 那么求和得 24. 一般来说, 遍历树有两种方式: 深度优先DFS和广度优先BFS. 解这题的关键就在需要知道叶子节点是从左边来的还是从右边来的. C++ 定义二叉树 struct TreeNode { int val; TreeNode *left; …
Category: C++
C++ 编程练习题 – 最多水容器 (递归)
题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离. 上面的图的输入为 . 蓝色区域最可以装水为49. 最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈: class Solution { public: int f(vector<int>& height, int j) { if …
C编程练习题: 翻转整数位
题意: 给定两个整数, 计算从一个整数需要翻转几个位才能到另一个整数. 比如: 给定29 二进制为11101 和 15, 二进制是01111, 则答案是2次. 这题的关键就是用 XOR 异或来获得两个整数不同位. 因为只有当两个位不一样的时候 异或的结果才是1. 所以我们可以写成以下循环, 每次向右移1位, 累计 c & 1 int bitSwapRequired(int a, int b) { int count …
C++编程练习题: 对两单向链表求和
这题难度中等, 原因就是在实现的时候细节很多, 不容易一次性搞对. 还好这两个列表表示的整数是反过来的, 所以实现上可以边遍历边相加, 只需要在累加每一位的时候记得记住进位即可. C++单向列表定义如下: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 当然, 还有更笨的方法, 就是先把每个列表转换成数字, 然后想加再把结果换成列表. 我们需要创建一个dummy结点, 记住, 在函数返回的时候返回 dummy.next …
现代编译语言: 整数计算性能比较: Delphi, C, C++, C#, JAVA
现在的编译器已经非常强大, 在大多数情况下, 开发者无需手动进行底层代码优化. 正如计算机科学家 Donald Knuth 所说: “过早优化是万恶之源”. Pre-optimisation is the root of evil. 过早关注细节优化, 反而可能导致代码复杂度增加, 降低可读性和可维护性. 与其过度纠结于微小的性能提升, 不如专注于编写清晰/可扩展的代码, 并在真正的性能瓶颈显现后, 基于数据进行针对性的优化. 现代软件开发更强调架构设计/算法选择和合理的数据结构, 这些往往比局部优化更能带来实质性的性能提升. 以下测试是基于: Benchmark. 计算PI的程序在这里能找到 源代码. 测试机器的性能配置如下: 16GB …