数据结构与算法_笔记

有趣的位运算

duchaochen阅读(501)评论(0)赞(0)

有趣的位运算   计算机的终极程序其实只有0和1,转化成集成电路的低电压和高电压来进行存储和运算。如果你是计算机相关专业出身或者是一名软件开发人员即使不对计算机体系结构如数家珍,至少也要达到能够熟练使用位运算的水平,要不然还是称为代码搬运工...

谈谈等概率不重复随机数生成算法中的大学问

duchaochen阅读(501)评论(0)赞(0)

  等概率不重复的生成随机数应该是在平时开发中常见的,也是面试中常问的基础之一。有多种实现方式,有人人都可以想到的,也有不容易想到的巧妙算法,那么当有人问你哪个实现方式更好的时候你该怎么回答呢?回答巧妙的算法比普通算法好?答案显而易见,首先...

面试中的排序算法总结

duchaochen阅读(501)评论(0)赞(0)

前言   查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在面试中最常考的是快速排序和归并...

二分查找的递归和非递归实现

duchaochen阅读(501)评论(0)赞(0)

最近在复习基础知识,下面是二分查找算法的递归和非递归实现: package sortandsearch; /** *@Description:<p>二分查找的递归和非递归算法</p> *@author 王旭 *@ti...

再谈0-1背包问题

duchaochen阅读(501)评论(0)赞(0)

上次解0-1背包问题用的是动态规划法:http://www.cnblogs.com/wxisme/p/4898057.html 这次用回溯法来解。 01背包问题:给定n种物品和一背包。物品i的重量是wi其价值为vi,背包的容量为c。问如何选...

完全背包问题

duchaochen阅读(501)评论(0)赞(0)

问题描述: 有一个容量为c的背包,有n种物品,第i种物品的重量是wi,价值是vi;可以拿走一种物品的全部或者部分。怎样才能使背包装入的物品价值最大? 分析: 与0-1背包不同的是可以装入一种物品的一部分,在0-1背包只能用动态规划的方法来解...

最优二叉查找树

duchaochen阅读(501)评论(0)赞(0)

最优二叉查找树: 给定n个互异的关键字组成的序列K=<k1,k2,…,kn>,且关键字有序(k1<k2<…<kn),我们想从这些关键字中构造一棵二叉查找树。对每个关键字ki,一次搜索搜索到的概...

最长公共子序列问题

duchaochen阅读(501)评论(0)赞(0)

最长公共子序列: 给定一个序列X={x1,x2,x3…xm},另一个序列Z={z1,z2,z3…zk}满足如下条件时称为X的子序列,即存在一个严格递增的X的下标序列<i1...

最大子段和问题

duchaochen阅读(502)评论(0)赞(0)

最大子段和问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a ...

01背包问题

duchaochen阅读(503)评论(0)赞(0)

01背包问题:给定n种物品和一背包。物品i的重量是wi其价值为vi,背包的容量为c。问如何选择装入背包的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有两种选择,即装入或者不装入。不能将物品i装入背包多次也不...