TypeScript版算法

1. 两数之和

要求

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

我的思路

利用双重 for 循环来判断，数组第一个和第二个相加判断是否等于 target，不是则换数组为第一个与第三个相加依次类推，第一轮循环结束则继续判断数组第二个与第三个相加是否等于 target，一直循环下去，如果相等则返回对应的数组下标，注意的是第二个数组下标不能与第一个相同，因为数组可能会是[3, 3]而 target 是 6 的情况。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function twoSum(nums: number[], target: number): number[] {
  let numArr: number[] = [];
  for (let j = 0; j < nums.length; j++) {
    numArr = [];
    for (let i = j; i < nums.length; i++) {
      numArr.push(nums[i]);
      if (numArr.length === 2) {
        const sum = numArr[0] + numArr[1];
        if (sum === target) {
          const index1 = nums.findIndex((k) => k === numArr[0]);
          const index2 = nums.findIndex(
            (k, index) => k === numArr[1] && index !== index1
          );
          numArr = [index1, index2];
          return numArr;
        } else {
          numArr.pop();
        }
      }
    }
  }
  return numArr;
}

9. 回文数

要求

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。

示例 1：

1
2
输入：x = 121
输出：true

我的思路

将输入的数据变为字符串数组，再构建一个反转的数组依次比较相同数组下标对应的值是否一致，一致则返回 true，否则返回 false

我的代码

1
2
3
4
5
6
function isPalindrome(x: number): boolean {
  const stringArr = [...x.toString()];
  const stringArrReverse = [...x.toString()].reverse();
  const flag = stringArr.every((v, index) => v === stringArrReverse[index]);
  return flag;
}

13. 罗马数字转整数

要求

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例

1
2
3
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

我的思路

首先将输入的罗马字符转成字符数组，将字符数组转为对应的数字数组，然后从头开始遍历，如果数组第一位大于第二位则继续遍历，如果数组第二位小于第三位，那么将数组的第二位变为数组的第三位减去第二位，依次类推，最后将筛选过的数组相加。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function getValue(s: string): number {
  const arr = [
    { name: "I", value: 1 },
    { name: "V", value: 5 },
    { name: "X", value: 10 },
    { name: "L", value: 50 },
    { name: "C", value: 100 },
    { name: "D", value: 500 },
    { name: "M", value: 1000 },
  ];
  return arr.find((v) => v.name === s)!.value;
}

function sortArr(arr: number[]): number[] {
  const newArr: number[] = [];
  for (let i = 0; i < arr.length; i++) {
    if (i === arr.length - 1) {
      newArr.push(arr[i]);
      break;
    }
    if (arr[i] >= arr[i + 1]) {
      newArr.push(arr[i]);
    } else {
      newArr.push(arr[i + 1] - arr[i]);
      i++;
    }
  }
  return newArr;
}

function romanToInt(s: string): number {
  const stringArr = [...s];
  let newArr: number[] = sortArr(stringArr.map((i) => getValue(i)));
  return newArr.reduce(
    (accumulator, currentValue) => accumulator + currentValue,
    0
  );
}

14. 最长公共前缀

要求

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

我的思路

最长公共前缀的长度一定小于等于数组第一位，所以直接利用数组第一位的值来进行依次比较。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
function longestCommonPrefix(strs: string[]): string {
  const firstStringArr = [...strs[0]];
  const stringArr: string[] = [];
  for (let i = 0; i < firstStringArr.length; i++) {
    if (strs.every((v) => [...v][i] === firstStringArr[i])) {
      stringArr.push(firstStringArr[i]);
    } else {
      break;
    }
  }
  return stringArr.length === 0 ? "" : stringArr.join("");
}

20. 有效的括号

要求

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 2：

1
2
输入：s = "()[]{}"
输出：true

我的思路

利用栈结构特性，为左括号时进栈，当遇到右括号时就出栈比较是否匹配，匹配则继续出栈比对，当栈为空时则为有效的括号。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function isSame(s1: string, s2: string) {
  const arr = [
    { s1: "(", s2: ")" },
    { s1: "[", s2: "]" },
    { s1: "{", s2: "}" },
  ];
  return s2 === arr.find((v) => v.s1 === s1)?.s2;
}
function isValid(s: string): boolean {
  const stringArr = [...s];
  const newArr: string[] = [];
  for (let i = 0; i < stringArr.length; i++) {
    if (["(", "[", "{"].includes(stringArr[i])) {
      newArr.push(stringArr[i]);
    } else {
      if (!isSame(newArr.pop()!, stringArr[i])) return false;
    }
  }
  return newArr.length === 0 ? true : false;
}