本文按照牛客网的顺序，牛客网剑指offer刷题网址：https://www.nowcoder.com/ta/coding-interviews
本篇涉及的题目有：
1、两个链表的第一个公共节点
2、数字在排序数组中出现的次数
3、二叉树的深度
4、平衡二叉树
5、数组中只出现一次的数字
6、和为s的连续正数序列
1、两个链表的第一个公共节点
问题描述
输入两个链表，找出它们的第一个公共结点。
思路解析
两个指针，一个先遍历链表1，再遍历链表2 一个先遍历链表2再遍历链表1
代码实现
java
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null)
return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (p1 != p2){
p1 = p1.next;
p2 = p2.next;
if(p1==null && p2==null)
break;
if (p1== null)
p1 = pHead2;
if (p2 == null)
p2 = pHead1;
}
return p1;
}
}
python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
# 两个指针，一个先遍历链表1，再遍历链表2 一个先遍历链表2再遍历链表1
if not pHead1 or not pHead2:
return None
p1 = pHead1
p2 = pHead2
while p1!=p2:
p1 = p1.next
p2 = p2.next
if not p1 and not p2:
return None
if not p1:
p1 = pHead2
if not p2:
p2 = pHead1
return p1
2、数字在排序数组中出现的次数
问题描述
统计一个数字在排序数组中出现的次数。
思路解析
使用两次二分查找，分别找到最后一次出现的位置和第一次出现的位置。
代码实现
java
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length==0)
return 0;
if(k<array[0] || k>array[array.length-1])
return 0;
int first = getFirst(array,k);
int last = getLast(array,k);
if(first==-1 || last==-1){
return 0;
}
return last - first + 1;
}
private static int getFirst(int[] array,int k){
int left = 0;
int right = array.length - 1;
int mid;
while(left <= right){
mid = (right - left) / 2 + left;
if(array[mid] == k){
if(mid==0 || array[mid]!=array[mid-1])
return mid;
else
right -= 1;
}
else if(array[mid] > k)
right -= 1;
else
left += 1;
}
return -1;
}
private static int getLast(int[] array,int k){
int left = 0;
int right = array.length - 1;
int mid;
while(left <= right){
mid = (right - left) / 2 + left;
if(array[mid] == k){
if(mid==array.length-1 || array[mid]!=array[mid+1])
return mid;
else
left += 1;
}
else if(array[mid] > k)
right -= 1;
else
left += 1;
}
return -1;
}
}
python
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if not data or k>data[-1] or k<data[0]:
return 0
first = self.getFirstK(data,k)
last = self.getLastK(data,k)
if first>-1 and last>-1:
return last-first + 1
return 0
def getFirstK(self,data,k):
left = 0
right = len(data) - 1
while left <= right:
mid = (right - left) // 2 + left
if data[mid] == k:
if mid==0 or data[mid-1] != data[mid]:
return mid
else:
right = mid - 1
elif data[mid] > k:
right = mid - 1
else:
left = mid + 1
return -1
def getLastK(self,data,k):
left = 0
right = len(data) - 1
while left <= right:
mid = (right - left) // 2 + left
if data[mid] == k:
if mid==len(data)-1 or data[mid+1] != data[mid]:
return mid
else:
left = mid + 1
elif data[mid] > k:
right = mid - 1
else:
left = mid + 1
return -1
3、二叉树的深度
问题描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路解析
使用递归的思路实现。
代码实现
java
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public static int TreeDepth(TreeNode root) {
if(root == null)
return 0;
int leftDepth = TreeDepth(root.left);
int rightDepth = TreeDepth(root.right);
return Math.max(leftDepth,rightDepth) + 1;
}
}
python
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
leftDepth = self.TreeDepth(pRoot.left)
rightDepth = self.TreeDepth(pRoot.right)
return max(leftDepth,rightDepth) + 1
4、平衡二叉树
问题描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路解析
使用递归的思路求解二叉树的深度。定义一个新函数，用来求解二叉树的深度，如果左右子树的深度之差超过1，那么返回-1，代表不是平衡二叉树，否则，返回子树的深度。
代码实现
java
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
int flag = isBalance(root);
if(flag == -1)
return false;
return true;
}
private static int isBalance(TreeNode root){
if(root == null)
return 0;
int left = isBalance(root.left);
int right = isBalance(root.right);
if(left == -1 || right == -1 || Math.abs(left - right) > 1)
return -1;
return Math.max(left,right) + 1;
}
}
python
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
depth,isBalance = self.isBalanced(pRoot,0)
return isBalance
def isBalanced(self,pRoot,depth):
if not pRoot:
return 0,True
dleft,isleft = self.isBalanced(pRoot.left,0)
dright,isright = self.isBalanced(pRoot.right,0)
if isleft and isright:
diff = dleft - dright
if abs(diff) <= 1:
return 1 + max(dleft,dright),True
return -1,False
5、数组中只出现一次的数字
问题描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路解析
这道题比较难想，不过我们可以从简单的入手，如果数组中只有一个数字出现了一次，我们会怎么办，对的，就是对数组所有数求一次异或，然后根据两个相同的数的异或是0这么一个条件
那么如果数组中有两个数出现了一次，其他出现了两次，那么我们可以根据一定的规则，将这数组分成两个子数组，这两个数字分别出现在这两个子数组中，那么就转换成了前面所说的求异或的问题。那么怎么分呢，这里的思路是根据要求的这两个数的异或之后最右边不为1的这一位进行划分的。
代码实现
java
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int xor = 0;
for(int x:array)
xor ^= x;
int splitBit = 1;
while((xor & splitBit)==0)
splitBit = splitBit << 1;
int xor1 = 0;
int xor2 = 0;
for(int x:array){
if((x & splitBit) != 0)
xor1 ^= x;
else
xor2 ^= x;
}
num1[0] = xor1;
num2[0] = xor2;
}
}
python
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
res = 0
for i in array:
res ^= i
splitBit = 1
while splitBit & res == 0:
splitBit = splitBit << 1
res1 = 0
res2 = 0
for i in array:
if i & splitBit == 0:
res1 ^= i
else:
res2 ^= i
return [res1,res2]
6、和为s的连续正数序列
问题描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
思路解析
维护两个指针，一个指针指向这个连续正数序列的开始，一个指向连续正数序列的结束，判断当前的序列和与目标的关系，不断更新这两个指针的位置。
另一个思路，判断每一个起始位置，然后往后遍历，如果和大于目标的话，就进行下一次循环，如果等于目标，将arraylist添加到返回结果。
我们用python实现第一个思路，用java实现第二个思路。
代码实现
java
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> aList=new ArrayList<ArrayList<Integer>>();
if(sum<2)
return aList;
for(int i=1;i<=sum/2;i++){
ArrayList<Integer> aList2=new ArrayList<Integer>();
int count=0;
for(int j=i;j<sum;j++){
count+=j;
aList2.add(j);
if(count>sum)
break;
else if(count==sum){
aList.add(aList2);
break;
}
}
}
return aList;
}
}
python
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
res = []
small = 1
big = 2
cursum = small + big
while small <= tsum/2:
if cursum == tsum:
res.append(range(small,big+1))
big = big + 1
cursum += big
elif cursum > tsum:
cursum -= small
small += 1
else:
big += 1
cursum += big
return res
