剑指 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)递归调用左右子节点
|