Codeforces Round #345 (Div. 1) C. Table Compression

原题C. Table Compressiotime limit per tes4 secondmemory limit per tes256 megabyteinpustandard inpuoutpustandard outpuLittle Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.Petya decided to compress tables. He is give... Read More

深度优先搜索之栈解迷宫(C++)

在之前的一篇关于搜索的文章中《广度优先搜索算法队解迷宫问题》有提到深度优先搜索(dfs)算法,其中有一种就是本篇文章提到的实现方法:利用栈解迷宫;《广度优先搜索算法队解迷宫问题》中利用栈解迷宫有一个bug,比如:在x点出发,向右走直到尽头回到x点,此时在向其他方向(比如上),那么不能再走曾经向右走过的路(坐标)。这次,我们增加一个direct_mark数组,来标记在每一个坐标上曾经走过的方向。程序范例[code lang="cpp"/** 栈解迷宫 - 深度优先搜索.* @authur genialx <admin@ihuxu.com>*#include <iostr#include <st#define LEFT #define RIGHT #define UP #define DOWN using namespace std;struct Path int x;... Read More

分治法解矩阵乘积

题目假设有A,B两个矩阵,且其均为n*n维矩阵,n为2的幂(n>=2)。求A与B的乘积。分治法解矩阵乘积通过上图我们可以看到书中的利用分治法解决的伪代码。解决思路一暴力解法时间复杂度O(n^3程序范例void solve_matrix_multiply_n3(int a[][MATRIX_LENGTH], int b[][MATRIX_LENGTH], int c[][MATRIX_LENGTH]for (int i = 0; i < MATRIX_LENGTH; i++) for (int j = 0; j < MATRIX_LENGTH; j++) for (int k = 0; k < MATRIX_LENGTH; k++) c[i][j] += a[i][k] * b[j][k];解决思路二利用分治法解决矩阵乘积程序范例void solve_matrix_mul... Read More

动态规划解决最大子数组问题

问题Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4]the contiguous subarray [4,−1,2,1] has the largest sum = 6.问题来自于Leetcode:Maximum Subarra解决方式利用动态规划思想来解决最大子数组问题。之前的文章有写过有关动态规划的思路。如果你对动态规划不清楚可以通过这篇文章来简单了解下,里面有相应的视频还是不错的:拆分集合为两个和相等的子集合问题(动态规划)。该方法相对于分治法策略解决最大子数组问题来解决的时间复杂度中会有很大提升。时间复杂度O(n程序范例... Read More

分治法策略解决最大子数组问题

问题描述Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4]the contiguous subarray [4,−1,2,1] has the largest sum = 6.问题来自于Leetcode:Maximum Subarra解决方式利用分治策略来解决最大子数组问题时间复杂度O(nlgn程序范例[code lang="cpp"#include <iostr#include <cstdusing namespace std;int find_max_crossing_subarray(int* a, int... Read More

LeetCode OJ Algorithm – Sliding Window Maximum(hard)

原题Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.For exampleGiven nums = [1,3,-1,-3,5,3,6,7], and k = 3.Window position Ma--------------- ----[1 3 -1] -3 5 3 6 7 1 [3 -1 -3]... Read More

LeetCode OJ Algorithm – reverse linked list ii (medium)

原题Reverse a linked list from position m to n. Do it in-place and in one-pass.For exampleGiven 1->2->3->4->5->NULL, m = 2 and n = 4return 1->4->3-&gNoteGiven m, n satisfy the following condition1 ≤ m ≤ n ≤ length of list.地址https://leetcode.com/problems/reverse-linked-list-ii程序范例[code lang="cpp"/** Definition for singly-linked list.* struct ListNode * int val;* ListNode *next;* ... Read More

数据结构与算法之线性表

上一篇《数据结构与算法(一),概述》中介绍了数据结构的一些基本概念,并分别举例说明了算法的时间复杂度和空间复杂度的求解方法。这一篇主要介绍线性表。本节内容一、基本概念二、顺序表三、链表1、单向链表2、单向循环链表3、双向链表4、静态链表一、基本概念线性表是具有零个或多个数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的基本特征第一个数据元素没有前驱元素;最后一个数据元素没有后继元素;其余每个数据元素只有一个前驱元素和一个后继元素。抽象数据类型线性表一般包括插入、删除、查找等基本操作。其基于泛型的API接口代码如下[code lang="java"public interface List<//线性表的大小int size();//判断线性表是否为空boolean isEmpty();void clear();... Read More

广度优先搜索算法队解迷宫问题

面对迷宫问题,求解路径一共有三种方式。分别为:栈解迷宫(深度优先搜索)、递归法(深度优先搜索)与本文提到的队解迷宫(广度优先搜索),有兴趣可以参阅这篇文章。其中,栈指的是堆栈,队指的是队列。搜索中,利用了其堆栈的先进后出和队列的先进先出的特性。其中,前两种算法无法直接求出最短路径,而广度优先搜索会直接求出其最短路径。下面来具体讨论下队解迷宫的问题。问题这个迷宫问题的解答,主要参考了《LINUX一站式编程》中的第12章“栈与队列”的正文和习题。假设有这样一个迷宫,用一个5*5的数组来表示,其中0表示有路可走,1表示无路可走。那么,如何找到一个通路,使得可以从左上角的(0,0)点走到右下角的(4,4)点?迷宫搜索过程其中2代表已经走过的路,故观察2的覆盖流程即算法的运行流程。2 1 0 0 2 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 *********... Read More

插入排序(Insertion Sort)

在上篇文章介绍的并归排序(Merge Sort)后,再来了解下插入排序。简介插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。分类排序算法数据结构数组最差时间复杂度最优时间复杂度平均时间复杂度最差空间复杂度总共 ,需要辅助空间记载最早拥有排序概念的机器出现在1901至1904年间由Hollerith发明出使用基数排序法的分类机,此机器系统包括打孔,制表等功能,1908年分类机第一次应用于人口普查,并且在两年内完成了所有的普查数据和归档。 Hollerith在1896年创立的分类机公司的前身,为电脑制表记录公... Read More

分治法的经典运用归并排序(Merge Sort)

简介归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。分类排序算法数据结构数组最差时间复杂度最优时间复杂度平均时间复杂度最差空间复杂度归并操作归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。迭代法申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列设定两个指针,最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针到达序列尾将另一序列剩下的所有元素直接复制到合并序列尾递归法原理如下(假设序列共有n个元素)... Read More

机器学习优化算法之爬山算法小结

 简言机器学习的项目,不可避免的需要补充一些优化算法,对于优化算法,爬山算法还是比较重要的.鉴于此,花了些时间仔细阅读了些爬山算法的paper.基于这些,做一些总结. 目录1. 爬山算法简单描述2. 爬山算法的主要算法2.1 首选爬山算法2.2 最陡爬山算法2.3 随机重新开始爬山算法2.4 模拟退火算法(也是爬山算法3. 实例求解 正文爬山算法,是一种局部贪心的最优算法. 该算法的主要思想是:每次拿相邻点与当前点进行比对,取两者中较优者,作为爬坡的下一步.举一个例子,求解下面表达式的最大值. 且假设 x,y均按为0.1间隔递增.为了更好的描述,我们先使用pyhton画出该函数的图像图像的python代码[code lang="python"# encoding:utffrom matplotlib import pyplot as plimport numpy as nfr... Read More

拆分集合为两个和相等的子集合问题(动态规划)

题意问题描述:将1到N的连续整数组成的集合划分为两个子集合,且保证每个集合的数字和相等。例如,对于N=4,对应的集合{1,2,3,4},能被划分为{1,4}、{2,3}两个集合,使得1+4=2+3,且划分方案只有此一种。编程实现给定任一正整数N(1<=N<=39),输出其符合题意的划分方案数。样例输入1:样例输出1:1    (可划分为{1,2}、{3}样例输入2:样例输出2:1    (可划分为{1,3}、{2,4}样例输入3:样例输出3:4    (可划分为{1,6,7}、{2,3,4,5},或{1,2,4,7}、{3,5,6},或{1,3,4,6}、{2,5,7},或{1,2,5,6}、{3,4,7}思路根据动态规划思想,可以得到状态转移方程如下[code lang="php"$d[$i][$j] = $d[$i - 1][$j] + $d[$i - 1][$j - $... Read More

Codeforces Round #345 (Div. 1) B Image Preview

原题B. Image Previetime limit per test1 seconmemory limit per test256 megabyteinputstandard inpuoutputstandard outpuVasya's telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last ... Read More

Codeforces Round #345 (Div. 1) A watchmen

原题A. Watchmetime limit per tes3 secondmemory limit per tes256 megabyteinpustandard inpuoutpustandard outpuWatchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are n watchmen on a plane, the i-th watchman is located at point (xi, yi).They need to arrange a plan, but there are some difficulties on their way. As yo... Read More