Google电面的Bit操作题, 问你能不能用一个O(1)的方法, 判断n是不是4的倍数. 既然是O(1), 所以不能用循环, 先把n对n-1取&, 假设n = 16, 即10000. n-1=15,即01111. 但是我们还需要判断这个数是不是0. 所以我们让n对一个比它小的质数取mod. 比如4%3==1, 这样就可以判断n是不是4的倍数了. public static boolean isPowerof4(int n) { return (n&n-1)+n%3==1; } 下边是power of 8 public static boolean isPowerof8(int n) { return (n&n-1)+n%7==1; }
Bit操作的题, 给一个整数+1,不能用加号. 其实很简单,扫一下整数的每个bit(从低位到高位), 对它做&操作, 如果结果是0, 证明此位是0, 那么我们在这位+1, 如果是1, 那么我们清空此位. public class addBinaryNumberBy1WithoutPlus { public int add(int n) { for(int i = 0; i < 32; i++) { if (((1 << i) & n) == 0){ //until we find the first 1 bit n = n | (1 << i); break; } else n = n […]
1. 给个数组, 已经排序了, 找到第一个比n大的数. 如果没有, 返回-1. 二分搜索一下就可以, 注意一下返回-1的条件. public static int fixBox(int[] nums, int product) { int n = nums.length; int l = 0; int r = nums.length – 1; while (l <= r) { int mid = l + (r – l) / 2; if (nums[mid] < product) l = mid + 1; else […]
给一个数组, 找出里面的两个数, 使得这两个数的乘积最大.这是geeksforgeeks上的题, 我看原题下面的代码有点复杂, 就重新想了想. 先看两个例子: Input: arr[] = {1, 4, 3, 6, 7, 0} Output: {6,7} Input: arr[] = {-1, -3, -4, 2, 0, -5} Output: {-4,-5} 但是上面的例子不能完全说明问题, 比如说{0,1,-5}, 这时候, pair应该是0, 1 OR 0, -5. 思路很简单, 通过观察上面的例子, 不难发现, 这个pair和四个数字有关: 数组中, 正数的最大值pmax和第二大值psec, 负数的最大值nmax和第二大值nsec. 而最大值应为Math.max(pmax*psec, nmax*nsec). 代码如下: public int[] find(int[] nums) { if (nums == null […]
最近好像这个面试题很流行, 因为考点很多, 而且出题人可以从这个题延展到很多基础知识, 所以是很好的面试题, 也是很好的准备基础知识的题, 大概设计的考点如下: Hash vs Encoding: 一般会问, 生成url的时候, 为什么不能通过生成hash来查找? 回答: hash有冲突. 1个tinyurl, 在decode的时候会map到多个url上. Encoding利用了URL中字符串的可能字符为定值(a->z, A->Z, 0->9, 符号不算), 把每位字符转换成数字, 然后对其用62(26(小写)+26(大写)+10(数字))位编码. 确保了唯一性.代码如下: private static final String alphabet = “abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789”; public static int encode(String s) { int res = 0; for (int i = 0 ; i < s.length(); i++) { if (‘a’ <= s.charAt(i) […]
今天geeksforgeeks上刷出来的题.一看不能用stack, 基本就是Morris遍历了. 但是做了一下, 发现需要注意的地方挺多的, 比如当我们算visit的时候, 在rebuild link后, 我们也需要increase counter. 不然打印出来的是The Bottom of Tree 代码: public static int find(TreeNode root, int k) { int count = 0;// int res = Integer.MAX_VALUE; TreeNode cur = root; while (cur != null) { if (cur.left == null) { // if left == null, then we print(or do something, in […]