剑指offer｜11-20题解题思路及代码(Java版)
2019-04-12 本文已影响0人
蓝白绛
剑指offer11到20题总览：
- 二进制中1的个数
- 数值的整数次方
- 调整数组顺序使奇数位于偶数前面
- 链表中倒数第k个结点
- 反转链表
- 合并两个排序的链表
- 树的子结构
- 二叉树的镜像
- 顺时针打印矩阵
- 包含min函数的栈
11、二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路
如果一个整数n(包括0、正数和负数)不等于0，则该整数一定有至少一位为1。如果将n减一，则最右边的1会变为0，原最右边的1的右边的所有0都会变成1。例如n=1100，n-1=1011。我们将n和n-1做与运算，的n&(n-1)=1000，得到的1000相当于去掉了1100中的最右边的1。如此重复，直到n变为0，就可以得到n中包含的1的个数。
注意事项
- 整数包括了负数。
- 循环条件是n!=0。
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0){//循环直到去掉n中所有的1为止
n = n & (n-1);//去掉n中最右边的1
count++;
}
return count;
}
}
12、数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解题思路
此题求幂，如果按照将base乘abs(exponent)次计算，则时间复杂度为，参考快速幂的方法，可以将求幂运算的时间复杂度降为
。例如求
，将11化成二进制为1011。则
注意事项
- 输入数据判断：底数base等于0时返回0，exponent为0时返回1，exponent为1时返回base。
- 当exponent为负时，先按照exponent为正计算，然后返回幂的倒数。
public class Solution {
public double Power(double base, int exponent) {
if(base == 0){return 0;}
if(exponent == 1){return base;}
double res = 1;//res为返回结果
double curr = base;//curr表示如果当前位为1，则res需要乘上的数
int n = Math.abs(exponent);//对指数求绝对值，先按正数计算
while(n!=0){//我们将将指数n的二进制数不断右移一位
if((n & 1) == 1){//如果n最右边的一位为1
res = res * curr;//则res乘上当前位为1需要乘上的curr
}
curr = curr * curr;//curr变为原来数的平方是每次n右移一位都要做的
n = n >> 1;
}
return exponent>0? res : 1/res;
}
}
13、调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路
一种是排序的方法，只要排序的算法是稳定的就行。再就是新建数组的方法。
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
ArrayList<Integer> odd = new ArrayList<>();//奇数
ArrayList<Integer> even = new ArrayList<>();//偶数
for(int i=0; i<array.length; i++){
if(array[i]%2 == 1){
odd.add(array[i]);
}else{
even.add(array[i]);
}
}
for(int i=0; i<odd.size(); i++){
array[i] = odd.get(i);
}
for(int i=0; i<even.size(); i++){
array[i+odd.size()] = even.get(i);
}
}
}
14、链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路
用两个指针，理想情况下，指针p先走k-1步，然后p和q一起走，直到指针p走到链表尾，提出q.val即可。
注意事项
- 检查输入：当输入链表为空时返回null；当k=0时返回null。
- 当链表长度小于k时，返回null。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null){return null;}//链表为空时返回null
if(k==0){return null;}//k等于0时返回null
ListNode p = head;
ListNode q = head;
int count = 0;//count记录p提前走的步数
while(count < k-1){
if(p.next!=null){//如果p可以往后走，则往后走
p = p.next;
count++;
}else{//如果p无法往后走，而此时count还没有达到k-1步，则链表长小于k，返回null
return null;
}
}
while(p.next != null){//p和q同时往后走
p = p.next;
q = q.next;
}
return q;
}
}
15、反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
解题思路
设置两个指针p和q，p一直指向原head，q指向p的next。我们将p的next指向的节点插入到新head的前面，并成为新head。如下图：
剑指offer15｜反转链表
注意事项
- 输入数据判断：链表为空则返回null；只有一个节点则不需要反转，直接返回head。
- 插入节点的时候，指针变化的前后顺序。
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null){return null;}
if(head.next == null){return head;}
ListNode p = head;
ListNode q;
while(p.next != null){//将q插到最前面，成为新head
q = p.next;
p.next = q.next;
q.next = head;
head = q;
}
return head;
}
}
16、合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
可以用非递归也可以用递归的方法。比较list1和list2的头结点的val，如果list1小则新链表接上list1的头结点，将list1剩下的部分和list2再递归进行Merge。
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){return list2;}
if(list2 == null){return list1;}
ListNode head = null;
if(list1.val <= list2.val){
head = list1;
head.next = Merge(list1.next, list2);//将list1剩下的部分和list2合并
}else{
head = list2;
head.next = Merge(list1, list2.next);//将list1和list2剩下的部分合并
}
return head;
}
}
17、树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路
本题是判断子结构而不是子树，也就是，当我们发现root1的某个结点与root2的根节点的val相同后，我们判断其是否是子结构时，如果root2中的结点在root1中都对应相同，但是root1后面还有一些多的结点，这种也属于子结构。也就是，root2中的叶子结点，在root1中不一定非要也是叶结点，还有一些子结点也是可以的。
基本的思路没有什么特殊的技巧，就是在root1中找到与root2根节点val相同的值，然后判断root2是否与root1中的一样。
public class Solution {
public boolean isSub(TreeNode root1,TreeNode root2){
//root1==null root2!=null ->false
//root1==null root2==null ->true
//root1!=null root2==null ->true，只需是子结构就可以
//root1!=null root2!=null ->判断val，如果val不相等则返回false，val相等则递归左右子树
if(root1 == null && root2 != null) return false;
if(root2 == null) return true;
if(root1.val != root2.val) return false;
return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
}
public boolean HasSubtree(TreeNode root1,TreeNode root2)
{
boolean result = false;
//root1==null root2==null ->false
//root1!=null root2==null ->false
//root1==null root2!=null ->false
//root1!=null root2!=null ->判断val是否相等，如果相等则调用isSub()，如果不相等则递归左右子树，root2不变
if(root1 != null && root2 != null){//只需要判断root!=null && root2!=null的情况
if(root1.val == root2.val){
result = isSub(root1,root2);//如果根结点val一样，则调用isSub
}
if(!result){
result = (HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2));
//如果根节点不一样，则对root1的左右子树进行递归
}
}
return result;
}
}
18、二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
解题思路
就是对树中每个结点的左右子树进行交换。
public class Solution {
public void Mirror(TreeNode root) {
if(root != null){
TreeNode temp = root.left;//交换左右子树
root.left = root.right;
root.right = temp;
Mirror(root.right);//将左子树进行镜像
Mirror(root.left);//将右子树进行镜像
}
}
}
19、顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
解题思路
没有什么特别的，就是需要计算清楚边界，比较麻烦。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if(matrix.length == 0){return list;}
if(matrix[0].length == 0){return list;}
int row_num = matrix.length;//原矩阵行数
int column_num = matrix[0].length;//原矩阵列数
int row_current = row_num;//内部圈行数，每次循环-2
int column_current = column_num;//内部圈列数，每次循环-2
while(row_current>1 && column_current>1){//如果内部圈行或列为1后面再考虑，这里考虑内圈行列大于1的情况
int margin = (row_num - row_current)/2;//计算内圈距离外圈的边界厚度
int i = margin;//循环从内圈的左上顶点开始
int j = margin;
for(; j<column_current+margin-1; j++){//向右
list.add(matrix[i][j]);
}
for(; i<row_current+margin-1; i++){//向下
list.add(matrix[i][j]);
}
for(; j>margin; j--){//向左
list.add(matrix[i][j]);
}
for(; i>margin; i--){//向上
list.add(matrix[i][j]);
}
row_current -= 2;//循环完之后行列-2
column_current -=2;
}
if(row_current == 1){//当内圈行数为1时，一次循环就行
int margin = (row_num-1)/2;
int column_len = column_num - 2*margin;
for(int i=0; i<column_len; i++){
list.add(matrix[margin][margin+i]);
}
column_current = 0;//因为我将行列分开判断，这里需要将剩余列数置为0
}
if(column_current == 1){//当内圈列数为1时
int margin = (column_num-1)/2;
int row_len = row_num - 2*margin;
for(int i=0; i<row_len; i++){
list.add(matrix[margin+i][margin]);
}
}
return list;
}
}
20、包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
解题思路
使用两个栈，一个数据栈data_stack，一个最小值栈min_stack。
当push数据时，如果数据栈为空，则将数据push到数据栈，同时将数据push到最小值栈；如果数据栈不为空，则将数据push到数据栈，将数据与最小值栈栈顶元素比较，如果比栈顶元素小，则将新数据push到最小值栈，如果比栈顶元素大，则将栈顶元素再push一遍到最小值栈。
当pop数据时，数据栈和最小值栈同时pop。
注意事项：
- 获取栈顶元素的方法是stack.peek();
public class Solution {
Stack<Integer> data_stack = new Stack<>();
Stack<Integer> min_stack = new Stack<>();
public void push(int node) {
if(data_stack.empty()){//如果栈为空，则将node分别push到数据栈和最小值栈
data_stack.push(node);
min_stack.push(node);
}else{//如果栈不为空，则要与最小值栈的栈顶元素进行比较，将较小者push到最小值栈中
data_stack.push(node);
if(node > min_stack.peek()){
min_stack.push(min_stack.peek());
}else{
min_stack.push(node);
}
}
}
public void pop() {//题目规定没有返回值
data_stack.pop();
min_stack.pop();
}
public int top() {//java中栈获取栈顶元素是stack.peek();
return data_stack.peek();
}
public int min() {//直接获取最小值栈的栈顶元素即可
return min_stack.peek();
}
}
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！
