算法 - 字符串 - 翻转整数、有效的字母异位
算法 - 字符串 - 翻转整数、有效的字母异位
用户3258338
发布于 2020-05-22 11:10:06
发布于 2020-05-22 11:10:06
概述
1. 翻转整数
- reverse方法
- 欧几米德方法
2. 有效的字母异位
- 利用数组的sort()方法
- 计数累加算法
翻转整数
给出一个32位的有符号整数，你需要将整数的每位上的数字进行翻转
示例
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21方法一：翻转字符串方法
- 首先设置边界极值
- 使用字符串的翻转函数进行主逻辑
- 补充符号
- 拼接最终结果
/**
* @param {number} x
* @return {number}
**/
const reverse = (x)=>{
if(typeof !== 'number'){ //校验参数类型
return;
}
// 假设我们的环境只能存储得下32位的有符号证书
// 取值范围[−2^31,2^31-1]
const MAX = 2147483647;
const MIN = -2147483647;
// 识别数字剩余部分并翻转
const rest =
x>0
?String(x).split('').reverse().join('')
:String(x).slice(1).split('').reverse().join('')
// 将符号加上
const result = x>0 ? parseInt(rest) : 0-parseInt(rest);
// 边界情况
if(result >= MIN && result <= MAX){
return result;
}
return 0;
}
- 时间复杂度O(n)；n为整数长度。
- 空间复杂度O(n)；n为整数长度。
方法二：类似欧几米德算法 求解
通过除以10取得最低位，然后又通过乘10将最低位迭代到最高位，完成翻转。
- 首先设置边界极值
- 借鉴欧几米德
- 补充符号
- 返回最终结果
/**
* @param {number} x
* @return {number}
**/
const reverse = (x) =>{
// 取得绝对值
let int = Math.abs(x);
// 假设我们的环境只能存储得下32位的有符号证书
// 取值范围[−2^31,2^31-1]
const MAX = 2147483647;
const MIN = -2147483647;
let num =0;
while(int != 0){
// 取末尾数字 + 之前取得的数字往左移动一位
num = (int % 10) + (num * 10)
// 剔除已经遍历过的部分
int = Math.floor( int / 10);
}
if(num >= MAZ || num <= MIN){
return 0;
}
return x<0 ? num * -1 : num
} - 时间复杂度O(n)；for循环，次数是n
- 空间复杂度O(1)；算法中只用到常数个变量
有效的字母异位词
给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。
示例1
输入: s = "anagram", t = "nagaram"
输出: true
示例2
输入: s = "rat", t = "car"
输出: false方法一：利用数组sort()方法
首先，对字符串字母进行排序，然后比较两个字符串是否相等。
const isAnagram = (s, t) => {
const sArr = s.split('');
const tArr = t.split('');
const sortFun =(a,b) => {
return a.chartCodeAt - b.chartCodeAt();
}
sArr.sort(sortFun);
tArr.sort(sortFun);
return sArr.join('') === tArr.join('');
}- 时间复杂度：O(n logn) JS的sort方法的实现原理：当数组长度小于等于10的时候，采用插入排序，大于10的时候，采用快排列，快排的时间复杂度是O(n logn);
- 空间复杂度 O(n) 算法中申请了2个数组变量用来存放字符串分割后的字符串数组，所以数组空间长度和字符串长度线性相关
方法二：计数累加方法
方法：
1.声明一个变量，遍历其中一个字符串，对每个字母出现的次数进行累加
2.遍历另一个字符串，使每个字母在已得到的对象中匹配，如果匹配则对象下字母个数减1，如果匹配不到则返回false。如果最后对象中每个字母个数都为0，则表示两个字符串相等。
const isAnagram = (s, t)=>{
if(s.length != t.length){
return false;
}
const hash = {};
for(const k of s){
hash[k] = hash[k] || 0;
hash[k] += 1;
}
for(const k of t){
if(!hash[k]){
return false;
}
hash[k] -= 1;
}
return true;
}- 时间复杂度：O(n) 算法中使用了2个单层循环
- 空间复杂度 O(1) 申请的变量hash最大长度是256，因为AsciI字符最多256种可能，考虑为常量空间
参考：https://101.zoo.team/zi-fu-chuan/zi-fu-chuan-part-1-fan-zhuan-zheng-shu-you-xiao-de-zi-mu-yi-wei-ci-he-fan-zhuan-zheng-shu
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读