20220629

发表于 2022-06-29 更新于 2025-04-03 分类于开发技术

位 1 的个数

题目

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：00000000000000000000000000001011

输出：3

解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

示例 2：

输入：00000000000000000000000010000000

输出：1

解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。

示例 3：

输入：11111111111111111111111111111101

输出：31

解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

提示：

输入必须是长度为 32 的二进制串。

进阶：

如果多次调用这个函数，你将如何优化你的算法？

题解

// 自己写的 0ms 2mb
impl Solution {
    pub fn hammingWeight (n: u32) -> i32 {
        let mut count = 0;
        let mut i = 1;
        while i <= n && i != 0 {
            if n & i != 0 {
                count += 1;
            }
            i = i << 1;
        }
        count
    }
}

// 构造32位蒙版（只有一个1），进行与操作
impl Solution {
    pub fn hammingWeight (n: u32) -> i32 {
        let (mut ret, mut mask) = (0, 1u32);
        for i in 0..32 {
            if n & mask != 0 { ret += 1; }
            mask = mask << 1;
        }
        ret
    }
}

// count_one 方法 可以直接获取数量
impl Solution {
    pub fn hammingWeight (n: u32) -> i32 {
        n.count_ones() as i32
    }
}

思路

位的与方法判断是否是 1，是的话，数量加 1
位移的方式变更 1 的位置
位移可能会越界，超出最大值的时候位移数据就是 0，需要注意一下
别人的操作是真的牛皮

20220627

发表于 2022-06-27 更新于 2025-04-03 分类于开发技术

最长公共前缀

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

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

示例 1：

输入：strs = [“flower”,”flow”,”flight”]

输出：”fl”

示例 2：

输入：strs = [“dog”,”racecar”,”car”]

输出：””

解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

题解

impl Solution {
    pub fn longest_common_prefix(strs: Vec<String>) -> String {
            let mut result = String::from("");
            let mut index = 0;
            'looper: loop {
                let mut _temp = "";
                for str in &strs {
                    if str.len() == 0 {
                        break 'looper;
                    }
                    if index >= str.len() {
                        break 'looper;
                    }
                    let c_val = &str[index..index + 1];
                    if c_val == "" {
                        break 'looper;
                    }
                    if _temp == "" {
                        _temp = c_val;
                        continue;
                    }
                    if _temp != c_val {
                        break 'looper;
                    }
                    _temp = c_val;
                }
                result.push_str(&strs.get(0).unwrap()[index..index + 1]);
                index += 1;
            }
            result
    }
}

解释

找出所有字符串的第{index}个元素，判断是否全部相等。
如果相等放入结果中，继续循环
不相等跳出外层循环，返回结果
0ms，2.1mb

来源

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnmav1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

20220622 JS中数据结构的一些想法

发表于 2022-06-22 更新于 2025-04-03 分类于开发技术

JS 中的数据结构

数组

优点

原型方法较多，可以比较方便的实现各种功能
JSON 支持
相比 java，数组的长度不是固定的，不存在越界问题
兼容性好

缺点

没有获取到索引的情况下，查询效率相对低，时间复杂度为 O(n)
插入数据效率低O(n)
删除数据效率O(n)

应用场景

绝大部分数据处理
JSON 支持，可以直接在接口中返回
前端列表渲染

对象

优点

兼容性好
查询效率高，时间复杂度为 O(1)
JSON 支持
相对 Map 可以继承原型链上的属性

缺点

相对 MAP 键值只能是 string
相对 MAP 顺序不确定
相对 MAP 没有迭代属性

应用场景

通用场景
需要一个固定 key 来做区分数据内容

MAP

优点

查询效率高，时间复杂度为 O(1)
相对对象这种结构，数据更清晰，效率更高
相对 OBJECT，语义化更好，支持功能多

缺点

原型方法没有数组多
JSON 不支持，如果作为接口数据返回，需要重新转换为数组或对象

应用场景

需要一个固定格式的 key value

链表

优点

插入性能比数组高 O(1)
删除性能比数组高 O(1)

缺点

索引效率低 O(n)
原生不支持，需要自己实现链表结构

应用场景

动态插入与删除比较多的场景

栈

应用场景

先进后出
JS 执行顺序

队列

应用场景

先进先出
排队场景
性能瓶颈的时候，使用队列，排队处理数据

位图

应用场景

打标签的场景

树

应用场景

DOM 树、CSS 树
多层JSON
级联菜单

20220605

发表于 2022-06-05 更新于 2025-04-03 分类于生活感想

尝试着去分享更多的东西

起码留下点什么

加油

20220427-daily

发表于 2022-04-27 更新于 2025-04-03 分类于生活感想

为众人抱薪者，不可使其冻毙于风雪；

为大众谋福利者，不可使其孤军奋战；

为自由开路者，不可使其困顿于荆棘。

如果天空是黑暗的，那就摸黑生存；如果发出声音是危险的，那就保持沉默；如果自觉无力发光，那就蜷伏于墙角。但是，不要习惯了黑暗就为黑暗辩护，也不要为自己的苟且而得意，不要嘲讽那些比自己更勇敢的人。我们可以卑微如尘土，但不可扭曲如蛆虫

20220206

发表于 2022-02-06 更新于 2025-04-03 分类于生活感想

原来，有你陪着已经这么开心
房间里，没有你，这么空旷
一边流泪，一边收拾衣服的感觉确实不好
有点怀疑，自己为什么会劝你回到哪里
我果然是个傻逼

一直在身边的，才是最容易被忽视的。
有一天突然不见了。
原来是这么难受。

嗯。

有些不知所措

跟自己想的那种情况不太一样

哭成了傻逼

我以为我能很平静的接受这件事

回到家里，看着熟悉的房间，总是感觉她在那里

还没有离开

一边写一边哭

不写了

20211230题目

发表于 2021-12-30 更新于 2025-04-03 分类于开发技术

外观数列

题目

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1

描述前一项，这个数是 1 即 “ 一个 1 ”，记作 “11”

描述前一项，这个数是 11 即 “ 二个 1 ” ，记作 “21”

描述前一项，这个数是 21 即 “ 一个 2 + 一个 1 ” ，记作 “1211”

描述前一项，这个数是 1211 即 “ 一个 1 + 一个 2 + 二个 1 ” ，记作 “111221”
要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

示例 1：

输入：n = 1

输出：”1”

解释：这是一个基本样例。

示例 2：

输入：n = 4

输出：”1211”

解释：

countAndSay(1) = “1”

countAndSay(2) = 读 “1” = 一个 1 = “11”

countAndSay(3) = 读 “11” = 二个 1 = “21”

countAndSay(4) = 读 “21” = 一个 2 + 一个 1 = “12” + “11” = “1211”

题解

普通做法

function countAndSay(n: number): string {
  const getNextNum = (num: string) => {
    let i = 0;
    let result = "";
    let counter = 1;
    while (i < num.length) {
      if (num[i] === num[i + 1]) {
        counter++;
      } else {
        result += `${counter}${num[i]}`;
        counter = 1;
      }
      i++;
    }
    return result;
  };
  let current = "1";
  for (let i = 1; i < n; i++) {
    current = getNextNum(current);
  }
  return current;
}

递归做法

感觉性能会比较差

来源

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnpvdm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

20211228题目

发表于 2021-12-28 更新于 2025-04-03 分类于开发技术

实现 strStr() 函数。

题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = “hello”, needle = “ll”
输出：2
示例 2：

输入：haystack = “aaaaa”, needle = “bba”
输出：-1
示例 3：

输入：haystack = “”, needle = “”
输出：0

提示：

0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成

题解

// 不使用字符串原型方法
function strStr(haystack: string, needle: string): number {
  if (needle.length > haystack.length) {
    return -1;
  }
  if (!needle.length) {
    return 0;
  }
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] !== needle[0]) {
      continue;
    }
    let temp = false;
    for (let j = 0; j < needle.length; j++) {
      if (haystack[j + i] !== needle[j]) {
        temp = false;
        break;
      }
      temp = true;
    }
    if (temp) {
      return i;
    }
  }
  return -1;
}
// 原生方法
function strStr(haystack: string, needle: string): number {
  return haystack.indexOf(needle);
}

来源

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

20211227题目

发表于 2021-12-27 更新于 2025-04-03 分类于开发技术

验证回文数

题目

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true
解释：”amanaplanacanalpanama” 是回文串

示例 2:

输入: “race a car”
输出: false
解释：”raceacar” 不是回文串

提示：

1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成

答案

function isPalindrome(s: string): boolean {
  let leftIndex = 0;
  let rightIndex = s.length - 1;
  const lowS = s.toLowerCase();
  const isSmaller = (s: string) =>
    (s.charCodeAt(0) >= 97 && s.charCodeAt(0) <= 122) ||
    (s.charCodeAt(0) >= 48 && s.charCodeAt(0) <= 57);
  while (leftIndex < rightIndex) {
    if (!isSmaller(lowS[leftIndex])) {
      leftIndex++;
      continue;
    }
    if (!isSmaller(lowS[rightIndex])) {
      rightIndex--;
      continue;
    }
    if (lowS[leftIndex] !== lowS[rightIndex]) {
      return false;
    } else {
      leftIndex++;
      rightIndex--;
    }
  }
  return true;
}

版权声明

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xne8id/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

有效的字母异位词

发表于 2021-12-24 更新于 2025-04-03 分类于开发技术

有效的字母异位词

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”

输出: true

示例 2:

输入: s = “rat”, t = “car”

输出: false

提示:

1 <= s.length, t.length <= 5 * 104

s 和 t 仅包含小写字母

题解

两个map比较字母数是否相同

function isAnagram(s: string, t: string): boolean {
  const strToMap = (s: string) => {
    const strMap = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
      strMap.set(s[i], (strMap.get(s[i]) || 0) + 1);
    }
    return strMap;
  };
  const sMap = strToMap(s);
  const tMap = strToMap(t);
  if (sMap.size !== tMap.size) {
    return false;
  }
  for (let i of sMap.keys()) {
    if (sMap.get(i) !== tMap.get(i)) {
      return false;
    }
  }
  return true;
}

便利第一个字符串为map，便利第二个字符串，如果第一个map有，就减去1，最后看smap的数字是否都是0

function isAnagram(s: string, t: string): boolean {
  const strToMap = (s: string) => {
    const strMap = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
      strMap.set(s[i], (strMap.get(s[i]) || 0) + 1);
    }
    return strMap;
  };
  const sMap = strToMap(s);
  for (let i = 0; i < t.length; i++) {
    if (!sMap.get(t[i])) {
      return false;
    }
    sMap.set(t[i], sMap.get(t[i])! - 1);
  }
  for (let [, v] of sMap) {
    if (v !== 0) {
      return false;
    }
  }
  return true;
}

排序后遍历

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) {
    return false;
  }
  const sArr = s.split("").sort();
  const tArr = t.split("").sort();
  for (let i = 0; i < sArr.length; i++) {
    if (sArr[i] !== tArr[i]) {
      return false;
    }
  }
  return true;
}

字符替换法，耗时比较长

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) {
    return false;
  }
  for (let i = 0; i < s.length; i++) {
    t = t.replace(s[i], "");
    console.log(t);
  }
  return !t.length;
}

来源

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

位 1 的个数

题目

提示：

示例 1：

示例 2：

示例 3：

提示：

进阶：

题解

思路

相关连接

最长公共前缀

题解

解释

来源

JS 中的数据结构

数组

优点

缺点

应用场景

对象

优点

缺点

应用场景

MAP

优点

缺点

应用场景

链表

优点

缺点

应用场景

栈

应用场景

队列

应用场景

位图

应用场景

树

应用场景

外观数列

题目

题解

来源

实现 strStr() 函数。

题目

说明：

提示：

题解

来源

验证回文数

题目

提示：

答案

版权声明

有效的字母异位词

题目

题解

来源