递归书写方法
数学归纳法中的数学/自然语言–程序语言(证明递归函数正确执行)
严格定义递归函数作用，包括参数，返回值，Side-effect
先一般，后特殊
每次调用必须缩小问题规模
每次问题规模缩小程度必须为1
递归缺点
调用堆栈Stack太深，开销大
如果数据大，就会Stack Overflow!
不要尝试递归改成非递归
一般化的方法仍需要栈
代码复杂
不根本解决问题
Side-effect 函数副作用。理想的状态是函数运行完没有side-effect。 比较函数执行中会修改全局的一些属性，当执行完，也要将这些全局属性还原
链表
package interview.recursion;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import interview.common.Node;
public class LinkedListCreator {
/**
* Creates a linked list.
*
* @param data the data to create the list
* @return head of the linked list. The returned linked list
* ends with last node with getNext() == null.
*/
publicNodecreateLinkedList(Listdata) {
if (data.isEmpty()) {
return null;
}
NodefirstNode = new Node(data.get(0));
firstNode.setNext(
createLinkedList(data.subList(1, data.size())));
return firstNode;
}
public NodecreateLargeLinkedList(int size) {
Nodeprev = null;
Nodehead = null;
for (int i = 1; i = size; i++) {
Nodenode = new Node(i);
if (prev != null) {
prev.setNext(node);
} else {
head = node;
}
prev = node;
}
return head;
}
public static void main(String[] args) {
LinkedListCreator creator = new LinkedListCreator();
Node.printLinkedList(
creator.createLinkedList(new ArrayList()));
Node.printLinkedList(
creator.createLinkedList(Arrays.asList(1)));
Node.printLinkedList(
creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5)));
}
}
链表反转
package interview.recursion;
import java.util.ArrayList;
import java.util.Arrays;
import interview.common.Node;
public class LinkedListReverser {
/**
* Reverses a linked list.
*
* @param head the linked list to reverse
* @return head of the reversed linked list
*/
publicNodereverseLinkedList(Nodehead) {
// size == 0 or size == 1
if (head == null || head.getNext() == null) {
return head;
}
// 第一步(对应上图)
NodenewHead = reverseLinkedList(head.getNext());
// 第二步
head.getNext().setNext(head);
// 第三步 over
head.setNext(null);
return newHead;
}
public static void main(String[] args) {
LinkedListCreator creator = new LinkedListCreator();
LinkedListReverser reverser = new LinkedListReverser();
Node.printLinkedList(reverser.reverseLinkedList(
creator.createLinkedList(new ArrayList())));
Node.printLinkedList(reverser.reverseLinkedList(
creator.createLinkedList(Arrays.asList(1))));
Node.printLinkedList(reverser.reverseLinkedList(
creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5))));
System.out.println(Testing large data. Expect exceptions.);
reverser.reverseLinkedList(
creator.createLargeLinkedList(1000000));
System.out.println(done);
}
}
combinations([1,2,3,4],2)
缩小问题规模
选1combinations([2,3,4],1)
不选1combinations([2,3,4],2)
package interview.recursion;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Combinations {
/**
* Generates all combinations and output them,
* selecting n elements from data.
*/
public void combinations(
Listselected, Listdata, int n) {
if (n == 0) {
// output all selected elements
for (Integer i : selected) {
System.out.print(i);
System.out.print( );
}
System.out.println();
return;
}
if (data.isEmpty()) {
return;
}
// select element 0
selected.add(data.get(0));
combinations(selected, data.subList(1, data.size()), n - 1);
// un-select element 0
selected.remove(selected.size() - 1);
combinations(selected, data.subList(1, data.size()), n);
}
public static void main(String[] args) {
Combinations comb = new Combinations();
System.out.println(Testing normal data.);
comb.combinations(
new ArrayList(), Arrays.asList(1, 2, 3, 4), 2);
System.out.println(==========);
System.out.println(Testing empty source data.);
comb.combinations(
new ArrayList(), new ArrayList(), 2);
System.out.println(==========);
comb.combinations(
new ArrayList(), new ArrayList(), 0);
System.out.println(==========);
System.out.println(Selecting 1 and 0 elements.);
comb.combinations(
new ArrayList(), Arrays.asList(1, 2, 3, 4), 1);
System.out.println(==========);
comb.combinations(
new ArrayList(), Arrays.asList(1, 2, 3, 4), 0);
System.out.println(==========);
System.out.println(Testing large data);
comb.combinations(
new ArrayList(),
Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 4);
}
}
循环控制(循环不变式 loop invariant)
边界控制
列表项
初始值
特殊值
null
空字符串
数据结构
树的遍历
算法复杂度
代表最坏情况用时
f(x)=O(g(x))asx-oo 当且仅当
If(x)1≤Mlg(x)l for all x =xo 相当于高等数学中极限的定义
广义的“极限”是指“无限靠近而永远不能到达”的意思。数学中的“极限”指：某一个函数中的某一个变量，此变量在变大(或者变小)的永远变化的过程中，逐渐向某一个确定的数值A不断地逼近而“永远不能够重合到A”(“永远不能够等于A，但是取等于A‘已经足够取得高精度计算结果)的过程中，此变量的变化，被人为规定为“永远靠近而不停止”、其有一个“不断地极为靠近A点的趋势”。极限是一种“变化状态”的描述。此变量永远趋近的值A叫做“极限值”(当然也可以用其他符号表示)。
面向对象思想
商业代码复杂性，从用户角度思考问题
摒弃完全基于逻辑的思维
类与对象
类的成员变量对象状态
类的成员函数对象行为
类的静态变量
类的静态函数
没有this引用，静态变量全局唯一—份
普通函数可以引用静态变量、函数
对象上引用静态变量、函数会产生编译器警告
静态函数引用普通成员变量、函数会编译错误
类的特殊函数
构造函数
equals
hashCode
toString
a.equals(b)说明a.hashCode)==b.hashCode) 必要条件
接口与实现
与类相比
由编译器强制的一个模块间协作的合约(Contract)
无成员变量
成员函数只有申明不能有实现
接口的申明
Java:interface BankEndPoint{……
C++：一个全部是纯虚函数的类
Python/大部分动态语言：依靠注释申明
接口和抽象类有什么不同?
从实现角度看
抽象类可以有成员变量
抽象类可以有部分实现
抽象类不可以多重继承，接口可以
接口强调合约
强制协作双方无法犯错(编译器)
但是抽象类提供公共的实现
继承与封装
不可变对象 Immutable Objects
可以引用传递，可以缓存
线程安全
final 关键字
类申明类不可以被继承
函数申明函数不可以在派生类中重写
变量申明变量不可以指向其它对象
static final变量用于定义常量，名称一般大写
final关键字无法保证不可变性
从接口定义，类的实现上保证不可变性
Collections.unmodifiableXXX
泛型
c++虚函数表
void dispatch_work(Employee* p){
p-doWork();
dispatch_ work(manager);
设计模式(解耦和)
设计模式当初的提出就是因为GOF(Erich Gamma，Richard Helm，Ralph Johnson和John Vlissides)的博士论文(这才是真正的程序员)
再谈Singleton(单例模式)
确保全局至多只有一个对象
用于：构造缓慢的对象，需要统一管理的资源
缺点：很多全局状态，线程安全性
双重锁 Double checked locking
第一次check全局对象是不是null,不是null直接拿来用，如果是null,锁住，再check一次(防止其他人在这个空挡创建)
作为Java类的静态变量(全局只有一份，不过程序员初始化就要创建这个静态变量，所以也就增加了初始化的时间(如果是比较缓慢的对象))
使用框架提供的能力
依赖注入
变继承关系为组合关系(状态模式State)
描述is-a关系
不要用继承关系来实现复用
状态逻辑和动作实现没有分离。在很多的系统实现中，动作的实现代码直接写在状态的逻辑当中。这带来的后果就是系统的扩展性和维护得不到保证。
使用设计模式来实现复用
Decotator装饰器模式
interface Runnable{
void run);
如何实现LoggingRunnable,TransactionalRunnable.…
对象如何创建
使用new来创建的缺点
编译时必须决定创建哪个类的对象
参数意义不明确
Abstract Factory Pattern 抽象工厂
task=new Logging Task(new Coding Task);
task=taskFactory.createCodingTask); (好)
Builder Pattern 生成器
解决参数意义不明确的问题
不可变对象往往配合Builder使用
employee=new Employee(
oldEmployee.getName),15000);
employee=Employee.fromExisting(oldEmployee)
.withSalary(15000)
.build();
Beautiful Numbers
1,11，111…是beautiful的
32进制11
133进制111(选位数多的)
133+1*3+1=13
13%3=1,13/3=4
4%3=1,4/3=1
1%3=1,1/3=0
1312进制11
Nr进制111…1(k个) 求大数据集思路
N=r(k-1)+r(k-2)+.…+r+1
N=(1-r^k)/(1-r)
假设N能转化成k个1组成的Beautiful Number
那么这个Beautiful Number是几进制?r=?
因为k最多是64个(最低两位)，但是r最多就太大了
O(nlogn) 10*8 ~= 1s
package interview.google;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
public class BeautifulNumber {
public static void main(String[] args) {
Scanner in = new Scanner(
new BufferedReader(new InputStreamReader(System.in)));
int cases = in.nextInt();
for (int i = 1; i = cases; ++i) {
long n = in.nextLong();
System.out.println(Case # + i + :
+ beautiful(n));
}
}
private static long beautiful(long n) {
for (long radix = 2; radix n; radix++) {
if (isBeautiful(n, radix)) {
return radix;
}
}
throw new IllegalStateException(Should not reach here.);
}
private static boolean isBeautiful(long n, long radix) {
while (n 0) {
if (n % radix != 1) {
return false;
}
n /= radix;
}
return true;
}
}
O(logn*logn*logn) 64*64*64
package interview.google;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
public class BeautifulNumberLarge {
public static void main(String[] args) {
Scanner in = new Scanner(
new BufferedReader(new InputStreamReader(System.in)));
int cases = in.nextInt();
for (int i = 1; i = cases; ++i) {
long n = in.nextLong();
System.out.println(Case # + i + :
+ beautiful(n));
}
}
private static long beautiful(long n) {
for (int bits = 64; bits = 2; bits--) {
long radix = getRadix(n, bits);
if (radix != -1) {
return radix;
}
}
throw new IllegalStateException(Should not reach here.);
}
/**
* Gets radix so that n is 111...1 (bits 1 in total) in that
* radix.
*
* @return the radix. -1 if there's no such radix.
*/
private static long getRadix(long n, int bits) {
long minRadix = 2;
long maxRadix = n;
while (minRadix maxRadix) {
// 二分查找法
long m = minRadix + (maxRadix - minRadix) / 2;
long t = convert(m, bits);
if (t == n) {
return m;
} else if (t n) {
minRadix = m + 1;
} else {
maxRadix = m;
}
}
return -1;
}
/**
* Returns the value of 111...1 (bits 1 in total) in radix.
* 等比数列求和
*/
private static long convert(long radix, int bits) {
long component = 1;
long sum = 0;
for (int i = 0; i bits; i++) {
if (Long.MAX_VALUE - sum component) {
sum = Long.MAX_VALUE;
} else {
sum += component;
}
// 防止内存溢出
if (Long.MAX_VALUE / component radix) {
component = Long.MAX_VALUE;
} else {
component *= radix;
}
}
return sum;
}
}
