《编程珠玑》第二章：啊哈！算法——左旋转&&变位词-白红宇

《编程珠玑》第二章：啊哈！算法——左旋转&&变位词

阅读量：7142 次

发布时间：2019-06-28

本文共 9484 字，大约阅读时间需要 31 分钟。

本章讲解的是算法的作用，“看起来很困难的问题也可以有一个简单的、意想不到的答案。”在任何愿意在编程之前、之中和之后进行认真思考的程序员都有机会捕捉到这灵光一闪。

文章从三个问题展开，我独自先思考了一下，发现解决方法都是比较低效的，既浪费空间也浪费时间。

a.给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺少一个这样的数，为什么？就是2³² > 40亿所以就是有至少缺少一个）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？

b.将一个n元一维向量左旋转i个位置。例如，当n=8且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间变量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转？

c.给定一个英语词典，找出其中的所有变位词集合。例如，“pots","stop"和“tops"互为变位词，因为每个单词都可以通过改变其他单词中字母的顺序来得到。

对于a题，第一时间应该是想到“二分搜索”这个方法。在log n时间内完成对顺序文件的搜索。但因为前提是要顺序，所以这也是二分搜索的一个弊端。因为要对非排序的整数排序，至少是需要n的正比时间。此题所提到的“二分搜索”我会在第四章章才实现，因为那章提及到“二分搜索”的校验。对于第二个小问，如果仅有几百字节的内存，可以使用我上一章提及到位图存储的方法存储这40亿个整数。

对于b题，我第一时间会想到题目提及到的方法实现，但十分低效。文章中提及到三种方法（我实现了两种，第三种比较简单）

这里有一个抽象类是记录每种方法的旋转的运行时间：

package ckj.chapter2.swap;public abstract class Rotation {	public char[] m_input;	public String m_rotname;	public int m_length;	public int m_rotdist;		public Rotation(String input,int rotdist){		this.m_input = input.toCharArray();		this.m_length = input.length();		this.m_rotdist = rotdist;	}		public abstract void rotate();		/**	 * the cost time of the rotation	 */	public void rotCost(){		//printChar("before----->");		long t1 = System.currentTimeMillis();		rotate();		long cost = System.currentTimeMillis() - t1 ;		System.out.println("The cost of "+this.m_rotname+" :  " + cost);		//printChar("after----->");	}		/**	 * print out the char array with the string name before	 * @param str	 */	private void printChar(String str){		System.out.println(str);		for(int i = 0 ; i < this.m_length ; i ++){			System.out.print(this.m_input[i]);		}		System.out.println();	}}

第一种方法，按书上的说法是很有技巧性的：移动x[0]到临时变量t，然后移动x[i]至x[0]，x[2i]至x[i]，以此类推，直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。

package ckj.chapter2.swap;public class MagicRotate extends Rotation {	public MagicRotate(String input,int rotdist){		super(input,rotdist);		this.m_rotname = "Magic Rotation";	}	@Override	public void rotate() {		if (this.m_rotdist == 0 ) return;		for ( int i = 0 ; i < gcd(this.m_rotdist,this.m_length) ; i ++){			/* move i-th values of blocks */			char t = m_input[i];			int j = i,k ;			while(true){				k = j + m_rotdist ;				if ( k >= m_length )					k -= m_length ;				if (k == i)					break;				m_input[j] = m_input[k];				j = k;			}			m_input[j] = t;		}	}	/**	 * To find the greatest common divisor between i & j	 * @param i 	 * @param j	 * @return the greatest common divisor	 */	private int gcd(int i, int j) {		if ( i < j) return gcd(j,i);		if ( i%j == 0 ) return j;		while (i != j){			return gcd(i%j,j);		}		return 0;	}}

第二种方法是块旋转。旋转就是交换变量ab，得到变量ba。假如a比b短，将b分为b

_l和b

_r，使得

_r具有与a相同的长度，交换a与b_r 得到br

_{bl a ，然后最后交换b_r_bl ，（如果长度不一样，重复上述步骤），最后就能得到结果 bl_br a 。}

package ckj.chapter2.swap;public class MagicRotate extends Rotation {	public MagicRotate(String input,int rotdist){		super(input,rotdist);		this.m_rotname = "Magic Rotation";	}	@Override	public void rotate() {		if (this.m_rotdist == 0 ) return;		for ( int i = 0 ; i < gcd(this.m_rotdist,this.m_length) ; i ++){			/* move i-th values of blocks */			char t = m_input[i];			int j = i,k ;			while(true){				k = j + m_rotdist ;				if ( k >= m_length )					k -= m_length ;				if (k == i)					break;				m_input[j] = m_input[k];				j = k;			}			m_input[j] = t;		}	}	/**	 * To find the greatest common divisor between i & j	 * @param i 	 * @param j	 * @return the greatest common divisor	 */	private int gcd(int i, int j) {		if ( i < j) return gcd(j,i);		if ( i%j == 0 ) return j;		while (i != j){			return gcd(i%j,j);		}		return 0;	}}

第三种方法是求逆方法。从ab开始，先对a求逆a^r，再对b求逆b^r，最后在对a^rb^r整个求逆(a^rb^r)^r 这个方法比较容易实现，晚一点的时候补上。

^{最后调用的主函数MainClass.java}

package ckj.chapter2.swap;import java.io.BufferedWriter;import java.io.File;import java.io.FileNotFoundException;import java.io.FileOutputStream;import java.io.IOException;import java.io.OutputStreamWriter;public class MainClass {	private static final int _SIZE = 1000000;	/**	 * @param args	 */	public static void main(String[] args) {		// TODO Auto-generated method stub		char[] inputchar = new char[_SIZE];		/* produce a string repeated 123...789123...789123...789123... totally _SZIE digits  */		for ( int i = 0 ; i < _SIZE ; i ++)			inputchar[i] = (char)(i%9+49);		String input = new String(inputchar);				/* write the string to rotate in a file named "rotationString.txt" */		writeFile(input,false);				for (int rotdist = 1; rotdist < 50; rotdist++) {			System.out.println("No. " +rotdist+" ----->");			Rotation mr = new MagicRotate(input, rotdist);			mr.rotCost();			//writeFile(new String(mr.m_input),true);			mr = new BlockRotate(input, rotdist);			mr.rotCost();			//writeFile(new String(mr.m_input),true);		}	}	private static void writeFile(String input,boolean flag) {		try {			File file = new File("rotationString.txt");			FileOutputStream fos = new FileOutputStream(file,flag);			OutputStreamWriter osw = new OutputStreamWriter(fos);			BufferedWriter bw = new BufferedWriter(osw);			bw.write(input);			bw.newLine();			bw.newLine();			bw.close();			osw.close();		} catch (FileNotFoundException e) {			// TODO Auto-generated catch block			e.printStackTrace();		} catch (IOException e) {			// TODO Auto-generated catch block			e.printStackTrace();		}	}}

^{对于c题，用到的思想就是“标识”。以标记的方式，对数据进行标记，而不是直接对内容进行搜索。例如单词这里，mississippi 标识可以写成“i4m1p2s4"，分别表示字母出现的次数，字母要以升序排序。}

package ckj.chapter2.words;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Map;import java.util.Set;import java.util.TreeMap;public class WordManipulation {	private Map
    
     > result ;	private String[] wordInput;		public WordManipulation(String[] word){		this.wordInput = word;	}		/**	 * string sort to find a lable like (mississippi,i4m1p2s4)	 * @param word The string to be sorted	 * @return the string sorted	 */	private String sort(String word){		Map
     
       map = new TreeMap
      
       ();		for ( int i = 0 ; i < word.length() ; i ++ ){			char temp = word.charAt(i);			if ( map.get(temp) == null){				map.put(temp, 1);			} else {				int value = map.get(temp);				map.put(temp, ++value);			}		}		return map.toString();	}		/**	 * squash the same label into a ArrayList 	 * @param map	 */	private void squash(Map
       
         map){		result = new TreeMap
        
         >();		Set
         
          
           > entrySet = map.entrySet(); for (Map.Entry
           
             entry:entrySet){ String strKey = entry.getKey(); String strValue = entry.getValue(); System.out.println(strKey+" ----> "+ strValue); List
            
              resultList; if (result.get(strValue) == null){ resultList = new ArrayList
             
              (); } else { resultList = result.get(strValue) ; } resultList.add(strKey); result.put(strValue, resultList); } } /** * calculate the anagram */ public void doCalculate(){ Map
              
                temp = new TreeMap
               
                (); for(int i = 0 ; i < this.wordInput.length ; i ++){ temp.put(this.wordInput[i], sort(this.wordInput[i])) ; } squash(temp); print(); } private void print(){ System.out.println(result.values()); }}

最后的主函数，可以通过控制台输入想要的单词中找到所有变位词。以"over”作为结束的单词输入。

文件读写WordsFile.java . 会将输入的单词中存入words.txt的文件中，以后的运行，可以把主函数的wf.createWordsFile()语句注释，可以不用再输入单词。

package ckj.chapter2.words;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.File;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.FileOutputStream;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;public class WordsFile {	private String fileName ;	public WordsFile(){		this("words.txt");	}	public WordsFile(String fileName){		this.fileName = fileName;	}	private void createWordFile(String fileName){		System.out.println("input your words you want to find the anagram (with typing 'over' to end):");		try {			File file = new File(fileName);			FileOutputStream fos = new FileOutputStream(file);			OutputStreamWriter osw = new OutputStreamWriter(fos);			BufferedWriter bw = new BufferedWriter(osw);			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));			String s;			while(!(s = br.readLine()).equalsIgnoreCase("over")){				bw.write(s);				bw.newLine();			}			bw.flush();			br.close();			bw.close();			osw.close();			fos.close();		} catch (FileNotFoundException e) {			// TODO Auto-generated catch block			e.printStackTrace();		} catch (IOException e) {			// TODO Auto-generated catch block			e.printStackTrace();		}	}		public void createWordFile(){		createWordFile(this.fileName);	}		private String[] readWordFile(String fileName){				try {			File file = new File(fileName);			FileInputStream fis = new FileInputStream(file);			InputStreamReader isr = new InputStreamReader(fis);			BufferedReader br = new BufferedReader(isr);			String s ;			String result = "";			while((s=br.readLine())!=null){				result +=  s +" " ;			}			System.out.println("result---->"+result);			br.close();			isr.close();			return result.split(" ");		} catch (FileNotFoundException e) {			// TODO Auto-generated catch block			e.printStackTrace();		} catch (IOException e) {			// TODO Auto-generated catch block			e.printStackTrace();		}		return null;			}		public String[] readWordFile(){		return this.readWordFile(this.fileName);	}}

_{主函数调用MainClass.java}

package ckj.chapter2.words;public class MainClass {	public static void main(String[] args) {		WordsFile wf = new WordsFile();		/*  barring it's the first time to run this program , you should run the next code  .  */		wf.createWordFile();		//		WordManipulation wm = new WordManipulation(wf.readWordFile());		wm.doCalculate();	}}

_{本章的内容主要是两个——“二分搜索”的高效以及 “标识”等价关系的使用。}

转载于:https://my.oschina.net/gzckj/blog/90366

你可能感兴趣的文章