程序员达达

面试题

[LeetCode] Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight). For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3. [分析] 最笨的解法就是每次移位,这样的话不管是多少个1,都要循环执行32次。比较巧妙的解法可以将循环次数减少到与1的个数一样。利用的性质就是n-1之后,n最低位的1之后(包括其本身)的所有bits翻转。 这篇文章对于数1的个数,分析得很透彻。 [注意事项] 1)题目里面unsigned和signed的int会影响到种植条件的判定。比如说第5行中如果改为n

[LeetCode] Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. [分析] 第一反应就是排序然后返回中位数。 [注意事项] 这种做法其实破坏了原来的数组,而且复杂度为O(nlogn)不知道还有没有别的更高效的解法。 [Code] 1 2 3 4 5 6 public class Solution…