【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串

简介: 【刷力扣 TS 版】难度 简单,x 的平方根 & 验证回文串

原文来自 我的个人博客

前言

拒绝摆烂ヾ(◍°∇°◍)ノ゙

从今天开始(2023/02/12),定一个小目标,先刷个 300Leetcode 题目(之前刷的不计入)。

当然作为一个小前端,我选择的语言是 TS,而且刷的题目的难度会偏中等一些,大概按照 简单3 中等6 困难1 这样的题型分布吧。嗯,目前是这么打算的。

本题 Github 地址:因为比较喜欢 vscode 的界面,而且方便调试,所以 AC 完就顺便提到 github 了,也算做一个记录吧。

本篇的题目是这个系列的第 NO.2NO.3 题,分别是 Leetcode 上第 69 道题 x 的平方根, 和第 125 道题 验证回文串,难度都为 简单

我们开始吧,Here We Go~

1. x 的平方根

1.1 题目描述

给你一个非负整数  x ,计算并返回  x  的  算术平方根 。

由于返回类型是整数,结果只保留  整数部分 ,小数部分将被  舍去 。

注意: 不允许使用任何内置指数函数和算符,例如  pow(x, 0.5)  或者  x ** 0.5 。

示例 1:

输入: x = 4
输出: 2

示例 2:

输入: x = 8
输出: 2
解释: 8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

提示:

  • 0 <= x <= 231 - 1

1.2. 解法

思路:

  1. 设置一个变量 i = 0
  2. 通过 while 循环判断 i * i 是否小于等于 x
  3. i * i 大于 x 的时候,i -1 就是所需的值。
function mySqrt(x: number): number {
  let i: number = 0;
  while (i * i <= x) {
    i++;
  }

  return i - 1;
}

复杂度分析

  • 时间复杂度:O(logn)
  • 空间复杂度:O(1)

1.3 最后

提交通过之后,去看了一眼题解,发现很多的解法都没有我这一种,很奇怪。

因为我觉得我这种解法也并没有违反题目所说的【不允许使用任何内置指数函数和算符 pow**

基于 O(logn) 的时间复杂度 & 抱着 ACOK 的心情结束了这道题

2. 验证回文串

2.1 题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false **。

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出: true
解释: "amanaplanacanalpanama" 是回文串。

示例 2:

输入: s = "race a car"
输出: false
解释: "raceacar" 不是回文串。

示例 3:

输入: s = " "
输出: true
解释: 在移除非字母数字字符之后,s 是一个空字符串 "" 。
由于空字符串正着反着读都一样,所以是回文串。

提示:

  • 1 <= s.length <= 2 * 105
  • s 仅由可打印的 ASCII 字符组成

2.2 解法

  1. 【筛选 + 判断 】:这题最通俗的解法就是循环遍历字符串,做一些 if 条件判断,但是这样子代码总是很繁琐。
  2. 【正则 + Array.prototype.reverse】:通过 replace 将字符串中非字母数字的字符移除,在通过数组的 reverse 方法取反与字符串 s 比较,这样子基本上两行代码就能解决。
function isPalindrome(s: string): boolean {
  s = s.toLocaleLowerCase().replace(/[^a-z0-9]/g, "");
  const ret = s.split("").reverse().join("");
  return ret === s;
}

复杂度分析

  • 时间复杂度:O(|s|)|s| 为字符串 s 的长度
  • 空间复杂度:O(|s|)|s| 为 字符串字母数字的长度
相关文章
|
29天前
|
存储 canal 算法
[Java·算法·简单] LeetCode 125. 验证回文串 详细解读
[Java·算法·简单] LeetCode 125. 验证回文串 详细解读
32 0
|
29天前
|
Go
golang力扣leetcode 132.分割回文串II
golang力扣leetcode 132.分割回文串II
31 0
|
3天前
|
存储 算法 数据可视化
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
|
3天前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
3天前
|
canal 算法 数据可视化
LeetCode 125题:验证回文串
LeetCode 125题:验证回文串
|
3天前
|
SQL 算法 数据可视化
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
|
7天前
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
|
8天前
|
存储 算法 Java
【经典算法】LeetCode 125. 验证回文串(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 125. 验证回文串(Java/C/Python3实现含注释说明,Easy)
5 0
|
8天前
|
算法 Java Go
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
6 1
|
29天前
leetcode代码记录(对称二叉树 中序遍历+回文串 为什么不行
leetcode代码记录(对称二叉树 中序遍历+回文串 为什么不行
12 0