9.19~9.20刷题总结

小灰灰 2021-09-10 07:58 259阅读 0赞

使二叉树变为其镜像  
类似先序遍历的方法

public void mirror(TreeNode node){
            if(node==null)
                return;
            if(node.left==null&&node.right==null)
                return;
            TreeNode n=node.left;
            node.left=node.right;
            node.right=n;
            mirror(node.left);
            mirror(node.right);
        }

判断二叉树是否对称  
左节点的右子树和右节点的左子树相同 使用递归

boolean isSymmetrical(TreeNode pRoot){
            if(pRoot==null)
                return true;
            return comRoot(pRoot.left,pRoot.right);
        }
        
        boolean comRoot(TreeNode left,TreeNode right){
            if(left==null)
                return right==null;
            if(right==null)
                return false;
            if(left.val!=right.val)
                return false;
            return comRoot(left.right, right.left)&&comRoot(left.left, right.right);
        }

实现有Min函数的栈

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

给出入栈顺序，判断出栈顺序是否正确

public boolean IsPopOrder(int [] pushA,int [] popA) {
            if(pushA.length==0||popA.length==0)
                return false;
            Stack<Integer> s=new Stack<>();
            int popIndex=0;
            for(int i=0;i<pushA.length;i++){
                s.push(pushA[i]);
                while(!s.empty()&&s.peek()==popA[popIndex]){
                    s.pop();
                    popIndex++;
                }
            }
            return s.empty();
            
        }

判断是否是二叉搜索树的后序遍历序列

public boolean judge(int[] a,int start,int end){
            if(start>=end)
                return true;
            int i=start;
            while(i<end&&a[i]<a[end]){
                i++;
            }
            for(int j=i;j<end;j++){
                if(a[j]<a[end])
                    return false;
            }
            return judge(a,start,i-1)&&judge(a,i,end-1);
        }

寻找二叉树从根到叶子值为x的路径

//方法一 使用栈
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
           ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
           if(root==null)
               return all;
           Stack<Integer> stack=new Stack<Integer>();
           FindPath(root, target,stack,all);
           return all;
        }
        
    
        
        void FindPath(TreeNode root,int target,Stack<Integer> stack, ArrayList<ArrayList<Integer>> all){
            if(root==null)
                return;
            if(root.left==null&&root.right==null){
                if(root.val==target){
                    ArrayList<Integer> list=new ArrayList<>();
                    for(int i:stack){
                        list.add(new Integer(i));
                    }
                    list.add(new Integer(root.val));
                    all.add(list);
                }
            }else{
                stack.push(new Integer(root.val));
                FindPath(root.left,target-root.val,stack,all);
                FindPath(root.right, target-root.val, stack, all);
                stack.pop();
            }
        }

//方法二
      public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
                if(root==null)
                    return listAll;
                list.add(root.val);
                target-=root.val;
                if(target==0&&root.left==null&&root.right==null)
                    listAll.add(new ArrayList<Integer>(list));
                FindPath(root.left,target);
                FindPath(root.right, target);
                list.remove(list.size()-1);
                return listAll;
            }

求字符串全排列结果 按字典顺序返回  
划分为子问题 第一个数和后面每个数交换 第二个数和后面每个数交换 ...

public ArrayList<String>  Permutation(String str) {
            char []c=str.toCharArray();
            ArrayList<String> list=new ArrayList<>();
            if(str!=null&&str.length()>0){
                permutation(c,0,list);
                Collections.sort(list);
            }
            for(String i:list)
                System.out.println(i);
            return list;
        }
        
        void permutation(char[] c,int start,ArrayList<String> list){
            if(start==c.length-1){
                //System.out.println(Arrays.toString(c));
                String s=String.valueOf(c);
                if(!list.contains(s))
                    list.add(s);
            }
            for(int i=start;i<c.length;i++){
                char temp=c[start];
                c[start]=c[i];
                c[i]=temp;
                permutation(c,start+1,list);
                temp=c[start];
                c[start]=c[i];
                c[i]=temp;
            }
        }

克隆复杂链表 该链表两个指针 一个指向下一个 一个随机指向  
思路：  
第一步：根据原始链表每个节点N创建对应的N'，把N'链接到N后面  
第二步：根据原始链表每个节点N的random指针，设置新节点的random指针，为原指针的下一位  
第三步：将第二步得到的链表拆分，奇数位置是原始链表，偶数位置是复制出来的链表 实现过程的一些细节要注意

//根据原始链表每个节点N创建对应的N'，把N'链接到N后面
        void clonenodes(RandomListNode phead){
            RandomListNode pnode=phead;
            while(pnode!=null){
                RandomListNode pcloned=new RandomListNode(-1);
                pcloned.label=pnode.label;
                pcloned.next=pnode.next;
                pcloned.random=null;
                pnode.next=pcloned;
                pnode=pcloned.next;
            }
        }
    //根据原始链表每个节点N的random指针，设置新节点的random指针，为原指针的下一位  
        void connectrandom(RandomListNode phead){
            RandomListNode pnode=phead;
            while(pnode!=null){
                RandomListNode pcloned=pnode.next;
                if(pnode.random!=null){
                    pcloned.random=pnode.random.next;
                }
                pnode=pcloned.next;
            }
        }
        
        RandomListNode reconnect(RandomListNode phead){
            RandomListNode pnode=phead;
            RandomListNode pclonedHead=null;
            RandomListNode pclonedNode=null;
            if(pnode!=null){
                pclonedHead=pclonedNode=pnode.next;
                pnode.next=pclonedNode.next;
                pnode=pnode.next;
            }
            
            while(pnode!=null){
                pclonedNode.next=pnode.next;
                pclonedNode=pclonedNode.next;
                pnode.next=pclonedNode.next;
                pnode=pnode.next;
            }
            return pclonedHead;
        }
        
        RandomListNode clone(RandomListNode node){
            clonenodes(node);
            connectrandom(node);
            return reconnect(node);
        }
    
    class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;
    
        RandomListNode(int label) {
            this.label = label;
        }
    }

//O（1）时间删除链表非尾节点的节点  
将下一个节点的值复制给该节点，删除下一个节点，调整链接。

void delete(ListNode p,ListNode del){
            if(p==null||del==null)
                return;
            if(del.next!=null){
                del.val=del.next.val;
                del.next=del.next.next;
            }else if(p==del){
                p=null;
            }else{
                ListNode pnode=p;
                while(pnode.next!=del)
                    pnode=pnode.next;
                pnode.next=null;
            }
        }

顺时针打印矩阵  
俺圈数遍历，注意圈数的结束条件 x>2start&&y>2start  
注意每次上下左右遍历执行的前提条件

public class test3 {
    /*
     * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，
     * 如果输入如下矩阵： 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.
     */
        
        void printMartrixMethod(int [][]matrix){
            if(matrix==null||matrix.length==0||matrix[0].length==0)
                return;
            int start=0;
            while((matrix[0].length>start*2)&&(matrix.length>start*2)){
                printMatrix(matrix,start);
                ++start;
            }
        }
        
        public void printMatrix(int [][] matrix,int start) {
            int endx=matrix[0].length-1-start;//中止列号
            int endy=matrix.length-1-start;//中止行号
            for(int i=start;i<=endx;i++){
                int number=matrix[start][i];
                System.out.print(number+" ");
            }
            if(start<endy){//执行第二步的前提条件 中止行号大于起始行号start
                for(int i=start+1;i<=endy;i++){
                    int number=matrix[i][endx];
                    System.out.print(number+" ");
                }
            }
            if(start<endx&start<endy){//执行第三部前提 中止行号大于起始行号 中止列号大于起始列号
                for(int i=endx-1;i>=start;i--){
                    int number=matrix[endy][i];
                    System.out.print(number+" ");
                }
            }
            if(start<endx&&start<endy-1){ //执行第四步 至少三行两列 要求中止行号比起始至少大2
                for(int i=endy-1;i>=start+1;i--){
                    int number=matrix[i][start];
                    System.out.print(number+" ");
                }
            }
        }
        
        public static void main(String[] args) {
            int a[][]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
            new test3().printMartrixMethod(a);
        }
    }