leetcode刷題記錄(9)

1.階乘後的0

題目：給定一個整數 n，傳回 n! 結果尾數中零的數量。

思路：自習觀察可知，多少個0取決于數字的因數有多少個5（包括5自身），因為5×2就有一個0，偶數肯定有2，偶數的數量比5更多，是以因數中5的數量就是階乘的結果中0的數量

/**
 * @param {number} n
 * @return {number}
 */

const trailingZeroes = function (n) {
  let res = arguments[1] ? arguments[1] : 0;
  if (n < 5) {
    return res;
  }
  v = (n / 5) | 0;
  return trailingZeroes(v, res + v);
};
           

2.旋轉數組

題目：給定一個數組，将數組中的元素向右移動 k 個位置，其中 k 是非負數。

思路：首先，用pop和unshift方法，執行k次即可

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  for (let i = 0; i < k; i++) {
    let item = nums.pop();
    nums.unshift(item);
  }
};
           

優化方向：一次性完成操作。向右移動k，其實就是将後k個元素插入到前面。，用splice方法

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  if (nums.length < 2) return;
  const l = k % nums.length;
  nums.splice(0, 0, ...nums.splice(nums.length - l, l));
};
           

第三種方法：不修改原數組，借助一個新數組，将原數組的元素拷貝到新數組，然後替換即可

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
  if (nums.length < 2) return;
  const l = nums.length;
  const v = k % l;
  const res = [];
  nums.forEach((i, index) => {
    res[(index + v) % l] = i;
  });
  nums.splice(0, l, ...res);
};
           

3.颠倒二進制位

題目：颠倒給定的 32 位無符号整數的二進制位。

思路：轉換成字元串然後颠倒，再轉換成數字

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
  const s = n.toString(2).padStart(32, "0");
  let res = "";
  for (let i = 0, l = s.length; i < l; i++) {
    res = s[i] + res;
  }
  return parseInt(res, 2);
};
           

4.位1的個數

題目：編寫一個函數，輸入是一個無符号整數，傳回其二進制表達式中數字位數為 ‘1’ 的個數（也被稱為漢明重量）。

思路：轉換成字元串，然後統計1的個數即可

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
      const s = n.toString(2);
  let res = 0;
  for (let i = 0, l = s.length; i < l; i++) {
    if (s[i] === "1") res++;
  }
  return res;
};
           

5.打家劫舍

題目：

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。

思路：這題的思路很重要，動态規劃即可，和斐波那契數列很相似。

核心就是，對于長度為n的數組，前n個的最優解，是n-1的最優解和n-2的最優解+n的較大值

即Lfn(n)=math.max(fn(n-1),fn(n-2)+n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const l = nums.length;
   if (!l) return 0;
  let v1 = 0;
  let v2 = nums[0];
  let temp;
  for (let i = 1; i < l; i++) {
    temp = v2;
    v2 = Math.max(v1 + nums[i], v2);
    v1 = temp;
  }
  return v2;
};