跳台阶问题
题目描述 一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。 求总共有多少总跳法，并分析算法的时间复杂度。 分析与解法 解法一 首先考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。 现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。 当n>2时，第一次跳的时候就有两种不同的选择： 一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)； 另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。 因此n级台阶时的不同跳法的总数f(n)=f(n-1)+f(n-2)。 我们把上面的分析用一个公式总结如下： 123 / 1 n = 1f(n)= 2 n = 2 \ f(n-1) + f(n-2) ...
逆置顺序表
设顺序表a中数据元素递增有序,试着设计一个算法将x插入到顺序表的适当位置,以保持该表的有序性. 逐个遍历 以为顺序表递增有序,从头开始找到第一个不小于它的元素,放在该元素前面. 二分查找 步骤1:取顺序表中间元素的值与插入元素比较, 步骤2:相等则放在该元素前面;插入元素小于中间元素,将列表分割为两部分对前面的部分进行步骤1;如果大于,对后面部分进行步骤1 结束条件:比较结果相等,或者分割后顺序表元素个数为1
链表
链表简介 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间.同时失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。 链表有很多种不同的类型：单向链表，双向链表以及循环链表。 单链表 单链表中每个结点只包含一个数据域和一个指针. 单链表声明 123456789101112131415161718192021222324252627typedef int T;//元素类型typedef struct link{ T data; struct link *next;}SingleLinkList, *PSingleLinkList;PSingleLinkList Init();int...
附近地点搜索
附近地点搜索 题目详情 找一个点集中与给定点距离最近的点，同时，给定的二维点集都是固定的，查询可能有很多次，时间复杂度O(n)无法接受，请设计数据结构和相应的算法。 分析与解法 此题是去年微软的三面题，类似于一朋友@陈利人出的这题：附近地点搜索，就是搜索用户附近有哪些地点。随着GPS和带有GPS功能的移动设备的普及，附近地点搜索也变得炙手可热。在庞大的地理数据库中搜索地点，索引是很重要的。但是，我们的需求是搜索附近地点，例如，坐标(39.91, 116.37)附近500米内有什么餐馆，那么让你来设计，该怎么做？ 解法一：R树二维搜索 假定只允许你初中数学知识，那么你可能建一个X-Y坐标系，即以坐标(39.91,...
随机取出其中之一元素
随机取出其中之一元素 题目描述 一个文件中含有n个元素（n未知），要求在只能遍历一遍这n个元素的情况下，等概率随机的取出其中之一个元素。 分析与解法 假设5个人轮流抽签，只有其中某一个人能中签，那么，这5个人每个人中签的概率是相等的。不信的话，咱们可以具体计算下。 首先，第一个人中签的概率是1/5，第二个人中签的情况只能在第一个人未中时才有可能，所以第二个人中签的概率是4/5 X 1/4 = 1/5（4/5表示第一个人未中，1/4表示第二个人在剩下的4个签里中签的概率），所以，第二个人最终的中签概率也是1/5， 同理，第三个人中签的概率为：第一个人未中的概率 * 第二个人未中的概率 * 第三个人中的概率，即为：4/5 * 3/4 * 1/3 = 1/5， 一样的可以求出第四和第五个人的概率都为1/5，也就是说先后抽签顺序不影响每个人中签概率的大小。 回到咱们的问题，在明确了先后抽签顺序不影响不公平的原则之后，下面，给出选取策略： 顺序遍历，当前遍历的元素为第L个元素，变量e表示之前选取了的某一个元素，此时生成一个随机数r，如果r%L ==...
顺序表
定义 顺序表(array-based list)又称为向量(vector)是在计算机内存中以数组的形式保存的线性表. 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。 顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 顺序表的基本操作 顺序表的声明 array_based_list.h 1234567891011121314151617181920212223242526272829#define ListSize 100 //线性表的最大长度typedef int DataType;// 顺序表内元素类型/**** 顺序表**///定义typedef struct{ DataType data[ListSize]; //用数组存储线性表中的元素 int length; ...
JVM
Java虚拟机（JVM, Java Virtual Machine）是Java语言的核心组件，它是一个抽象的计算机，专门为执行Java字节码而设计。Java源代码经过Java编译器编译后生成与平台无关的字节码文件（.class文件），这些字节码可以在任何安装了Java运行环境（JRE）的设备上运行，这是因为不同的平台上都有对应的JVM实现来解释或即时编译这些字节码。 JVM的主要作用和特征包括： 跨平台性： JVM为Java程序提供了跨平台的能力。开发者只需要编写一次Java代码，就可以在任何支持Java的系统上运行，这得益于JVM对不同操作系统和硬件架构的支持以及统一的字节码格式。 类加载机制： JVM通过类加载器（ClassLoader）将.class文件从硬盘加载到内存中，进行验证、准备、解析和初始化等步骤，使得类可以被JVM识别并使用。 内存管理： JVM内部有自己的一套内存模型，包含方法区、堆、栈、程序计数器和本地方法栈等多个区域。JVM负责自动管理内存分配与回收，尤其是垃圾收集机制（Garbage...
JVM学习指南
...
JVM性能调优
JVM性能调优主要涉及内存管理、垃圾回收、线程管理和编译优化等方面，以下是一些常见的调优策略： 内存配置与调整： -Xms 和 -Xmx 参数用于设置JVM堆内存初始大小和最大大小，合理设置可避免频繁的内存扩容和缩容带来的性能损耗。 -Xmn 设定年轻代大小，调整新生代、老年代的比例有助于优化垃圾回收效果。 -XX:PermSize 和 -XX:MaxPermSize （在Java 8及以前版本中）或者 -XX:MetaspaceSize 和 -XX:MaxMetaspaceSize（Java 8及以后版本）控制元空间/永久代的大小。 垃圾回收调优： 选择合适的垃圾收集器，比如G1、ZGC、Shenandoah等，并根据应用特点调整其相关参数，如 -XX:+UseG1GC 等。 调整年轻代晋升阈值 -XX:NewRatio 和 -XX:SurvivorRatio，优化对象在各代间的分布。 对于并发标记扫描（CMS）垃圾收集器，可以调整 -XX:CMSInitiatingOccupancyFraction 来设定触发并发收集的堆占用率。 线程优化： 合理设置...
Java虚拟机（JVM）内存模型
Java虚拟机（JVM）内存模型，也称为Java内存模型（Java Memory Model, JMM），是Java程序在运行时数据存储和交互的抽象模型。它定义了线程如何共享和交互内存区域中的变量，以及如何确保并发环境下的内存一致性。 JVM内存主要分为以下几大区域： 堆内存 (Heap) 堆是所有线程共享的一块内存区域，主要用于存放对象实例。所有的对象都在堆中分配内存。 当一个对象不再被任何引用指向时，垃圾回收器会对其进行回收以释放内存。 根据对象生命周期的不同，堆内存通常又细分为新生代、老年代等区域，并采用不同的垃圾回收策略进行管理。 方法区 (Method Area/元空间 Metaspace) 方法区同样是一个各个线程共享的内存区域，存储已经被加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。 在Java 7及以前版本，方法区有时被称为“永久代”，但在Java 8及之后，HotSpot VM移除了永久代，将类元数据存放在本地内存的元空间中。 虚拟机栈 (Java...