面试题【Day16】

递归算法

1,简单练习

• 1，求1-100的和

// 假设递归已经写好了
// sum(100)
// 寻找递归体的关系
// sum(n) + sum(n-1)
// 判断临界条件 终止条件
// n == 1 return 1
// 将临界条件加入到递归体中
function sum(n) {
  if (n==1) return 1
  return sum(n-1) + n
}
console.log(sum(100))

• 2,求1 3 5 7 9奇数的和

function sum(n) {
    if (n % 2 == 0) {
      n--
    }
    if (n == 1) return 1
    return n+sum(n-2)
}
console.log(sum(10))  // 25

• 3,求第n项的和

function sum(n) {
  if (n == 1) return 1
  return n + sum(n-1)
}
console.log(sum(100))

• 斐波那契数列 (Fibonacci): 1,1,2,3,5,8,13,21....求第n项

// 1 1 2 3 5 8 13 21
// n = (n-1) + (n-2)
function Fibonacci(n) {
  if (n == 0 || n == 1) return 1
  return Fibonacci(n-1) + Fibonacci(n-2)
}
console.log(Fibonacci(5))  // 8

2,高级练习

• 1,阶乘

function factorial(n) {
  if (n ==1) return 1
  return factorial(n -1) * n
}
console.log(factorial(10))  // 3628800

• 2,求幂

// power(n, m)
// 递归关系 power(n, m) * n
// 临界条件 if (m == 0) return 1
function power(n, m) {
  if (m == 0) return 1
  return power(n, m-1) * n
}
console.log(power(2,3))  // 8

• 3,使用递归实现字符串逆序（反转字符串）

// reverseStr(str)
// var str = 'abcdefg'
// charAt() // 返回的是具体的字符串
// 递推关系 -> sortReverse = reverseStr.charAt(str.length--) 
// 临界条件 str.length-- < 0
function reverseStr(str, len, sortStr) {
  if (len < 0) return sortStr
  sortStr += str.charAt(len--)
  return reverseStr(str, len, sortStr)
}
let str = 'abcdefg'
var result = ''
reverseStr(str, str.length-1, result)
console.log(reverseStr(str, str.length-1, result))  // gfedcba

2,统计字串中出现最多的字符和次数

方法-：

var str = 'wmccndlllsaweeeemmmcx'
function getMax(str) {
  let json = {}
  for (var i = 0; i < str.length; i++) {
    if(!json[str.charAt(i)]) {  // 如果不存在添加到json对象中
      json[str.charAt(i)] = 1
    } else {
      // 如果存在 value + 1
      json[str.charAt(i)] += 1
    }
  }
  console.log(json)
  // 存储次数和字符
  let maxNum = 0,
      maxStr = ''
  // 遍历对象
  for (let i in json) {
    // 如果大于就更新
    if (json[i] > maxNum) {
      // 让当前的内容更新
      maxStr = i
      maxNum = json[i]
    }
  }
  return `出现最多的字符：${maxStr}, 出现的次数： ${maxNum}`
}
console.log(getMax(str))

方法二：

var str = 'ccccmmmdhoeeeaaeeeeeeee'
function getMax(str) {
  var str = str.split('').sort().join('')   // aaccccdeeeeeeeeeeehmmmo
  var defaultNum = 0
  var defaultChar = ''
  for (var i = 0; i < str.length; i++) {
    console.log(str[i])
    var char = str[i]
    var maxNum = str.lastIndexOf(char) - i + 1
    if (maxNum > defaultNum) {
      defaultNum = maxNum
      defaultChar = char
    }
    i = str.lastIndexOf(char)
  }
  return `出现最多的字符：${defaultChar}, 出现的次数： ${defaultNum}`
}
console.log(getMax(str))

3,字符串去重

var str = 'aaabbbccc'
function removeRepeat(str) {
  var json = {}
  var arr = []
  for(var i = 0; i < str.length; i++) {
    if (!json[str[i]]) {
      json[str[i]] = true  // 将数据添加到json对象中
      arr.push(str[i])
    }
  }
  return arr.join('')
}
console.log(removeRepeat(str))  // abc