BRCOCOLI-CSDN博客

原创算法第四版 2.3.20

package Cap2_3;import java.util.Stack;import Cap2_1.SortTemplate;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class Quick extends SortTemplate{ pu

2017-09-12 19:47:57 518

原创算法第四版 2.3.18

package Cap2_3;import edu.princeton.cs.introcs.StdDraw;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;import Cap2_1.SortCompare;import Cap2_1.SortTemplate;pub

2017-09-12 19:12:03 670 1

原创算法第四版 2.3.17

题目提示直接告诉我们了有两种情况：1.排序的数列包含a.length-1, 因为右边存在最大了，所以无需判断边界2.排序的子数列的右边一位是上一次排序的v，肯定比他小，所以也无需判断边界package Cap2_3;import Cap2_1.SortTemplate;import edu.princeton.cs.introcs.StdOut;import edu

2017-09-12 18:58:45 784

原创算法 2.3.15 螺丝和螺帽

借鉴快速排序的思想（就是你找的时候，顺便以此大小分为大小两堆嘛）先拿一个螺帽，再将所有的螺丝全试一遍将小的堆在左手边将大的堆在右手边这样可以完成一个螺丝根据匹配的螺丝，再将所有的螺帽全试一遍将小的堆在左手边将大的堆在右手边重复这两步螺丝和螺帽就会根据大小分为一堆一堆

2017-09-12 17:05:17 4795 1

原创算法第四版 2.3.9

当只有一个元素时：i和j扫描所有的元素（从lo到hi），比较了2*（hi-lo），交换了 j和v然后递归到下一层当只有2,3个元素时：i和j和普通快速搜索无差异，只不过跳过了很多重复的元素，浪费了很多时间，并且递归下去时也会出现全是重复相同的元素，很浪费时间

2017-09-12 16:47:34 401

原创算法第四版 2.3.8

大概是1.2*N*lnNpackage Cap2_3;import Cap2_1.SortTemplate;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class Quick extends SortTemplate{ private sta

2017-09-12 16:39:21 349

原创算法第四版 2.3.7

把通过统计可以得出，他们的大小是与N存在一定比例的关系package Cap2_3;import Cap2_1.SortTemplate;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class Quick extends SortTempl

2017-09-12 16:24:14 342

原创算法第四版 2.3.6

package Cap2_3;import edu.princeton.cs.introcs.StdDraw;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;import Cap2_1.SortCompare;import Cap2_1.SortTemplate;pub

2017-09-12 16:03:36 396

原创算法第四版 2.3.5

package Cap2_3;import edu.princeton.cs.introcs.StdRandom;import Cap2_1.sortTemplate;public class Quick3way extends sortTemplate{ public static void sort(Comparable[] a){ StdRandom.shuffle(a);

2017-09-12 15:29:21 993

原创算法第四章 2.2.9 | 2.2.11

package Cap2_2;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;import Cap2_1.Insertion;import Cap2_1.sortTemplate;public class MergeModify extends sortTemplate{

2017-09-11 18:04:20 265

原创算法第四版 2.2.8

由图可知，排序有序数组为线性的package Cap2_2;import edu.princeton.cs.introcs.StdDraw;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;import Cap1.Stopwatch;import Cap2_1.Selec

2017-09-11 12:55:49 363

原创算法第四版 2.2.6

package Cap2_2;import edu.princeton.cs.introcs.StdDraw;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;import Cap1.Stopwatch;import Cap2_1.Selection;import Cap2

2017-09-11 12:48:37 347

原创算法第四章 2.1.32

package Cap2_1;import Cap1.Stopwatch;import edu.princeton.cs.introcs.StdDraw;import edu.princeton.cs.introcs.StdRandom;public class Insertion extends sortTemplate{ public static void sort(Compa

2017-09-10 13:43:59 204

原创算法第四版 2.1.25 不需要交换的插入排序

public static void sort(Comparable[] a){ int N = a.length; for(int i=1;i<N;i++){ Comparable temp = a[i]; int j; for(j=i-1;j>=0 && less(temp, a[j]); j--){ a[j+1] = a[j]; } a[j+1]

2017-09-09 21:27:09 2705 2

原创算法第四版 2.1.18 可视轨迹

package Cap2_1;import edu.princeton.cs.introcs.StdDraw;import edu.princeton.cs.introcs.StdRandom;public class Insertion extends sortTemplate{ public static void sort(Comparable[] a){ int N = a

2017-09-09 21:11:48 629

原创算法第四版动画 2.1.17

package Cap2_1;import edu.princeton.cs.introcs.StdArrayIO;import edu.princeton.cs.introcs.StdDraw;import edu.princeton.cs.introcs.StdRandom;import edu.princeton.cs.introcs.StdStats;public class

2017-09-09 21:04:42 501

原创算法第四版 2.1.14 出列排序

说说你会如何将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。思路：模仿冒泡排序冒泡排序是移动i（即数组指针），而我们可以通过移动数组来近似实现我们可以固定交换前两个，移动数组package Cap2_1;import edu.princeton.cs.introcs.StdIn;import ed

2017-09-09 19:03:19 698

原创算法第四版 2.1.12

package Cap2_1;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class Shell { private static int cnt; public static void sort(Comparable[] a){ int N =

2017-09-09 16:44:47 565

原创算法第四版 1.4.22 仅用加减实现的二分查找

利用裴波那契数列来分区间 public static boolean MihaiPatrascuSearch(int[] a, int key){ Arrays.sort(a); int F1=1, F2=1; while(F2<=a.length){ int temp=F2; F2 = F1+F2; F1 = temp; } int lo = 0, hi

2017-09-07 16:38:08 678 1

原创算法第四版 1.4.20 双调查找

题目要求 lgN级别的复杂度一开始根本想不到，只能想到最简单的遍历 N复杂度后来收到1.4.18启发，只要数组局部最大元素只有一个，就说明这是双调数组复杂度lgN public static int Pro1_4_20(int[] a, int lo, int hi){ //[lo,hi) if(hi-lo<3) return 0; int mid = lo + (hi

2017-09-07 15:25:10 596

原创算法第四版 1.4.18

分治法 public static int Pro1_4_18(int[] a, int lo, int hi){ //[lo,hi) if(hi-lo<3) return 0; int mid = lo + (hi-lo)/2; if(a[mid-1]>a[mid]&&a[mid+1]>a[mid]) return mid; int Left = Pro1_4_18(a, l

2017-09-07 13:21:20 766

原创算法 1.4.17

public static double Pro1_4_17(double[] a){ double[] temp = a.clone(); for(int i=0;i<temp.length;i++) if(temp[i]<0) temp[i]=-temp[i]; Arrays.sort(temp); return temp[temp.length-1] - temp[0]

2017-09-07 12:58:21 326 1

原创算法第四版 1.4.16

public static double Pro1_4_16(double[] a){ double[] temp = a.clone(); for(int i=0;i<temp.length;i++) if(temp[i]<0) temp[i]=-temp[i]; Arrays.sort(temp); double ans = Double.MAX_VALUE; for

2017-09-07 12:57:35 540 2

原创算法 1.4.15 快速3-sum

我只考虑数组中并未存在重复的元素O(N) 只要把数组全部扫一遍就好了 public static int TwoSumFast2(int[] a){ // O N Arrays.sort(a); int cnt=0; int left = 0, right = a.length-1; while(left<right){ if(a[left]+a[right]==0)

2017-09-07 11:57:35 896 2

原创算法第四版 1.4.14 4-sum

N^3 log N public static int FourSumFast(int[] a){ Arrays.sort(a); int N = a.length; int cnt = 0; for(int i=0;i<N;i++) for(int j=i+1;j<N;j++) for(int z=j+1;z<N;z++) if(BinarySearc

2017-09-07 11:55:59 545

原创算法第四版 1.4.12

int N=20; int[] a = new int[N]; int[] b = new int[N]; for(int i=0;i<N;i++){ a[i]=(int)(StdRandom.random()*50); b[i]=(int)(StdRandom.random()*50); } Arrays.sort(a); Arrays.sort(b);

2017-09-06 20:20:26 475

原创算法 1.3.47 可连接的队列

public void catenation(Stack that){ for(Item i:that) push(i);}public void catenation(Steque that){ for(Item i:that) enqueue(i);}public void catenation(Queue that){ for(Item i:that) en

2017-09-05 16:30:17 315 1

原创算法 1.3.46 栈的可生成性问题

即禁止栈中出现a所以对每个要入栈的元素进行判断，如果栈中有两个比他小的元素则禁止入栈判断栈中的两个最小的元素：1.在每次push的时候全部遍历一遍，复杂度O(n)2.类中维护两个变量min1，min2，分别表示最小，次小，那么在每次push时候更新这两个变量，复杂度O(1)在每次pop的时候更新这两个变量，有:

2017-09-05 16:20:40 561

原创算法 1.3.45 栈的可生成性

package Cap1;import edu.princeton.cs.introcs.StdArrayIO;import edu.princeton.cs.introcs.StdOut;public class StackProblem { /** * 算法 1.3.45 栈的可生成性 */ public static boolean problem1(String[

2017-09-05 15:59:54 751

原创算法 1.3.44 文本编辑器的缓冲区

package Cap1;import java.util.Iterator;import edu.princeton.cs.introcs.StdOut;public class Buffer implements Iterable{ Stack front = new Stack(); // 光标前面的 Stack after = new Stack(); // 光标后面的

2017-09-05 11:39:21 709

原创算法第四版 1.3.43 文件列表

package Cap1;import java.io.File;import edu.princeton.cs.introcs.StdOut;public class MyListFiles { /** * @param args */ public static void listAllFiles(String path, int dep){ File f = n

2017-09-05 10:57:36 772 1

原创算法 1.3.41 | 1.3.42 复制栈复制队列

public Stack(Stack that){ Stack temp = new Stack(); for(Item i:that){ temp.push(i); } for(Item i:temp){ push(i); } }public Queue(Queue that){ for(Item i:that) enqueue(i);}

2017-09-04 19:42:15 805

原创算法第四版 1.3.40 前移编码

package Cap1;import edu.princeton.cs.introcs.StdOut;public class MoveToFront { /** * @param args */ private Node first; private int N; private class Node{ Item item; Node next; } pu

2017-09-04 19:29:30 700

原创算法第四版 1.3.39 环形缓冲区

public class RingBuffer { /** * @param args */ private Item[] a; private int first=0, last=0; public RingBuffer(int N){ a = (Item[]) new Object[N]; } public boolean isEmpty(){ return firs

2017-09-04 16:39:48 793

原创算法 1.3.35 RandomQueue

package Cap1;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class RandomQueue { /** * @param args */ private Item[] a = (Item[]) new Object[1]; pr

2017-09-04 16:03:22 410

原创算法第四版 1.3.34 RandomBag

要保证完全随机，可以用StdRandom.shuffle(Object[] o)该函数源代码如下： /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throw

2017-09-04 15:29:47 692

原创算法第四版 1.3.33 ResizingArrayDeque

package Cap1;import java.util.Iterator;import edu.princeton.cs.introcs.StdOut;public class ResizingArrayDeque implements Iterable { private Item[] a = (Item[]) new Object[1]; private int N =

2017-09-04 12:47:20 332

原创算法第四版 1.3.32 Steque

package Cap1;import java.util.Iterator;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class Steque implements Iterable{ /** * @param args */ pri

2017-09-04 10:30:30 310

原创《算法（第四版）》1.3.31 双向链表

package Cap1;import java.util.Iterator;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class DoubleNode implements Iterable { /** * @param args */

2017-09-02 16:03:24 334

原创《算法（第四版）》 1.3.29 环形链表

package Cap1;import java.util.Iterator;import edu.princeton.cs.introcs.StdOut;import edu.princeton.cs.introcs.StdRandom;public class CircleQueue implements Iterable{ /** * @param args */

2017-09-02 14:32:26 264

空空如也

空空如也