剑指offer（二）

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：我的思路就是使用先使用Integer的toBinaryString方法将该数转换成二进制形式的字符串，然后统计1的个数。

另一种更好的解法：位运算符&，|，~等是针对二进制的。所以我们可以使用&求解本题。一个数如果不为0，则它表示的二进制必定带有1，当它减1的时候，其最低位的1必定会变成0，其后的0必定全部变成1，如1100，减1，第三位变成了0，后面的两个0 都变成1，就变成了1011，而1100 & 1011 = 1000，也就是说每次这个数和比它小1的数进行&运算，都会消去一个1，基于此，可以得到下面的解法。

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：直接使用有个linkedList作为额外空间，然后把数组的奇数插入前半部分，偶数插入后半部分。

不使用额外的空间求解，使用类似于冒泡的思想，每次循环把一个偶数移动到数组的最后

输入一个链表，输出该链表中倒数第k个结点。

思路1：首先遍历一遍链表，得到链表的长度len，则len - k就是倒数第k个节点

思路2：使用两个指针，第一个指针先移动k个位置，之后两个指针一起移动，当第一个指针移动到链表尾部的时候，第二个指针所指向的元素就是倒数第k个元素

输入一个链表，反转链表后，输出新链表的表头。

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：看到树就有点懵逼，还有递归，看来要勤加练习树这一块。

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述

二叉树的镜像定义：源二叉树

8

/ \

6 10

/ \ / \

5 7 9 11

镜像二叉树

10 6

11 9 7 5

思路：直接用递归即可

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路：首先打印矩阵的第一行元素，然后把剩下的矩阵逆时针旋转90度，继续打印矩阵的第一行元素，直到矩阵为空。

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：首先遍历压入序列，遇到和弹出序列不一样的元素，则放入一个list中，遍历完压入序列后，若弹出序列还没遍历完，则反向遍历list，继续和弹出序列比较，如果有任何一个不相等，则返回false。