代码随想录

代码随想录解题记录

JZ8 二叉树的下一个结点

//方法1：找到根节点去中序遍历，遍历结束之后放到一个list中，看一下list中寻找的指定节点的下一个节点
时间和空间复杂度都是O(n)
    

import java.util.*;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    ArrayList<TreeLinkNode> list = new ArrayList();


    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //找到根节点head
        TreeLinkNode result = null;
        TreeLinkNode head = pNode;
        while (head.next != null) {
            head = head.next;
        }
        Traversal(head);
        //进行中序遍历
        for(int i = 0 ; i < list.size(); i++){
            if(list.get(i) == pNode){
                if(i == list.size() - 1){
                    result = null;
                }else{
                    result = list.get(i+1);
                }
            }
        }

        return result;

    }

    public void Traversal (TreeLinkNode node) {

        if(node == null){
            return;
        }

        Traversal(node.left);
        list.add(node);
        Traversal(node.right);
    }

}

//方法二、分情况讨论


import java.util.*;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    TreeLinkNode head = null;
    TreeLinkNode headPre = null;
    public TreeLinkNode GetNext(TreeLinkNode pNode) {

        //分类讨论
        //(1)有右节点
        if(pNode.right != null){
            TreeLinkNode cur = pNode.right;
            while(cur.left != null){
                cur = cur.left;
            }
            return cur;
        }else{
            //(2)无右节点,且无父节点
            if(pNode.next == null){
                return null;
            }else{
                //(3)无右节点，有父节点,且是父节点的左节点
                if(pNode == pNode.next.left){
                    return pNode.next;
                }else{
                    //(3)无右节点，有父节点,且是父节点的右节点
                    TreeLinkNode ppar = pNode.next;
                    // 沿着左上一直爬树，爬到当前结点是其父节点的左自己结点为止
                    while(ppar.next != null && ppar.next.right == ppar) ppar = ppar.next;
                    return ppar.next;
                }
            }

        }     
    }
}

JZ59 滑动窗口的最大值

累了，直接记住吧，去看代码随想录的视频

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @param size int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        LinkedList<Integer> deque = new LinkedList();
        ArrayList<Integer> res = new ArrayList();
        //非法校验
        if(num.length == 0 || size <= 0 || num.length < size){
            return res;
        }
        //未能够形成窗口
        for(int i = 0 ; i < size ; i++){
            while(!deque.isEmpty() && deque.peekLast() < num[i]){
                deque.removeLast();
            }
            deque.add(num[i]);
        };
        res.add(deque.peek());
        //形成窗口后
        for(int i = size ; i <num.length ; i++){
            if(deque.peek() == num[i-size]){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && deque.peekLast() < num[i]){
                deque.removeLast();
            }
            deque.add(num[i]);
            res.add(deque.peek());
            
        }
        return res;
    }
}

ACM模式练习（卡码网kamaCoder）

20.删除重复元素

import java.util.*;

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()){
            int length = scanner.nextInt();
            if(length == 0){
                System.out.println("list is empty");
            }else{
                ArrayList<Integer> nums = new ArrayList();
                while(length > 0){
                    nums.add(scanner.nextInt());
                    length--;
                }
                ListNode head = build(nums);
                print(head);
                ListNode newHead = del(head);
                print(newHead);
            }
        }
    }
    
    public static void print(ListNode head){
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val);
            System.out.print(" ");
            cur = cur.next;
        }
        System.out.println("");
    }

    public static ListNode build( ArrayList<Integer> nums){
        ListNode dummyhead = new ListNode(0);
        ListNode cur = dummyhead;
        for(Integer num : nums){
            ListNode node = new ListNode(num);
            cur.next = node;
            cur = cur.next;
        }

        return dummyhead.next;

    }

    public static ListNode del(ListNode head){
        HashMap<Integer,Integer> hm = new HashMap();
        ListNode temp = head;
        while(temp != null){
            if(!hm.containsKey(temp.val)){
                hm.put(temp.val,1);
            }else{
                int tempval = temp.val;
                int count = hm.get(tempval);
                hm.put(tempval,count+1);
            }
            temp = temp.next;
        }
        ListNode dummyhead = new ListNode(0);
        dummyhead.next = head;
        ListNode cur = dummyhead;
        while(cur.next != null){
            ListNode node = cur.next;
            if(hm.get(node.val) != 1){
                cur.next = cur.next.next;
                int precount = hm.get(node.val);
                hm.put(node.val,precount-1);
            }else{
                cur = cur.next;
            }
        }
        
        return dummyhead.next;

    }
}