原题:
请实现一个算法,确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
给定一个string iniString,请返回一个bool值,True代表所有字符全都不同,False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
测试样例:
"aeiou"
返回:True
"BarackObama"
返回:False
思路:
首先想到如果可以有一个辅助的hash表,把遍历过的字符存储起来,这样会很容易判断。但题目要求不能使用额外存储结构,再一个,字符为ASCII字符,一共128个。
想到完全可以使用128个bit位,来表示128个字符是否出现过。2个long就可以存储了,代码如下:
public static boolean checkDifferent(String iniString){
long asc1 = 0;
long asc2 = 0;
int len = iniString.length();
for(int i=0;i<len;i++){
char c = iniString.charAt(i);
if(c < 64){
long mask = 1L << c;
long r = asc1 & mask;
if(r == mask){
return false;
}else{
asc1 |= mask;
}
}else{
c &= 63;
long mask = 1L << c;
long r = asc2 & mask;
if(r == mask){
return false;
}else{
asc2 |= mask;
}
}
}
return true;
}
分享到:
相关推荐
给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。这里规定大小写为不同字符,且考虑字符串重点空格。 思路:使用一个计数的数组来做 1.4 空格替换 请编写一个方法,将字符串...
这道题要求检查一个字符串中的所有字符是否互不相同,不能使用额外的存储结构。提供的解决方案是先对字符串进行排序,然后遍历排序后的字符串,如果相邻的字符相等,则返回`false`,表示有重复字符;否则,如果遍历...
1. "作业1 插值.doc" - 这可能是一个关于插值问题的作业文档,插值是数学中的一个概念,用于构造一个函数,使得该函数在特定点上的值与给定的数据点匹配。这与牛顿差商相关,因为差商可以用来构建插值多项式。 2. ...
通过对弹簧振子系统的深入分析,文章不仅对原论文的错误进行了纠正,还为读者提供了一个重新审视和理解物理概念的机会。 在研究弹簧振子系统时,要特别注意弹簧的弹性势能与系统总机械能之间的守恒关系。在非保守力...
在编程领域,这可能是一个算法问题,涉及到数值计算、遍历、比较和可能的优化技巧。由于标签提到了“源码”和“工具”,我们可以推测博主可能提供了Java代码实现来解决这个问题。 `InequalityPerfectPowerNumber....
- 构造二叉搜索树(BST):5个互异结点可以构建的BST数量。 - 直接插入排序:对于序列(64,63,62...1),比较次数的近似计算。 - 逆波兰表达式:一种没有括号的运算符优先级表示方法,通常用于简化计算。 - ...
给定两个字符串,请编写程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。这里规定大小写为不同字符,且考虑字符串重点空格。 思路:使用一个计数的数组来做 1.4 空格替换 请编写一个方法,将字符串...
哈夫曼树是一种带权重的二叉树,其中每个节点代表一个字符,权重对应字符出现的频率。构建哈夫曼树的过程使得频繁出现的字符拥有较短的编码,而不常出现的字符则编码较长。题目的答案显示,字符的编码长度是根据其...
在数据结构的学习中,串是一种重要的数据类型,它是由一个或多个字符组成的有限序列。本章主要讨论了串的相关概念、操作以及算法。以下是基于题目内容的详细知识点解析: 1. **串的定义**:串是字符的有限序列,...
20. Concat - 联合,合并两个或多个字符串形成一个新的字符串。 21. Column - 列,数据库表格中的垂直单元,用于存储特定类型的数据。 22. Cross Join - 交叉连接,返回两个表所有可能的组合,不考虑任何连接条件...
数据结构是计算机科学中至关重要的一个领域,它研究如何有效地组织和存储数据,以便进行高效地访问和处理。本题目涉及的数据结构知识点包括二叉树、完全二叉树、平衡二叉树(AVL树)、哈夫曼编码、二分查找、字符串...
- **位映射概念**:位映射是一种将每个元素映射到一个位的方法,其中每个位代表一个元素是否存在或是否被选中。在这个例子中,可以使用一个位数组来表示每个整数的存在状态,这样就可以在有限的内存空间内高效地...
条件语句`(1)`应该是判断字符`ch`是否等于`set`指向的字符,`(2)`则是递归调用时更新指针到下一个字符。 - 函数`combine`用于合并两个互异的字符集合。它使用了动态内存分配,字符串复制以及循环遍历。变量`lenC`...
首先,对于字符串的子串问题,我们知道一个长度为n的非空字符串S,其中字符各不相同,它的互异的非平凡子串(非空且不同于S本身)个数可以通过观察规律来计算。例如,对于长度为7的字符串"abcdefg",我们可以找出...
5. Next数组和Nextval数组:Next数组记录了模式串中每个字符后可能跟的最长前缀也是后缀的长度,Nextval数组则进一步记录了这种前缀后缀的下一个字符。例如,对于串`ababaaababaa`,Next数组是`0 1 0 1 0 2 1 0 1`,...
- **定义**:串(String)是字符的有限序列,可以由零个或多个字符构成。 - **空串与空白串**: - 空串(Empty String)是指不含任何字符的串,记作ε,其长度为0。 - 空白串(Blank String)是指由空格构成的串,...
单链表【例2.6】逆转):另一种线性表的实现,每个节点包含数据元素和指向下一个节点的指针,支持插入和删除操作。 2. **字符串处理**: - **变量字符串类**(03.2.3 变量字符串类【例3.3】插入、删除):这里...
- 题目中提到集合的定义,例如第1题,指出集合的元素必须是确定的、互异的,故①③选项错误。 - 空集是任何非空集合的子集,但不是其真子集,所以④选项正确。 2. **函数的定义与性质**: - 第3题涉及了函数相等...
通过递归或迭代方法可以实现后序遍历,并根据遍历过程确定任意结点的下一个结点。 #### 组成原理部分 **2.1 填空题解析** - **2.1.1 指令组成** - **题目**: 指令由指令操作码和——组成。 - **解析**: 指令由...