剑指offer上的题目学习笔记整理和记录。
1.斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
编程
根据斐波那契数列的定义F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*），想到可以递归实现。
讨论
- 但递归实现的时间代价太高了，其时间复杂度为O(2^N)。
- 于是我们可以考虑用一定的空间复杂度换取时间复杂度，采用动态规划的方法，与递归的区别在于每次重复运算都只会进行一次，结果会保存起来，时间复杂度降低到O(N)。
- 当然还可以像参考教程中写的一样，将斐波那契数列的定义式进行简化，用矩阵的形式进行计算，可将时间复杂度降低到O(logN)。
参考
2.跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
编程
这个问题可以抽象成一个F(1)=1，F(2)=2, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）的斐波那契数列问题。
思路1——递归，时间复杂度较高
思路2——动态规划，用一定的空间复杂度换取时间复杂度
3.变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
编程
讨论
看题目提示说考察了贪心算法，但感觉自己是强行找规律，然后用了动态规划的方法。网上的大佬们也是找规律，但比我找的更精简一些，如下图。
参考
4.矩形覆盖
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
编程
讨论
最开始把矩形当成矩阵了，然后情况就很复杂，后来看了网上的解答思路，发现这还是可以抽象成一个F(1)=1，F(2)=2, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）的斐波那契数列问题，关键在于前期分析推断出具体规律。参考分析过程如下图所示——
思路一：逻辑分析
思路二：根据n=1，n=2，n=3，n=4的情况摸索规律
5.二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
编程
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!=0){
if((n & 1) == 1){ //逐位判断是否为1
count++;
}
n = n >>> 1; //无符号右移
}
return count;
}
}
讨论
涉及到位操作，需要熟悉java的移位运算符(左移位（<<）、右移（>>）、无符号右移（>>>）、无符号左移（<<<）)。本题的其他参考思路如下——
思路一：利用API
public class Solution {
public int NumberOf1(int n) {
return Integer.toBinaryString(n).replaceAll("0","").length(); }
}
思路二
6.数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
编程
public class Solution {
public double Power(double base, int exponent) {
double result = base;
int ep = Math.abs(exponent);
if(ep == 0){
return 1.0;
}
for(int i=1; i<ep; i++){
result = result*base;
}
if(exponent < 0){ //整数为负数的情况
result = 1.0/result;
}
return result;
}
}
讨论
本题的其他参考思路如下——
思路一：利用API
public class Solution {
public double Power(double base, int exponent) {
return Math.pow(base, exponent);
}
}
思路二：快速幂
思路三：递归
7.链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
编程
思路如下：两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指正走(k-1)步，到达第k个节点。然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了（时间复杂度O(n),一次遍历即可）。
讨论
本题的其他参考思路如下——
1、使用Stack，将结点压入栈中，再取出第k个就好;
2、将链表反转，然后取出第k个即可。
8.反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
编程
思路如下：利用java数据结构中的栈来实现。
import java.util.Stack;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode result;
Stack<ListNode> sc = new Stack<ListNode>();
if(head == null){
return null;
}
while(head.next!=null){
sc.push(head);
head = head.next;
}
result = head;
while(!sc.empty()){
head.next = sc.pop();
head = head.next;
}
head.next = null;
return result;
}
}
讨论
本题的其他参考思路如下——
从原链表的头部一个一个取节点并插入到新链表的头部;
9.树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
编程
思路：参考剑指offer
1.首先设置标志位result = false，因为一旦匹配成功result就设为true，剩下的代码不会执行，如果匹配不成功，默认返回false。
2.递归思想，如果根节点相同则递归调用DoesTree1HaveTree2（），如果根节点不相同，则判断tree1的左子树和tree2是否相同，再判断右子树和tree2是否相同。
3.注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断，DoesTree1HasTree2中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功，tree1为空有两种情况（1）如果tree1为空&&tree2不为空说明不匹配，（2）如果tree1为空，tree2为空，说明匹配。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
if(root1 != null && root2 != null){
if(root1.val == root2.val){
result = DoesTree1HaveTree2(root1,root2);
}
if(!result){result = HasSubtree(root1.left, root2);}
if(!result){result = HasSubtree(root1.right, root2);}
}
return result;
}
public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
if(root1 == null && root2 != null) return false;
if(root2 == null) return true;
if(root1.val != root2.val) return false;
return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
}
}
讨论
对于二叉树的遍历操作，一般都会首先考虑递归大的形式。