您现在的位置是：主页 > news > 菏泽企业网站建设/十大经典案例

菏泽企业网站建设/十大经典案例

admin2025/6/18 22:43:36【news】

简介菏泽企业网站建设,十大经典案例,不知此网站枉做男人,做网站制作挣钱吗leetcode每日一题 ps：今天的每日一题没意思，简单的模拟，自己换一道面试题 08.04. 幂集幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。说明：解集不能包含重复的子集。示例: 输入&#xff…

菏泽企业网站建设,十大经典案例,不知此网站枉做男人,做网站制作挣钱吗leetcode每日一题 ps：今天的每日一题没意思，简单的模拟，自己换一道面试题 08.04. 幂集幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。说明：解集不能包含重复的子集。示例: 输入&#xff…

leetcode每日一题

ps：今天的每日一题没意思，简单的模拟，自己换一道

面试题 08.04. 幂集

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

示例:

输入： nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

题解：

class Solution {List<List<Integer>> list;public List<List<Integer>> subsets(int[] nums) {list=new ArrayList();dfs(nums.length-1,nums,new ArrayList<Integer>());return list;}void dfs(int n,int[] nums,List<Integer> list2){if(n<0){list.add(new ArrayList<Integer>(list2));return;}list2.add(nums[n]);dfs(n-1,nums,list2);list2.remove(list2.size()-1);dfs(n-1,nums,list2);}
}

练习题1

面试题 01.09. 字符串轮转

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

输入：s1 = “waterbottle”, s2 = “erbottlewat”
输出：True
示例2:

输入：s1 = “aa”, s2 = “aba”
输出：False

class Solution {public boolean isFlipedString(String s1, String s2) {int len1 = s1.length();int len2 = s2.length();if(len1 != len2)    return false;String s3 = s1+ s1;for(int i = 0;i < s3.length()-len2;i++){String s4 = s3.substring(i,i+len2);if(s4.equals(s2)){return true;}}return s1.equals(s2)?true:false;}
}

class Solution {public boolean isFlipedString(String s1, String s2) {return s1.length() == s2.length() && (s2 + s2).contains(s1);}
}

练习题2

648. 单词替换

在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

class Solution {public String replaceWords(List<String> dict, String sentence) {int len = dict.size();int len1 = sentence.length();String[] s = sentence.split(" ");                             StringBuffer str = new StringBuffer();for (int i = 0;i < s.length;i++){for(int j = 0;j < len;j++){int len2 = dict.get(j).length();if(s[i].length() < len2){continue;}String temp = s[i].substring(0,len2);if(temp.equals(dict.get(j))){s[i] = dict.get(j);}}str.append(s[i]);str.append(" ");}return str.toString().substring(0,str.length()-1);}
}

ps:咔咔一顿暴力，给暴力求解出来了，很意外

主要的思路就是把句子变成数组，然后遍历数组，判断list集合中有没有，有的话就代替（tip：因为找的是词根，所以截取单词前面的部分就行，另外，如果有可能句子的单词太短，那么就直接跳过）

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZzqDhZ5d-1642836664935)(C:\Users\Admin\AppData\Roaming\Typora\typora-user-images\image-20220122142607806.png)]$

题解：

前缀哈希

class Solution {public String replaceWords(List<String> roots, String sentence) {Set<String> rootset = new HashSet();for (String root: roots) rootset.add(root);StringBuilder ans = new StringBuilder();for (String word: sentence.split("\\s+")) {String prefix = "";for (int i = 1; i <= word.length(); ++i) {prefix = word.substring(0, i);if (rootset.contains(prefix)) break;}if (ans.length() > 0) ans.append(" ");ans.append(prefix);}return ans.toString();}
}

ps：这个前缀哈希，提交之后，不是很理想，时间大幅度增长了，但是内存节省了一点

仔细看题解之后发现跟我的暴力就是多加了一层hashset去重，时间复杂度的提升主要就在rootset.contains这一行了，去遍历内部是否存在，直接将时间复杂度翻倍了

前缀树

class Solution {public String replaceWords(List<String> roots, String sentence) {TrieNode trie = new TrieNode();for (String root: roots) {TrieNode cur = trie;for (char letter: root.toCharArray()) {if (cur.children[letter - 'a'] == null)cur.children[letter - 'a'] = new TrieNode();cur = cur.children[letter - 'a'];}cur.word = root;}StringBuilder ans = new StringBuilder();for (String word: sentence.split("\\s+")) {if (ans.length() > 0)ans.append(" ");TrieNode cur = trie;for (char letter: word.toCharArray()) {if (cur.children[letter - 'a'] == null || cur.word != null)break;cur = cur.children[letter - 'a'];}ans.append(cur.word != null ? cur.word : word);}return ans.toString();}
}class TrieNode {TrieNode[] children;String word;TrieNode() {children = new TrieNode[26];}
}

ps：时间复杂度降下来了，空间复杂度提升上去了

前缀树不会，开始刷前缀树的题

练习题3

剑指 Offer II 062. 实现前缀树

Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：Trie() 初始化前缀树对象。

void insert(String word) 向前缀树中插入字符串 word 。

boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

学习前缀树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

public class Trie {// 记录前缀树的根节点TreeNode root;// 定义前缀树节点class TreeNode{TreeNode[] next;boolean isEnd;public TreeNode (){next = new TreeNode[26];}}// 初始化前缀树public Trie() {root = new TreeNode();}// 插入public void insert(String word) {TreeNode cur = root;for(char ch : word.toCharArray()){// 判断对应节点是否为空，如果为空，则直接插入if(cur.next[ch - 'a'] == null){cur.next[ch - 'a'] = new TreeNode();}// 继续插入下一个节点cur = cur.next[ch - 'a'];}// 将最后一个字符设置为结尾cur.isEnd = true;}// 查找单词public boolean search(String word) {TreeNode cur = root;for(char ch : word.toCharArray()){// 如果对应节点为空，则表明不存在这个单词，返回falseif(cur.next[ch - 'a'] == null)return false;cur = cur.next[ch - 'a'];}// 检查最后一个字符是否是结尾return cur.isEnd;}// 查找前缀public boolean startsWith(String prefix) {TreeNode cur = root;for(char ch : prefix.toCharArray()){if(cur.next[ch - 'a'] == null)return false;cur = cur.next[ch - 'a'];}return true;}
}