本文按照牛客网的顺序，牛客网剑指offer刷题网址：https://www.nowcoder.com/ta/coding-interviews
本篇涉及的题目有：
1、二进制中1的个数
2、链表中的倒数第K个节点
3、反转链表
4、合并两个排序的链表
5、树的子结构
6、二叉树的镜像
1、二进制中1的个数
问题描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路解析
考虑二进制1100，减1之后变为1011 1100&1011 为 1000，也就是说n和n-1的与运算，结果是将n的最后一位变成了0
代码实现
java
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while (n!=0)
{
++ count;
n = (n - 1) & n;
}
return count;
}
}
python
def NumberOf1( n):
# write code here
count = 0
while n:
n = (n - 1) & n
count = count + 1
return count
2、链表中的倒数第K个节点
问题描述
输入一个链表，输出该链表中倒数第k个结点。
思路解析
假设链表中的节点数大于等于k个，那么一定会存在倒数第k个节点，那么我们首先使用一个快指针往前走k步，然后使用一个慢指针随快指针一起每次往前走一步，两个指针之间始终有k的距离，当快指针走到末尾变为Null时，慢指针所在的位置就是倒数第k个节点。
代码实现
java
/*
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 null;
ListNode fast = head;
int t = 0;
while(fast != null && t < k){
t += 1;
fast = fast.next;
}
if (t < k)
return null;
ListNode slow = head;
while (fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
if not head or k<=0:
return None
p = head
t = 0
while p!=None and t<k:
p = p.next
t = t + 1
# 判断有没有k个节点
if t < k:
return None
q = head
while p!=None:
p = p.next
q = q.next
return q
3、反转链表
问题描述
输入一个链表，反转链表后，输出链表的所有元素。
思路解析
从根节点开始，利用头插法将链表进行反转
代码实现
java
/*
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 dummy = new ListNode(-1);
dummy.next = head;
ListNode p = head;
ListNode q = p;
while(p!=null){
q = p.next;
p.next = dummy.next;
dummy.next = p;
p = q;
}
head.next = null;
return dummy.next;
}
}
python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if not pHead:
return None
dummy = ListNode(-1)
dummy.next = pHead
p = pHead.next
while p!=None:
q = p
p = p.next
q.next = dummy.next
dummy.next = q
pHead.next = None
return dummy.next
4、合并两个排序的链表
问题描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路解析
利用两个指针分别指向两个链表。
代码实现
java
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode p1 = list1;
ListNode p2 = list2;
ListNode q = dummy;
while(p1 != null && p2 != null){
if (p1.val < p2.val){
q.next = p1;
p1 = p1.next;
}
else{
q.next = p2;
p2 = p2.next;
}
q = q.next;
}
while(p1!=null){
q.next = p1;
q = q.next;
p1 = p1.next;
}
while(p2!=null){
q.next = p2;
q = q.next;
p2 = p2.next;
}
return dummy.next;
}
}
python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
dummy = ListNode(-1)
q = dummy
p1 = pHead1
p2 = pHead2
while p1 and p2:
if p1.val <= p2.val:
q.next = p1
q = p1
p1 = p1.next
else:
q.next = p2
q = p2
p2 = p2.next
if p1:
q.next = p1
if p2:
q.next = p2
return dummy.next
5、树的子结构
问题描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路解析
采用递归的思路，单独定义一个函数判断B是不是从当前A的根节点开始的子树，这里判断是不是子树也需要一个递归的判断。如果是，则返回True，如果不是，再判断B是不是从当前A的根节点的左子节点或右子节点开始的子树。
代码实现
java
/**
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;
boolean result = false;
if (root1.val == root2.val)
result = isSubTree(root1,root2);
if(!result)
result = HasSubtree(root1.left,root2);
if(!result)
result = HasSubtree(root1.right,root2);
return result;
}
public boolean isSubTree(TreeNode root1,TreeNode root2){
if(root2==null)
return true;
if(root1==null)
return false;
if(root1.val != root2.val)
return false;
return isSubTree(root1.left,root2.left) && isSubTree(root1.right,root2.right);
}
}
python
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot2 or not pRoot1:
return False
result = False
if pRoot1.val == pRoot2.val:
result = self.isSubTree(pRoot1,pRoot2)
if not result:
result = self.HasSubtree(pRoot1.left,pRoot2)
if not result:
result = self.HasSubtree(pRoot1.right,pRoot2)
return result
def isSubTree(self,pRoot1,pRoot2):
if not pRoot2:
return True
if not pRoot1:
return False
if pRoot1.val != pRoot2.val:
return False
return self.isSubTree(pRoot1.left,pRoot2.left) and self.isSubTree(pRoot1.right,pRoot2.right)
6、二叉树的镜像
问题描述
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
思路解析
利用递归的思路,每次对换传入的根节点的左右子树即可。
代码实现
java
/**
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;
TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
Mirror(root.left);
Mirror(root.right);
}
}
python
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if not root:
return None
# 要保存下来，要不没用
p = root.left
root.left = self.Mirror(root.right)
root.right = self.Mirror(p)
return root
