基础算法题

参考资料

摄氏度转换为华氏度 ```javascript function convertToF(celsius) { let fahrenheit = celsius * 9 / 5 + 32; return fahrenheit; }

convertToF(30);


2.  反转字符串
```javascript
// 解法1， 逆序遍历
function reverseString(str) {
  let res = '';
  for (let i = str.length -1; i >= 0; i--) {
    res += str[i]
  }
  return res;
}
reverseString("hello");
// 解法2, 使用首尾指针，前后对称交换
function reverseString(str) {
  let arr = str.split('')
  let start = 0, end = arr.length - 1;
  while(start < end) {
    [arr[end], arr[start]] = [arr[start], arr[end]]
    start++;
    end--
  }
  return arr.join('')
}
reverseString("hello");
// 解法三，首尾指针优化，start + end = 2 * mid = length - 1, end = length  - 1 - start
function reverseString(str) {
  let arr = str.split('')
  let start = 0, len = arr.length;
  while(start < Math.floor(len / 2)) {
    let end = len - 1 - start;
    [arr[end], arr[start]] = [arr[start], arr[end]]
    start++;
  }
  return arr.join('')
}
reverseString("hello");
// 解法四，使用数组API, split, reverse, join
function reverseString(str) {
  let arr = str.split('')
  return arr.reverse().join('')
}
reverseString("hello");
// 解法五， 使用递归，每次交互首尾字符
function reverseString(str) {
  if (!str) return ""
  if (str.length == 1) return str
  let end = str.length - 1
  return str[end] + reverseString(str.slice(1,end))  +str[0]
}
reverseString("hello");

阶乘计算 ```javascript //解法1，使用迭代 function factorialize(num) { let res = 1; for (let i = 2; i <= num; i++) { res *= i; } return res; }

factorialize(5);

// 解法2，使用递归 function factorialize(num) { if (num === 0) return 1 return num * factorialize(num - 1) }

factorialize(5);


4. 寻找字符串中的最长单词长度
```javascript
// 解法1， 使用遍历，使用res变量记录最终结果，temp记录扫描的每个单词长度
function findLongestWordLength(str) {
  let res = 0
  let temp = 0;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === ' ') {
      res = Math.max(res, temp)
      temp = 0
    } else {
      temp++
    }
  }
  return Math.max(res, temp)
}
findLongestWordLength("The quick brown fox jumped over the lazy dog");
// 解法2， 把字符串转换成数组处理
function findLongestWordLength(str) {
  let arr = str.split(' ')
  let res = 0;
  for(let i = 0; i < arr.length; i++) {
    res = Math.max(res, arr[i].length)
  }
  return res
}
findLongestWordLength("The quick brown fox jumped over the lazy dog");
// 解法2优化，使用map 和 Math.max，展开运算符
function findLongestWordLength(str) {
  return Math.max(...str.split(' ').map(item => item.length))
  // 等同于
  // return Math.max.apply(null, str.split(' ').map(item => item.length))
}
findLongestWordLength("The quick brown fox jumped over the lazy dog");

寻找数组中的每一项中的最大值并返回 ```javascript // 解法一，使用for循环迭代 function largestOfFour(arr) { let res = [] for(let i = 0; i < arr.length; i++) { let max = -Infinity; for (let j = 0; j < arr[i].length; j++) { max = Math.max(max, arr[i][j]) } res.push(max) } return res; }

largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);

// 解法2，使用数组API function largestOfFour(arr) { return arr.map(subArr => Math.max(…subArr)) } largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]]);


6. 检查一个字符串是否是目标字符串的末尾子符串
```javascript
// 解法1，endsWith API
function confirmEnding(str, target) {
  return str.endsWith(target)
}
confirmEnding("Bastian", "n");
// 解法2， 使用i,j指针从尾部扫描
function confirmEnding(str, target) {
  if (str.length < target.length) return false;
  let j = target.length - 1;
  let i = str.length - 1;
  while(j > -1) {
    if (str[i] !== target[j]) {
      return false;
    }
    i--;
    j--;
  }
  return true
}
confirmEnding("Bastian", "n");
// 解法3， 使用slice API
function confirmEnding(str, target) {
  if (str.length < target.length) return false;
  return str.slice(-target.length) === target;
}
confirmEnding("Bastian", "n");
// 解法4， 使用正则
function confirmEnding(str, target) {
  if (str.length < target.length) return false;
  return RegExp(target + '$').test(str)
}
confirmEnding("Bastian", "n");

重复一个字符串 ```javascript // 解法1，遍历相加 function repeatStringNumTimes(str, num) { let res = ‘’ for (let i = 0; i < num; i++) { res += str } return res; }

repeatStringNumTimes(“abc”, 3); // abcabcabc

// 解法2，利用数组然后join function repeatStringNumTimes(str, num) { if (num <= 0) return ‘’ return Array(num + 1).join(str) }

repeatStringNumTimes(“abc”, 3);

// 解法3，使用递归 function repeatStringNumTimes(str, num) { if (num <= 0) return ‘’ if (num == 1) return str; return str + repeatStringNumTimes(str, num - 1); }

repeatStringNumTimes(“abc”, 3);


9. 截取字符串，超出变成 ...
```javascript
function truncateString(str, num) {
  if (str.length > num) {
    return str.slice(0, num) + '...'
  }
  return str;
}
truncateString("A-tisket a-tasket A green and yellow basket", 8);

遍历数组里每个元素，对数组的每个元素都调用指定的函数，并返回第一个为真的结果的元素，没有返回undefined ```javascript // 解法1， for遍历 function findElement(arr, func) { for(let i = 0; i < arr.length; i++) { if (func(arr[i])) { return arr[i] } } return undefined; }

findElement([1, 2, 3, 4], num => num % 2 === 0);

// 解法2，使用filter function findElement(arr, func) { return arr.filter(func)[0] }

findElement([1, 2, 3, 4], num => num % 2 === 0);

// 解法3，使用find function findElement(arr, func) { return arr.find(func) }

findElement([1, 2, 3, 4], num => num % 2 === 0);


10. 判断值是否为布尔值
```javascript
// 解法1, 判读为true or false 
function booWho(bool) {
  return bool === true || bool === false
}
booWho(null);
// 解法2, typeof
function booWho(bool) {
  return typeof bool === 'boolean'
}
booWho(null);

每个单词的首字符大写 ```javascript // 解法1，遍历 + 标志位 function titleCase(str) { let shouldCap = true; let res = ‘’; for(let i = 0; i < str.length; i++) { if(shouldCap) { res += str[i].toUpperCase() shouldCap = false; } else { res += str[i].toLowerCase() if (str[i] === ‘ ‘) {
```
shouldCap = true
```
} } } return res; }

titleCase(“I’m a little tea pot”);

// 解法2，转换为数组处理 function titleCase(str) { return str.split(‘ ‘).map(word => { return word[0].toUpperCase() + word.slice(1).toLowerCase() }).join(‘ ‘) }

titleCase(“I’m a little tea pot”);

// 解法3，使用正则表达式 function titleCase(str) { return str.toLowerCase() .replace(/(^|\s)[a-z]/g, match => match.toUpperCase()) }

titleCase(“I’m a little tea pot”);


12. 使用数组的slice和splice 方法把一个数组中的元素放在第二个数组的指定索引位置之后，不改变第二个数组
```javascript
function frankenSplice(arr1, arr2, n) {
  let copy = arr2.slice()
  copy.splice(n, 0, ...arr1)
  return copy
}
frankenSplice([1, 2, 3], [4, 5, 6], 1);

从一个数组中移除所有的falsy值，falsy = false | null | 0 | ‘’ | undefined | NaN ```javascript // 解法1，使用数组API function bouncer(arr) { return arr.filter(Boolean) }

bouncer([7, “ate”, “”, false, 9]);

// 解法2 ，遍历 function bouncer(arr) { let res = [] for (let i = 0; i < arr.length; i++) { if (Boolean(arr[i])) { res.push(arr[i]) } } return res }

bouncer([7, “ate”, “”, false, 9]);


14.  返回数组被插入元素后，再排序后的，该元素的索引
```javascript
// 例如， getIndexToIns([1,2,3,4], 1.5)  // 数组插入1.5，排序后，值的索引为1
// 解法1， 数组排序后使用indexOf返回索引
function getIndexToIns(arr, num) {
  return arr.concat(num).sort((a,b)=> a-b).indexOf(num)
}
getIndexToIns([40, 60], 50);
//解法2， 使用filter
function getIndexToIns(arr, num) {
  return arr.filter(e => e < num).length
}
getIndexToIns([40, 60], 50);
//解法3， 遍历记数小于num的数量，即为插入的索引值
function getIndexToIns(arr, num) {
  let res = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < num) {
      res++
    }
  }
  return res
}
getIndexToIns([40, 60], 50);

第一个字符串是否包含第二字符串中所有字符，不考虑字符的大小写 ```javascript // 解法1，遍历 function mutation(arr) { let arr1 = arr[0].toLowerCase() let arr2 = arr[1].toLowerCase() for (let i = 0; i < arr2.length; i++) { if (!arr1.includes(arr2[i])) { return false; } } return true }

mutation([“hello”, “hey”]);

// 解法2，转为数组处理, every; function mutation(arr) { let str1 = arr[0].toLowerCase(); let arr2 = arr[1].toLowerCase().split(‘’); return arr2.every(item => str1.includes(item)) }

mutation([“hello”, “hey”]);

// 解法3，使用set, 时间复杂度O(n) function mutation(arr) { let set = new Set(arr[0].toLowerCase()) for (let char of arr[1].toLowerCase()) { if (!set.has(char)) { return false; } } return true }

mutation([“hello”, “hey”]);

// 解法4，使用者正则表达式，第二个字符串有第一个字符串不存在的字符，结果取反 function mutation(arr) { return !RegExp([^${arr[0]}], ‘i’).test(arr[1]) }

mutation([“hello”, “hey”]);


16. 写一个函数能够按照指定的大小切割原数组，并返回一个二维数组
```javascript
// 解法1， 遍历 + 临时数组保存，双指针
function chunkArrayInGroups(arr, size) {
  let result = []
  for (let i = 0; i < arr.length; i+=size) {
    let temp = []
    for (let j = i; j < i + size && j < arr.length; j++) {
      temp.push(arr[j])
    }
    result.push(temp)
  }
  return result
}
chunkArrayInGroups(["a", "b", "c", "d"], 2);
// 解法2， 使用mod 取余
function chunkArrayInGroups(arr, size) {
  let result = []
  let temp = []
  for (let i = 0; i < arr.length; i++) {
    temp.push(arr[i])
    if (i % size === size - 1) {
      result.push(temp)
      temp = []
    }
  }
  if (temp.length > 0) {
    result.push(temp)
  }
  return result
}
chunkArrayInGroups(["a", "b", "c", "d"], 2);
// 解法3， 使用数组 splice
function chunkArrayInGroups(arr, size) {
  let result = []
  while(arr.length > 0) {
    result.push(arr.splice(0, size))
  }
  return result;
}
chunkArrayInGroups(["a", "b", "c", "d"], 2);
// 解法4， 使用数组 slice
function chunkArrayInGroups(arr, size) {
  let result = []
  for(let i = 0; i < arr.length; i += size) {
    result.push(arr.slice(i, i + size))
  }
  return result
}
chunkArrayInGroups(["a", "b", "c", "d"], 2);
// 解法5,  使用数组 reduce
function chunkArrayInGroups(arr, size) {
  return arr.reduce((acc, cur) => {
    let last = acc[acc.length - 1]
    if (last.length < size) {
      last.push(cur)
    } else {
      acc.push([cur])
    }
    return acc
  }, [[]])
}
chunkArrayInGroups(["a", "b", "c", "d"], 2);
// 解法6， 使用递归
function chunkArrayInGroups(arr, size) {
  if (arr.length <= size) {
    return [arr]
  }
  return [arr.splice(0, size)]
    .concat(chunkArrayInGroups(arr, size))
}
chunkArrayInGroups(["a", "b", "c", "d"], 2);
function chunkArrayInGroups(arr, size) {
  if (arr.length <= size) {
    return [arr]
  }
  return [arr.slice(0, size)]
    .concat(chunkArrayInGroups(arr.slice(size), size))
}
chunkArrayInGroups(["a", "b", "c", "d"], 2);

参考资料