liuyubobobo / play-with-algorithms

Codes of my MOOC Course <Play with Algorithms>, Both in C++ and Java language. Updated contents and practices are also included. 我在慕课网上的课程《算法与数据结构》示例代码，包括C++和Java版本。课程的更多更新内容及辅助练习也将逐步添加进这个代码仓。

北京人儿，毕业后在北京创业，现旅居美国，自由职业，持续学习者。热爱算法，游戏和游戏编程，前端以及苹果开发。喜欢研究让人头疼的基础问题和数学问题，对一切艺术形式感兴趣。

如果你想找到我，欢迎光临我的公众号【是不是很酷】（见最下二维码）；逛逛我的知识星球【是不是很酷（免费） 】；或者在知乎关注我：）

我的教程

收费课程 算法和数据结构体系课程 课程 玩转图论算法 课程 | 代码仓 看得见的算法 课程 | 代码仓 C++ 算法和数据结构 课程 | 代码仓 C++ 玩转算法面试 课程 | 代码仓 Python 3 入门机器学习 课程 | 代码仓 专给程序员设计的线性代数 课程 | 代码仓 还有一个神秘课程，正在设计中：）

免费课程 玩转数据结构 已下架 | 代码仓 玩儿转 Swift 2.0 S01, S02, S03, S04 | 代码仓 炫丽的倒计时 Canvas 绘图与动画基础 课程 Canvas 绘图详解 课程 Canvas 玩儿转图像处理 课程 Canvas 应用：学写一个字 Canvas 应用：玩儿转红包照片 | 代码仓 其他前端相关：CSS3 3D 特效, 2048 游戏制作

其他

我的文字 公众号文章备份 【是不是很酷】开源分享文字备份 AI 学习路径 & 资源分享 我的知识星球（免费）

我打比赛 Leetcode 题解 Google Foobar Advent of Code Project Euler

杂七杂八 C++ 绘制心型曲线 Swift 重力感应 Demo Google Material Design Colors in Swift Swift NASDate 教程

私有代码仓里的神秘项目，就不能公开了：）👻

play-with-algorithms's Issues

5.8节二分搜索树remove操作部分代码优化

Hi，刘老师！关于5-8节二分搜索树的remove操作，在左右两个子节点都存在的情况下，删除该节点，貌似有一种更合理的方式。

• 您的代码：

  Node* successor = new Node(minimum(node->right));
  count++;
  successor->right = removeMin(node->right);
  successor->left = node->left;
  delete node;
  count--;
  return successor;

• 我的代码：
  Node* minNodeInRightChildTree = minimum(node->right); //找到替代节点
  //用替代节点的属性覆盖node，起到更新node节点的作用
  node->key = minNodeInRightChildTree->key;
  node->value = minNodeInRightChildTree->value;
  node->right = removeMin(node->right);
  return node; //将该节点返回

• 性能分析：
  我的代码不需要新建Node，也不需要delete过程。比起你的代码，

1. 少了一次动态空间的分配和释放
2. 少了count一加一减过程
3. 少了左节点指针left的复制
4. 多了key和value的单独复制
   综上，在批量remove的场景下，我的代码性能也许更优。

班门弄斧，请多指教@…@

IndexMaxHeap问题

   // 获取最大索引堆中索引为i的元素
    public Item getItem( int i ){
        assert i + 1 >= 1 && i + 1 <= capacity;
        return data[i+1];
    }

获取最大索引堆中索引为 i 的元素，应该是data[indexes[i+1]]吧

C++生成随机数

1. 0 <= rand() < RAND_MAX
2. 0 <= rand() % (rangR - rangL) < rangR - rangL
3. 1 <= rand() % (rangR - rangL + 1) < rangR - rangL + 1
4. rangL + 1 <= rand() % (rangR - rangL + 1) + rangL < rangR + 1
   是不是写的有点问题呢？

代码结构问题

希望能把java和c++的代码分开整理两个项目中，现在的结构导入到IDE中非常不便，感谢~

对swift性能的疑虑

我使用swift实现了一个选择排序，发现它的性能比C++实现差了100多倍，是不是swift中Array是值类型的原因？我使用标准库中排序方法(array = array.sorted(by: <)),仅耗时0.013734 s
c++ SelectionSort : 0.116541 s
swift SelectionSort: 13.858506 s

swift 选择排序的实现:
func selectSort<T:Comparable>(array: inout [T]){
let n = array.count
for i in 0 ..< n{
var minIndex = i
for j in i ..< n{
if array[j] < array[minIndex] {
minIndex = j
}
}
if i != minIndex {
swap(&array[i], &array[minIndex])
}
}
}

5.4二分查找树的查找一节的Java源码问题

在main函数的末尾，
if( i < N ) assert res == Integer.toString(i); else assert res == null;
是不是应该改成
if( i < N ) assert res.equals(Integer.toString(i)); else assert res.equals(null);
更合适一些呢？

LinkedList的add和pop方法不能实现队列的效果

Play-with-Algorithms/07-Graph-Basics/Course Code (Java)/Chapter-07-Completed-Code/src/bobo/algo/ShortestPath.java 这个文件的34行创建了一个LinkedList，作为队列使用。但是add和pop方法不能实现队列的效果，应该是使用add和poll。

BST后继的子函数递归时有笔误

https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-06-Predecessor-and-Successor-in-BST/main.cpp 的475行

Node* tempNode = predecessorFromAncestor(node->left, key);

应该是
Node* tempNode = successorFromAncestor(node->left, key);

选择排序的优化。

优化思路：同时选择最大和最小的值,是一个常数级的优化。

public class SelectionSortDouble {

    //SelectionSortDouble不允许产生实例
    private SelectionSortDouble() {
    }

    public static void sort(Comparable[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int min = left;
            int max = right;
            for (int i = left; i <= right; i++) {
                //遍历left到right之间，寻找最小和最大的数的索引
                if (arr[i].compareTo(arr[min]) < 0) min = i;
                if (arr[i].compareTo(arr[max]) > 0) max = i;
            }
            swap(arr, right, max);
            //由于这里最小值所在索引的数可能刚好和最大值做了交换，故此要修正min的值
            if (min == right) min = max;
            swap(arr, left, min);
            right--;
            left++;
        }

    }

    private static void swap(Comparable[] arr, int i, int j) {
        Comparable t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

索引堆的反向查找

在有反向查找的索引堆，shiftup的过程中
reverse[indexes[k]]=k和reverse[indexes[k/2]]=k/2
这两个步骤不能想明白原理，希望得到解答。
谢谢

ifstream file(filename); 这里file好像创建不成功

macOS 10.12.1下，CLion2016.3.5；图中，ReadGraph读取文件内容；ifstream file(filename); 这里file好像创建不成功，文件打开也是失败的；是因为路径的问题吗....

您好，归并求逆序对问题

你的方式会让相同的数也会算一对，怎么避免计算这个相同的数对呢？
我在if else把 aux[i - l] < aux[j - l] 改成 > ... 并且添加了处理相同数的else .
但是出现了更大的问题（很多数对不被计算 了）
请问该怎么处理呢？谢谢 :)

js插入排序优化后反而变慢了，和语言底层实现有关吗？

老师，请问js插入排序优化后反而变慢了，和语言底层实现有关吗。

// 优化前代码
const randomArr = require('./randomArr')

function insertionSort(arr) {
	for (let i = 1, len = arr.length; i < len; i++) {
		let _temp = null
		for (let j = i; j > 0; j--) {
			if (arr[j] < arr[j - 1]) {
				// 交换比较元素和被比较元素
				_temp = arr[j]
				arr[j] = arr[j - 1]
				arr[j - 1] = _temp
			} else {
				break
			}
		}
	}
}
module.exports = insertionSort


// 优化后的代码
const randomArr = require('./randomArr')
const insertionSort1 = (arr) => {
	for (let i = 1, len = arr.length; i < len; i++) {
		let _temp = arr[i]
		let j
		for (j = i; j > 0; j--) {
			if (_temp < arr[j - 1]) {
				arr[j] = arr[j - 1]
			} else {
				break
			}
		}
		arr[j] = _temp
	}
}


module.exports = insertionSort1

测试普遍是优化后的代码要慢，100000个 1-10000的数，接近的数也一样。

优化前sort: 2.075ms
优化后sort: 2.497ms

随机数生成文件

// randomArr.js
let arr = []

// 生成随机数 n 项， 从x到y
// 5-10   0 - 1
const range = (n, x, y) => {
	for (let i = 0; i < n; i++) {
		let random = parseInt(Math.random() * (y - x) + x)
		arr.push(random)
	}
}

range(100000, 1, 10000)
module.exports = arr

性能测试文件

//  performance.js
const randomArr = require('./randomArr')
const selectionSort = require('./selectionSort')
const insertionSort = require('./insertionSort')
const insertionSort1 = require('./insertionSort1')
const mergeSort = require('./mergeSort')

const performanceSort = (fn, arr) => {
	console.time('sort')
	fn(arr)
	console.timeEnd('sort')
}


performanceSort(insertionSort1, randomArr)
performanceSort(insertionSort, randomArr)

最大堆的插入自动扩展容量补充

老师看看O不OK？

//往堆中添加一个元素
	public void insert(Item item){
		if(count+1 >= capacity){
			int newCapacity = 1;
			if(capacity <= 1)
				newCapacity = 2;
			else
				newCapacity = capacity + (capacity>>1);
			data = Arrays.copyOf(data, newCapacity);
			capacity = newCapacity;
		}
		data[count+1] = item;
		count++;
		shiftUp(count);
	}

用快速排序算法进行接近有序数据的问题

用未做优化的快速排序对一百万的数据进行排序，随机性大的数据排序没有问题，但接近有序的数据排序会出现栈溢出的错误。同时，若把数据规模调成十万，就没有问题了。自己没有分析出问题所在，应该不是JVM内存或机子配置的问题，因为我同时用其他算法排序同等级别的数据时也不会报错。还请算法大神们帮忙看看，多谢~~

控制台信息如下：

Test for random array, size = 1000000 , random range [0, 1000000]
MergeSortOpt : 355ms
QuickSort : 242ms

Test for nearly ordered array, size = 1000000 , swap time = 100
MergeSortOpt : 121ms
java.lang.reflect.InvocationTargetException
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:606)
	at generateTestCase.SortTestHelper.testSort(SortTestHelper.java:79)
	at test.testMain.main(testMain.java:72)
Caused by: java.lang.StackOverflowError
	at sortingAdvance.quickSort.QuickSort.partition(QuickSort.java:30)
	at sortingAdvance.quickSort.QuickSort.sort(QuickSort.java:41)
	at sortingAdvance.quickSort.QuickSort.sort(QuickSort.java:42)
	at sortingAdvance.quickSort.QuickSort.sort(QuickSort.java:42)
	at sortingAdvance.quickSort.QuickSort.sort(QuickSort.java:42)
	at sortingAdvance.quickSort.QuickSort.sort(QuickSort.java:42)
	at sortingAdvance.quickSort.QuickSort.sort(QuickSort.java:42)
	at sortingAdvance.quickSort.QuickSort.sort(QuickSort.java:42)
        ········

代码基本上是拷贝过来的，如下：

private static int partition(Comparable[] arr, int l, int r){

        Comparable v = arr[l];

        // 注意初始条件
        int j = l; 
        // arr[l+1...j] < v ; arr[j+1...i) > v
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i].compareTo(v) < 0 ){
//                j ++;
//                swap(arr, j, i);
            		 swap(arr, ++j, i); // 更为优雅
            }

        swap(arr, l, j);

        return j;
    }

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){

        if( l >= r )
            return;

        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

讲的很好，建议整理出书

hi 我觉得你的课程讲的真的很好，如果能把所有的内容整理出书应该会更加造福群众！

some

Play-with-Algorithms/07-Graph-Basics/Course Code (C++)/02-Graph-Representation/DenseGraph.h

Line 20 in bd14f6c

vector<vector<bool>> g; // 图的具体数据

Some IDEs can be report errors where ">>" in "vector<vector<type>>". And if users use those IDEs, they must change "vector<vector<type>>" into "vector<vector<type> >".

插入排序外层循环应该是i=1

关于第二章选择排序优化的问题

当我测试选择排序优化与为优化代码对比的时候，发现当数组元素在几百个的时候优化效果明显，当达到1000以上，多次测试基本优化代码运行时间都比未优化的时间长

int n = 2000;
Integer[] array = SortTestHelper.generateRandomArray(n, 0, 10000);
Integer[] copy = Arrays.copyOf(array, array.length);

SortTestHelper.testSort("com.lxh.sort.basic.SelectionSort", array);
SortTestHelper.testSort("com.lxh.sort.basic.SelectionSort2", copy);

运行结果基本保持在

SelectionSort : 9.2122ms
SelectionSort2 : 12.2485ms

find(p)

波波老师，find(p)方法里不用更新rank的值吗

One link in readme is not valid anymore

The link https://github.com/kingAnyWHere/codding.cn/tree/master/algo in readme is not valid any more.

为什么在头文件中实现函数

您好，我是个c++小白，想请教两个问题。
1 为什么要在头文件中实现函数，为什么不分成.h文件和.cpp文件呢？
2在图这一章中您在SparseGraph.h中的class SparseGraph里面又实现了adjIterator类，我以前没有接触过这种写法，请问您是基于什么考虑要这么写呢？

插入排序在Java中使用System.arraycopy()方法会更加高效

代码如下

static void insertSort(int data[], int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            int tmp = data[i];
            for (int j = start; j < i; j++) {
                if(data[j] > tmp) {
                    System.arraycopy(data, j, data, j + 1, i - j);
                    data[j] = tmp;
                    break;
                }
            }
        }
    }

二分搜索树的查找后继的函数似乎有点问题（##后面的函数，应该是调用successorFromAncestor()）

`// 在以node为根的二叉搜索树中, 寻找key的祖先中,比key大的最小值所在节点, 递归算法
// 算法调用前已保证key存在在以node为根的二叉树中
Node* successorFromAncestor(Node* node, Key key){

    if(node->key == key)
        return NULL;

    if(key > node->key)
        // 如果当前节点小于key, 则当前节点不可能是比key大的最小值
        // 向下搜索到的结果直接返回
        return successorFromAncestor(node->right, key);
    else{
        assert(key < node->key);
        // 如果当前节点大于key, 则当前节点有可能是比key大的最小值
        // 向左继续搜索, 将结果存储到tempNode中
        Node* tempNode = ## predecessorFromAncestor(node->left, key);
        if(tempNode)
            return tempNode;
        else
            // 如果tempNode为空, 则当前节点即为结果
            return node;
    }
}`

快速排序的2个问题

老师讲的快速排序最后一个优化：即大小接近的数据，采用 partition2

这个应该可以直接用下面2个方法：

1. 采用 partition 1，如果是 =v 的数，随机分配到左右 2边
2. 采用partition 2，下面的代码，应该直接可以 arr[i]<=v，加上了 = 号，而不用像老师那样用 <

while(i <=r && arr[i] <= v ) i++
while(j >= l+1 && arr[j] >= v) j--

Play-with-Algorithms/02-Sorting-Basic/Course Code (C++)/06-Insertion-Sort-Advance/main.cpp

void insertionSort(T arr[], int n){

for( int i = 1 ; i < n ; i ++ ) {

    // 寻找元素arr[i]合适的插入位置
    // 写法1

// for( int j = i ; j > 0 ; j-- )
// if( arr[j] < arr[j-1] )
// swap( arr[j] , arr[j-1] );
// else
// break;

    // 写法2

// for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
// swap( arr[j] , arr[j-1] );

    // 写法3
    T e = arr[i];
    int j; // j保存元素e应该插入的位置
    for (j = i; j > 0 && arr[j-1] > e; j--)
        arr[j] = arr[j-1];
    arr[j] = e;
}

return;

}

这段代码有错吧？
每次循环完，j都是等于0，e永远插在0的位置

bug- binary-search-tree ： levelOrder

06-Binary-Search-Tree-Traverse 中 levelorder 没有对空树 进行检验 ，会出现 空指针异常的情况。如果是空树 ，直接返回就行了。

pr 我提了一下 ：

#32