热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

剑指offerJAVA版笔记(第四天、第十九题至第二十四题)

19.顺时针打印矩阵题目描述:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4X4矩阵:12345678910111213141516则依次打印出

19.顺时针打印矩阵

  • 题目描述:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
  • 解题思路:计算好层数然后左,下,右,上这样循环输出注意判断是否重复输出即可。

public class printMatrix {
public ArrayList printMatrix(int [][] matrix) {
ArrayList result = new ArrayList<>();
int row = matrix.length;
int column = matrix[0].length;
if(row == 0 || column == 0){
return result;
}
int layer = (Math.min(row,column)-1)/2 + 1 ;
for (int i = 0;i for(int j = i ; j for(int j = i + 1; j for(int j = column - i - 2; (j > i - 1) &&(row-i-1!=i) ; j--){result.add(matrix[row - i - 1 ][j]);}
for(int j = row - i - 2; (j > i)&&(column-i-1!=i) ; j--){result.add(matrix[j][i]);}
}
return result;
}
}

20.包含min函数的栈

  • 题目描述:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
  • 解题思路:使用辅助栈每次存小的数。

Stack data = new Stack();
Stack min = new Stack();
Integer temp = null;
public void push(int node) {
if(temp != null){
if(node <= temp ){
temp = node;
min.push(node);
}
data.push(node);
}else{
temp = node;
data.push(node);
min.push(node);
}
}
public void pop() {
int num = data.pop();
int num2 = min.pop();
if(num != num2){
min.push(num2);
}
}
public int top() {
int num = data.pop();
data.push(num);
return num;
}
public int min() {
int num = min.pop();
min.push(num);
return num;
}

21.栈的压入、弹出序列

  • 题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
  • 解题思路:模拟入栈出栈的过程,出错返回false。

public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack stack = new Stack<>();
if(pushA.length != popA.length){
return false;
}
int j = 0;
for (int i = 0; i stack.push(pushA[i]);
if (pushA[i] == popA[j]){
stack.pop();
j++;
}
}
while (!stack.isEmpty()){
if(popA[j] == stack.pop()){
j++;
}
else return false;
}
return true;
}

22.从上往下打印二叉树

  • 题目描述:从上往下打印出二叉树的每个节点,同层节点从左至右打印。
  • 解题思路:思路是用arraylist模拟一个队列来存储相应的TreeNode。

public class PrintFromTopToBottom {
public ArrayList PrintFromTopToBottom(TreeNode root) {
ArrayList list = new ArrayList<>();
ArrayList queue = new ArrayList<>();
if (root == null) {
return list;
}
queue.add(root);
while (queue.size() != 0) {
TreeNode temp = queue.remove(0);
if (temp.left != null){
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
list.add(temp.val);
}
return list;
}
}

23.二叉搜索树的后序遍历序列

  • 题目描述:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
  • 解题思路:BST的后序序列的合法序列是,对于一个序列S,最后一个元素是x (也就是根),如果去掉最后一个元素的序列为T,那么T满足:T可以分成两段,前一段(左子树)小于x,后一段(右子树)大于x,且这两段(子树)都是合法的后序序列。完美的递归定义 : ) 。

public boolean VerifySquenceOfBST(int [] sequence) {

if(sequence.length==0)
return false;
if(sequence.length==1)
return true;
return ju(sequence, 0, sequence.length-1);
}
public boolean ju(int[] a,int star,int root){
if(star>=root)
return true;
int i = root;
//从后面开始找
while(i>star&&a[i-1]>a[root])
i--;//找到比根小的坐标
//从前面开始找 star到i-1应该比根小
for(int j = star;j if(a[j]>a[root])
return false;;
return ju(a,star,i-1)&&ju(a, i, root-1);
}

24.二叉树中和为某一值的路径

  • 题目描述:输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)
  • 解题思路:

private ArrayList> listAll = new ArrayList>();
private ArrayList list = new ArrayList();
public ArrayList> FindPath(TreeNode root,int target) {
if(root == null) return listAll;
list.add(root.val);
target -= root.val;
if(target == 0 && root.left == null && root.right == null)
listAll.add(new ArrayList(list));
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size()-1);
return listAll;
}

推荐阅读
  • STL迭代器的种类及其功能介绍
    本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系,并详细描述了各个迭代器的功能和使用方法。其中,输入迭代器用于从容器中读取元素,输出迭代器用于向容器中写入元素,正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]
  • 广度优先遍历(BFS)算法的概述、代码实现和应用
    本文介绍了广度优先遍历(BFS)算法的概述、邻接矩阵和邻接表的代码实现,并讨论了BFS在求解最短路径或最短步数问题上的应用。以LeetCode中的934.最短的桥为例,详细阐述了BFS的具体思路和代码实现。最后,推荐了一些相关的BFS算法题目供大家练习。 ... [详细]
  • 文章目录题目:二叉搜索树中的两个节点被错误地交换。基本思想1:中序遍历题目:二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下 ... [详细]
  • JVM 学习总结(三)——对象存活判定算法的两种实现
    本文介绍了垃圾收集器在回收堆内存前确定对象存活的两种算法:引用计数算法和可达性分析算法。引用计数算法通过计数器判定对象是否存活,虽然简单高效,但无法解决循环引用的问题;可达性分析算法通过判断对象是否可达来确定存活对象,是主流的Java虚拟机内存管理算法。 ... [详细]
  • 本文讨论了Kotlin中扩展函数的一些惯用用法以及其合理性。作者认为在某些情况下,定义扩展函数没有意义,但官方的编码约定支持这种方式。文章还介绍了在类之外定义扩展函数的具体用法,并讨论了避免使用扩展函数的边缘情况。作者提出了对于扩展函数的合理性的质疑,并给出了自己的反驳。最后,文章强调了在编写Kotlin代码时可以自由地使用扩展函数的重要性。 ... [详细]
  • 模板引擎StringTemplate的使用方法和特点
    本文介绍了模板引擎StringTemplate的使用方法和特点,包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时,还介绍了StringTemplate语法中的属性和普通字符的使用方法,并提供了向模板填充属性的示例代码。 ... [详细]
  • 欢乐的票圈重构之旅——RecyclerView的头尾布局增加
    项目重构的Git地址:https:github.comrazerdpFriendCircletreemain-dev项目同步更新的文集:http:www.jianshu.comno ... [详细]
  • 重入锁(ReentrantLock)学习及实现原理
    本文介绍了重入锁(ReentrantLock)的学习及实现原理。在学习synchronized的基础上,重入锁提供了更多的灵活性和功能。文章详细介绍了重入锁的特性、使用方法和实现原理,并提供了类图和测试代码供读者参考。重入锁支持重入和公平与非公平两种实现方式,通过对比和分析,读者可以更好地理解和应用重入锁。 ... [详细]
  • 本文介绍了使用哈夫曼树实现文件压缩和解压的方法。首先对数据结构课程设计中的代码进行了分析,包括使用时间调用、常量定义和统计文件中各个字符时相关的结构体。然后讨论了哈夫曼树的实现原理和算法。最后介绍了文件压缩和解压的具体步骤,包括字符统计、构建哈夫曼树、生成编码表、编码和解码过程。通过实例演示了文件压缩和解压的效果。本文的内容对于理解哈夫曼树的实现原理和应用具有一定的参考价值。 ... [详细]
  • HashMap的相关问题及其底层数据结构和操作流程
    本文介绍了关于HashMap的相关问题,包括其底层数据结构、JDK1.7和JDK1.8的差异、红黑树的使用、扩容和树化的条件、退化为链表的情况、索引的计算方法、hashcode和hash()方法的作用、数组容量的选择、Put方法的流程以及并发问题下的操作。文章还提到了扩容死链和数据错乱的问题,并探讨了key的设计要求。对于对Java面试中的HashMap问题感兴趣的读者,本文将为您提供一些有用的技术和经验。 ... [详细]
  • 深入解析Linux下的I/O多路转接epoll技术
    本文深入解析了Linux下的I/O多路转接epoll技术,介绍了select和poll函数的问题,以及epoll函数的设计和优点。同时讲解了epoll函数的使用方法,包括epoll_create和epoll_ctl两个系统调用。 ... [详细]
  • Ihaveaworkfolderdirectory.我有一个工作文件夹目录。holderDir.glob(*)>holder[ProjectOne, ... [详细]
  • 本文介绍了一道经典的状态压缩题目——关灯问题2,并提供了解决该问题的算法思路。通过使用二进制表示灯的状态,并枚举所有可能的状态,可以求解出最少按按钮的次数,从而将所有灯关掉。本文还对状压和位运算进行了解释,并指出了该方法的适用性和局限性。 ... [详细]
  • HashMap的扩容知识详解
    本文详细介绍了HashMap的扩容知识,包括扩容的概述、扩容条件以及1.7版本中的扩容方法。通过学习本文,读者可以全面了解HashMap的扩容机制,提升对HashMap的理解和应用能力。 ... [详细]
  • linux进阶50——无锁CAS
    1.概念比较并交换(compareandswap,CAS),是原⼦操作的⼀种,可⽤于在多线程编程中实现不被打断的数据交换操作࿰ ... [详细]
author-avatar
手机用户2602896463
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有