一、二维数值中的查找:
1、题目:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
2、解题思路:
通过分析可以很简单的找出一个规律,二维数组的最左下角的的点,该点的所在列上边的点都是减少的,该点所在行右边的点都是增加的。因此,我们以该点作为切入点,如果目标数比左下角的数大,则往右边移动;如果目标数比左下角的数小,则往上边移动;之后以此类推,如果匹配到目标数,则返回true;如果当移动到最右上角的点仍然没有匹配到目标数,则返回false。
3、代码示例:
public boolean Find(int target, int[][] array) {
int rowCount = array.length;
int colCount = array[0].length;
int x, y;
for (y = rowCount - 1, x = 0; y >= 0 && x < colCount;) {
if (target == array[y][x]) {
return true;
} else if (target > array[y][x]) {
x++;
continue;
} else if (target < array[y][x]) {
y--;
continue;
}
}
return false;
}
二、从头到尾打印链表:
1、题目:
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
2、代码实现:
public class Solution{
//第二种方式:递归实现:
ArrayList<Integer> resultList = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
if(listNode!=null){
this.printListFromTailToHead2(listNode.next);
resultList.add(listNode.val);
}
return resultList;
}
//第一种方式,使用堆栈结构
public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
Stack<Integer> stack = new Stack<Integer>();
while(listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> resultList = new ArrayList<Integer>();
while(!stack.isEmpty()){
resultList.add(stack.pop());
}
return resultList;
}
}
三、重建二叉树:
1、题目:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
2、思路:
通过分析前序遍历和中序遍历的规律,前序遍历的第一个节点就是二叉树的根节点,中序遍历中,位于根节点前面的所有节点都位于左子树上,位于根节点后面的所有节点都位于右子树上面。通过这个规律,我们可以使用递归方法来重建二叉树。
3、代码实现:
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
}
public class Test1 {
public TreeNode reConstructBinaryTree(int[] pre,int[] in){
//前序的第一个数是根节点
TreeNode root = new TreeNode(pre[0]);
int len=pre.length;
if(len==1){
root.left=null;
root.right=null;
return root;
}
//找出中序中的根节点位置
int rootVal=root.val;
int i;
for(i=0;i<len;i++){
if(rootVal==in[i])
break;
}
//构建左子树
if(i>0){
int[] pr = new int[i];
int[] ino = new int[i];
for(int j=0;j<i;j++){
pr[j]=pre[j+1];
ino[j]=in[j];
}
root.left=reConstructBinaryTree(pr,ino);
}else{
root.left=null;
}
//构建右子树
if(len-i-1>0){
int[] pr =new int[len-i-1];
int[] ino = new int[len-i-1];
for(int j=i+1;j<len;j++){
pr[j-i-1]=pre[j];
ino[j-i-1]=in[j];
}
root.right=reConstructBinaryTree(pr,ino);
}else{
root.right=null;
}
return root;
}
}
4、第二种写法:
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
if(startPre>endPre||startIn>endIn)
return null;
TreeNode root=new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++)
if(in[i]==pre[startPre]){
root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
break;
}
return root;
}
}
四、旋转数组的最小数字:
1、题目:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
2、思路:
采用二分查询的方法,但是需要处理两种特殊情况:
即{1 0 1 1 1} 以及{1 1 1 0 1}这两种类型的排序。
3、代码实现:
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length==0){
return 0;
}
int leftIndex=0;
int rightIndex=array.length-1;
int midIndex=0;
while(array[leftIndex]>=array[rightIndex]){
//当左右两个指针相互接触,则说明已经找到最小值,即右边的指针的元素
if(rightIndex-leftIndex<=1){
midIndex=rightIndex;
break;
}
midIndex=(leftIndex+rightIndex)/2;
//这里是处理特殊情况,即当左中右三个指针的值都是一样的时候,我们不能判断最小元素位于哪个位置,只能通过遍历的方法找出最小元素
//特殊情况:{1 0 1 1 1} 以及{1 1 1 0 1}这两种类型的排序
if(array[rightIndex]==array[leftIndex] && array[leftIndex]==array[midIndex]){
return MinInOrder(array,leftIndex,rightIndex);
}
//如果中间元素大于末尾元素,那么表明最小元素在后半段数组中,修改leftIndex指针位置
if(array[midIndex]>=array[leftIndex]){
leftIndex=midIndex;
}else if(array[midIndex]<=array[rightIndex]){
//如果中间元素小于末尾元素,那么表明最小元素在前半段部分中,修改rightIndex指针位置
rightIndex=midIndex;
}
}
return array[midIndex];
}
public int MinInOrder(int[] array,int leftIndex,int rightIndex){
int result=array[leftIndex];
for(int i=leftIndex+1;i<rightIndex;i++){
if(result>array[i]){
result=array[i];
}
}
return result;
}
}
4、代码实现2:
public class Solution {
public int minNumberInRotateArray(int [] array) {
int low=0;int high = array.length-1;
while(low<high){
int mid = low + ((high - low) >> 2);
if(array[mid] > array[high]){
low = mid+1;
}else if(array[mid] == array[high]){
high--;
}else{
high =mid;
}
}
return array[low];
}
}
注意这里有个坑:如果待查询的范围最后只剩两个数,那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid – 1,就会产生错误, 因此high = mid
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114700.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...