剑指offer（25-30）题解
剑指offer（25-30）题解
剑指offer（25-30）题解
- 25题解--复杂链表的复制
- 26题解--二叉搜索树与双向链表
- 27题解--字符串的排列
- 28题解--数组中出现次数超过一半的数字
- 29题解--最小的K个数
- 30题解--连续子数组的最大和
25题解–复杂链表的复制
题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路解析
这里首先图解让大家明白题目的主要意思： 实线表示next指针，虚线表示random指针
所以重点就是创建新的结点，并不是直接用已经存在的结点。
源代码
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null) return null;
RandomListNode node=pHead;
while(node!=null){
RandomListNode copy = new RandomListNode(node.label);
copy.next=node.next;
node.next=copy;
node=copy.next;
}
node=pHead;
while(node!=null){
if(node.random!=null){
node.next.random=node.random.next;
}
node=node.next.next;
}
node=pHead;
RandomListNode root=pHead.next;
RandomListNode tmp=root;
while(node!=null){
node.next=tmp.next;
tmp.next=node.next==null?null:node.next.next;
node=node.next;
tmp=tmp.next;
}
return root;
}
}26题解–二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路解析
既然是二叉搜索树，并且构成一个排序的双向链表这不是很符合二叉搜索树的中序序列是有序的这一性质嘛，所以这里，通过中序遍历将所有的节点存入list之中，之后我们通过list来对链表内元素的左右结点进行重构，如下图所示：
源代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.ArrayList;
public class Solution {
ArrayList<TreeNode>list=new ArrayList<TreeNode>();
public void Print(TreeNode pRoot)
{
if(pRoot.left!=null)
Print(pRoot.left);
list.add(pRoot);
if(pRoot.right!=null)
Print(pRoot.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)
return null;
Print(pRootOfTree);
for(int i=0;i<list.size()-1;i++)
{
list.get(i).right=list.get(i+1);
list.get(i+1).left=list.get(i);
}
return list.get(0);
}
}27题解–字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路解析
这里主要运用的就是全排列的知识，但是又因为这里可能会出现重复的元素，所以最后我们存储这个元素之前 我们需要判断是不是已经有过该元素。全排列演示如下图：
主要思想就是：每次先固定一个元素，之后将其后面的元素进行交换。
源代码
import java.util.*;
public class Solution {
public ArrayList Permutation ( String str) {
ArrayList res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
helper(res, 0, str.toCharArray());
// 符合结果的输出顺序
Collections.sort(res);
return res;
}
private void helper(ArrayList res, int index, char[] s) {
//全排列终止条件
if (index == s.length - 1)
{
//判断是否已经包含该元素
if(!res.contains(String.valueOf(s)))
res.add(String.valueOf(s));
return;
}
//全排列
for (int i = index; i < s.length; i++) {
if (i == index || s[index] != s[i]) {
swap(s, index, i);
helper(res, index + 1, s);
swap(s, index, i);
}
}
}
//交换字符函数
public void swap(char[] c, int a,int b) {
char temp = c[a];
c[a] = c[b];
c[b] = temp;
}
}28题解–数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路解析
这里我是将这个数组先进行排序操作，之后分别计数每个元素以及该元素出现的其实位置，并且存入list之中，之后就循环对list中的元素进行判断即可。
源代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public class node
{
int num;
int start;
}
public int MoreThanHalfNum_Solution(int [] array) {
int i=0;
int len=1+array.length/2;
int sum=0;
Arrays.sort(array);
List<Integer>list1=new ArrayList<Integer>();
List<node>list2=new ArrayList<node>();
for(int j=0;j<array.length;j++)
{
if(!list1.contains(array[j]))
{
list1.add(array[j]);
node node=new node();
node.num=array[j];
node.start=j;
list2.add(node);
}
}
for(int j=0;j<list2.size();j++)
{
if(list2.size()==1)
{
return list2.get(j).num;
}
if(j<list2.size()-1)
{
sum=list2.get(j+1).start-list2.get(j).start;
if(sum>=len)
{
i=list2.get(j).num;
break;
}
}
else
{
sum=array.length-list2.get(j).start-1;
if(sum>=len)
{
i=list2.get(j).num;
break;
}
}
}
return i;
}
}29题解–最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
思路解析
这里只需要对数组进行重新排序，之后运用一点数学知识即可解决问题。
源代码
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
Arrays.sort(input);
ArrayList<Integer>list=new ArrayList<Integer>();
if(k>input.length)
return list;
else
{
for(int i=0;i<k;i++)
list.add(input[i]);
return list;
}
}
}30题解–连续子数组的最大和
题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
思路解析
这题是一条很基础的动态规划的问题，就是在遍历的过程边比较边存储。还是通过下面的图来演示：
源代码
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int max=array[0];
int []dp=new int [array.length];
dp[0]=array[0];
for(int i=1;i<array.length;i++)
{
int newmax=dp[i-1]+array[i];
if(newmax>array[i])
dp[i]=newmax;
else
dp[i]=array[i];
if(dp[i]>max)
max=dp[i];
}
return max;
}
}