剑指offer打卡day03:二叉搜索树与双向链表 & 扑克牌顺子

题1:二叉搜索树与双向链表

题目描述

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

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息

解析:

双向链表:

在没有特指的情况下说链表一般指代“单向链表”,只能进行单项遍历,万一不行其中有一个链接断裂,那么后面的链表数据就无法复原了。

双向链表(Double LinkedList)在一个节点有两个指针变量,一个指向后面节点,一个指向前面的节点,可以双向通行。

  • 优缺点:

    • 优点:能根据任意节点找到其他节点,不用反转或对比等处理,执行速度较快
    • 缺点:双向链表有两个链接,在删除或增加节点操作时会花更多时间移动指针,浪费空间
  • 双向链表特点:

    • 每个节点有三个字段,数据字段,以及左右的链接字段。

    • 在链表中通常加上一个链表头,此链表节点不存放任何数据,其左连接字段指向链表最后一个节点,而右连接指向第一个节点(好家伙,又是一个环形链表)

    • 假设ptr 为一个指向此链表上任一节点的链接,则有:

      ptr = RLink(LLink(ptr)) = LLink(RLink(ptr))
      
  • 用Java语言声明双向链表节点的数据结构:

    class Node
    { 
        int data;
        Node rnext;
        Node lnext; 
        
        public Node(int data){ 
            this.data = data;
            this.rnext = null;
            this.lnext  = null;
        }
    }
    
  • 回到题目,将二叉搜索树转换为链表:

    • 对比不难发现二叉树的TreeNode和双向链表的Nod同样有着三个字段。
    • 因此只需遍历BST,将整个树分成无数的小树,然后将他们分别转化成一小段一小段的双向链表,在拼接起来即可。

解答:

参考此题在牛客剑指OFEER(大北砸)的答案<自己实在搞不出来哈哈>

//明确成员变量pLast:用于记录当前链表的末尾节点
private TreeNode pLast = null;

/* 输入:BST的根节点 处理:将其转化为一个有序的双向链表 输出:返回该链表的头节点 */
public TreeNode Convert(TreeNode pRootOfTree) { 
    if(pRootOfTree == null){ 
        return null;
    }
    //如果左子树为空,那么跟根节点root为双向链表的头节点
    TreeNode head = Convert(pRootOfTree.left);
    if(head == null){ 
        head = pRootOfTree;
    }

    //连接当前节点root和当前链表的为节点plast;
    pRootOfTree.left = pLast;
    if(pLast != null){ 
        pLast.right = pRootOfTree;
    }
    pLast = pRootOfTree;

    Convert(pRootOfTree.right);

    return head;
}

题2:扑克牌顺子

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何, 如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0。

示例

输入

[0,3,2,6,4]

返回值

true

解析:

  1. 题目中对“顺子”的定义:

    1. 牌的点数为连续五张差值为1的牌。
    2. 大小王(有四张)可以当作任意的牌补充在所抽的五张牌里。
  2. 综合题目,可以得出能满足为顺子的条件,分为两种情况:

    1. 所抽五张牌没有任意牌:

      1. 不能出现两张相同点数的牌(对子)
      2. 在五张牌中最大的点数与最小的点数的差值 小于等于4.
    2. 所抽五张牌有任意牌:

      1. 若有四张任意牌,则任意加任意一张点数的牌都能成为顺子

      2. 若任意牌的数量 < 4 ,

        则在满足五张牌中最大的点数与最小的点数的差值 小于等于4的情况下,都能满足顺子。

解答:

/* 整理思路: 1.对数组进行排序 2.计算任意牌数量,如果等于4则直接为true 3.判断牌组中是否存在对子 5.判断牌组中最大值与最小值的差值是否小于等于4 */
public boolean isContinuous(int [] numbers) { 
    if(numbers.length == 0){ 
        return false;
    }
    ArrayList<Integer> cardList = new ArrayList<Integer>();
    //1.对数组进行排序(此处用最基础的冒泡排序)
    bubbleSort(numbers);
    //2.计算大小王数量,并把不是大小王的添加到cardList中
    int count = 0;
    for(int i = 0 ; i<numbers.length ; i++){ 
        if(numbers[i]!=0){ 
            cardList.add(numbers[i]);
        }else{ 
            count++;
        }
    }
    if (count == 4){ 
        return true;
    }
    //3.查看数组中是否有对子
    for(int i = cardList.size()-1 ; i >=1  ; i--){ 
        if(cardList.get(i) == cardList.get(i-1)){ 
            return false;
        }
    }
    //5.最大值减最小值小于等于4,则能成为顺子
    if(cardList.get(cardList.size()-1) - cardList.get(0) <= 4){ 
        return true;
    }else{ 
        return false;
    }
}

public void bubbleSort(int[] numbers) { 
    int tmp ;
    for (int j = numbers.length - 1; j >= 0; j--) { 
        for (int i = 0; i < j; i++) { 
            if (numbers[i] > numbers[i + 1]) { 
                tmp = numbers[i];
                numbers[i] = numbers[i + 1];
                numbers[i + 1] = tmp;
            }
        }
    }
}

补充:

上述思路是对的,但为最普遍的一把梭思路,毫无算法的技术含量(如果要说算法只能是冒泡的时候用到了点?)

现对上述思路进行与优化:

 public boolean isContinuous2(int [] numbers) { 
        //1.非空校验
        if(numbers.length == 0){ 
            return false;
        }
        //2.创建数组做计数(0~13)
        int[] container =  new int[14];
        //在0的计数位设置为-4
        container[0] = -4;
        int len = numbers.length;
        int max = -1;
        int min = 14;
        //遍历数组
        for(int i = 0 ;i < len; i++){ 
            container[numbers[i]]++;
            if(numbers[i] == 0){ 
                continue;
            }
            //若5张牌中间会有四张任意牌,则直接为顺子
            if(container[0] == 0){ 
                return true;
            }
            //判断五张牌中是否存在对子
            if(container[numbers[i]]>1){ 
                return false;
            }
            //更换五张牌中的最大最小值
            if(numbers[i] > max){ 
                max = numbers[i];
            }
            if(numbers[i] < min){ 
                min  = numbers[i];
            }
        }
        if(max - min < 5 ){ 
            return true;
        }else{ 
            return false;
        }
    }
    原文作者:coolgwayne
    原文地址: https://blog.csdn.net/qq_42191980/article/details/112107210
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞