最近的事情有点多啊，还有毕业设计啥的，就不该立flag！还好之前剑指offer多写了几题，所以这次更博就把剑指offer中的十题更新一下，但我还是要保持三天更新一次博客，就相当于是学习吧！今天是第三天，事不宜迟，不然要食言啦。
十一：二进制中的1的个数
1：题目
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
2：思路
我看到很多牛友的解答都是自己将其转换成二进制，然后计数，这当然是特别厉害的。但是既然有造好的轮子，我们不妨调用库函数，只要知道有这个函数并会正确使用就可以了，见代码注释。
3：代码
public class Solution {
public int NumberOf1(int n) {
String s=Integer.toBinaryString(n);//调用Integer中的静态方法，即将其转换成二进制字符
char[]c=s.toCharArray();//为了便于计数字符串中的1的个数，我们再将其放入数组中，下面的代码就是简单的计数
int count=0;
for(int i=0;i<c.length;i++)
{
if(c[i]=='1')
{
count++;
}
}
return count;
}
}十二：数值的整数次方
1：题目
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
2：思路
这题实际上是考虑我们对问题思考的全面性，我们要想到，指数有正负或零，这样的话，分三种情况分别考虑就可以啦
3：代码
public class Solution {
public double Power(double base, int exponent) {
double result=1;
if(exponent>0)
{
for(int i=0;i<exponent;i++)
{
result=result*base;
}
return result;
}
else if(exponent<0)
{
exponent=-exponent;
for(int i=0;i<exponent;i++)
{
result=result*base;
}
result=1.0/result;
return result;
}
else
{
return 1;
}
}
}十三：调整数组顺序使奇数位于偶数前面
1：题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
2：思路
（结合冒泡思想，举例见下图，其中代码中交换二者没有开辟第三变量）
3：代码
public class Solution {
public void reOrderArray(int [] array) {
for(int i= 0;i<array.length-1;i++)
{
for(int j=0;j<array.length-1-i;j++)
{
if(array[j]%2==0&&array[j+1]%2==1)
{
array[j]=array[j]+array[j+1];
array[j+1]=array[j]-array[j+1];
array[j]=array[j]-array[j+1];
}
}
}
}
}十四：链表中倒数第k个结点
1：题目
输入一个链表，输出该链表中倒数第k个结点。
2：思路
如果我没记错的话，这题是408统考的第一年的算法设计题，最好的办法是双指针法，先让前面的指针先走k步，然后再让两个指针一起走，当前面的指针走到末尾，那么前面的指针就指向倒数第k个结点了。此方法一次遍历即可。
因为用Java，所以就用普通的思路，走两遍，先获取链表长度，然后让指针走长度减k步即可。（当然要考虑全面，譬如k不合法，或其为空链表都要单独处理）
3：代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null)
{
return head;
}
else
{
ListNode node1=head;
int count=0;
while(node1!=null)
{
count++;
node1=node1.next;
}
if(count<k)
{
return null;
}
ListNode node2=head;
for(int i=0;i<count-k;i++)
{
node2=node2.next;
}
return node2;
}
}
}十五：反转链表
1：题目
输入一个链表，反转链表后，输出新链表的表头。
2：思路
（注意指向，保存，后移的区别）
3：代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null)
{
return null;
}
ListNode pre=null;
ListNode next=null;
while(head!=null)
{
next=head.next;//保存下一结点
head.next=pre;//指向前面的结点
pre=head;//后移
head=next;//后移
}
return pre;
}
}十六：合并两个排序的链表
1：题目
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
2：思路
采用递归的思想
不画图了；
譬如 1 3 6 9和2 4 5 8
首先比较第一个值，1比2小，所以合成的链表第一个肯定是1，接下来的链表就是递归调用来合并 3 6 9 和2 4 5 8.注意到如果其中一个链表为空了，只需返回另一条链表即可，譬如1 2 3 4 5和空链合并，结果就是1 2 3 4 5
3：代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null)
{
return list2;
}
if(list2==null)
{
return list1;
}
if(list1.val<=list2.val)
{
list1.next=Merge(list1.next,list2);
return list1;
}
else
{
list2.next=Merge(list1,list2.next);
return list2;
}
}
}十七：树的子结构
1：题目
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
2：思路
递归
核心思想是如果A树的根不等于B树的根，就递归判断A的左子树或右子树是否等于B的根值。因为是子结构，仅仅是根相同还是不行的，再写另外一个函数，左右子树是否相等，同样，这个函数也是递归的。
3：代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null||root2==null)
{
return false;
}
return IsSubtree(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
public boolean IsSubtree(TreeNode roota,TreeNode rootb)
{
if(roota==null&&rootb!=null)//注意必须并上 rootb不为空 否则错误
{
return false;
}
if(rootb==null)
{
return true;
}
if(roota.val==rootb.val)
{
return IsSubtree(roota.left,rootb.left)&&IsSubtree(roota.right,rootb.right);
}
else
{
return false;
}
}
}十八：二叉树的镜像
1：题目
操作给定的二叉树，将其变换为源二叉树的镜像。
2：思路
递归
首先判断特殊情况，空根和无子树的情况；
再者，直接交换左右子树，然后再把交换后的两个子树递归交换即可；两个子树，递归两次哦。
3：代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root==null)
{
return;
}
if(root.left==null&&root.right==null)
{
return ;
}
else
{
TreeNode p=root.left;
root.left=root.right;
root.right=p;
}
if(root.left!=null)
{
Mirror(root.left);
}
if(root.right!=null)
{
Mirror(root.right);
}
}
}十九：顺时针打印矩阵
1：题目
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
2：思路
关键是处理下标，提交几次失败了，暂且挖坑吧。。。我太菜了
3：代码
二十：包含min 的栈
1：题目
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法
2：思路
我们直接在系统栈的基础上添加一个寻找最小值的函数即可，注意跟第一篇博客中c++那个容器的“指针”一样，Java中也有类似的用法，关键代码Iterator<integer> p = stk.iterator();同时不要忘记导入
import java.util.Iterator;
3：代码</integer>
import java.util.Stack;
import java.util.Iterator;
public class Solution {
Stack<Integer> stk=new Stack<Integer>();
public void push(int node)
{
stk.push(node);
}
public void pop()
{
stk.pop();
}
public int top()
{
return stk.peek();
}
public int min()
{
int min=stk.peek();
int temp=0;
Iterator<Integer> p = stk.iterator();
while(p.hasNext())
{
temp=p.next();
if(temp<min)
{
min=temp;
}
}
return min;
}
}
以上，就是剑指offer中的十一到二十题（第十九题没成功，待更新），实际上是没有完成上次的任务，下次不能再偷懒了。先去交开题报告，朋友们，三天后再见！
京公网安备 11010502036488号