剑指offerJava版(一)

综合技术 2018-12-08 阅读原文

数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

解法:递归or迭代

public class Solution {
    public double Power(double base,int e1) {
        int e = Math.abs(e1);
        if(e==0)
            return 1;
        if(e==1)
            return base;
        double result = Power(base, e>>1);
        result *= result;
        if(e%2==1)
            result *= base;
        if(e1<0)
            return 1.0/result;
        return result;
  }
}

调整数组顺序使得奇数位于偶数的前面

题目描述

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

解法一:使用两个指针,分别从数组两边开始行走,判断并交换

解法二:创建一个新的数组,遍历原数组,时间复杂度为O(n*2)

public class Solution {
    public void reOrderArray(int [] array) {
        int[] arr = new int[array.length];
        int k = 0;
        for(int i = 0 ; i<array.length;i++){
            if(array[i]%2==1)
                arr[k++] = array[i];
        }
        for(int i = 0 ; i<array.length;i++){
            if(array[i]%2==0)
                arr[k++] = array[i];
        }
        for(int j = 0 ; j<array.length;j++){
            array[j] = arr[j];
        }
    }
}

链表中倒数第K个节点

题目描述

输入一个链表,输出该链表中倒数第k个结点。

解法:类似于快慢指针的思想,假设链表长度为n,倒数第K个节点就是整数第n-k个节点,快指针走到第k个的时候,慢指针开始和快指针一起走,当快指针走到最后一个的时候,慢指针走到n-k的位置及倒数第k个节点,在此之前要判断链表的长度是否大于等于k;

/*
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|| k == 0){
            return null;
        }
        ListNode node = head;
        for(int i = 0 ; i< k ; i++){
            if(node!=null){
                node = node.next;
            }else{
                return null;
            }
        }
        while(node!=null){
            node = node.next;
            head = head.next;
        }
        return head;
    }
}

反转链表

题目描述

输入一个链表,反转链表后,输出新链表的表头。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pNode = head;
        ListNode preNode = null;
        ListNode newNode = null;
        while(pNode!=null){
            ListNode pnext = pNode.next;
            if(pNode.next==null)
                newNode = pNode;
            pNode.next = preNode;
            preNode = pNode;
            pNode = pnext;
        }
        return newNode;
    }
}

合并两个排序的链表

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

解法:使用递归的思想

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null && list2 == null){
            return null;
        }
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;
        ListNode list3 = null;
        if(list1.val<list2.val){
            list3 = list1;
            list3.next = Merge(list1.next,list2);
        }else{
            list3 = list2;
            list3.next = Merge(list1,list2.next);
        }
        return list3;
    }
}

树的子结构

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

解法:看到树的操作就往递归的思想靠拢

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public boolean DoesTree(TreeNode r1,TreeNode r2){
        if(r2 == null){
            return true;
        }
        if(r1 == null){
            return false;
        }
        if(r1.val != r2.val){
            return false;
        }
        return DoesTree(r1.left,r2.left)&&DoesTree(r1.right,r2.right);
    }
    
    public boolean HasSubtree(TreeNode r1,TreeNode r2) {
        boolean flag = false;
        if(r1 != null && r2 != null){
            if(r1.val == r2.val){
                flag = DoesTree(r1,r2);
            }
            if(flag == false){
                flag = HasSubtree(r1.left,r2);
            }
            if(flag == false){
                flag = HasSubtree(r1.right,r2);
            }
        }
        return flag;
    }
}

二叉树的镜像

题目描述

操作给定的二叉树,将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义:源二叉树

8

/

6 10

/ /

5 7 9 11

镜像二叉树

8

/

10 6

/ /

11 9 7 5

/**
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;
        }
        if(root.left == null && root.right == null)
            return;
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        
        if(root.left!=null){
            Mirror(root.left);
        }
        if(root.right!=null){
            Mirror(root.right);
        }
    }
}

顺时针打印矩阵

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下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> list = new ArrayList<>();
    public void Print(int[][] matrix,int columns,int rows,int start){
        int endX = columns - 1 -start;
        int endY = rows -1 -start;
        //从左到右打印一行
        for (int i = start ; i<= endX;i++ ){
            int num = matrix[start][i];
            list.add(num);
        }
        //从上到下打印一列
        if(start < endY){
            for (int j = start+1;j<=endY;j++){
                int num = matrix[j][endX];
                list.add(num);
            }
        }
        //从右到左打印一行
        if( start < endX && start < endY){
            for (int i = endX-1;i>=start;i--){
                int num = matrix[endY][i];
                list.add(num);
            }
        }

        //从下向上打印一行
        if(start<endX && start<endY-1){
            for (int j = endY-1;j>=start+1;j--){
                int num = matrix[j][start];
                list.add(num);
            }
        }
    }
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        int columns = matrix[0].length;//矩阵列数
        int rows = matrix.length;//矩行数
        if (matrix == null || columns <= 0 || rows <= 0)
            return null;
        int start = 0;
        while (start*2<columns && start*2<rows){
            Print(matrix,columns,rows,start);
            ++start;
        }
        return list;
    }
}

包含min函数的栈

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

import java.util.Stack;

public class Solution {

    public static Stack<Integer> stack1 = new Stack<>();
    public static Stack<Integer> stack2 = new Stack<>();

    public void push(int node) {
        if(stack2.isEmpty()){
            stack2.push(node);
        }
        if(node <= stack2.peek()){
            stack2.push(node);
        }else{
            stack2.push(stack2.peek());
        }
        stack1.push(node);
    }
    
    public void pop() {
        if(stack2.isEmpty()){
            throw new RuntimeException();
        }
        stack1.pop();
        stack2.pop();
    }
    public int top() {
        if(stack1.isEmpty()){
            throw new RuntimeException();
        }
        return stack1.peek();
    }
    public int min() {
        if(stack2.isEmpty()){
            throw new RuntimeException();
        }
        return stack2.peek();
    }
}

栈的压入,弹出序列

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

解法:直接创建一个辅助栈,模拟一遍压入弹出的过程,看最后栈是否为空,若是空,则匹配成功

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      if(pushA.length==0||popA.length==0){
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0 ;
        for (int i = 0 ; i < pushA.length ; i++){
            stack.push(pushA[i]);
            while (!stack.empty()&&stack.peek() == popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

公众号写的比较全,更多请关注公众号:

qrcode_for_gh_bca5e6591047_258 (1).jpg

简书

责编内容by:简书阅读原文】。感谢您的支持!

您可能感兴趣的

数据结构——栈 目录 1、定义 2、实现 2.1 简单数组实现 2.1.1 代码实现 2.1.2 性能和局限性 2.2 动态数组实现 2.2.1 代码实现 2.2.2 性能 2.3 链表实现 2.3.1 代码实...
二叉树(前序,中序,后序,层序)遍历递归与循环的python实现... 二叉树的遍历是在面试使比较常见的项目了。对于二叉树的前中后层序遍历,每种遍历都可以递归和循环两种实现方法,且每种遍历的递归实现都比循环实现要简洁。下面做一个小结。 一、中序遍历 前中后序三种遍历方法对于左右结点的遍历顺序都...
Convert Sorted Array to Binary Search Tree 二叉查找树(BST)是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。具体的说,就是使用每个节点含有两个链接(链表中每个节点只含有一个链接)的二叉查找树来高效地实现符号表。我们定义的数据结构由 结点 组成,结点...
数据结构与算法(3)——树(二叉、二叉搜索树)... 前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列...
Make a copy of a binary tree iteratively&comma... i was asked this question in an interview, and it literally cost me a job :P the interviewer asked, that you will be giv...