JS

JS-OJ(1)

最近在做LeetCode有各种语言。刚好有JavaScript。做做算法的同时也能熟悉JS。

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
2
3
4
5
6
7
8
9
10
11
var hammingWeight = function(n) {
    var bits = n.toString(2);
    var pos = bits.indexOf("1");
    var i = 0;
    while(pos > -1)
    {
        i++;
        pos = bits.indexOf("1",pos+1);
    }
    return i; 
};

求汉明重量。就是找出一个二进制的数字中有多少个1。
直接用最暴力的方法就是转化之后一个个数出来。
Number类型的toString()方法返回字符串形式的数值，传递一个表示基数的参数能返回对应进制。
String类型的indexOf()从字符串中搜索给定的子字符串，返回位置。第二个参数表示从字符串中的哪个位置开始搜索。上面的方法就是遍历一个字符串的感觉了
看C的解法都是右移啊，与运算啊什么的。

1
2
3
4
5
6
7
8
9
10
11
var hammingWeight = function(n) {
  var re = 0;
  
  while(0 !== n)
    {
      n = n&(n-1);
      ++re;
    }
  
  return re;
};

可是这个解法用的时间比我前面的解法还要多几毫秒。
然后用上面的位运算换成C语言来写。结果吓尿了哈哈：
JS用了170ms
c用了1ms…
根本不是一个重量级啊…
Number of 1 Bits

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
var bits = n.toString(2);
var length = bits.length;
var newbits = "";
for(var i = bits.length;i<32;i++){
  bits = "0".concat(bits);
}
length = bits.length;
    
while(length--){
  newbits = newbits.concat(bits[length]);
}
    return parseInt(newbits,2);
};

没找到直接把数字类型中转换为32位的方法。直接手动写成了。。原来弱类型的语言有这个坏处。以前一直觉得弱类型好好，不用考虑太多。太年轻啦。
然后是字符串的转置（后面还有一种方法），最后再转成数字。
parseInt(),第二个参数是以此为基数转化字符串。和toString()有点类似呢。。
Reverse Bits

Rotate Array

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    k = k%nums.length;
var Reverse = function(arr,begin,end){
  for(;begin<end;begin++,end--){
    arr[begin] ^= arr[end];
    arr[end] ^= arr[begin];
    arr[begin] ^= arr[end];
  }
};
Reverse(nums,0,nums.length-k-1);
Reverse(nums,nums.length-k,nums.length-1);
Reverse(nums,0,nums.length-1);
};

传说中的无空间交换数字大法。。。
一个数字异或两次等于他本身。

1
2
3
a = a ^ b;
b = a ^ b;
a = a ^ b;

看起来逼格很高的样子。。
然后就是ba = (a*b*)* *是转置的意思。
嗯就是这样，编程珠玑的解法。
Rotate Array

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    var count = 0;
    while(n){
        count += Math.floor(n/5);
        n /= 5;
    }
    return count;
};

这些简单的题目解法也是好简洁啊。
不过想了很久都不知道怎么做。还是看了一下答案。
尾数为0只能是25；
所以可以把n!分解为2^n5^m;
因此0的个数是min(n,m);
又因为在阶乘里，必然有n>m；
所以求出n!里有多少个5就好了。
Factorial Trailing Zeroes

分享到