力扣-数据结构-7【算法学习day.78】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.链表随机节点

题目链接:382. 链表随机节点 - 力扣（LeetCode）

分析:数组存节点值，生成索引范围内的随机数并返回该随机数索引下的值

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    int[] arr = new int[10005];
    int count = 0;
    public Solution(ListNode head) {
        for(ListNode i = head;i!=null;i=i.next){
            arr[count++] = i.val;
        }
    }
    
    public int getRandom() {
        Random r = new Random();
        int number=r.nextInt(count);
        return arr[number];
    }
}
 
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

2.扁平化多级双向链表

题目链接: 430. 扁平化多级双向链表 - 力扣（LeetCode）

题面:

分析:用数组递归存储数值然后构造双向链表更加简单些

代码:

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    int[] arr = new int[1005];
    int count = 0;
    public Node flatten(Node head) {
        if(head==null)return head;
        for(Node i = head;i!=null;i=i.next){
            arr[count++] = i.val;
            if(i.child!=null){
                recursion(i.child);
            }
        }
        Node fhead = new Node();
        Node pre = fhead;
        for(int i = 0;i<count;i++){
            Node node = new Node(arr[i]);
            pre.next=node;
            node.prev=pre;
            pre = node;
        }
        // for(Node i = fhead.next;i!=null;i=i.next){
        //     System.out.println(i.val);
        // }
        Node ans = fhead.next;
        ans.prev = null;
        return ans; 
    }
    public void recursion(Node head){
         for(Node i = head;i!=null;i=i.next){
            arr[count++] = i.val;
            if(i.child!=null){
                recursion(i.child);
            }
        }
    }
}