-
牛客题目——链表的奇偶重排、输出二叉树的右视图、括号生成、字符流中第一个不重复的字符
题目1——链表的奇偶重排
给定一个单链表，请设定一个函数，将链表的奇数位结点和偶数位结点分别放在一起，重排后输出。
要求：时间复杂度O(n)，空间复杂度O(n)。示例
输入：{1,2,3,4,5,6}
输出：{1,3,5,2,4,6}解题思路
可以利用双指针，一个指针用来链接奇数结点，一个指针用来链接偶数结点。具体做法如下：
- 首先处理链表为空的情况，链表为空，则直接返回头结点；
- 使用双指针odd和even分别遍历奇数结点和偶数结点，开始时，odd指向第一个结点，even指向第二个结点；
- 每次遍历两个结点，循环条件为even指针不为空且even.next也不为空，遍历时，奇数指针的下一个结点指向偶数的下一个，偶数指针的下一个结点指向奇数结点的下一个；
- 将偶数结点接在奇数最后一个结点后，再返回头部。
代码实现
import java.util.*； /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { public ListNode oddEvenList (ListNode head) { if(head == null) return head; ListNode even = head.next; ListNode evenHead = even; ListNode odd = head; while(even != null && even.next != null){ //奇数位连接偶数位的后一个 odd.next = even.next; //奇数位指针后移指向下一个 odd = odd.next; //偶数位连接奇数的下一个 even.next = odd.next; //偶数位指针后移指向下一个 even = even.next; } odd.next = evenHead; return head; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
题目2——输出二叉树的右视图
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图。
要求：空间复杂度O(n)，时间复杂度O(n)。示例
输入：[1,2,4,5,3], [4,2,5,1,3]
输出：[1,3,5]
解题思路
首先检查两个遍历序列的大小，若是为0，则不打印空树。利用递归算法构造二叉树，然后利用深度优先搜索对构造好的树进行遍历，遍历过程中(首先遍历根结点，接着将其左结点和右节点分别入栈，根据栈先入后出原理，每次都是最右边的结点先被访问)，我们可以使用栈来保存访问的结点和深度，并根据深度将每层的最右结点值加入到哈希表中。
时间复杂度为O(n^2)，空间复杂度为O(n)。上述方法中每次都要寻找中序遍历的根结点，为了解决这个问题，我们可以利用哈希表直接将中序元素和下标做一个映射，后续可以直接访问。
递归建造树的时候，为保证正确地访问数组下标，我们将每次递归访问的先序，后序及其左右结点下标都作为参数。
同时还可以使用层次遍历去找到每层的最右结点，层次遍历树的做法如下：建立队列，将根结点入队，使用一个size变量，每次进入一层的时候记录当前队列大小，等到size为0的时候，就到了最右边的结点，记录下该结点的元素。
时间复杂度为O(n)，空间复杂度为O(n)。代码实现
import java.util.*; public class Solution { //构造二叉树 public TreeNode buildTree(int[] xianxu,int[] zhongxu){ if(xianxu.length == 0 || zhongxu.length == 0) return null; TreeNode root = new TreeNode(xianxu[0]); for(int i=0;i<zhongxu.length;i++){ if(zhongxu[i] == xianxu[0]){ root.left = buildTree(Arrays.copyOfRange(xianxu,1,i+1),Arrays.copyOfRange(zhongxu,0,i)); root.right = buildTree(Arrays.copyOfRange(xianxu,i+1,xianxu.length),Arrays.copyOfRange(zhongxu,i+1,zhongxu.length)); } } return root; } public ArrayList<Integer> rightSlideView(TreeNode root){ Map<Integer,Integer> mp = new HashMap<Integer,Integer>(); int max_depth = -1; //维护深度访问的结点 Stack<TreeNode> nodes = new Stack<TreeNode>(); //维护深度遍历时的深度 Stack<Integer> depths = new Stack<Integer>(); nodes.push(root); depths.push(0); //开始进行遍历 while(!nodes.isEmpty()){ TreeNode node = nodes.pop(); int depth = depths.pop(); if(node != null){ max_depth = Math.max(max_depth,depth); if(mp.get(depth) == null) mp.put(depth,node.val); //最右结点的值加入到哈希表中 nodes.push(node.left); nodes.push(node.right); depths.push(depth+1); depths.push(depth+1); } } ArrayList<Integer> res = new ArrayList<Integer>(); for(int i=0;i<=max_depth;i++){ res.add(mp.get(i)); } return res; } public int[] solve (int[] xianxu, int[] zhongxu) { if(xianxu.length == 0) return new int[0]; TreeNode root = buildTree(xianxu,zhongxu); ArrayList<Integer> temp = rightSlideView(root); int[] res = new int[temp.size()]; for(int i=0;i<temp.size();i++){ res[i] = temp.get(i); } return res; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
import java.util.*; public class Solution { public Map<Integer, Integer> index; //l1,r1分别是前序最左节点下标，前序最右节点下标 //l2,r2分别是中序最左节点下标，中序最右节点坐标 public TreeNode buildTree(int[] xianxu, int l1, int r1, int[] zhongxu, int l2, int r2){ if(l1 > r1 || l2 > r2) return null; //前序遍历中的第一个节点就是根节点 int xianxu_root = l1; //在中序遍历中定位根节点 int zhongxu_root = index.get(xianxu[xianxu_root]); TreeNode root = new TreeNode(xianxu[xianxu_root]); //得到左子树中的节点数目 int leftsize = zhongxu_root - l2; root.left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, zhongxu_root - 1); root.right = buildTree(xianxu, l1 + leftsize + 1, r1, zhongxu, zhongxu_root + 1, r2); return root; } //层次遍历 public ArrayList<Integer> rightSideView(TreeNode root) { ArrayList<Integer> res = new ArrayList<Integer>(); Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while(!q.isEmpty()){ //队列中的大小即是这一层的节点树 int size = q.size(); while(size-- != 0){ TreeNode temp = q.poll(); if(temp.left != null) q.offer(temp.left); if(temp.right != null) q.offer(temp.right); //最右元素 if(size == 0) res.add(temp.val); } } return res; } public int[] solve (int[] xianxu, int[] zhongxu) { index = new HashMap<Integer, Integer>(); //空节点 if(xianxu.length == 0) return new int[0]; //用哈希表标记中序节点在前序中的位置 for(int i = 0; i < xianxu.length; i++) index.put(zhongxu[i], i); //建树 TreeNode root = buildTree(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1); //获取右视图输出 ArrayList<Integer> temp = rightSideView(root); //转化为数组 int[] res = new int[temp.size()]; for(int i = 0; i < temp.size(); i++) res[i] = temp.get(i); return res; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
题目3——括号生成
给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给定n=3，解集为：
“((()))”, “(()())”, “(())()”, “()()()”, “()(())”
要求：空间复杂度O(n)，时间复杂度O(2^n)。解题思路
一种就是暴力解法，生成所有可能的括号序列，然后判断是否合法，但是时间复杂度比较高。
为了减少时间复杂度，我们可以减少枚举的括号数量，如果想要生成合法的字符串，在枚举字符串序列的过程中，只能有两个选择，要么加入左括号，要么加入右括号，加入左括号的前提是左括号的数量小于n，加入右括号的前提是右括号的数量小于左括号数量，直到字符串长度等于2n，则保存合法字符串。代码实现
import java.util.*; public class Solution { public void backtrack(String str,int open,int close,int n,List<String> result){ if(str.length() == n<<1){ result.add(str); return; } if(open<n){ backtrack(str+"(",open+1,close,n,result); } if(close<open){ backtrack(str+")",open,close+1,n,result); } } public ArrayList<String> generateParenthesis (int n) { ArrayList<String> result = new ArrayList<>(); backtrack("",0,0,n,result); return result; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
题目4——字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符，例如当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"，当从该字符流中读出前6个字符"google"时，第一个只出现一次的字符是"l"。
如果当前字符流没有存在出现一次的字符，返回#字符。
要求：空间复杂度O(n)，时间复杂度O(n)。示例
输入：“google”
输出：“ggg#ll”解题思路
使用哈希表记录字符的出现的次数，然后遍历字符数组，找到哈希表中出现次数为1的第一个字符。
还可以将字符串数组换成队列，不断检查队首元素，找到出现次数为1的队首元素。import java.util.*; public class Solution { public ArrayList<Character> arr = new ArrayList<Character>(); public HashMap<Character,Integer> map = new HashMap<Character,Integer>(); //Insert one char from stringstream public void Insert(char ch) { arr.add(ch);//插入字符 if(!map.containsKey(ch)){ map.put(ch,1); }else{ map.put(ch,map.get(ch)+1); } } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { for(int i=0;i<arr.size();i++){ if(map.get(arr.get(i)) == 1) return arr.get(i); } return '#'; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
-
相关阅读:
一、nginx安装第三方模块[apt安装、源码安装]
python中字符替换的方法
java url编码 解码
ios应用内支付
解决JSON传参报错问题
Nginx完全指南 第二版 下载
5 分钟带你小程序入门 [实战总结分享]
Unity Game FrameWork—模块使用—资源热更新
Azure - 机器学习实战：快速训练、部署模型
了解Shader
- 原文地址：https://blog.csdn.net/zhangzhang_one/article/details/126002771
