问题1：
有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，
这两个房间是分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
分析：
灯泡和开关的问题。三个灯泡、三个开关，要在灯泡和开关之间建立对应关系。使用一条准则，一个灯泡可以关联一个开关。再使用一条准则，又一个灯泡可以再关联一个开关。那么，最后剩下的灯泡就必然和剩下的开关对应。因此，只要找到两条判断的依据即可。依据1：当前灯泡的亮灭。依据2：亮过的灯泡会发热。
1.先走进有开关的房间，将三个开关编号为a b c。
2.将开关a 打开5分钟，然后关闭，然后打开b
问题2：
你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。
如果你只能将金条切割两次，你怎样分给这些工人?
分析：
1+2+4;
两刀分金条。共7天，每天给1/7。
第一天从金条上切1/7支付给工人。
第二天从金条上切2/7，这时剩下4/7。支付2/7给工人，收回1/7。
第三天将收回的1/7支付给工人
第四天将4/7支付给工人，并将1/7、2/7收回
...
问题3：
★用一种算法来颠倒一个链接表的顺序。现在不用递归式的情况下做一遍。
class LinkedListIT8{
static class Node{
int data;
Node next;
Node(int x, Node n){
data = x;
next = n;
}
}
private Node head;
private Node tail;
private int theSize;
LinkedListIT8(){
head = new Node(-1, null);
tail = new Node(-1, null);
head.next = tail;
theSize = 0;
}
public int size(){
return theSize;
}
public void add(int x){
addAfter(getNode(size()), x);
}
private void addAfter(Node p, int x){
Node newNode = new Node(x, p);
newNode.next = p.next;
p.next = newNode;
theSize++;
}
private Node getNode(int idx){
Node p = head;
for (int i = 0; i < idx; i++)
p=p.next;
return p;
}
public void printList(){
Node p = head.next;
for (int i = 0; i < size(); i++) {
System.out.print(p.data + " ");
p = p.next;
}
}
public void reverse(){
//reverseR(head);
reverseNR(head);
}
private Node reverseR(Node currentNode){
if(currentNode == tail) {
head = currentNode;
} else {
reverseR(currentNode.next).next = currentNode;
}
return currentNode;
}
private void reverseNR(Node phead){
Node pre = head;
Node cur = head.next;
Node np;
while(cur != tail){
np = cur.next;
cur.next = pre;
pre = cur;
cur = np;
}
head = cur;
cur.next = pre;
tail = phead;
tail.next = null;
}
}
public class IT8 {
public static void main(String[] args) {
LinkedListIT8 ll = new LinkedListIT8();
ll.add(0);ll.add(1);ll.add(2);ll.add(3);
ll.add(4);ll.add(5);ll.add(6);ll.add(7);
ll.printList();
ll.reverse();
System.out.println("\n***************");
ll.printList();
}
}
★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。
★用一种算法整理一个数组。你为什么选择这种方法?
★用一种算法使通用字符串相匹配。
★颠倒一个字符串。优化速度。优化空间。
★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
★找到一个子字符串。优化速度。优化空间。
★比较两个字符串，用O(n)时间和恒量空间。
★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?
★不用乘法或加法增加8倍。现在用同样的方法增加7倍。
原文：http://my.oschina.net/jimmyhan/blog/526004