1.1

发布时间:2017-5-25 17:13:14 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"1.1",主要涉及到1.1方面的内容,对于1.1感兴趣的同学可以参考一下。

Topic: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures. //  知识点0:一旦什么设为static, 数据和方法不会因为任何实例而改变。 //  知识点1:空间复杂度不是所有数据占用的空间,而是使用的辅助空间的大小,通常都是O(1), 主要就是看新开的数组的大小 //  知识点2:& 按位与,| 按位或,~ 按位非,^按位异或。&&逻辑与,||逻辑或。 //  知识点3:for(循环变量类型 循环变量名称:要被遍历的对象)循环体。 如int [] integers={1,2,3,4}; for (int i:integers){System.out.println(i);}   //   关键点1:An ASCII string (256)? or letter string (26), or Unicode?  (足以编码地球上所有编程语言)Assume the character set is ASCII. If not, need increase the storage size, the rest of the logic is the same. //   关键点2:If string larger than total character set, immediate false //   方法1:Use an array of boolean values. Index i indicates whether character i is contained in the string. If run across index i a second time, return false. 【Time complexity O(n). Space complexity O(1) (数组大小是256就够了, 不管string多长,都不变). (O(n)是会随string变长而增长)】 //  方法2:Use a bit vector (增补条件:字符集只是26个字母)     //   ( 不使用额外数据结构) 方法1:Compare every character of the string to every other, Time: O(n^2), Space: O(1) //   ( 不使用额外数据结构) 方法2:Sort the string in O(nlog(n)), lineraly check neighboring to see whether same. Sort may take up extra space. (增补条件:allow to sort string)  public class C1_1 { //Use an array of boolean values public static boolean isUniqueChars1(String str) { if (str.length() > 256) { return false; } boolean[] char_set = new boolean[256]; for (int i = 0; i < str.length(); i++) { int val = str.charAt(i); if (char_set[val]) return false; char_set[val] = true; } return true; } public static boolean isUniqueChars2(String str) { if (str.length() > 256) { return false; } int checker = 0; // checker相当于上面的boolean[256]数组,对应为表示出现过否的状态 for (int i = 0; i < str.length(); i++) { int val = str.charAt(i) - 'a'; if ((checker & (1 << val)) > 0) return false; checker |= (1 << val); //这一句把已经出现过的字母对应那位置为1,或操作可以用来置1,而不改变其他位状态。 } return true; } public static void main(String[] args) { String[] words = {"abcde", "hello", "apple", "kite", "padle"}; for (String word : words) {//word相当于for循环里的i System.out.println(word + ": " + isUniqueChars1(word) + " " + isUniqueChars2(word)); } } } // 结果 abcde: true true hello: false false apple: false false kite: true true padle: true true

上一篇:this.options[selectedIndex]的使用
下一篇:socket同步、异步、阻塞和非阻塞

相关文章

关键词: 1.1

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。