Merge k Sorted Lists

问题描述:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分而治之的思想:   404ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return NULL;
        return dac(lists,0,lists.size()-1);
    }
private:
    ListNode* dac(vector<ListNode*>& lists,int low,int high)
    {
        int mid=(low+high)/2;
        if(low==high)
            return lists[low];
        ListNode* l1=dac(lists,low,mid);
        ListNode* l2=dac(lists,mid+1,high);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val<l2->val)
            l1->next=mergeTwoLists(l1->next,l2);
        else
            l2->next=mergeTwoLists(l1,l2->next);
    }
};

使用优先队列priority_queue找到最小的元素   436ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp{
    bool operator()(const ListNode* l, const ListNode* r){
        return l->val > r->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for(auto l : lists){
            if(l) q.push(l);
        }
        if(q.empty())
            return NULL;
        ListNode* result = q.top();      // head
        q.pop();
        if(result->next)
            q.push(result->next);
        ListNode* pointer = result;
        while(!q.empty()){
            pointer->next = q.top();      // the min
            q.pop();
            pointer = pointer->next;
            if(pointer->next)             // the responding ListNode* is not empty
                q.push(pointer->next);
        }
        return result;
    }
};

使用make_heap 480ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//struct cmp{
//   bool operator()(const ListNode* l, const ListNode* r){
//        return l->val > r->val;
//    }
//};
bool cmp(const ListNode* l, const ListNode* r){
    return l->val > r->val;
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       ListNode head(0);
       ListNode *curr = &head;
       vector<ListNode*> v;
        for(auto l : lists){
            if(l) v.push_back(l);
        }
        make_heap(v.begin(), v.end(), cmp);
        while(v.size()>0){
            curr->next = v.front();      // the min
            pop_heap(v.begin(), v.end(), cmp);
            v.pop_back();
            curr = curr->next;
            if(curr->next){             // the responding ListNode* is not empty
                v.push_back(curr->next);
                make_heap(v.begin(), v.end(), cmp);
            }
        }
        return head.next;
    }
};

 

Merge Two Sorted Lists

ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }

延伸:
在两个有序链表中查找第K大元素。 思路:和有序链表合并思路一样,不过在合并过程中需添加计数,同时需要注意相同大小元素只记1次。

求数组的字数组之和的最大值

思路:给定一个数组A, 找其中和最大的子串,可以可以从A[0]开始,往后累加和放在start中,如果start<0,将可以抛弃当前元素值,不再进行累加,maxSum保存最大的子串和。。并从下一个位置重复上述过程。

/*******************************************
   Author        : Jun Zhang
   Email         : ewalker.zj@gmail.com
   Last Modified : 2015-08-02 14:08
   Filename      : subMax.cpp
   Description   :
*******************************************/
#include<iostream>
int subMax(int *data, int n)
{
   	int start = data[0];           // record the current sum, >0
   	int maxSum = data[0];          // the maxSum
   	for(int i = 1; i < n; i++)
   	{
      		if(start < 0)             // preSum < 0
         			start = 0;            // new start position
      		start += data[i];
      		if(start > maxSum)
         			maxSum = start;
   	}
   	return maxSum;
}
int main()
{
   	int buf[10] = {2, -4, 5, 6, 2, -3, 8, 1, -12, -3};
   	std::cout<<subMax(buf, 10)<<std::endl;
   	return 0;
}

时间复杂度O(n),空间复杂度O(1)
3种变形:
1、求字数组和的绝对值的最大值
2、返回最大字数组位置
 

//需返回最大字数组的位置
struct outInfo
{
   	int begin;
   	int end;
   	int sum;
   	struct outInfo *next;
};
int subMax1(int *data, int n)
{
   	int start data[0];
   	int maxSum = data[0];
   	int pos;
   	int begin = 0, end;
   	int new;
   	outInfo *p, *info, *head;
   	head = (outInfo*)malloc(sizeof(outInfo));
   	p = head;
   	int ret = 0;
   for(int i = 1; i < n; i++)
   	{
     		if(start < 0)
     		{
       			if(ret == 0){
       				start = 0;
				       //此处可以保存当前字数组信息
       				ret = -1;
       				if(maxSum > p->sum)          // 子数组和大于当前存储值,覆盖
       				{
					          p->begin = begin;
          					p->end = end;
          					p->sum = maxSum;
       				}
       				else if(maxSum == p->sum)    // 相同的子数组和
       				{
          					info = (outInfo*)malloc(sizeof(outInfo));
          					info->begin = begin;
          					info->end = end;
          					info->sum = maxSum;
          					info->next = NULL;
          					p->next = info;
          					p = p->next;
       				}
     			}
   		}
  		if((ret == -1))&&(data[i] > 0))
  		{
			     begin = i;                // new begin;
			     ret = 0;
  		}
		  start += data[i];
  		if(start > maxSum)
  		{
     			maxSum = start;
     			end = i;
  		}
	}
  	if(ret == 0)
  	{
     		if(maxSum > p->sum)
     		{
        			p->begin = begin;
        			p->end = end;
        			p->sum = maxSum;
     		}
		     else if(maxSum == p->sum)
     		{
        			info =(outInfo*)malloc(sizeof(outInfo));
        			info->begin = begin;
        			info->end = end;
        			info->sum = maxSum;
        			info->next = NULL;
        			p = p->next;
     		}
   	}
	return maxSum;
}

 
3、数组收尾相连

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路:统计所有数中,各数位上1的个数。可以用循环的方式,从小达大对每个数位上1的个数进行统计。

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0)
            return 0;
       int count = 0;
       for(long base = 1; base <= n; base *= 10)     // long, base*10 可能溢出
       {
           long data = n/base;
           long remain = n%base;
           count += (data+8)/10*base;               //  =0, =1, >1
           if(data%10 == 1)                        //  =1
              count += remain+1;
       }
       return count;
    }
};

Two Sum

题目1:Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目意思是从给定一组数中,选出2个数,他们的和满足给定的一个目标值,按顺序输出这两个数对应的索引。(假设正好只有一个解)
思路:先按从小到大顺序数组排序,然后从小到大依次遍历,先确定一个较小的数,然后再其后面的数中使用二分查找的方式找另外一个数。

class Solution {
public:
    struct Item{
        int value;
        int index;
        Item(int pvalue, int pindex):value(pvalue), index(pindex){};
        bool operator<(const Item &it)
        {
            return value < it.value;
        }
    };
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        vector<Item> data;
        for(int i = 0; i <nums.size(); i++)
        {
            data.push_back(Item(nums[i], i));
        }
        sort(data.begin(), data.end());
        int lindex = 0, rindex = data.size() - 1;
        for( int lindex = 0; lindex <= rindex; lindex++){
            if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target)){
                result.push_back(min(data[lindex].index+1, data[lindex+1].index+1));
                result.push_back(max(data[lindex].index+1, data[lindex+1].index+1));
                return result;
            }
            else if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target))
                continue;
            int ret = -1;
            int remain = target - data[lindex].value;
            int left = lindex, right = rindex;
            while(left <= right){
                int mid = (left+right)/2;
                if(data[mid].value == remain){   // must compare the index
                    result.push_back(min(data[lindex].index+1, data[mid].index+1));
                    result.push_back(max(data[lindex].index+1, data[mid].index+1));
                    return result;
                }
                else if(data[mid].value < remain){
                    left = mid + 1;
                }
                else
                    right = mid - 1;
            }
        }
    }
};

时间复杂度为O(nlogn)
听说使用hashmap能将为O(n) 后续再探讨

Bitonic sort(也称双调排序)

Bitonic sequence. A sequence (a_{{1}}, a_{{2}},..., a_{{m}} ) is said to be bitonic if and only if:
(a) Either there is an integer j, 1 ≤ j ≤ 2m, such that a_{{1}} leq   a_{{2}}leq ... a_{{j}}geq  a_{{j+1}}geq  a_{{j+2}}geq ...geq  a_{{m}}
(b) Or the sequence does not initially satisfy the condition in (a), but can be shifted cyclically until the condition is satisfied.

/*
 * binotic.h
 *
 *  Created on: 2015年5月17日
 *      Author: zhangjun
 */
#ifndef BITONIC_SORT_H_
#define BITONIC_SORT_H_
#include<iostream>
#include<iterator>
#include<algorithm>
using namespace std;
class bitonic_sorter
{
public:
	bitonic_sorter(int a[], int len);
	void sort(bool direction = true);
	void sort_for_arbitary_length(bool direction = true);
private:
	int *array;
	int length;
	void bitonic_sort(int low, int len, bool direction);
	void bitonic_sort_for_arbitary_length(int low, int len, bool direction);
	void bitonic_merge(int low, int len, bool direction);
	void bitonic_merge_for_arbitary_length(int low, int len, bool direction);
	void compare_and_swap(int i, int j, bool direction);
	int greatest_power_of_2_lessthan(int len);
};
#endif /* BINOTIC_H_ */

 

/*
 * bitonic_sort.cpp
 *
 *  Created on: 2015年5月17日
 *      Author: zhangjun
 */
#include "bitonic_sort.h"
bitonic_sorter::bitonic_sorter(int a[], int len)
{
	array = a;
	length = len;
}
void bitonic_sorter::sort(bool direction)
{
	bitonic_sort(0, length, direction);
}
void bitonic_sorter::sort_for_arbitary_length(bool direction)
{
	bitonic_sort_for_arbitary_length(0, length, direction);
}
void bitonic_sorter::bitonic_sort(int low, int len, bool direction)                   // bitonic_sort
{
	if(len > 1)
	{
		int m = len/2;
		bitonic_sort(low, m, direction);
		bitonic_sort(low+m, m, !direction);
		bitonic_merge(low, len, direction);
	}
}
void bitonic_sorter::bitonic_sort_for_arbitary_length(int low, int len, bool direction)               // bitonic_sort_for_arbitary
{
	if(len > 1)
	{
		int m = len/2;
		if(direction == true)
		{
			bitonic_sort_for_arbitary_length(low, m, !direction);                                                                   // len-m > m
			bitonic_sort_for_arbitary_length(low+m, len-m, direction);                                                       // the big end
			bitonic_merge_for_arbitary_length(low, len, direction);
		}
		else
		{
			int half = greatest_power_of_2_lessthan(len);
			bitonic_sort_for_arbitary_length(low, len-half, !direction);                                                        // half > hen -half
			bitonic_sort(low+len-half, half, direction);                                                // the big end
			bitonic_merge_for_arbitary_length(low, len, direction);
		}
	}
}
void bitonic_sorter::bitonic_merge(int low, int len, bool direction)
{
	if(len > 1)
	{
		int m = len/2;
		for( int i = low; i < low + m; i++)
			compare_and_swap(i, i+m, direction);
		bitonic_merge(low, m, direction);
		bitonic_merge(low+m, m, direction);
	}
}
void bitonic_sorter::bitonic_merge_for_arbitary_length(int low, int len, bool direction)
{
	if(len > 1)
	{
		int m = greatest_power_of_2_lessthan(len);                                             // low+m >= low+len-m
		for( int i = low; i < low + len - m; i++)
			compare_and_swap(i, i+m, direction);
		bitonic_merge(low, m, direction);                                                                   // m >= len -m
		bitonic_merge(low+m, len-m, direction);
	}
}
void bitonic_sorter::compare_and_swap(int i, int j, bool direction)
{
	if(direction ==(array[i]>array[j]))
		std::swap(array[i], array[j]);
}
int bitonic_sorter::greatest_power_of_2_lessthan(int len)
{
	int p = 1;
	while(p<len)
		p = p<<1;
	return p>>1;
}

 

/*
 * test.cpp
 *
 *  Created on: 2015年5月6日
 *      Author: zhangjun
 */
#include<stdio.h>
#include<string.h>
#include"bitonic_sort.h"
int main()
{
	int num1[8] = {3, 67, 3, 5, 8, 4, 7, 9};
	int num2[34] = {7, 5, 8, 3, 5, 78, 9, 5, 6, 23,24,1,8,10,32, 2, 3, 8, 9, 21, 15, 3, 4, 8, 9, 6, 3, 2, 1,78,43, 56, 23, 41};
	bitonic_sorter s1(num1, 8);
	bitonic_sorter s2(num2, 34);
	s1.sort(false);
	std::copy(num1, num1+8, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	s2.sort_for_arbitary_length(true);
	std::copy(num2, num2+34, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	return 0;
}
/*
 * test.cpp
 *
 *  Created on: 2015年5月6日
 *      Author: zhangjun
 */
#include<stdio.h>
#include<string.h>
#include"bitonic_sort.h"
int main()
{
	int num1[8] = {3, 67, 3, 5, 8, 4, 7, 9};
	int num2[34] = {7, 5, 8, 3, 5, 78, 9, 5, 6, 23,24,1,8,10,32, 2, 3, 8, 9, 21, 15, 3, 4, 8, 9, 6, 3, 2, 1,78,43, 56, 23, 41};
	bitonic_sorter s1(num1, 8);
	bitonic_sorter s2(num2, 34);
	s1.sort(false);
	std::copy(num1, num1+8, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	s2.sort_for_arbitary_length(true);
	std::copy(num2, num2+34, std::ostream_iterator<int>(cout, " "));
	std::cout<<"n";
	return 0;
}

 
cuda bitonic代码

__global__ static void bitonicSort(int * values)
{
    extern __shared__ int shared[];
    const int tid = threadIdx.x;
    // Copy input to shared mem.
    shared[tid] = values[tid];
    __syncthreads();
    // Parallel bitonic sort.
    for (int k = 2; k <= NUM; k *= 2)                   // from 2 to
    {
        // Bitonic merge:
        for (int j = k / 2; j>0; j /= 2)                // from k/2 to 1
        {
            int ixj = tid ^ j;
            if (ixj > tid)           // tid 对应位为0, ixj对应位为1
            {
                if ((tid & k) == 0)               // 对应位为0,ascending
                {
                    if (shared[tid] > shared[ixj])
                    {
                        swap(shared[tid], shared[ixj]);
                    }
                }
                else                             // 对应位为1,descending
                {
                    if (shared[tid] < shared[ixj])
                    {
                        swap(shared[tid], shared[ixj]);
                    }
                }
            }
            __syncthreads();
        }
    }
    // Write result.
    values[tid] = shared[tid];
}

 
 

牛生牛问题

问题:一头母牛出生后,每两年可以生下一头母牛,即第二年和第四年可以分别剩下一头母牛,第五年将会死去。假设农场现有一头牛,N年后农场母牛数是多少?
20150517
每2年新增小牛数为斐波那契数列,从第6年开始,死去的牛的数目也为斐波那契数列

青蛙跳台阶问题

题目:一直青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级台阶的总共有多少种跳法?
思路:当n>3时,第一次跳有两种跳法:跳1级,剩余n-1级;跳2级剩余n-2级。所有总的跳法就是f(n) = f(n-1) + f(n-2),可以看出是一个斐波那契数列。

class Solution {
public:
    int jumpFloor(int number) {
        if(number == 1 || number == 2)
            return number;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

拓展:如果青蛙一次可以跳1级,也可以跳2级,…,也可以跳n级,此时有多少种跳法?
其实思路就是一样的,只不过跳法多了一些。 可以这么思考:第一次跳时,可以跳n级;可以跳n-1级,剩余1级;可以跳n-2级,剩余2级;…;可以跳1级,剩余n-1级。 用循环的方法计算,可以很快得到答案,可以避免重复的计算。 其实,通过观察,f(n) = 2^(n-1)
f(1) = 1;
f(2) = 1+f(1);
f(3) = 1+f(1)+f(2);

100 Best GitHub: Deep Learning

100 Best GitHub: Deep Learning

ghdeeplearning170714

Deep Learning

Resources:

See also:

100 Best MATLAB VideosDeep Learning & Dialog Systems | MATLAB & Dialog Systems 2010 | MATLAB & Dialog Systems 2011 | MATLAB & Dialog Systems 2012 | MATLAB & Dialog Systems 2013Software Meta Guide


deep-learning [100x Jul 2014]

  • rasmusbergpalm/DeepLearnToolbox .. Matlab/Octave toolbox for deep learning. Includes Deep Belief Nets, Stacked Autoencoders, Convolutional Neural Nets, Convolutional Autoencoders and vanilla Neural Nets. Each method has examples to get you started.
  • karpathy/convnetjs .. Deep Learning in Javascript. Train Convolutional Neural Networks (or ordinary ones) in your browser.
  • nicholas-leonard/dp .. A deep learning library designed for streamlining research and development using the Torch7 distribution.
  • daemonmaker/DMPC .. Repository for experimenting with combining deep learning and model predictive control techniques.
  • woobe/deepr .. An R package to streamline the training, fine-tuning and predicting processes for deep learning based on ‘darch’ and ‘deepnet’.
  • RAMLab/deepbrains .. DeepBrains is a deep learning framework based on GO programming language and common machine learning hierarchical models.
  • colah/DL-Types-FP-posts .. Blog post exploring connection between Deep Learning, Types and Functional Programming
  • Misrab/deeplearning .. A collection of Go packages for Machine Learning, with an emphasis on Deep Learning
  • drshrey/deep_learning .. Playing around with the Alchemy API, and see what’s going on with Natural Language Processing and Deep Learning
  • hycis/pynet .. pynet is meant to be a flexible and modular deep learning framework base on theano.
  • Cysu/dlearn .. A deep learning Python module based on Theano.
  • zhaojunbo/paracel-SDAE .. The repo involves a Deep Learning method, Stacked Denoising Autoencoder. The repo exploits “paracel”, which is a new parallel computing framework.
  • DrDanRyan/ML-Framework .. A modular machine learning framework for Matlab with an emphasis on deep neural network models.
  • junku901/dnn .. Deep learning library for node.js. (Includes Logistic-Regression, MLP, RBM, DBN, CRBM, CDBN)
  • mimosavvy/PairsTradingDL .. Class project regarding a pairs trading strategy with deep learning and social information
  • xqcao/mywebapp .. Deep Learning is a new area of Machine Learning research, I share my deeper learning work overhere,
  • EderSantana/DeepEEG .. Deep learning for EEG analysis. This script was used to generate the results of the paper “Joint Optimization of Algorithmic Suites for EEG analysis” at EMBC 2014
  • samuel1208/UFLDL .. The solution of Andrew Unsupervised Feature Learning and Deep Learning
  • nibroc/SimpleSocket .. A simple non-production, hobby library for socket operations. This is intended as a learning project to deeply familiarize myself with unix sockets. It is not intended for real use.
  • daemonmaker/hedgehog .. Re-implementation of method in Playing Atari with Deep Reinforcement Learning paper.
  • chausler/deep .. some temporal RBM based models we’re playing with. Deep Learning ;-)
  • zewemli/DeepLearning .. An OpenCL implementation of Deep Belief Networks and Restricted Boltzmann Machines