I saw a Microsoft's algorithm, and the topic is probably: there is a big integer array, how can we find a value in this array. Suppose a large size of an array is large (for example, 35,000 values), we know that the integer range is 16 in a certain C / C compiler, which can only be 65536. So how can you find the integer value in this array through the least cost? ! Solution: 1. We can use the same algorithm as a digital number to answer this question. For example, when we are 1 to 10, if 1 to 10 is continuous, then we can definitely there will be no value in this range, and we can think about this environment. Suppose we traverse the arrays, remove all of these continuous values, then those discontinuous segments in the middle of the continuous values are the value we are looking for. 2. Because Java language is a good package of data structures, this Java solution is simple and easy. First we describe the following data structure: / * * Created on 2003-4-6 * * to change this generated comment Go to * window> preferences> java> code generation> code and commertes * / package bia.arithmetic;
Import Java.io.printStream;
/ ** * @author Administrator * * To change this generated comment go to * Window> Preferences> Java> Code Generation> Code and Comments * / public class NumberNode {int value; boolean hasLeft; boolean hasRight; NumberNode next, prev; public Void Print (PrintStream out) {string s = string.valueof (value); if (Hasleft) {s = "-" s;} else {s = " s;} if (HASRIGHT) {s = s "-";} else {s = s "";} out.print (s);} public numbernode () {value = 0; Hasleft = false; HASRIGHT = false;} / ** * @return boolean * / Public boolean ishasleft () {returnşn;
/ ** * @Return Boolean * / public boolean ishalasright () {Return hasRight;}
/ ** * @Return Numbernode * / public numberNode getNext () {Return next;}
/ ** * @Return Numbernode * / public numlernode getprev () {Return prev;}
/ ** * @Return Int * / public int getValue () {return value;}
/ ** * sets the Hasleft. * @Param Hasleft The Hasleft to set * / public void setHaslex (Boolean Hasleft) {this.hasleft = Hasleft;} / ** * sets the hasright. * @Param Hasright the Hasright to set * / Public void sethasright (boolean hasright) {this.hasright = HASRIGHT;}
/ ** * sets the next. * @Param next the next to set * / public void setnext (Numbernode next) {this.next = next;}
/ ** * sets the prev. * @Param prev the prev to set * / public void setprev (Numbernode prev) {this.prev = prev;}
/ ** * sets the value. * @Param Value the value to set * / public void setvalue (int value) {this.value = value;
} Then, we use this structure to construct a NumberList linked list to handle the operation of sorting and sequential reading, in which the middle continuous part is blocked, leaving only a continuous boundary.
/ * * Created on 2003-4-6 * * to change this generated comment go to * window> preferences> java> code generation> code and comments * / package bia.arithmetic;
Import Java.io.printStream;
/ ** * @Author administrator * * to change this generated comment Go to * window> preferences> java> code generation> code and commerss * / public class number111111
Public void print {out.println ("====== begin print list ======"); NumberNode P = first; while (null! = p) {P.Print (out) P = p.getNext ();} out.println ("/ n =========");} public numberlist ()}
Public Numbernode getFirst () {return first;}
public void addNumber (int number) {NumberNode node = new NumberNode (); node.setValue (number); addNode (node);} / ** * add a node method * @Renzhichao * @param node * / public void addNode (NUMBERNODE NODE) {if (first == NULL) {first = node; first.setprev (null); first.setnext (null); first.setHaslex (false); first.sethasright (false);} else {NumberNode TMP = First; NumberNode P = Tmp; While (Tmp.getValue ()
