剑指offer心得

下面是对每道的重点提示：
1.赋值运算符函数：若为本身，则返回本身；否则清除原来内存，重新分配内存，strcpy复制
2.实现singleton模式:

public class Singleton {
    private static Singleton singleton = new Singleton();
    private Singleton(){}
    public static Singleton getInstance(){
        return singleton;
    }
}

3.二维数组的查找：找右上角的点，去不断清除行列
4.替换空格：首先找到空格个数，然后加上相应值，得到替换后的末端，原末端到现末端去移动
5.从尾到头打印链表：能改变链表结构，打就可以；不能的话，就去使用栈
6.重建二叉树：给出前中序 找根节点 左右支去构建就行
7.两栈实现队列 ：进队列从左边进栈，出队列从右边出栈，右边没有便把左边的出栈再进右边栈
8.旋转数组的最小数字：用二分查找，中间值大于最左边，在右边查，小于最左边值，在左边查
9.斐波那契数列：递归效率不高 用数列中间项
10.二进制中1的个数：普通是用这个数与1相与 值为1加一，数向右一个循环，负数会死循环时，故相与的1向左移
11.数值的整数次方 考虑多种整数使用递归
12.打印1到N位数，太大，使用字符串
13.O（1）时间删除结点，把下一个结点的内容复制到这个结点上，删除下一个结点
14.调整奇数为与偶数前面 用交换而不用单个遍历
15.链表中倒数第k个结点 增加个指针先移动K-1个结点
16.反转链表 ：防止断裂 要增加这个结点及前结点 两个一起走
17.合并排序链表：空值返回 找最小的插入
18.树的子结构 ：遍历树中与根值相同的点，找到后再比较子树相同吗
19.二叉树镜像：遍历二叉树，然后改变左右子树
20.顺时针打印矩阵：起始都在对角线，找到终点值，根据大小来确定走几次
21.包含min函数的栈：如果进栈值更小，辅助栈进栈。出栈：值出则出
22.栈的压入弹出序列：看出栈，一直到序列第一个才停止入栈，同时出栈，直到所有的都压入栈
23.从上往下打印二叉树：使用队列，根进队列，然后出队列，根的左右结点进队列
24.二叉搜索树的后序遍历序列：找到根，看左边是否小于根，右边是否大于根，然后递归
25.二叉树中和为某一值的路径：使用栈的形式，看栈中的数和是否为那个值，然后遍历
26.复杂链表的复制：在每个链表结点后加一个相同的，同行为，然后删掉前面的
27.二叉搜索树与双向链表:构建根节点和左右子树的最大最小的点，然后遍历
28.字符串的排列，N皇后问题，使用递归回溯法，将第一个与后面一个一个对调，然后递归回溯
29.数组中出现次数超过一半的数字：使用快速排序，返回在中间数右在左边找，左在右找O（n）
30.最小的K个数问题：O（n）同样使用快排找到第k个值
海量数据：辅助一个容器 存放当前最小的N个数 这个容器可以是最大堆，实现困难，所以使用一定程度平衡的红黑树 在stl中set 
multiset都是。
31.连续子数组的最大和：使用动态规划，以i为结尾的子数组最大和与i-1 如果i-1为负数则抛弃，否则加进来 求最大值
动态规划：分析用递归，编码基于循环
32.1到N中1出现的次数：分治 使用排列组合
33.把数组排成最小的数：进行谁在前后排序：mn nm转化为字符串，比较大小
34.丑数：使用数组来存储丑数
35.第一个只出现一次的字符：遍历两边 使用哈希表记录字符及次数
36.数组中的逆序对：划分数组 然后归并排序
37.两个链表的第一个公共结点：先让长的走一个长短差的位置，然后同时走
38.在排序数组中找到某一个数字出现的次数：二分排序找第一个数字和最后一个（只要找到的中间是这个数就看前一个是不是这个数 不是就二分去找）
39求二叉数的深度：空节点返回0，不空返回左右子树深度大的加一
40数组中只出现一次的数：所有的数进行异或，得到一个数，看这个数哪一位为1,就对着一位01进行分类，得到的两组分别异或
41.和为s的两个数字的连续正数序列：从1 2开始和没到所要的值就加入，超过就去把前面一个数去掉
42.翻转单词顺序和左旋字符串：先整体倒置，在一个一个单词倒置
43.n个骰子的点数：两个数组迭代，下一个的n点次数是上一个点数n-6，到n-1点数次数的和
44.扑克牌问题：把扑克牌排序，看相邻的差距是否小于大小王的个数
45.圆圈中最后剩下的数字：使用循环形链表
46.求1+2+ +n ：不用循环 使用构造函数的静态成员变量
47.不用加减乘除做加法：使用异或运算 加上进位 进位用与运算表示 迭代加起来
48.不能被继承的类：常规：把构造函数设为私有
49.把字符串化为整数：考虑输入空串，有符号的数字，后面一个一个提取 然后前面*10+这个数迭代    C++成员初始化与初始化列表无关，与声明有关
50.树中两个结点的最低公共祖先：如果是搜索二叉树的话，如果根比两个都大，在左边找，如果小，右边找
如果树有父亲结点指针，求链表的第一个公共结点
都没有，遍历得到两个结点的路径，求最后的公共结点