Welcome to LeaCoder's Blog!
持之以恒终有收获，自律自强方至成功-
LeetCode-338--比特位计数(Counting-Bits)
338. 比特位计数
338. 比特位计数 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 示例 1: 输入: 2 输出: [0,1,1] 示例 2: 输入: 5 输出: [0,1,1,2,1,2] 进阶: 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？ 要求算法的空间复杂度为O(n)。 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。Python3 实现
# @author:leacoder # @des: 比特位计数 class Solution: def countBits(self, num: int) -> List[int]: res = [0] * (num + 1) for i in range(1,num+1): res[i] = res[i&(i-1)] + 1 return res
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-231--2的幂(Power-of-Two)
231. 2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例 1:
输入: 1 输出: true 解释: 20 = 1示例 2:
输入: 16 输出: true 解释: 24 = 16示例 3:
输入: 218 输出: falsePython3 实现
# @author:leacoder # @des: 位运算 2的幂 class Solution: def isPowerOfTwo(self, n: int) -> bool: if n != 0 and n & (n-1) == 0: return True else: return False
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-191-位1的个数(Number-of-1-Bits)
191. 位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
Python3 实现
方法1
# @author:leacoder # @des: 32位均判断 位1的个数 class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count = 0 #位1 计数 mask = 1 # for i in range(32): #对32位 整数 每位判断 if n & mask: #判断每个位是否为1 count += 1 mask = mask << 1 #左移移位 return count方法2
# @author:leacoder # @des: 位1的个数 class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count = 0 #位1 计数 while n: count += 1 n = n & (n-1) return count
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
C-语言知识点-思维导图
下面是我整理的关于 C 语言的相关知识点，欢迎大家来一起交流学习。
结合思维导图 食用 《The_C_Programming_Language第二版中文版》《C语言程序设计_现代方法》《C陷阱与缺陷》等书籍 效果也很不错
如需要xmind 格式的，可以去我的GitHub下载：
https://github.com/lichangke/Mind-Mapping/tree/master/C%20language
自己收集的一些C语言相关书籍：
链接：https://pan.baidu.com/s/1UjTGAzQHVCWiH2rpBeTb4Q
提取码：4s67
-
LeetCode-212-单词搜索-II(212-Word-Search-II)
212. 单词搜索 II
给定一个二维网格 **board **和一个字典中的单词列表 **words**，找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。 **示例:** **输入:** **words** = `["oath","pea","eat","rain"]` and **board** = [ ['**o**','**a**','a','n'], ['e','**t**','**a**','**e**'], ['i','**h**','k','r'], ['i','f','l','v'] ] **输出:**["eat","oath"] **说明:** 你可以假设所有输入都由小写字母 `a-z` 组成。 **提示:** - 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？ - 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： [实现Trie（前缀树）](https://leetcode-cn.com/problems/implement-trie-prefix-tree/description/)。Python3 实现
# @author:leacoder # @des: Trie (前缀树，字典树) + DFS 单词搜索 II # 将words存入 Trie 中，然后将board 中的字母按顺序依次与 Trie 中字母比较 dx = [ 0, 0,-1, 1] dy = [-1, 1, 0, 0,] # 在board 中以当前位置（x0,y0） 上下左右的偏移量 ,上偏移(x0,y0-1) 下偏移（x0,y0+1） 左偏移（x0+1,y0） 右偏移（x0-1,y0） class Trie: #辅助 Trie def __init__(self): self.root = {} self.endofword = "end" def insert(self, word: str) -> None: node = self.root for char in word: # dict.setdefault(key, default=None) 如果 key 在 字典中，返回对应的值。 # 如果不在字典中，则插入 key 及设置的默认值 default，并返回 default ，default 默认值为 None。 node = node.setdefault(char,{}) node[self.endofword] = self.endofword class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: if not board or not board[0]: return [] if not words: return [] self.result = set() self.myTrie = Trie() for word in words: self.myTrie.insert(word) self.row ,self.col = len(board), len(board[0]) # 行 y 列 x for i in range(self.row): for j in range(self.col): #board中每一个字符开始 深度优先搜索 if board[i][j] in self.myTrie.root: # myTrie 中有前缀 board[i][j] self._dfs(board,i,j,"",self.myTrie.root) return list(self.result) # def def _dfs(self, board, i, j, cur_word, cur_dict): cur_word += board[i][j] #board[i][j] 必然已经搜索到 累加字符 cur_dict = cur_dict[board[i][j]] # Trie树的下一层 某个word的下一字符 if self.myTrie.endofword in cur_dict: # 是否已经探寻到Trie最后 也就是words中某个word 被找到 self.result.add(cur_word) tmp,board[i][j] = board[i][j],"#" #暂存 board[i][j] 用“#” 标记是否被访问过了 用于下面偏移 for k in range(4): # 上下左右偏移 y, x = i + dy[k], j + dx[k] # 上下左右偏移 必须在row和col之内，偏移后的字符 board[y][x]没有被访问处理过，并且 偏移后的字符在Trie树的下一层有 if 0 <= x < self.col and 0 <= y < self.row: # 注意范围 if board[y][x] !="#" and board[y][x] in cur_dict: self._dfs(board,y,x,cur_word,cur_dict) # 深度优先继续搜索 board[i][j] = tmp #循环结束 恢复以前数据 （board[i][j]之前被设置为"#"标记是否被访问过了）
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
-
LeetCode-208-实现-Trie-(前缀树)-(Implement-Trie-(Prefix-Tree))
208. 实现 Trie (前缀树)
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 示例: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true 说明: 你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。 在真实的面试中遇到过这道题？Python3 实现
# @author:leacoder # @des: 实现 Trie (前缀树) class Trie: def __init__(self): """ Initialize your data structure here. """ self.root = {} self.endofword = "end" def insert(self, word: str) -> None: """ Inserts a word into the trie. """ node = self.root for char in word: # dict.setdefault(key, default=None) 如果 key 在 字典中，返回对应的值。 # 如果不在字典中，则插入 key 及设置的默认值 default，并返回 default ，default 默认值为 None。 node = node.setdefault(char,{}) node[self.endofword] = self.endofword def search(self, word: str) -> bool: """ Returns if the word is in the trie. """ node = self.root for char in word: if char not in node: return False #node = node[char] node = node.get(char) return self.endofword in node def startsWith(self, prefix: str) -> bool: """ Returns if there is any word in the trie that starts with the given prefix. """ node = self.root for char in prefix: if char not in node: return False #node = node[char] node = node.get(char) return TrueJava 实现
/* *@author:leacoder *@des: 实现 Trie (前缀树) */ class Trie { public int SIZE = 26; public TrieNode root; class TrieNode { TrieNode(char c){ this.val = c; this.isWord = false; this.child = new TrieNode[SIZE]; } public char val; public boolean isWord; public TrieNode[] child ; } /** Initialize your data structure here. */ public Trie() { this.root = new TrieNode(' '); } /** Inserts a word into the trie. */ public void insert(String word) { if(word == null || word.length() == 0) return; TrieNode node = this.root; for( int i = 0; i < word.length(); i++ ){ char c = word.charAt(i); if( node.child[c - 'a'] == null){ node.child[c - 'a'] = new TrieNode(c); } node = node.child[c - 'a']; } node.isWord = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { TrieNode node = this.root; for( int i = 0; i < word.length(); i++ ){ char c = word.charAt(i); if( node.child[c - 'a'] == null){ return false; } node = node.child[c - 'a']; } return node.isWord; } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { TrieNode node = this.root; for( int i = 0; i < prefix.length(); i++ ){ char c = prefix.charAt(i); if( node.child[c - 'a'] == null){ return false; } node = node.child[c - 'a']; } return true; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */
GitHub链接： https://github.com/lichangke/LeetCode
个人Blog: https://lichangke.github.io/
欢迎大家来一起交流学习
Recent Posts
Tags