题意:给一个长度为N(N≤200000)的序列,要删除一个连续子序列,使得剩下的序列中有一个长度最大的连续递增子序列,输出其长度。解法:(参考自紫书)1.X 暴力枚举删除的区间 [l,r],O(n^2),再数需要O(n)。总共O(n^3)。2.X 前者+O(n)预处理 f[i] 和 g[i] 表示前缀和后缀的长度最大的连续递增子序列长度。总共O(n^2)。3.√ 前者O(n)预处理+ 只枚举 r(部分枚举),快速找最优的 l。而最优的就是 Ai 尽量小而f[i]尽量大,就可以排除...
二分查找 这些天深刻的体会到了巩固知识的重要性。对数据结构和算法的学习有一年的时间,然后搁置了一年,最后发现都忘记了。 不过还好不是失忆,看了之前做过的笔记,还是能回想起来的。 现在想在写一遍,算是对本子上的笔记做一个备份,更重要的是加深我的印象。 首先说一下二分查找的思想:假设数据是按升序排序的,对于给定值val,从序列的中间位置开始比较。 ...
据结构和算法概述什么是计算机科学?首先明确的一点就是计算机科学不仅仅是对计算机的研究,虽然计算机在科学发展的过程中发挥了重大的作用,但是它只是一个工具,一个没有灵魂的工具而已。所谓的计算机科学实际上是对问题、解决问题以及解决问题的过程中产生产生的解决方案的研究。例如给定一个问题,计算机科学家的目标是开发一个算法来处理该问题,最终得到该问题的解、或者最优解。所以说计算机科学也可以被认为是对算法的研究...
package com.kuang;import java.util.Arrays;/** * @auther 付强 * @date 2020/2/15 - 10:46 */public class RadixSort { public static void main(String[] args) { int[] arr=new int[]{23,6,189,45,9,289,56,1,789,32,65,652,5}; radixSort(arr); System.out.println(Arrays.toString(arr)); } public static void radixSort(int[] arr){ //存数组中最大的数字 int max=Integer.MI...
一、顺序存储结构对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树,由于它的特殊性,使得用顺序存储结构也可以实现。 二、二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系等。 三、完全二叉树可以将相应下标的结点存到数组的相应下标的位置上,对于一般的二叉树来说,完全可以将其...
这一章要讲的数据结构基本以实用为主。12.1 自顶而下的伸展树一些定义展开:对于树的操作,叶结点X被插入之后,经过旋转使X成为新的树根。摊还时间:在摊还分析中的一个概念,就是求一个操作的所有情况的平均时间。和O()的时间不同,后者体现的是最糟糕的情况下程序完成所要花费的时间。P345之中,还有一些内容不是很明白,比如图12.1之中,为什么旋转之后树之间是断开的。我不是很清楚这是怎么回事。原文:http://www.cnblogs.c...
#include <stdio.h>#include <stdlib.h>#define OVERFLOW -2#define OK 1#define ERROR 0typedef int ElemType;//单向链表结构体typedef struct LNode { ElemType data; struct LNode *next;}LNode,*LinkList;LinkList CreateList_L(LinkList L,int n);void TraverseList_L(LinkList L);int GetElem_L(LinkList L,int i,ElemType *e);LinkList ListInsert_L(LinkList L,int i,ElemType e);LinkList ListDelete(LinkList L,in...
参考:http://blog.csdn.net/dazhong159/article/details/7906916百度面试题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数 22 ,如下图二元树:10/512/ \ 47 则打印出两条路径:10, 12和10, 5, 7。#include <stdafx.h>
#include<stdlib.h>
#define MAX 20 struct BiTreeNode
{ int data; struct BiTreeNode *l...
漂流在海上的帆,像极了鲨鱼的鳍 一、数据结构和算法的概述1、数据(data)结构(structure) 是一门研究 组织数据方式 的学科。2、程序 = 数据结构 + 算法3、数据结构 是算法的基础 二、看几个实际编程中遇到的问题 1、关于单链表数据结构publicstaticvoid main(String[] args) {String str = "Java,Java,Java,Hello,World";String newStr = str.replaceAll("Java", "c++");System.out.println(newStr);}问:试写出用单链表标识的...
哈希表的链地址法来解决冲突问题将所有关键字为同义词的记录存储在同一个线性链表中,假设某哈希函数产生的哈希地址在区间[0,
m - 1]上,则设立一个至振兴向量Chain ChainHash[m]; 数据结构//链表结点
typedef struct _tagNode
{int data; //元素值(关键字)struct _tagNode* next; //下一个结点
}Node, *PNode;//哈希表结点
typedef struct _tagHashTable
{//这里用一个联合体来解释一下,其index也即哈希值 u...
一、为什么要有模板?将类型参数化,可以实现算法与类型的分离,编写针对类型更加抽象的函数或者类。 二、函数模板通用定义:template<typename 类型形参1, ...>返回类型 函数模板名 (形参表) { ... }特化定义:template<>返回类型 函数模板名<类型实参1, ...> (形参表) { ... } 三、类模板通用定义:template<typename 类型形参1, ...>class 类模板名 { ... };全类特化:template<>class 类模板名<类型实参1, ...> { ... };成员特...
在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生改变,则称这种排序方法是不稳定的。即所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,则说这种排序算法是稳定的,反之,就是不稳定的。、一、冒泡排序 冒泡排序(BubbleSort)的基本概念是: 个人理解就是将待排序的元素看作...
什么是八皇后问题: 指的是,在一个8 * 8的棋盘中, 放置8个棋子, 保证这8个棋子相互之间, 不在同一行,同一列,同一斜线, 共有多少种摆法?
游戏连接: http://www.4399.com/flash/42643.htm#search3
直接上代码:public class QueueLv8 {int maxSize =8;int[] array = new int[maxSize];static int count = 0;//正解次数static int okCount = 0;//判断次数public static void main(String[] args){//8皇后问题: 指的是,在一个8 * 8的棋盘...
数据结构/算法语言内置内置库线性结构list/tuplearry/collections.namedtuple链式结构collections.deque(双端队列)字典结构dictcollections. Counter/OrderedDict集合结构set/frozenset排序算法sorted二分算法bisect模块堆算法heapq模块缓存算法functools.lru_cache原文:https://blog.51cto.com/12080420/2389067
链表的插入初始条件:1.带有头结点的链表 2.插入位置 i 3.插入的节点Node基本操作:假设p指向某个节点 q指向被插入的节点 则可以执行的是在p之后插入节点 初始化:1.p=L 指向头结点 2.j=1寻找第i-1个结点: while(j<i){ p=p->next; j++; }这样最终指向的是第i-1个结点;i的不同情况:1.i<1 直接跳出 2.1<=i<=length 可以正常执行 3.i=length+1 在链表末尾插入数据 4.i>length+1 出现空指针异...