剑指offer第四天

25.复杂链表的复制

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        //一定注意考虑输入为空链表的情况
        if(pHead == null) return null;
        //第一步:克隆每个结点的值和next,并且将新节点放置在对应旧结点之后
        RandomListNode node = pHead;
        while(node != null){
            RandomListNode cloneNode = new RandomListNode(node.label);
            //cloneNode.label = node.label;
            cloneNode.next = node.next;
            node.next = cloneNode;
            node = cloneNode.next;
        }
        //第二步:克隆每个随机指针
        node = pHead;
        while(node != null){
            RandomListNode cloneNode = node.next;
            if(node.random != null)
                cloneNode.random = node.random.next;
            node = cloneNode.next;
        }
        //第三步:拆分拼接的链表
        node = pHead;
        RandomListNode cloneHead = pHead.next;
        while(node != null){
            RandomListNode cloneNode = node.next;
            node.next = cloneNode.next;
            node = node.next;
            if(node != null)
                cloneNode.next = node.next;
            else
                cloneNode.next = null;
        }
        return cloneHead;
    } 
}

26.二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        if(pRootOfTree.left == null && pRootOfTree.right == null) return pRootOfTree;
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode node = left;
        
        if(node == null)
            pRootOfTree.left = null;
        else{
            while(node.right != null)
                node = node.right;
            pRootOfTree.left = node;
            node.right = pRootOfTree;
        }
        TreeNode right = Convert(pRootOfTree.right);
        pRootOfTree.right = right;
        if(right != null)
            right.left = pRootOfTree;
        return left != null ? left : pRootOfTree; 
    }
}

27.==字符串的排列==

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

输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Solution {
    ArrayList<String> result = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if(str == null) return null;
        char[] charArray = str.toCharArray();
        permutation(charArray,0);
        Collections.sort(result);
        return result;
    }
    public void permutation(char[] charArray,int beginIdx){
        if(beginIdx >= charArray.length) return;
        if(beginIdx == charArray.length-1){
            result.add(String.valueOf(charArray));
        }
        HashSet<Character> charSet = new HashSet<>();
        for(int i = beginIdx;i<charArray.length;i++){
            if(i == beginIdx){
                charSet.add(charArray[i]);
                permutation(charArray,beginIdx+1);
            }else if(i != beginIdx && !charSet.contains(charArray[i])){
                char temp = charArray[beginIdx];
                charArray[beginIdx] = charArray[i];
                charArray[i] = temp;
                permutation(charArray,beginIdx+1);
                temp = charArray[beginIdx];
                charArray[beginIdx] = charArray[i];
                charArray[i] = temp;
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

Hashtable源码解析(JDK1.8)

1 package java.util; 2 3 import java.io.*; 4 import java.util.concu...

31140
来自专栏LeetCode

LeetCode 872. Leaf-Similar Trees

Consider all the leaves of a binary tree.  From left to right order, the values ...

15500
来自专栏菩提树下的杨过

XStream、JAXB 日期(Date)、数字(Number)格式化输出xml

XStream、Jaxb是java中用于对象xml序列化/反序列化 的经典开源项目,利用它们将对象转换成xml时,经常会遇到日期(Date)、数字按指定格式输出...

28270
来自专栏LeetCode

BST & AVL 二分搜索树 & 平衡二叉树的实现原理

本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

27910
来自专栏格子的个人博客

Java源码阅读之TreeMap(红黑树) - JDK1.8

TreeMap实现了NavigableMap接口, 而NavigableMap则是通过sortedMap间接继承了Map接口,它定义了一系列导航方法,这些Map...

37630
来自专栏Echo is learning

剑指offer04--重建二叉树

12150
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

11740
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(中)

在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要...

13510
来自专栏机器学习入门

LWC 62:742. Closest Leaf in a Binary Tree

LWC 62:742. Closest Leaf in a Binary Tree 传送门:742. Closest Leaf in a Binary Tree...

312100
来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

15640

扫码关注云+社区

领取腾讯云代金券