C++ 编程练习题: 如何合并两个二叉树?
题意: 合并两个二叉树, 没有说不可以改变原来的二叉树. 合并的时候把结点求合. C/C++ 中二叉树的定义 在C或者C++中, 二叉树的定义可以很方便的用结构体来表征. 其中左右子树都是递归定义. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) …
Tag: 算法
C++编程练习题: 找出字符串的所有大小小组合
题意: 给定一个字符串, 输出所有字符大小写都可以组成的字符串. 如: “ab1” 能成生 DFS 深度优先 – 递归 我们可以从字符串的开头递归的把当前字符给添加到最终的字符串中, 当当前字符是字母的时候, 就有两种可能了. 当到达字符串尾部的时候我们把当前字符串添加到结果数组中即可. class Solution { public: vector<string> letterCasePermutation(string S) { search("", S, 0, S.length() - 1); return …
C++ 编程练习题 – 找出第三大的数
题意: 给出一个数组, 求第三大的数字是多少, 重复的数字并不算在内, 比如 第3大的数字是1 而不是 2. Using std::set set 是集合, 是有序的(从小到大), 集合中不包含重复的元素, 所以我们可以遍历数组并把数字添加到集合中. 在这过程中, 如果集合大小大于三个, 就把最小的元素删除. 我们不能直接按照索引的访问集合中的元素, 但是我们可以用迭代器 rbegin() 和 begin() 来访问集合中最大和最小的元素. class Solution { public: int …
C++ 编程练习题 – 最多连续的 1
Given a binary array, find the maximum number of consecutive 1s in this array. Example 1: Input: Output: 3 Explanation: The first two digits or the last three digits …
C++ 编程练习题: 左子树叶节点之和 (深度优先搜索+广度优先搜索+递归算法)
题意: 找出所有左子树上的叶节点的值之和. 3 / \ 9 20 / \ 15 7 比如上面 9 和15是左子树上的子节点, 那么求和得 24. 一般来说, 遍历树有两种方式: 深度优先DFS和广度优先BFS. 解这题的关键就在需要知道叶子节点是从左边来的还是从右边来的. C++ 定义二叉树 struct TreeNode { int val; TreeNode *left; …
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 …