第一章 引論

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性：對(duì)于大量輸入的運(yùn)算性能的重要性

目錄

• 1.1 本書討論的內(nèi)容
• 1.2 數(shù)學(xué)知識(shí)復(fù)習(xí)
• 1.3 遞歸簡(jiǎn)論
• 1.4 實(shí)現(xiàn)泛型特性構(gòu)件 pre - Java 5
• 1.5 利用Java 5泛性實(shí)現(xiàn)泛型特性成分

1.1 本書討論的內(nèi)容

• 應(yīng)用合理的算法 與 普通的算法解決問(wèn)題的"差異"。

1.1.1 選擇問(wèn)題

設(shè)有一組N個(gè)數(shù)而要確定其中第k個(gè)最大者。我們稱之為選擇問(wèn)題。

• 方法一：
  將這N個(gè)數(shù)讀進(jìn)一個(gè)數(shù)組中，通過(guò)某種簡(jiǎn)單的算法，比如冒泡排序，以遞減順序?qū)?shù)組排序，然后返回位置k上的元素。

   /**
     * 選擇問(wèn)題：設(shè)有一組N個(gè)數(shù)而要確定其中第k個(gè)最大者 方法： 使用冒泡排序，然后返回位置 k-1 上的元素
     */
     @Test
    public void No1_1_1() {
        //獲取全局變量數(shù)組的克隆數(shù)組。
        int array[] = mdzz_array.clone();
        int m = (int) System.currentTimeMillis();
        //排序
        MyUtils.sort(array);
        int k = array.length / 2;
        System.out.println(array[k - 1]);
        //計(jì)算結(jié)束時(shí)間
        int n = (int) System.currentTimeMillis();
        System.out.println(n - m);
    }

• 方法二：
  稍微好一點(diǎn)的算法就可以先把前k個(gè)元素讀入數(shù)組并（以遞減的順序）進(jìn)行排序。接著將剩下的元素逐個(gè)讀入，當(dāng)新元素被讀到時(shí)，如果它小于等于該數(shù)組的第k個(gè)元素則忽略之，否則就將其放到數(shù)組的正確位置上。同時(shí)將數(shù)組中的一個(gè)元素?cái)D出數(shù)組

   /**
     * 第二種方法 先把前k個(gè)元素讀入數(shù)組并(遞減排序).接著將剩下的元素逐個(gè)讀入。
     * 當(dāng)新元素被讀到時(shí)，如果它小于數(shù)組中的第k個(gè)元素則忽略之，否則將其放到數(shù)組中的正確的位置上， 同時(shí)將數(shù)組中的一個(gè)元素?cái)D出數(shù)組。
     */
    // @Test
    public void No1_1_1_2() {
        System.out.println("================================");
        //獲取全局變量數(shù)組的克隆數(shù)組。
        int array[] = mdzz_array.clone();
        int n = (int) System.currentTimeMillis();
        int k = array.length / 2;
        //填充數(shù)組
        int array_copy[] = new int[k];
        for (int i = 0; i < k; i++) {
            array_copy[i] = array[i];
        }
        //排序
        MyUtils.sort(array_copy);
        for (int i = k; i < array.length; i++) {
            if (array[i] > array_copy[array_copy.length - 1]) {
                MyUtils.insertToArray(array[i], array_copy);
            }
        }
        //計(jì)算程序結(jié)束時(shí)間
        int m = (int) System.currentTimeMillis();
        //打印
        System.out.println(array_copy[k - 1]);
        System.out.println(m - n);
    }

全局變量

   static int mdzz_array[];
   static {
   //生成一個(gè)十萬(wàn)長(zhǎng)度的隨機(jī)數(shù)組
       mdzz_array = MyUtils.upSetRandom(100000);
   }

運(yùn)行結(jié)果

image.png

分析

• 當(dāng)數(shù)據(jù)量達(dá)到10w的時(shí)候，兩個(gè)方法都能運(yùn)行出正常結(jié)果，但是方法二時(shí)間明顯小于方法一的時(shí)間
• 當(dāng)數(shù)據(jù)量達(dá)到100w的時(shí)候，兩個(gè)方法都不能在短時(shí)間內(nèi)運(yùn)行出結(jié)果。（肯定會(huì)有更好的方法去解決，這個(gè)放到后面去講解，我暫時(shí)也沒(méi)學(xué)到233333）

1.1.2 解決流行的字謎

image.png

輸入是由一些字母構(gòu)成的一個(gè)二維數(shù)組以及一組單詞組成。目標(biāo)是要找出字謎中的單詞，這些單詞可能是水平的、垂直或沿對(duì)角線上任何方向放置的。
該圖，字謎是由單詞this、two、fat組成。

思路

• 通過(guò)循環(huán)，對(duì)該二維數(shù)組上的每一個(gè)點(diǎn)進(jìn)行遍歷，八個(gè)方向開(kāi)始。如果有形成單詞的，則放到答案隊(duì)列當(dāng)中。
• 改進(jìn)：如果我們知道字典中最小的單詞長(zhǎng)度的話，那么我們遍歷某個(gè)點(diǎn)的某個(gè)方向的時(shí)候，判斷這個(gè)方向構(gòu)成單詞的最大長(zhǎng)度如果小于字典中最小單詞的長(zhǎng)度的話。那么就可以過(guò)濾掉該方向。增加算法的效率。

代碼

本章講解思想，代碼不是很重要，所以這種篇幅過(guò)長(zhǎng)的代碼就放到附件去了。主要是思路，思路對(duì)了代碼沒(méi)多長(zhǎng)時(shí)間就自己敲出來(lái)了。

1.3 遞歸

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。
遞歸的兩個(gè)基本準(zhǔn)則：

• 基準(zhǔn)情形（base case）。必須總要有某些基準(zhǔn)的情形，他們不用遞歸就能求解。
• 不斷推進(jìn)（making progress）。對(duì)于那些要遞歸求解的情形，遞歸調(diào)用必須總能朝著一個(gè)基準(zhǔn)情形推進(jìn)。

1.3.1 案例1、階乘

可能學(xué)遞歸都接觸過(guò)這個(gè)階乘問(wèn)題，這個(gè)問(wèn)題可能有些人都嚼爛了，隨手一打就出來(lái)了。但是，這個(gè)思想還是蠻重要的，化繁為簡(jiǎn)。

public int jiecheng(int n){
        if(n==1||n==0){
            return 1;
        }else{
            return n * jiecheng(n-1);
        }
    }

（↑ 這么簡(jiǎn)單的案例，糊弄誰(shuí)呢）

1.3.2 案例2、全排列

image.png

（對(duì)不起，打擾了）

分析與思路：

• 對(duì)于這個(gè)問(wèn)題，我們首先在紙上畫一畫，大家想的思路應(yīng)該都是，先固定"a",然后輸出"b","c",再將"b","c"交換，之后再輸出"acb"。b，c也是先固定再讓剩下的交換。

  
  
  abc.png
• 那四個(gè)數(shù)呢，"abcd",一樣的，先固定a ,再 固定 b 然后輸出 abcd，交換c d，輸出 abdc 在固定a，c輸出 acbd……

實(shí)現(xiàn)方法：

    @Test
    public void No1_1_4() {
        permute("xyz");
    }

    public void permute(String str) {
        char[] c_str = str.toCharArray();
        permute(c_str, 0, c_str.length - 1);
    }

    public void permute(char[] str, int low, int high) {
        if (low == high) {
            System.out.println(String.valueOf(str));
        } else {
            for (int i = low; i < str.length; i++) {
                swap(str, low, i);
                permute(str, low+1, high);
                swap(str, i, low);
            }
        }
    }
    
    public void swap(char[]str,int i,int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

總結(jié)

本章總體上來(lái)講了算法的一些優(yōu)點(diǎn)，還有一些數(shù)學(xué)和Java的泛型基礎(chǔ)知識(shí)，就不在這里進(jìn)行講解了。

代碼下載

點(diǎn)我下載