『アルゴリズム導論』第二章demoコード実現(Java版)
12394 ワード
『アルゴリズム導論』第二章demoコード実現(Java版)
前言
夜は心が落ち着かないので、ブログを書いてゆっくりします。囧
『アルゴリズム導論』という神作を拝見して、もちろん練習します。練習問題や思考問題のような理論的思考以外にも、コーディングの実践から切り離せない。
ですから、後の章ごとに、章に関連するアルゴリズムのJavaコードを整理して実現します。
二分割検索
アルゴリズム
泡の並べ替え
アルゴリズム
アルゴリズム
アルゴリズム
このコードの実装は、内容が多いかもしれません。一方は方法抽出(ホイッスルを抽出して作成する操作)によるものであり、一方は練習問題に言及されたホイッスルレスの帰順順が増加したことによるものである。
整理の中でこのハードディスクの操作を増やしたのは、この問題をやって長い間会った面接問題を思い出したからです。つまり、どのように1 Gの空間を使って、8 Gのデータを並べ替えますか?答えは並べ替えです。
この問題はleetcodeに存在します。前のブログでも対応した解析があります。さらにleetcodeには三数の和を求めるというテーマがあります。
アルゴリズム
締め括りをつける
実は、このアルゴリズムのデモは比較的に実現しやすいです。もっと多いのはアルゴリズムを実現する感じを探すことですよね。
コードに何か問題があったら、あるいは何か疑惑があったら、私信か@私を信じてもいいです。
諸君と共に進歩したい。
前言
夜は心が落ち着かないので、ブログを書いてゆっくりします。囧
『アルゴリズム導論』という神作を拝見して、もちろん練習します。練習問題や思考問題のような理論的思考以外にも、コーディングの実践から切り離せない。
ですから、後の章ごとに、章に関連するアルゴリズムのJavaコードを整理して実現します。
二分割検索
アルゴリズム
package tech.jarry.learning.test.algorithms.binarysearch;
public class BinarySearch {
public static int binarySearch(int[] array, int target) {
return binarySearch(array, target, 0, array.length - 1);
}
// ,
public static int binarySearch(int[] array, int target, int startIndex, int endIndex) {
if (endIndex > startIndex) {
int middleIndex = (startIndex + endIndex) / 2;
if (target < array[middleIndex]){
return binarySearch(array, target, startIndex, middleIndex);
} else if (target > array[middleIndex]) {
return binarySearch(array, target, middleIndex + 1, endIndex);
} else if (target == array[middleIndex]) {
return middleIndex;
}
}
return -1;
}
}
アルゴリズムテスト
package tech.jarry.learning.test.algorithms.binarysearch;
public class BinarySearchTest {
public static void main(String[] args) {
int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12};
System.out.println(BinarySearch.binarySearch(testArray, 100));
}
}
結果出力-1
これは、目標データが見つからなかったという意味で、テストクラスの中のtargetを他の数字に変更することができます。泡の並べ替え
アルゴリズム
package tech.jarry.learning.test.algorithms.bubblesort;
public class BubbleSort {
public static int[] bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++){
for (int j = i; j < array.length; j++) {
if (array[j] < array[i]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
}
}
アルゴリズムテスト
package tech.jarry.learning.test.algorithms.bubblesort;
import java.util.Arrays;
public class BubbleSortTest {
public static void main(String[] args) {
int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12};
System.out.println(Arrays.toString(BubbleSort.bubbleSort(testArray)));
}
}
結果出力[0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18]
並べ替えの挿入アルゴリズム
package tech.jarry.learning.test.algorithms.insertsort;
import java.util.Arrays;
public class InsertionSort {
public static int[]insertSort(int[] originArray) {
// ( )
for (int j = 1; j < originArray.length; j++) {
//
int key = originArray[j];
//
int i = j - 1;
// key ( key )
while (i >= 0 && originArray[i] > key) {
originArray[i + 1] = originArray[i];
i = i - 1;
}
// originArray[i] <= key, i+1 ( i+1 , i+2 i+1 )
originArray[i + 1] =key;
}
return originArray;
}
public static int[] insertSortProWithBinarySearch(int[] array) {
// , , , n^2, n*lgn
return null;
}
}
アルゴリズムテスト
package tech.jarry.learning.test.algorithms.insertsort;
import java.util.Arrays;
public class InsertionSortTest {
// test
public static void main(String[] args) {
int[] originArray = new int[]{9, 6, 4, 5, 8};
int[] resultArray = InsertionSort.insertSort(originArray);
System.out.println(Arrays.toString(resultArray));
}
}
結果出力[4, 5, 6, 8, 9]
並べ替えアルゴリズム
このコードの実装は、内容が多いかもしれません。一方は方法抽出(ホイッスルを抽出して作成する操作)によるものであり、一方は練習問題に言及されたホイッスルレスの帰順順が増加したことによるものである。
package tech.jarry.learning.test.algorithms.mergesort;
import java.util.Arrays;
/**
*
*/
public class MergeSort {
public static int[] mergeSort(int[] array) {
return mergeSort(array, 0, array.length - 1);
}
public static int[] mergeSort(int[] array, int startIndex, int endIndex) {
if (startIndex < endIndex) {
int middleIndex = startIndex + (endIndex - startIndex) / 2;
array = mergeSort(array, startIndex, middleIndex);
array = mergeSort(array, middleIndex + 1, endIndex);
// ,
// return merge(array, startIndex, middleIndex, endIndex);
// ,
return noSentinelMerge(array, startIndex, middleIndex, endIndex);
}
// startIndex = endIndex, array
return array;
}
private static int[] merge(int[] array, int startIndex, int middleIndex, int endIndex) {
int[] sentinelLeftArray = createSentinelArray(array, startIndex, middleIndex);
int[] sentinelRightArray = createSentinelArray(array, middleIndex + 1, endIndex);
for (int i = 0, m = 0, n = 0; i < endIndex - startIndex + 1; i++) {
if (sentinelLeftArray[m] < sentinelRightArray[n]) {
// startIndex,
array[startIndex + i] = sentinelLeftArray[m++];
} else {
array[startIndex + i] = sentinelRightArray[n++];
}
// Integer.MAX_VALUE,
}
return array;
}
private static int[] createSentinelArray(int[] array, int startIndex, int endIndex) {
int length = endIndex - startIndex + 1;
int[] sentinelArray = new int[length + 1];
for (int i = 0; i < length; i++) {
sentinelArray[i] = array[startIndex + i];
}
sentinelArray[endIndex - startIndex + 1] = Integer.MAX_VALUE;
return sentinelArray;
}
// p.22_practise2.3-2 ,
private static int[] noSentinelMerge(int[] array, int startIndex, int middleIndex, int endIndex) {
int[] leftArray = createNonSentinelBranchArray(array, startIndex, middleIndex);
int[] rightArray = createNonSentinelBranchArray(array, middleIndex + 1, endIndex);
for (int i = 0, m = 0, n = 0; i < endIndex - startIndex + 1; i++) {
if (leftArray[m] < rightArray[n]) {
array[startIndex + i] = leftArray[m++];
if (m == leftArray.length) {
// rightArray array
array = branchArray2Array(array, startIndex + i + 1, rightArray, n);
break;
}
} else {
array[startIndex + i] = rightArray[n++];
if (n == rightArray.length) {
// leftArray array
array = branchArray2Array(array, startIndex + i + 1, leftArray, m);
break;
}
}
// Integer.MAX_VALUE,
}
return array;
}
private static int[] createNonSentinelBranchArray(int[] array, int startIndex, int endIndex) {
int length = endIndex - startIndex + 1;
int[] branchArray = new int[length];
for (int i = 0; i < length; i++) {
branchArray[i] = array[startIndex + i];
}
return branchArray;
}
private static int[] branchArray2Array(int[] array, int targetIndex, int[] branchArray, int startIndex) {
while (startIndex < branchArray.length) {
array[targetIndex++] = branchArray[startIndex++];
}
return array;
}
// ( ), 。
private static void merge2Disk(int[] array, int startIndex, int middleIndex, int endIndex){
int[] sentinelLeftArray = createSentinelArray(array, startIndex, middleIndex);
int[] sentinelRightArray = createSentinelArray(array, middleIndex + 1, endIndex);
for (int i = 0, m = 0, n = 0; i < endIndex - startIndex + 1; i++) {
if (sentinelLeftArray[m] < sentinelRightArray[n]) {
Disk.store(sentinelLeftArray[m++]);
} else {
Disk.store(sentinelRightArray[n++]);
}
// Integer.MAX_VALUE,
}
}
// test_creatreSentinelArray
public static void main(String[] args) {
int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0};
System.out.println(Arrays.toString(createSentinelArray(testArray, 0 , 2)));
}
}
補足:上記コードに係るDisk類整理の中でこのハードディスクの操作を増やしたのは、この問題をやって長い間会った面接問題を思い出したからです。つまり、どのように1 Gの空間を使って、8 Gのデータを並べ替えますか?答えは並べ替えです。
package tech.jarry.learning.test.algorithms.mergesort;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* ,
*/
public class Disk {
private static List diskIntegerInstance = new ArrayList<>();
public static void store(int element) {
diskIntegerInstance.add(element);
}
public static void printAll() {
Iterator integerIterator = diskIntegerInstance.iterator();
while (integerIterator.hasNext()) {
System.out.println(integerIterator.next());
}
}
}
アルゴリズムテスト
package tech.jarry.learning.test.algorithms.mergesort;
import java.util.Arrays;
public class MergeSortTest {
public static void main(String[] args) {
int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12};
// 3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12
// correct result: [0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18]
int[] resultArray = MergeSort.mergeSort(testArray);
System.out.println(Arrays.toString(resultArray));
}
}
結果出力[0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18]
両数の和を固定値とするこの問題はleetcodeに存在します。前のブログでも対応した解析があります。さらにleetcodeには三数の和を求めるというテーマがあります。
アルゴリズム
package tech.jarry.learning.ch2.algorithms.twosum;
import tech.jarry.learning.ch2.algorithms.mergesort.MergeSort;
public class TwoSum {
// , index。 , index , binarySearch
public static boolean twoSum(int[] array, int target) {
array = MergeSort.mergeSort(array);
for (int i = 0; i < array.length; i++) {
int branchTarget = target - array[i];
// lgn
if (binarySearch(array, branchTarget)) {
return true;
}
}
return false;
}
private static boolean binarySearch(int[] array, int target) {
return binarySearch(array, target, 0, array.length - 1);
}
private static boolean binarySearch(int[] array, int target, int startIndex, int endIndex) {
if (endIndex > startIndex) {
int middleIndex = (endIndex + startIndex) / 2;
if (target < array[middleIndex]) {
return binarySearch(array, target, startIndex, middleIndex);
} else if (target > array[middleIndex]) {
return binarySearch(array, target, middleIndex + 1, endIndex);
} else if (target == array[middleIndex]) {
return true;
}
}
return false;
}
}
アルゴリズムテスト
package tech.jarry.learning.test.algorithms.twosum;
public class TwoSumTest {
public static void main(String[] args) {
int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12};
int target = 80;
System.out.println(TwoSum.twoSum(testArray, target));
}
}
結果出力false
本の中のデモは出力の有無だけを要求しますので、leetcodeの類似の問題は二つの要素のindexを返します。興味がある友達は、私が以前書いたleetcodeに関する2つの数と解法に関するブログを見ることができます。締め括りをつける
実は、このアルゴリズムのデモは比較的に実現しやすいです。もっと多いのはアルゴリズムを実現する感じを探すことですよね。
コードに何か問題があったら、あるいは何か疑惑があったら、私信か@私を信じてもいいです。
諸君と共に進歩したい。