跳至主要內容

从1到n整数中1出现的次数

微信公众号：储凡About 3 min

从1到n整数中1出现的次数

题目链接

题目描述

输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数 例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

数据范围：1≤n≤30000 进阶：空间复杂度O(1) ，时间复杂度O(lognn)

刷题思路

方案一：

  • 转化为字符串，再遍历计数，属于投机方法

方案二：

  • 数学方法，对进位、余数进行处理

代码实现

/*
 * @Description:第一个只出现一次的字符
 * @Version: Beta1.0
 * @Author: 微信公众号：储凡
 * @Date: 2021-04-28 22:23:51
 * @LastEditors: 微信公众号：储凡
 * @LastEditTime: 2021-04-28 22:24:20
 */

/**
 * 利用indexOf和lastIndexOf角标不一致
 * @param str
 * @returns {number}
 */
function firstNotRepeatingCharOne(str) {
  const arr = str.split('')
  for (let index = 0; index < arr.length; index++) {
    if (arr.indexOf(arr[index]) === arr.lastIndexOf(arr[index])) {
      return index
    }
  }
  return -1
}

/**
 * 数组按字母查找
 * @param str
 * @returns {number}
 */
function firstNotRepeatingCharTwo(str) {
  const len = str.length
  for (let index = 0; index < len - 1; index++) {
    const s = str.slice(index, index + 1)
    const remainStr = `${str.slice(0, index)}${str.slice(index + 1)}`
    if (!remainStr.includes(s)) {
      return index
    }
  }
  return -1
}

/**
 * 使用Map结构计数
 * @param str
 * @returns {number|*}
 */
function firstNotRepeatingCharThree(str) {
  const resMap = new Map()
  const resArr = str.split('')

  // 计数操作
  resArr.forEach((r, index) => {
    if (resMap.has(r)) {
      resMap.set(r, resMap.get(r) + 1)
    }
    else {
      resMap.set(r, 1)
    }
  })

  for (const [key, value] of resMap) {
    if (value === 1) {
      return str.indexOf(key)
    }
  }
  return -1
}

console.log(firstNotRepeatingCharOne('google'))
console.log(firstNotRepeatingCharTwo('google'))
console.log(firstNotRepeatingCharThree('google'))

一些建议

  • 需要特别注意Math的一些操作方法
// 取整，丢弃小数部分,保留整数部分
Number.parseInt(5 / 2)　　// 2

// 向上取整,有小数就整数部分加1
Math.ceil(5 / 2)　　// 3

// 向下取整,丢弃小数部分
Math.floor(5 / 2)　　// 2

// 四舍五入
Math.round(5 / 2)　　// 3

// 取余
6 % 4　　// 2