IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 力扣:剑指 Offer 05. 替换空格 06 .从尾到头打印链表 07. 重建二叉树 -> 正文阅读

[数据结构与算法]力扣:剑指 Offer 05. 替换空格 06 .从尾到头打印链表 07. 重建二叉树

剑指 Offer 05. 替换空格

难度简单352

请实现一个函数,把字符串?s?中的每个空格替换成"%20"。

示例 1:

输入:s = "We are happy."
输出:"We%20are%20happy."

限制:

0 <= s 的长度 <= 10000

class Solution {
    public String replaceSpace(String s) {
        //在java中String是不可以被修改的 ,所以要在借用一个数组来重新写
       //StringBuilder 是被允许在与原来的对象上进行多次修改  ,一个一个字符
       //所以只需要在遇到空格将他替换成%20 剩下的就直接复制就行
       StringBuilder sb=new StringBuilder();
       for(Character c : s.toCharArray()){//toCharArray() 方法将字符串转换为字符数组
           if(c==' ') sb.append("%20");
           else sb.append(c);
       }
        return sb.toString();//最后要将StringBUilder类型转成String类型
    }
}

?注意:本题主要考察java中String类的对象,不能被修改;要使用StringBuffer或StringBuilder类,它们允许字符串进行修改。

(1)先将String类型转换成数组(使用toCharArray()方法)

(2)创建StringBuilder对象,进行字符串的拼接。

?(3)别忘了转型,调用toString()方法。

String StringBuffer和?StringBuilder的区别:

String字符串常量,不能被修改。StringBuilder和StringBuffer可以在内存中频繁修改。
同时StringBuilder是线程安全的类,StringBuffer是线程不安全的类。
速度:
String<StringBuffer<StringBuilder

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2]
输出:[2,3,1]
?

限制:

0 <= 链表长度 <= 10000

这道题有两种思路:

一 利用栈,这种数据结构 栈先进后出 ,刚好满足题意。

(1)利用集合LinkedList类(底层是双向链表) 先将链表中的数据存起来

(2)利用数组存储反向连表里的数据

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {//链表 转成栈
        LinkedList<Integer> arr =new LinkedList<Integer>();//利用集合
        //链表是 data和next 指针 组成
        while(head!=null){
            arr.addLast(head.val);//如果当前值不为空,那我就把当前这个值存起来
            head=head.next;//head.next 就是下一个值
        }
        int[] res =new int[arr.size()];//获取集合长度 size()
        for(int i=0;i<res.length;i++){
            res[i]=arr.removeLast();//集合从最后一个数开始赋值 出来后就变成 倒序排列了
            //removeLast() 删除并返回最后一个
        }
        return res;
    }
}

第二种运用递归:如下图:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    LinkedList<Integer> arr =new LinkedList<Integer>();//使用链表
    public int[] reversePrint(ListNode head) {//使用递归
    res(head);
    int[] end =new int[arr.size()];
    for(int i=0;i<end.length;i++){
        end[i]=arr.removeFirst();
    }
    return end;
    }
    public  void res(ListNode head){
        //设置递归终止条件
        if(head==null) return ;
        res(head.next);//如果head不为空,那就调用
        //当递归到最后 一层一层存储。
        arr.add(head.val);

    }

}

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

?

Input: preorder = [-1], inorder = [-1]
Output: [-1]
?

限制:

0 <= 节点个数 <= 5000

?前提:一般与二叉树有关的题目 都与分治和递归的算法有关。

我们都知道二叉树有前序,中序,后序遍历。

四种主要的遍历思想为:

前序遍历:根结点 ---> 左子树 ---> 右子树

中序遍历:左子树--->?根结点?---> 右子树

后序遍历:左子树 ---> 右子树?---> 根结点

层次遍历:只需按层次遍历即可。

当已知前序和中序遍历时就可以确定一棵二叉树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 //前序遍历和中序遍历可以确定一颗二叉树  我只要知道前序遍历的第一个数一定是这棵树的根节点,那我就可以知道中序遍历中
 //左右子树的位置
 //解题思路:二叉树题目一般与分治 和 递归算法有关
 //1.先确定根节点 前序遍历第一个数就是根节点 root
 //2.找到左子树的个数  在中序中找到根节点(由前序可得) index,确定左子树的长度 int left =index-inStart
 //3.创建二叉树 左右节点递归
 //递归
 // 1 明确递归结束条件 在二叉树中 左子树一定要小于右子树
 // 2 每次找的步骤都是相同的

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //使用递归,建立函数
        return rebuildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    //使用递归
    public TreeNode rebuildTree(int[] preorder,int preStart,int preEnd ,int[] inorder,int inStart,int inEnd){
        //1。确定递归结束条件
        if(preStart>preEnd){
            return null;
        }
        //确定根节点--有前序遍历可知
        int root=preorder[preStart];
        int index=0;
        //找到中序遍历的根节点的位置--中序遍历可知
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root){
                index=i;
                break;
            }
        }
        TreeNode node=new TreeNode(root);
        //左子树的大小--中序遍历
        int left=index-inStart;
        //递归调用 左右节点 根据前序遍历数组中的下标创建
        node.left=rebuildTree(preorder,preStart+1,preStart+left,inorder,inStart,index-1);
        node.right=rebuildTree(preorder,preStart+left+1,preEnd,inorder,index+1,inEnd);
        return  node;
    }
}

(1)首先根据前序遍历可知根节点

(2)然后在中序遍历中找到根节点,确定左子树的长度 中序遍历中 根节点位置-初始位置

(3)递归调用左右子节点

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-30 01:12:58  更:2022-09-30 01:14:28 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 19:49:05-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码