Category: 计算机
题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离. 上面的图的输入为 . 蓝色区域最可以装水为49. 最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈: class Solution { public: int f(vector<int>& height, int j) { if …
题意: 给定两个整数, 计算从一个整数需要翻转几个位才能到另一个整数. 比如: 给定29 二进制为11101 和 15, 二进制是01111, 则答案是2次. 这题的关键就是用 XOR 异或来获得两个整数不同位. 因为只有当两个位不一样的时候 异或的结果才是1. 所以我们可以写成以下循环, 每次向右移1位, 累计 c & 1 int bitSwapRequired(int a, int b) { int count …
这题难度中等, 原因就是在实现的时候细节很多, 不容易一次性搞对. 还好这两个列表表示的整数是反过来的, 所以实现上可以边遍历边相加, 只需要在累加每一位的时候记得记住进位即可. C++单向列表定义如下: struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 当然, 还有更笨的方法, 就是先把每个列表转换成数字, 然后想加再把结果换成列表. 我们需要创建一个dummy结点, 记住, 在函数返回的时候返回 dummy.next …
2018年7月19日
ACM题解, 学习笔记, 数学, 数据结构与算法, 有意思的, 程序员, 程序设计, 算法, 编程, 计算机, 软件工程, 面试
这题据说是 GOOGLE的面试题, 但是却真实的被一些软件公司拿来考应聘者. 比如我在前几年面试剑桥的博通公司/Broadcom, 在第二轮也被问到了这个问题. 题意是: 给你两个鸡蛋, 有个100层楼, 你可以把鸡蛋从任意一层楼扔下, 鸡蛋可能破, 也可能不破, 如果不破的话, 你可以继续用这个鸡蛋扔. 你需要用这两个鸡蛋来试出鸡蛋会破的最小楼层高度. 这两个鸡蛋一模一样. 问你采用什么策略可以使最坏情况下的尝试次数最少? 什么是最差情况? 如果你只有一个鸡蛋, 那么你最坏需要100次(需要从1层楼开始测试)才可以得到结论. 最直接的做法就是从第一层开始试, 然后第二层以此类推, 但是这种方法只需要用到1个鸡蛋即可. 如果第N层鸡蛋没碎但是第N+1层碎了, 答案就是N. 这种情况下最坏需要尝试100次. 如果我们在第50层扔呢? 如果鸡蛋碎了, 那么答案就在第1到第49层, 反之答案就在第51到第100. …
我们都知道 斐波那契数列 的定义如下: We all know the Fibonacci sequence is defined as: and the terminating conditions are 其中 First few Fibonacci numbers are 前面几项的值为: 0, 1, 1, 2, 3, …
问题: Python 的 List 和 Dictionary 有啥区别? 不许查资料, 你怎么回答这个面试题? 我不加思索的回答到: List 就像数组一样 而 Dictionary 是 键值对的一数据结构. 面试官继续说, 那么 Dictionary 是有序的么? 啥? 啥是有序? 我还是犹豫了一下, 说是无序的, 面试官说, 为什么? 我说, 因为 Python …
现在最吃香的工程师是 全栈工程师 (Full Stack), 因此你除了要好的算法数据结构知识外 你还需要懂数据库等计算机知识. 有人说, SQL好简单, 其实SQL也可以考考你的逻辑, 比如有这么一个简单的 (含有两个字段, 三行记录) 的关系表 (假设表名为 Employee). 对了, 数据工程师/Data Engineer, 还有相关的一些职位: Machine Learning Engineer/机器学习工程师等 都会需要面试SQL. +----+--------+ | Id | Salary | …
