字符串转化为整数
首先判断字符串是否为空，返回0
考虑前面的是否是空格，使用trim()去掉，然后判断长度是否为0，是的话，返回0
判断第一个字符是不是+和-，设置变量sign记录
循环取得字符串的数字，考虑字符串中有非数字，遇到就退出，保留前面的数字
考虑溢出的情况，溢出返回Integer的最大值或最小值
public static int myAutoNumber(String str){
//首先判断空值
if(str == null){
return 0;
}
//去掉空格的情况
str = str.trim();
if(str.length() == 0)
return 0;
//正负数标志
int sign = 1;
int index = 0;
if(str.charAt(index) == '+')
index ++;
else if(str.charAt(index) == '-'){
index ++;
sign = -1;
}
//取得数字部分，遇到溢出和非数字退出
long number = 0;
for(; index < str.length();index++){
if(str.charAt(index) < '0' && str.charAt(index) > '9'){
break;
}
number = number * 10 + (str.charAt(index) - '0');
if(number >= Integer.MAX_VALUE)
break;
}
if(number * sign <= Integer.MIN_VALUE)
return Integer.MIN_VALUE;
if(number * sign >= Integer.MAX_VALUE)
return Integer.MAX_VALUE;
return (int) number * sign;
}
遍历二叉树
// 顺序存储结构的递归先序遍历
var tree = [1, 2, 3, 4, 5, , 6, , , 7];
void function preOrderTraverse(x, visit) {
visit(tree[x]);
if (tree[2 * x + 1]) preOrderTraverse(2 * x + 1, visit);
if (tree[2 * x + 2]) preOrderTraverse(2 * x + 2, visit);
}(0, function (value) {
console.log(value);
});
// 链式存储结构的递归先序遍历
BinaryTree.prototype.preOrderTraverse = function preOrderTraverse(visit) {
visit(this.data);
if (this.leftChild) preOrderTraverse.call(this.leftChild, visit);
if (this.rightChild) preOrderTraverse.call(this.rightChild, visit);
};
非递归
// 链式存储的非递归先序遍历
// 方法1
BinaryTree.prototype.preOrder_stack = function (visit) {
var stack = new Stack();
stack.push(this);
while (stack.top) {
var p;
// 向左走到尽头
while ((p = stack.peek())) {
p.data && visit(p.data);
stack.push(p.leftChild);
}
stack.pop();
if (stack.top) {
p = stack.pop();
stack.push(p.rightChild);
}
// 方法2
BinaryTree.prototype.preOrder_stack2 = function (visit) {
var stack = new Stack();
var p = this;
while (p || stack.top) {
if (p) {
stack.push(p);
p.data && visit(p.data);
p = p.leftChild;
} else {
p = stack.pop();
p = p.rightChild;
}
}
查询链表第N个元素
第一种方法先求出元素个数，在遍历元素个数-n个，时间复杂度为：O(N+N-、
n)=O(2N-n)。
第二种设置俩个指针，第一个先走N步，第二个开始走。俩者速度一样，时间复
杂度为O(N)。
代码如下：
/**
* 获取单链表倒数第N个元素
* @author xiucai
*/
public class SingleLinkedList_LastN {
/**
* 第一种方法先求出元素个数，在遍历元素个数-n个
* 时间复杂度为：O(N+N-n)=O(2N-n)
* @param list
* @param n
* @return
* @throws Exception
*/
public static<T> T getLastN1(SingleLinkedList<T> list,int n) throws Exception{
int count=0;
Node<T> node=list.head;
while(node.next!=null){
count++;
node=node.next;
}
if(count<n)
throw new Exception("单链表元素个数小于 "+n+" !");
node=list.head;
for(int i=0;i<count-n;i++){
node=node.next;
}
return (T)node.data;
}
/**
* 设置俩个指针，第一个先走N步，第二个开始走。俩者速度一样
* 时间复杂度为O(N)
* @param list
* @param n
* @return
* @throws Exception
*/
public static<T> T getLastN2(SingleLinkedList<T> list,int n) throws Exception{
//fastN先走N步，slowN等fastN走N步后在开始走
Node<T> fastN=list.head,slowN=list.head;
for(int i=0;i<n;i++){
if(fastN.next==null){
throw new Exception("单链表元素个数小于 "+n+" ！");
/*try {
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}*/
}
fastN=fastN.next;
}
while(fastN.next!=null){
fastN=fastN.next;
slowN=slowN.next;
}
return (T)slowN.data;
}
100个球三种颜色多少种情况
//假设白球1个，红球和黄球任意组合，那么有 1，98，98，1
//98 个可能，猜测，觉得应该不对
//那么98 * 98 = 9604
集合中第一个只出现一次的字符，考虑时间效率与空间效率之间的平衡
为了解决这个问题，我们可以定义一个哈希表（外部空间），其键值（Key）是
字符，而值（Value）是该字符出现的次数。
同时我们还需要从头开始扫描字符串两次：
1）第一次扫描字符串时，每扫描到一个字符就在哈希表的对应项中把次数加1。
（时间效率O(n)）
2）第二次扫描时，每扫描到一个字符就能从哈希表中得到该字符出现的次数。
这样第一个只出现一次的字符就是符合要求的输出。（时间效率O(n)）
这样算起来，总的时间复杂度仍然是O(n)，满足了题目要求，擦一擦汗，感
叹：这*装得真有点技术！
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str == null || str.length() == 0)
return -1;
int[] sign = new int[256];
char[] array = str.toCharArray();
for(int i=0;i<array.length;i++){
if(sign[array[i]] < 2)
sign[array[i]] ++ ;
}
for(int i=0;i<array.length;i++){
if(sign[array[i]] == 1)
return i;
}
return -1;
}
}
最长无重复字符的子串
思路：[pre,i]表示一个无重复子串，用hash表记录子串中每个字符的出现次
数。初始pre = 0，i = 0，i从左往右扫描字符串，maxLength保存当前最
大长度。每扫描一个字符，根据对应的值来判断这个字符是否已经出现。
如果A[i]已存在, 将pre与当前字符A[i]位置的下一个位置进行比较，选择最
大者作为最新pre所指位置，然后再更新maxLength；
如果不存在，则继续扫描，(i - pre + 1)与最大长度进行比较，更新
maxLength。
将A[i]以及对应的位置i保存，更新字符最近出现的位置。
int longestSubstring(string A, int n) {
map<char, int> m;
//map中的键key存放字符串中出现的字符，值value存放该字符当前的位置
int maxLength = 0; //保存最长字串长度
int pre = 0; //记录头指针位置
for(int i=0; i<n; i++ ){
map<char, int>::iterator iter=m.find(A[i]);
if(iter!=m.end()){//如果map中已存在当前字符 m[A[i]]
//更新当前指针位置，如果当前指针大，则使用当前指针，否则使用该指
针下一个字符的位置
pre = max(pre, (m[A[i]]+1));
}
maxLength = max(maxLength, i-pre+1);//更新最长字串的长度
m[A[i]]=i;//修改当前字符的value，记录最新位置
}
return maxLength;
}
另一种类似：
int longestSubstring(string A, int n) {
map<char, int> m; //表示字符串中每个字符是否出现，初始化为
0，表示未出现
int start = 1,MAX = 0;
//遍历该字符串，每遍历一个字母时，利用map去找该字母最近一次出现
是什么时候
//中间这一段便是无重复字符的字符串。
for (int i = 1; i <= n; i++){
char c = A[i - 1];
if (m[c] >= start){
start = m[c] + 1;
}
MAX = max(MAX, i - start + 1);
m[c] = i; //map添加数据 mapStudent[char] = int
}
return MAX;
}
二分查找法查找多少次
寻找距离最近的公共父视图，已知两个节点和根节点
二叉树查找
栈的push和pop的时间复杂度，实现O（1）的找出栈中最小值的算法（栈只在一端操作，以空间换时间）
Hash碰撞冲突
我们知道，对象Hash的前提是实现equals()和hashCode()两个方法，那么
HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样
时，这就发生了碰撞冲突。如下将介绍如何处理冲突，当然其前提是一致性
hash。
1.开放地址法
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为
1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为
1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散
列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
2.再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺
点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第
二位进行哈希，再冲突，第三位，直到不冲突为止
3.链地址法（拉链法）
NSMutableArray以及NSMutableDictionary的设计不是多线程安全的，
当然这种设计的好处是处理速度快，不需要任何锁进行同步，所以我们在使用
Objective-C的这些容器的时候需要注意，在哪个线程中创建它们就在哪个线
程中对它们进行操作。不过在某些情况下，我们由于一些算法或业务需求，需要
在多个线程中共享一个NSMutableArray容器对象，这时候我们需要通过一些
同步机制来实现多线程操作的安全性。
一个对象的引用计数记录在一个hash表中的话，如何保证多线程的时候计数的
准确性？（从上到下加锁消耗太大，可以采用分治，每十个加一个锁）