剑指offfer(56~67)

第五十六题:删除链外中重复的结点

题目描述:在一个排序的链外中,存在重复的结点,请删除该链外中重复的结点,重复的结点不保留,返回链外头指针。 例如,链外1->2->3->3->4->4->5 处理后为 1->2->5

public class Solution {    public ListNode deleteDuplication(ListNode pHead){        if(pHead==null||pHead.next==null){// 只有0个或1个结点,则返回            return pHead;        }        //现在是重复节点        if(pHead.val==pHead.next.val){            ListNode pNode=pHead.next;            // 跳过值与现在结点相通的通盘结点,找到第一个与现在结点差别的结点            while(pNode!=null&&pNode.val==pHead.val){                pNode=pNode.next;            }            return deleteDuplication(pNode);//从第一个与现在结点差别的结点最先递归        }else{// 现在结点不是重复结点            pHead.next=deleteDuplication(pHead.next);// 保留现在结点,从下一个结点最先递归            return pHead;        }    }}
第五十七题:二叉树的下一个结点

题目描述:给定一个二叉树和其中的一个结点,请找出中序遍历挨次的下一个结点并且返回。仔细,树中的结点不光包含旁边子结点,同时包含指向父结点的指针。

public class Solution {    public TreeLinkNode GetNext(TreeLinkNode pNode){        if(pNode==null){            return null;        }        //倘若该节点有右子树,不息沿着指向左子结点的指针找到的叶子节点即为下一个节点        if(pNode.right!=null){            pNode=pNode.right;            while(pNode.left!=null){                pNode=pNode.left;            }            return pNode;        }        //倘若该节点异国右子树,则找第一个现在节点是父节点左孩子的节点        while(pNode.next!=null){            if(pNode.next.left==pNode){                return pNode.next;            }            pNode=pNode.next;        }        return null;    }}
第五十八题:对称的二叉树

题目描述:请实现一个函数,用来判定一颗二叉树是不是对称的。仔细,倘若一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

public class Solution {    boolean isSymmetrical(TreeNode pRoot){        if(pRoot==null){            return true;        }        return f(pRoot.left,pRoot.right);    }    private boolean f(TreeNode t1,TreeNode t2){        if(t1==null&&t2==null){            return true;        }        if(t1!=null&&t2!=null){            return t1.val==t2.val&&f(t1.left,t2.right)&&f(t1.right,t2.left);        }        return false;    }}
第五十九题:按之字形挨次打印二叉树

题目描述:请实现一个函数依照之字形打印二叉树,即第一走依照从左到右的挨次打印,第二层依照从右至左的挨次打印,第三走依照从左到右的挨次打印,其他走以此类推。

import java.util.*;public class Solution {    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {        ArrayList<ArrayList<Integer>>result=new ArrayList<>();        if(pRoot==null){            return result;        }        Stack<TreeNode>stack1=new Stack<>();//安放奇数走数据        Stack<TreeNode>stack2=new Stack<>();//安放偶数走数据        stack1.push(pRoot);        ArrayList<Integer>temp=new ArrayList<>();//一时存储数据        int flag=1;        while(!stack1.isEmpty()||!stack2.isEmpty()){            //奇数走            if(flag%2!=0){                while(!stack1.isEmpty()){                    TreeNode node=stack1.pop();                    temp.add(node.val);                    if(node.left!=null){//先左后右                        stack2.push(node.left);                    }                    if(node.right!=null){                        stack2.push(node.right);                    }                }            }            //偶数走            if(flag%2==0){                while(!stack2.isEmpty()){                    TreeNode node=stack2.pop();                    temp.add(node.val);                    if(node.right!=null)//先右后左                        stack1.push(node.right);                    }                    if(node.left!=null){                        stack1.push(node.left);                    }                }            }            result.add(new ArrayList<Integer>(temp));            temp.clear();//一时存储清空刷新            flag++;        }        return result;    }}
第六十题:把二叉树打印成众走

题目描述:从上到下按层打印二叉树,联相符层结点从左至右输出。每一层输出一走。

import java.util.*;public class Solution {    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {        ArrayList<ArrayList<Integer>>ans=new ArrayList<>();        Queue<TreeNode>queue=new LinkedList<>();        queue.add(pRoot);        int sum=1;//记录二叉树每层节点的个数        while(!queue.isEmpty()&&pRoot!=null){            ArrayList<Integer>list=new ArrayList<>();            int temp=0;            while(sum>0){                TreeNode node=queue.poll();                list.add(node.val);                if(node.left!=null){                    queue.add(node.left);                    temp++;                }                if(node.right!=null){                    queue.add(node.right);                    temp++;                }                sum--;            }            sum=temp;            ans.add(list);        }        return ans;    }}
第六十一题:序列化二叉树

题目描述:请实现两个函数,别离用来序列化和逆序列化二叉树:

二叉树的序列化是指:把一棵二叉树依照某栽遍历手段的效果以某栽格式保存为字符串,从而使得内存中竖立首来的二叉树能够持久保存。序列化能够基于先序、中序、后序、层序的二叉树遍历手段来进走修改,序列化的效果是一个字符串,序列化时经过 某栽符号外示空节点(#),以 ! 外示一个结点值的终结(value!)。

二叉树的逆序列化是指:根据某栽遍历挨次得到的序列化字符串效果str,重构二叉树。

import java.util.*;public class Solution {    StringBuffer sb=new StringBuffer();    String Serialize(TreeNode root) {//依据前序遍历序列来序列化二叉树        if(root==null){            return sb.append("#!").toString();        }        sb.append(String.valueOf(root.val)+"!");        Serialize(root.left);        Serialize(root.right);        return sb.toString();    }    TreeNode Deserialize(String str) {        String[]strs=str.split("!");        Queue<String>queue=new LinkedList<>();        for(int i=0;i<strs.length;i++){            queue.add(strs[i]);        }        return buildTree(queue);    }    public TreeNode buildTree(Queue queue){        if(queue.isEmpty()){            return null;        }        String s=(String)queue.poll();        if(s.equals("#")){            return null;        }        TreeNode root=new TreeNode(Integer.valueOf(s));        root.left=buildTree(queue);        root.right=buildTree(queue);        return root;    }}
第六十二题:二叉搜索树的第k个结点

题目描述:给定一棵二叉搜索树,请找出其中的第k幼的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大幼挨次第三幼结点的值为4。

import java.util.*;public class Solution {    TreeNode KthNode(TreeNode pRoot, int k){        if(pRoot==null||k<=0){            return null;        }        ArrayList<TreeNode>list=new ArrayList<>();        list=KthNodeSub(pRoot,list);        if(k>list.size()){            return null;        }        return list.get(k-1);    }    //变前序为中序    ArrayList<TreeNode>KthNodeSub(TreeNode proot,ArrayList<TreeNode>list){        if(proot==null){            return null;        }        if(proot.left!=null){            KthNodeSub(proot.left,list);        }        list.add(proot);        if(proot.right!=null){            KthNodeSub(proot.right,list);        }        return list;    }}
第六十三题:数据流中的中位数

题目描述:如何得到一个数据流中的中位数?倘若从数据流中读出奇数个数值,那么中位数就是一切数值排序之后位于中间的数值。倘若从数据流中读出偶数个数值,那么中位数就是一切数值排序之后中间两个数的平均值。吾们行使Insert()手段读取数据流,行使GetMedian()手段获取现在读取数据的中位数。

import java.util.*;public class Solution {    ArrayList<Integer>list=new ArrayList<>();    public void Insert(Integer num){        list.add(num);    }    public Double GetMedian(){        Collections.sort(list);//排序链外        int len=list.size();        Double num=len%2!=0?(list.get(len/2)/1.0):        ((list.get(len/2-1)+list.get(len/2))/2.0);        return num;    }}
第六十四题:滑动窗口的最大值

题目描述:给定一个数组和滑动窗口的大幼,找出一切滑动窗口里数值的最大值。例如,倘若输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大幼3,那么统统存在6个滑动窗口,他们的最大值别离为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

import java.util.*;public class Solution {    //num外示数组,size外示滑动窗口的大幼    public ArrayList<Integer> maxInWindows(int [] num, int size){        ArrayList<Integer>list=new ArrayList<>();        if(size==0||num==null){            return list;        }        int start=0,end=size-1;        while(end<=num.length-1){            ArrayList<Integer>list1=new ArrayList<>();            for(int i=start;i<=end;i++ ){                list1.add(num[i]);            }            Collections.sort(list1);            list.add(list1.get(list1.size()-1));            start++;            end++;        }        return list;    }}
第六十五题:矩阵中的路径

题目描述:请设计一个函数,用来判定在一个矩阵中是否存在一条包含某字符串一切字符的路径。路径能够从矩阵中的肆意一个格子最先,每一步能够在矩阵中向左,向右,向上,向下移动一个格子。倘若一条路径经过了矩阵中的某一个格子,则该路径不克再进入该格子。 例如

棋牌炎点

矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,由于字符串的第一个字符b占有了矩阵中的第一走第二个格子之后,路径不克再次进入该格子。

public class Solution {    public boolean hasPath(char[] matrix, int rows, int cols, char[] str){        if(matrix.length==0||rows<=0||cols<=0||str.length==0){            return false;        }        //标志位,初首化为false        boolean[]flag=new boolean[matrix.length];        //循环遍历二维数组,找到首点等于str第一个元素的值,再递归判定四周是否有相符条件的----回溯法        for(int i=0;i<rows;i++){            for(int j=0;j<cols;j++){                if(judge(matrix,i,j,rows,cols,flag,str,0)){                    return true;                }            }        }        return false;    }    //judge(初首矩阵,索引走坐标i,索引纵坐标j,矩阵走数,矩阵列数,待判定的字符串,字符串索引初首为0即先判定字符串的第一位)    private boolean judge(char[] matrix, int i, int j, int rows, int cols, boolean[] flag, char[] str, int k) {        //先根据i和j计算匹配的第一个元素转为一维数组的位置        int index=i*cols+j;        //递归终止条件        if(i<0||j<0||i>=rows||j>=cols||matrix[index]!=str[k]||flag[index]==true){            return false;        }        if(k==str.length-1){            return true;        }         //要走的第一个位置置为true,外示已经走过了        flag[index]=true;         //回溯,递归追求,每次找到了就给k添一,找不到,还原        if(judge(matrix, i+1, j, rows, cols, flag, str, k+1)||                judge(matrix, i-1, j, rows, cols, flag, str, k+1)||                judge(matrix, i, j+1, rows, cols, flag, str, k+1)||                judge(matrix, i, j-1, rows, cols, flag, str, k+1)){            return true;        }        //走到这,表明这一条路不通,还原,再试其他的路径        flag[index]=false;        return false;    }}
第六十六题:机器人的活动范围

题目描述:地上有一个m走和n列的方格。一个机器人从坐标0,0的格子最先移动,每一次只能向左,右,上,下四个倾向移动一格,但是不克进入走坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),由于3+5+3+7 = 18。但是,它不克进入方格(35,38),由于3+5+3+8 = 19。请示该机器人能够达到众少个格子?

public class Solution {    public int movingCount(int threshold, int rows, int cols){        if(threshold<0||rows<=0||cols<=0){            return 0;        }        boolean[][]flag=new boolean[rows][cols];        return helper(threshold,rows,cols,0,0,flag);    }    private int helper(int threshold, int rows, int cols, int r, int c, boolean[][] flag) {        //递归终止条件        if(r<0||c<0||r>=rows||c>=cols||flag[r][c]==true||bitsum(r)+bitsum(c)>threshold){            return 0;        }        //表明上面的一步已经走过了        flag[r][c]=true;        //返回1 + 4 个倾向的追求值之和        return helper(threshold, rows, cols, r+1, c, flag)            +helper(threshold, rows, cols, r-1, c, flag)            +helper(threshold, rows, cols, r, c+1, flag)            +helper(threshold, rows, cols, r, c-1, flag)+1;    }//计算数位之和    private int bitsum(int x) {        int sum=0;        while(x>0){            sum+=x;            x/=10;        }        return sum;    }}
第六十七题:剪绳子

题目描述:给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...,k[m]。请示k[0]*k[1]*...*k[m]能够的最大乘积是众少?例如,当绳子的长度是8时,吾们把它剪成长度别离为2、3、3的三段,此时得到的最大乘积是18。

思路:行使贪婪算法,尽能够众的分割长度为3的段,再分割长度为2的段,能够数学表明得到长度段的积最大。

public class Solution {    public int cutRope(int target) {        if(target<2){            return 0;        }        if(target==2){            return 1;        }        if(target==3){            return 2;        }        int time3=target/3;        if(target-3*time3==1){            time3--;        }        int time2=(target-3*time3)/2;        return (int)(Math.pow(3,time3)*Math.pow(2,time2));    }}


Powered by AG8亚洲游戏国际平台 @2018 RSS地图 HTML地图

Copyright 365站群 © 2013-2021