本文中的算法题，来自但不限于力扣、牛客网等网站。

反转数字

题目描述

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
你有注意到翻转后的整数可能溢出吗？因为给出的是32位整数，则其数值范围为[−2^{31}, 2^{31} − 1][−231,231−1]。翻转可能会导致溢出，如果反转后的结果会溢出就返回 0。

题解

方法1: 使用字符串反转

  1. /**
  2.   * 
  3.   * @param x 整型 
  4.   * @return 整型
  5.   */
  6. function reverse( x ) {
  7.     const nevagite = x < 0;
  8.     let str = '';
  9.     if(nevagite){
  10.         str = (x+'').slice(1);
  11.     }else{
  12.         str = x + '';
  13.     }
  14.     const v = +str.split("").reverse().join("");
  15.     if(v > (2**31 - 1) || v < -(2**31)){
  16.         return 0;
  17.     }
  18.     if(nevagite){
  19.         return -v;
  20.     }
  21.     return +v;
  22.     // write code here
  23. }

方法2：使用数学方法反转

  1. function reverse( x ) {
  2.     const flag = x < 0 ? -1 : 1;
  3.     let result = 0;
  4.     let r  = Math.abs(x);
  5.     while(r!==0){
  6.         const v = r % 10;
  7.         result = result * 10 + v;
  8.         r = Math.floor(r / 10);
  9.     }
  10.     if(result>2**31-1){
  11.         return 0;
  12.     }
  13.     return result * flag;
  14. }

出现一次的数字

描述

现在有一个整数类型的数组，数组中素只有一个元素只出现一次，其余的元素都出现两次。

注意： 你需要给出一个线性时间复杂度的算法，你能在不使用额外内存空间的情况下解决这个问题么？

题解

  1. /**
  2.   * 
  3.   * @param A 整型一维数组 
  4.   * @return 整型
  5.   */
  6. function singleNumber( A ) {
  7.     return A.reduce((acc,cur)=>(acc^cur))
  8. }

回文数字

描述

在不使用额外的内存空间的条件下判断一个整数是否是回文数字
输入整数位于区间 [-2^{31}, 2^{31}-1][−231,231−1]之内

提示： 负整数可以是回文吗？（比如-1） 如果你在考虑将数字转化为字符串的话，请注意一下不能使用额外空间的限制 你可以将整数翻转。但是，如果你做过题目“反转数字”，你会知道将整数翻转可能会出现溢出的情况，你怎么处理这个问题？

题解

  1. /**
  2.   * 
  3.   * @param x 整型 
  4.   * @return 布尔型
  5.   */
  6. function isPalindrome( x ) {
  7.     // write code here
  8.     if(x<0) return false;
  9.     let result = 0;
  10.     let re = x;
  11.     while(re!==0){
  12.         const r = re % 10;
  13.         result = result * 10 + r;
  14.         re = Math.floor(re/10);
  15.     }
  16.     if(result>(2**31-1)) return false;
  17.     return x === result;
  18. }

装最多水的容器

描述

给定n个非负整数a1，a2，…，an，其中每个数字表示坐标(i, ai)处的一个点。以（i，ai）和（i，0）（i=1,2,3…n）为端点画出n条直线。你可以从中选择两条线与x轴一起构成一个容器，最大的容器能装多少水？

注意：你不能倾斜容器

image.png

题解

方法1：双循环

  1. /**
  2.   * 
  3.   * @param height 整型一维数组 
  4.   * @return 整型
  5.   */
  6. function maxArea( height ) {
  7.     const len = height.length;
  8.     let max = 0;
  9.     for(let i = 0; i < len; i++){
  10.         for(let j = i + 1; j < len; j++){
  11.             const min = Math.min(height[i],height[j]);
  12.             const area = min * (j - i);
  13.             max = Math.max(max,area)
  14.         }
  15.     };
  16.     return max;
  17. }

方法2：双指针

  1. /**
  2.   * 
  3.   * @param height 整型一维数组 
  4.   * @return 整型
  5.   */
  6. function maxArea( height ) {
  7.     let max = 0;
  8.     const len = height.length;
  9.     let l = 0, r = len -1;
  10.     while(l<r){
  11.         const min = Math.min(height[l],height[r]);
  12.         const area = min * (r-l);
  13.         max = Math.max(max,area);
  14.         if(height[l]<height[r]){
  15.             l+=1;
  16.         }else{
  17.             r-=1;
  18.         }
  19.     }
  20.     return max;
  21. }

最长公共前缀

描述

给你一个长度为 nn 的字符串数组 strsstrs , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： 算法题库 - 图2 算法题库 - 图3

题解

方法1: 暴力法

  1. /**
  2.   * 
  3.   * @param strs string字符串一维数组 
  4.   * @return string字符串
  5.   */
  6. function longestCommonPrefix( strs ) {
  7.     if(strs.length===0) return "";
  8.     let str = '';
  9.     const temp = strs[0];
  10.     const len = temp.length;
  11.     for(let i = 0; i<= len;i++){
  12.         const s = temp.slice(0,i);
  13.         const is = strs.every(item=>item.startsWith(s));
  14.         if(is){
  15.             str = s;
  16.         }
  17.     }
  18.     return str;
  19. }

最大公约数

描述

求得两个自然数的最大公约数，如：12和8 的最大公约数为4,5和7的最大公约数为1，9和3的最大公约数为3.

题解：

辗转相除法：

  1. /**
  2.  * 辗转相除法获取最大公约数
  3.  * @param number1 数值1
  4.  * @param number2 数值2
  5.  * @returns {number} 最大公约数
  6.  */
  7. function divisor(number1:number,number2:number){
  8.     let [max,min] = [number1,number2].sort((a,b)=>b-a);
  9.     let remainder = Math.floor(max % min);
  10.     while (remainder!=0){
  11.         max = min;
  12.         min = remainder;
  13.         remainder = Math.floor(max % min);
  14.     }
  15.     return min;
  16. }

更相减损法

  1. /**
  2.  * 更相减损法获取最大公约数
  3.  * @param n 数值1
  4.  * @param n1 数值2
  5.  * @returns {number} 最大公约数
  6.  */
  7. function divisor(n:number,n1:number):number{
  8.     let [max,min] = sort([n,n1]);
  9.     while(min!==max-min){
  10.         [max,min]=sort([min,max-min])
  11.     }
  12.     return min;
  14.     /**
  15.      * 排序数组
  16.      * @param numbers 数组
  17.      * @returns {number[]} 排序后的新数组
  18.      */
  19.     function sort(numbers:number[]){
  20.         return numbers.slice().sort((a,b)=>b-a);
  21.     }
  22. }

最小公倍数

描述

求得两个自然数的最小公倍数，如：12和8的最小公倍数是24，7和5的最小公倍数是35，9和3的最小公倍数是9.

题解：

两个自然数的最小公倍数为两个自然数的乘积除以两个自然数的最大公约数。

  1. /**
  2.  * 获取最小公倍数
  3.  * @param n 数值1
  4.  * @param n1 数值2
  5.  * @returns {number} 最小公倍数
  6.  */
  7. function commonMultiple(n:number,n1:number):number{
  8.     const multi = n *n1;
  9.     const divisor = compDivisor(n,n1);
  10.     return multi / divisor;
  12.     /**
  13.      * 获取最大公约数
  14.      * @param number 数值1
  15.      * @param number1 数值2
  16.      * @returns {number} 最大公约数
  17.      */
  18.     function compDivisor(number:number,number1:number):number{
  19.         let [max,min] = [number,number1].sort((a,b)=>b-a);
  20.         let remainder = Math.floor(max % min);
  21.         while (remainder!=0){
  22.             max = min;
  23.             min = remainder;
  24.             remainder = Math.floor(max % min);
  25.         }
  26.         return min;
  27.     }
  28. }

等差数列的前n项和

描述

有一个等差数列：2,5,8,11…。求其前n项和。

题解：

方法：使用公式算法题库 - 图4。
由等差数列的前n项和的公式，很容易得到结果。

  1. /**
  2.  * 等差数列的前n项和
  3.  * @param n 项数
  4.  * @param first 第一项的值
  5.  * @param d 等差数列的差
  6.  * @return {number} 前n项和
  7.  */
  8. function sum({ first, d, n }: { first: number; d: number; n: number }) {
  9.   return first * n + (d / 2) * (n - 1) * n;
  10. }
  11. sum({first:2,d:3,n});

求解立方根

描述

求解一个值的立方根，结果保留一位小数。比如： 216的立方根是6.0。

题解

使用牛顿迭代法可以求值一个多项式的解。其中，多项式的的迭代公式为算法题库 - 图5。误差在算法题库 - 图6

  1. /**
  2.  * 求解立方根
  3.  * @param num 要求解的值
  4.  */
  5. function cubeRoot(num: number) {
  6.   const diffOne = diff(num);
  7.   const derivativeOne = derivative(num);
  8.   let x = 1;
  9.   while (Math.abs(diffOne(x)) > 1e-3) {
  10.     x = x - derivativeOne(x);
  11.   }
  12.   console.log(x.toFixed(1));
  14.     /**
  15.      * 求得立方根的下一个近似解
  16.      * @param y 要求解的立方根的值
  17.      * @returns {(x: number) => number} 立方根的近似解
  18.      */
  19.   function derivative(y: number) {
  20.     return (x: number) => (x * x * x - y) / (3 * x * x);
  21.   }
  23.     /**
  24.      * 和近似解的误差
  25.      * @param y 要求解的立方根的值
  26.      * @returns {(x: number) => number} 近似解
  27.      */
  28.   function diff(y: number) {
  29.     return (x: number) => x * x * x - y;
  30.   }
  31. }

计算想字母出现的次数

描述

接受一个由字母、数字和空格组成的字符串，和一个字母，然后输出输入字符串中该字母的出现次数。不区分大小写，字符串长度小于500。
比如：‘abcABC’ ’a’ 输出2

题解

  1. /**
  2.  * 计算某字母在字符串中出现的次数
  3.  * @param string 字符串
  4.  * @param char 字母
  5.  * @returns {number} 出现的次数
  6.  */
  7. function calcCharCount(string: string, char: string) {
  8.   const charLower = char.toLowerCase();
  9.   return string
  10.     .toLowerCase()
  11.     .split("")
  12.     .filter((x) => x === charLower)
  13.     .reduce((acc) => acc + 1, 0);
  14. }

字符串分隔

描述

  • 连续输入字符串，请按长度为8拆分每个字符串后输出到新的字符串数组；
  • 长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。

    示例

    输入：
    abc 123456789
    复制
    输出：
    abc00000 12345678 90000000

    题解

    ```typescript /**
    • 分隔字符串
    • @param string 字符串
    • @returns {string} */ function splitStr(string: string) { return string.split(“”) .reduce((acc, cur) => { const len = acc.length; const last = len - 1; const latest = acc[last]; if (!latest || latest.length === 8) {
      1. return [...acc, [cur]];
      } return […acc.slice(0, last), […latest, cur]]; }, [] as string[][]) .map((x) => { return x.join(“”).padEnd(8, “0”); }).join(“\n”); }
  1. <a name="bGGJI"></a>
  2. ## 明明的随机数
  3. <a name="MaYFV"></a>
  4. ### 描述
  5. 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据(用于不同的调查)，希望大家能正确处理)。
  6. <a name="fLQSR"></a>
  7. #### 示例
  8. 输入：<br />3 2 2 1 11 10 20 40 32 67 40 20 89 300 400 15<br />输出：<br />1 2 10 15 20 32 40 67 89 300 400
  9. <a name="PT4br"></a>
  10. ### 题解
  11. ```typescript
  12. function random(list: number[]) {
  13.   let count = 0;
  14.     let array: number[] = [];
  15.   const result = [];
  16.   for (let v of list) {
  17.     let len = array.length;
  18.     if (len < count) {
  19.       array.push(v);
  20.       len = array.length;
  21.       if (len === count) {
  22.         const r = Array.from(new Set(array))
  23.           .sort((a, b) => a - b);
  24.         result.push(r);
  25.         init();
  26.       }
  27.     } else {
  28.       count = v;
  29.     }
  30.   }
  31.   return result;
  33.   function init() {
  34.     count = 0;
  35.     array = [];
  36.   }
  37. }

电话号码的字母组合

描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：

输入：digits = “”
输出：[]
示例 3：

输入：digits = “2”
输出：[“a”,”b”,”c”]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

题解

  1. function letterCombinations(digits:string) :string[] {
  2.     const dict = {
  3.         2: "abc",
  4.         3: "def",
  5.         4: "ghi",
  6.         5: "jkl",
  7.         6: "mno",
  8.         7: "pqrs",
  9.         8: "tvu",
  10.         9: "wxyz",
  11.     };
  13.     return digits
  14.         .split("")
  15.         .map(getFromDict)
  16.         .reduce(
  17.             (acc, cur) => {
  18.                 return acc
  19.                     .map((x) => {
  20.                         return cur.split("").map((y) => x + y);
  21.                     })
  22.                     .reduce((acc, cur) => acc.concat(cur), []);
  23.             },
  24.             [""]
  25.         );
  27.     function getFromDict(x:string):string {
  28.         return dict[x];
  29.     }
  30. }