首页
登录 | 注册

牛客网刷题记录(代码用的是java)

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。


前序遍历:C D A F E M H Z
中序遍历:A D E F G H M Z

sP,eP表示pre[]区间的开始和结束(前序遍历)
sI,eI表示in[]区间的开始和结束(中序遍历)

首先,更加前序遍历找root节点即C.
在根据中序遍历找结点C,那么C左边的结点就是他的左边的子树[A,D,E,F],右边的
子的子树[H,M,Z].
根据中序---pre对应的左子树区间就是[D,A,E,F],右子树区间就是[M,H,Z]
然后再继续上面的步骤继续。
public class _11 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode treeNode=dfs(
                pre,0,pre.length-1,in,0,in.length-1);
        return treeNode;
    }

    public TreeNode dfs(int[] pre,int sP,int eP,int[] in,int sI,int eI){
        if(sP>eP||sI>eI){
            return null;
        }
        TreeNode root=new TreeNode(pre[sP]);
        for (int i = sI; i <= eI; i++) {
            if(in[i]==pre[sP]){
                root.left=dfs(pre,sP+1,sP+i-sI,in,sI,i-1);
                root.right=dfs(pre,i-sI+sP+1,eP,in,i+1,eI);
                break;
            }
        }
        return root;
    }
}

从尾到头打印链表

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
遍历反转

public class _10 {
    static class ListNode{
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode==null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> list=new ArrayList<Integer>();
        while (listNode!=null){
            list.add(listNode.val);
            listNode=listNode.next;
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        ListNode node=new ListNode(1);
        node.next=new ListNode(2);
        System.out.println(new _10().printListFromTailToHead(node));
    }
}

二维数组中的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
有序 二分 对每一行二分 O(arrlen*log(arrlen)) 没看清楚第一次以为是整个二维数组呈递增。

public class _9 {
    /*public boolean Find(int target, int [][] array) {
        int len = array.length;
        int l=0;
        int r=len*len-1;
        while (l<=r){
            int mid=l+(r-l)/2;
            int x=mid/len;
            int y=mid-x*len;
            if(array[x][y]>target){
                r=mid-1;
            }else if(array[x][y]<target){
                l=mid+1;
            }else{
                return true;
            }
        }
        return false;
    }*/

    public boolean Find(int target, int [][] array) {
        for (int i = 0; i < array.length; i++) {
            if(binary(array[i],target)){
                return true;
            }
        }
        return false;
    }

    public boolean binary(int[] arr,int target){
        int l=0;
        int r=arr.length-1;
        while (l<=r){
            int mid=l+(r-l)/2;
            if(arr[mid]>target){
                r=mid-1;
            }else if(arr[mid]<target){
                l=mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
}

把字符串转换成整数

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能,但是string不符合数字要求时返回0),要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
记得判断+或者-

public class _8 {
    public static int StrToInt(String str) {
        if(str.equals("")){
            return 0;
        }
        char[] chars=str.toCharArray();
        int st=0;
        if(chars[0]=='+'){
            st=1;
        }
        char ch=' ';
        if(chars[0]=='-'){
            st=1;
            ch=chars[0];
        }
        int res=0;
        for (int i = st; i < chars.length; i++) {
            if(chars[i]>='0'&&chars[i]<='9'){
                res=res*10+(int)(chars[i]-'0');
            }else{
                return 0;
            }
        }
        if(ch!=' '){
            res*=-1;
        }
        return res;
    }

    public static void main(String[] args) {
        String var="-123";
        System.out.println(StrToInt(var));
    }
}

矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
和走楼梯那题其实是差不多的。
就是在num[i-2]的前提下放2块(横着放),在num[i-2]的情况下再放一块(竖着放)。

public class Solution {
    public int RectCover(int target) {
        if(target<=0){
            return 0;
        }
        if(target==1||target==2){
            return target;
        }
        return RectCover(target-1)+RectCover(target-2);
    }
}

用两个栈实现队列

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
一个栈弹出n-1个数,再压入另外一个栈,第n个数即为pop()操作的数。

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        while (!stack1.empty()){
            stack2.push(stack1.pop());
        }
        int res=stack2.pop();
        while (!stack2.empty()){
            stack1.push(stack2.pop());
        }
        return res;
    }
}

变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
dp做法:
dp[i]=dp[i-1]+dp[i-2]+…..dp[i-n]
第i阶梯其实就是第i-1阶梯走1步,第i-2阶梯走2步….以此类推
O(n2)做法

public class Solution {
    public int JumpFloorII(int target) {
        if(target==1||target==2){
            return target;
        }
        int[] dp=new int[target+1];
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= target; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i]+=dp[i-j];
            }
        }
        return dp[target];
    }
}

替换空格

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        String replaceString="%20";
        StringBuilder result=new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char ch=str.charAt(i);
            if(str.charAt(i)==' '){
                result.append(replaceString);
            }else{
                result.append(ch);
            }
        }
        return result.toString();
    }
}

二叉树的镜像

题目描述
操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义:源二叉树

            8
           /  \
          6   10
         / \  / \
        5  7 9 11
        镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5



public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null){
            return;
        }
        TreeNode l=root.left;
        TreeNode r=root.right;
        root.left=r;
        root.right=l;
        if(root.left!=null){
            Mirror(root.left);
        }
        if(root.right!=null){
            Mirror(root.right);
        }
    }
}

栈的压入、弹出序列

  • 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。
    假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1
    是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    (注意:这两个序列的长度是相等的)
直接用一个Stack栈模拟一下就行,按PushA的顺序压入栈,并判断栈顶元素是否和popA的当前第j个值是否相同,
若相同,则栈顶元素出栈。重复上述。
如栈为空,则说明出栈顺序是正确的,反之不正确。
public static boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> st=new Stack<Integer>();
        for(int i=0,j=0;i<pushA.length;++i){
            st.push(pushA[i]);
            while (!st.empty()&&st.peek()==popA[j]){
                st.pop();
                ++j;
            }
        }
        return st.empty();
    }

从上往下打印二叉树

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

题解:BFS广度优先搜索

public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        if(root==null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> result=new ArrayList<Integer>();
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode current=queue.peek();
            result.add(current.val);
            queue.remove();
            if(current.left!=null){
                queue.add(current.left);
            }
            if(current.right!=null){
                queue.add(current.right);
            }
        }
        return result;
    }

字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
深搜即可

public class _3 {

    public ArrayList<String> result=new ArrayList<String>();
    public char[] g=new char[10];
    public boolean[] flag=new boolean[10];

    public ArrayList<String> Permutation(String str) {
        if(str.equals("")){
            return new ArrayList<String>();
        }
        char[] chars=str.toCharArray(); 
        dfs(0,chars);
        Set<String> set=new HashSet<String>(result); //去重
        ArrayList<String> strings=new ArrayList<String>(set);
        Collections.sort(strings); //排序
        return strings;
    }
    public void dfs(int y,char[] f){ //深搜
        if(y==f.length){
            StringBuilder sb=new StringBuilder();
            for (int i = 0; i < f.length; i++) {
                sb.append(g[i]);
            }
            result.add(sb.toString());
            return;
        }
        for (int i = 0; i < f.length; i++) {
            if(!flag[i]){ //找没用过的位置的字符
                g[y]=f[i]; //设为该位为某字符
                flag[i]=true; //已用
                dfs(y+1,f); //继续查找下一位
                flag[i]=false; //把已用的设置为未使用过的 继续深搜
            }
        }
    }
    public static void main(String[] args) {
        _3 main=new _3();
        main.Permutation("aac");
    }

机器人的运动范围

  • 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
  • 对每个点上下左右暴力搜索就行了,每走过一个可以进入点记录是否走过即可,并且探索步数+1.
public class _4 {
    public final static int[] xRow=new int[]{0,0,1,-1}; //上,下,左,右
    public final static int[] yRow=new int[]{1,-1,0,0};
    public static int n=0;
    public static int m=0;
    public static int k=0;
    public boolean[][] visited;

    public int movingCount(int threshold, int rows, int cols) {
        n=rows;
        m=cols;
        k=threshold;
        visited=new boolean[n+1][m+1]; //记录是否走过
        return dfs(0,0);
    }

    public int help(int x){ //分解
        int res=0;
        while (x>0){
            res+=x%10;
            x/=10;
        }
        return res;
    }

    public int dfs(int x,int y){
        int res=0;
        if(x<0||y<0||x>=n||y>=m||(help(x)+help(y))>k||visited[x][y]){ //不可达条件
            return 0;
        }else { //可达该点记录为走过并加一
            res+=1;
            visited[x][y]=true;
        }
        for (int i = 0; i < 4; i++) {
            res+=dfs(x+xRow[i],y+=yRow[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new _4().movingCount(15,20,20));
    }

}

矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
解法:找出矩阵中所有包含 匹配字符串开头的点(s[0])继续深搜,记得剪枝。

public class _5 {
    public static final int[] xRow={0,0,1,-1};
    public static final int[] yRow={1,-1,0,0};
    public static boolean[] visited;
    public static int n=0;
    public static int m=0;
    public static int length=0;
    public static boolean flag=false;

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        n=rows;
        m=cols;
        length=str.length;
        visited=new boolean[(rows+1)*(cols+1)];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(matrix[i*m+j]==str[0]){
                    dfs(i,j,0,matrix,str);
                    if(flag){
                        flag=false;
                        return true;
                    }
                    Arrays.fill(visited,false);
                }
            }
        }
        return false;
    }

    public void dfs(int x,int y,int pos,char[] matrix,char[] str){
        if(x<0||x>=n||y<0||y>=m||str[pos]!=matrix[x*m+y]||visited[x*m+y]){ //剪枝 判断越界或者访问过或者等于str[pos]的值 剪枝
            return;
        }
        if(pos==length-1){ //符合条件
            flag=true;
        }
        if(flag){ //小剪枝 
            return;
        }
        visited[x*m+y]=true; //符合条件 设置为访问过
        for (int i = 0; i < 4; i++) { //对下一个点进行四个方向搜索
            dfs(x+xRow[i],y+yRow[i], pos + 1,matrix, str);
        }
        visited[x*m+y]=false; //回溯
    }

    public static void main(String[] args) {
        String s1="AAAAAAAAAAAA";
        String s2="AAAAAAAAAAAA";
        char[] matrix=s1.toCharArray();
        char[] str=s2.toCharArray();
        System.out.println(new _5().hasPath(matrix,3,4,str));
    }

}


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.010 s.
京ICP备10005923号