Cracking the coding interview--Q1.1
2024-08-29 09:29:41
原文:
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
译文:
实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)
解答:
假设题目中提到的字符是包含在ASCII中的字符的话,那么最多是256个。所以可以用一个256长的数组来标记,或者用一个8个32位的int值来标记。
如果题目中没有规定只使用基本的数据结构的话,用BitSet来做也很方便的。
public class Main {
public static boolean isUnique1(String str) {
boolean [] flag = new boolean[256];
for(int i = 0; i < 256; i++) {
flag[i] = false;
}
int len = str.length();
for(int i = 0; i < len; i++) {
int index = (int)str.charAt(i);
if(flag[index])
return false;
flag[index] = true;
}
return true;
} public static boolean isUnique2(String str) {
int [] flag = new int[8];
int len = str.length();
for(int i = 0; i < len; i++) {
int v = (int)str.charAt(i);
int index= v/32;
int offset = v%32;
if((flag[index] & (1 << offset)) == 1)
return false;
flag[index] |= (1 << offset);
}
return true;
} public static void main(String args[]) {
String s1 = "i am hawstein.";
String s2 = "abcdefghijklmnopqrstuvwxyzABCD1234567890";
System.out.println(isUnique1(s1) + " " + isUnique1(s2));
System.out.println(isUnique2(s1) + " " + isUnique2(s2));
}
}
最新文章
- try it, then you know . Emacs
- javascript日期验证:填写的日期大于等于当前日期
- Win7局域网文件共享方法
- IOS第三方地图-百度地图集成
- mac sublime3 无法安装Package Control
- C++(3):./Encryptor: undefined symbol:Z11startserviceLAKJDFLJALDKJFLLLLL
- 【转】python模块分析之typing(三)
- 我们在学习JDBC的时候会过度到J2EE。
- Devops流程规范
- Cocos2dx网络读取图片
- 协程之gevent
- UBUNTU 字符界面来回切换
- ==和equals方法:
- 如何灵活利用免费开源图标字体-IcoMoon篇——张鑫旭
- springboot整合mybatis将sql打印到日志
- python之插入排序
- scp加端口号
- Shiro框架的简单应用
- 【刷题】BZOJ 1143 [CTSC2008]祭祀river
- 【Atcoder】CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning