零散算法问题汇总

引言

以前在学校的时候，为了面试，看了一些面试的算法，现在回过头去，一方面发现满满地都是记忆，另一方面觉得博客里面不应该有很多的文章只是仅仅讨论一个小问题的算法，好吧，就把它们放在这个汇总的文章吧。里面的这些算法一些是C++的，一些是Python，但随着毕业以后，由于做安卓开发的缘故，主语言变成了Java，好吧，那就以后有时间慢慢的一个个翻译成Java的吧，但是暂时先机械的移动它们到一起。

让我们开始吧

一个问题就是一小节，就这么定了。

建堆排序

建堆排序，原理是将数据映射成严格二叉树，先建立一个大顶堆，然后头部是最优解，将最优的解换到最后，将一个普通元素换到头顶，然后隔离最后一个元素，将新来的顶部参与重新建堆，不断的重复此操作，最后得到排序完的数组。

public class FindMaxKAlgorithm {

    private int[] numbers;
    private int[] originalNumbers;

    private FindMaxKAlgorithm(int[] numbers) {
        this.numbers = numbers;
        this.originalNumbers = Arrays.copyOf(numbers, numbers.length);
    }

    private int[] getOriginalNumbers() {
        return originalNumbers;
    }

    private void swap(int from, int to) {
        if (from > numbers.length - 1 || to > numbers.length - 1)
            throw new IndexOutOfBoundsException("index out of number array");
        int tmpValue = numbers[from];
        numbers[from] = numbers[to];
        numbers[to] = tmpValue;
    }

    private void maxHeapify(int curSize, int index) {//curSize是用来设置交换停止条件
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int larger = index;
        if (left < curSize && numbers[larger] < numbers[left]) larger = left;
        if (right < curSize && numbers[larger] < numbers[right]) larger = right;
        if (larger != index) {
            swap(larger, index);
            maxHeapify(curSize, larger);
        }
    }

    private void buildMaxHeap() {
        int count = numbers.length;//后面的元素其实都不需要建堆，因为他们都没有三个元素不会执行
        for (int i = count / 2; i >= 0; i--) {
            maxHeapify(count, i);
        }
    }

    private void heapSort() {
        int heapSize = numbers.length;
        buildMaxHeap();
        for (int i = numbers.length - 1; i > 0; i--) {
            swap(i, 0);
            heapSize--;
            maxHeapify(heapSize, 0);
        }
    }

    private int[] getSortedNumbers() {
        heapSort();
        return numbers;
    }

    public int[] getMaxKNumbers(int k) {
        int[] retValue = new int[k];
        int pointer = 0;
        if (k > numbers.length) throw new IndexOutOfBoundsException();
        int validHeapSize = numbers.length;
        buildMaxHeap();
        for (int i = numbers.length - 1; i > numbers.length - k - 1; i--) {
            retValue[pointer++] = numbers[0];
            swap(0, i);
            validHeapSize--;
            maxHeapify(validHeapSize, 0);

        }
        return retValue;
    }

    public static int[] generateRandomNumbers() {
        Random seed = new Random();
        int[] retValue = new int[seed.nextInt(100)];
        for (int i = 0; i < retValue.length; i++) {
            retValue[i] = seed.nextInt(1000);
        }
        return retValue;
    }

    public static void main(String[] args) {
        FindMaxKAlgorithm algorithm = new FindMaxKAlgorithm(FindMaxKAlgorithm.generateRandomNumbers());
        System.out.println("original numbers:");
        Arrays.stream(algorithm.getOriginalNumbers()).forEach(System.out::println);
//        System.out.println("sorted numbers:");
//        Arrays.stream(algorithm.getSortedNumbers()).forEach(System.out::println);
        System.out.println("max numbers:");
        Arrays.stream(algorithm.getMaxKNumbers(4)).forEach(System.out::println);
    }
}

以上的代码中，除了可以排序外，我还插入一了一段使用建堆找出N个数中最优的几个解的算法，即getMaxKNumbers(int k)，原理都是堆算法。

找出2N+1个两两配对数中落单那个

如题，找出2N+1个两两配对数中落单那个，对于这个问题,最暴力的求解方法是采用遍历的操作,然后全部进行,以下方法使用了一个辅助类,其原理是一个智能容器,当插入元素的时候判断集合中是否已经有了该元素,没有就添加,有的话就删除,如下

#!/usr/bin/python
def findSingle(ls):
    con = Container()
    for i in range(len(ls)):
        con.add(ls[i])
    con.showResult()

class Container:
    def __init__(self):
        self.data = []
        self.count = 0

    def add(self,dat):
        if self.count > 0:
            flag = False
            index = 0
            for i in range(self.count):
                if self.data[i] == dat:
                    flag = True
                    index = i
                    break
            if flag:
                del self.data[index]
                self.count = self.count - 1
            else:
                self.data.append(dat)
                self.count=self.count + 1
        elif self.count == 0:
            self.data.append(dat)
            self.count = self.count + 1
            
    def showResult(self):
        for i in range(len(self.data)):
            print self.data[i]

if __name__=="__main__":
    ts = [1,2,1,2,3,4,3]
    findSingle(ts)

当时我就拿着这个算法给面试官看,面试官不是很满意,后来回来查询了一下,有个比较简单的办法,那就是采用异或操作

#!/usr/bin/python
def findSingle(lt):
    l = len(lt)
    ret = 0
    for i in range(l):
        ret^=int(lt[i])
    return ret

if __name__=="__main__":
    ts = "12123447887"
    print findSingle(ts)

递归求解二叉树的深度

如题，递归求解二叉树的深度，又是一个入门级的问题，可是常常会忘掉哦。
首先定义节点

class Node{
	int data = 0;
	Node left = null;
	Node right = null;
}

假设根节点为
Node root;
求解树的深度为

int getTreeDepth(Node node){
	if(node==null) return 0;
	int leftDepth = getTreeDepth(node.left);
	int rightDepth = getTreeDepth(node.right);
	return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}

求解为

getTreeDepth(node);

移动星号

要求字符串为号和26个字母的任意组合把号都移动到最右侧，把字母移到最右侧并保持相对顺序不变。

void adjustString1(char* str){
    int len = strlen(str);
    char* ceil = str+len-1;//找到数组的天花板，注意最后一个字符的'\0'，不要写成str+len
    char* letter = str;//字母指针
    char* star = str;//星号指针
    while(letter<=ceil&&star<=ceil){
        while(*star!='*'&&star <= ceil){//找到第一个*
            star++;
        }
        if(star==ceil) return;//都是星号
        letter = star;
        while(*letter=='*'&&letter <= ceil){
            letter++;
        }
        while(*letter!='*'&&*star=='*'&&letter<=ceil){
            char t = *star;
            *star = *letter;
            *letter = t;
            letter++;
            star++;
        }
    }
}

求一串彩色珠子中包含所有颜色最短的一串长度

以[1,2,2,1,1,3,0,0,2,2,3,2,3]为例子
最简单的是暴力破解法，两个循环，这肯定被鄙视的，在参考了网上的一些想法后，自己写了个Java版本的，主要思想为
第一步：使用两个指针，一开始都指向头节点。
第二步：指针一往后移动，在范围内，当包含了所有颜色的时候，停下来。
第三步：指针二往后移动，在范围内，移动的过程中判断是否包含所有颜色，当不包含的时候停下来。
第四步：计算两指针间距离，如果小于上一最小记录便将最小记录更改为该距离。
第五步：重复以上动作直到指针一越界停止。
这里使用一个判断函数，用来计算是否包含了所有元素，思路为开辟一个颜色大小的数组，将颜色分别对应一个数字，这可以通过枚举实现：
开始所有数组元素置为0，指针一移动时，将指针一指向的元素下标对应的元素加一，指针二移动的时候减一。如下：

public class LeastBeadsLength {
	
	private int[] beads = {1,2,2,1,1,3,0,0,2,2,3,2,3};
	private int[] flags = {0,0,0,0};
	
	void getResult(){
		System.out.println(getShortestBeads(beads));
	}
	
	boolean isFull(){
		int ret = 1;
		for (int i = 0; i < flags.length; i++) {
			ret*=flags[i];
		}
		return ret==0?false:true;
	}
	
	void checkState(){
		System.out.println(isFull());
	}
	
	int getShortestBeads(int[] beads){
		int len = beads.length;
		int ap = 0,bp = 0;
		int least = len;
		while(bp<len){
			while(!isFull()&&bp<len){
				flags[beads[bp]]+=1;
				bp++;
			}
			while(isFull()){
				flags[beads[ap]]-=1;
				ap++;
			}
			if(bp<=len){
				int count = bp-ap+1;
				if(count < least){
					least = count;
				}
			}
			else return least;
		}
		return least;
	}
	
	public static void main(String[] args) {
		LeastBeadsLength leastBeadsLength = new LeastBeadsLength();
		leastBeadsLength.getResult();
	}
}

求一个字符串的最大连续递增数子串

题目的意思呢，其实也是很好理解的，就是将递增的子字符串求出来，那么开始操刀工作吧。

public class FindLongestAccend {

	String findLongestAccendSubString(String src){
		if(src==null) return null;
		int len = src.length();
		if(len<=1) return src;
		int longest = 0;		
		String ret = "";
		int p1 = 0;
		while(p1<len){
			if(p1+1<len&&src.charAt(p1)+1==src.charAt(p1+1)){
				int count = 2;
				int p2 = p1+1;
				while(p2+1<len&&src.charAt(p2)+1==src.charAt(p2+1)){
					count++;
					p2++;
				}
				if(count > longest){
					longest = count;
					ret = src.substring(p1,p2+1);
					System.out.println(ret);
					p1 = p2;
				}
			}else {
				int count = 1;
				if(count > longest){
					longest = count;
					ret = String.valueOf(src.charAt(p1));
					System.out.println(ret);
				}
				p1++;
			}
		}
		return ret;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(new FindLongestAccend().findLongestAccendSubString("abcdebcdefghi123456789"));
	}
}

查找单链表的倒数第k个节点

这道题考察了边界条件，首先得判断链表的长度得小于或者等于k，然后按照先将一个指针移动到k-1的位置，再用一指针指向头部和它一起移动，直到第一个指针到底，这样时间复杂度为O(N),代码如下

public class LastK {
	
	class No{
		public int data;
		public No next;

		public No() {
			// TODO Auto-generated constructor stub
			data = 0;
			next = null;
		}
	}
	
	LastK(){
		buildList();
		System.out.println("all numbers are:");
		showAll();
		System.out.println("last "+5+" number is:");
		System.out.println(findLastK(head,5));
	}
	
	private No head;
	
	void showAll(){
		No pNo = head;
		while(pNo!=null){
			System.out.print(pNo.data);
			pNo=pNo.next;
		}
		System.out.println();
	}
	
	public void buildList(){
		head = new No();
		head.data = 0;
		No cur = head;
		for(int i = 0; i < 10;i++){
			No newNode = new No();
			newNode.data = i+1;
			cur.next = newNode;
			cur = newNode;
		}
	}
	
	public int findLastK(No hNo,int k){
		if(hNo==null) return -1;
		No p1 = hNo;
		No p2 = hNo;
		while(k!=0){
			p1 = p1.next;
			if(p1==null) return -1;
			k--;
		}
		while(p1!=null){
			p1=p1.next;
			p2=p2.next;
		}
		return p2.data;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LastK lk = new LastK();
	}
}

建树、前序、中序、后序遍历Java版

如题，建树、前序、中序、后序遍历是常见的算法问题，据说大牛到Google面试被要求反转二叉树没成功，当即被说you suck了，那么赶紧看看这个不至于以后被骂了。

public class Traverse {
	class Node{
		public Node() {
			// TODO Auto-generated constructor stub
			int data = 0;
			left = null;
			right = null;
		}
		int data;
		Node left;
		Node right;
	}

	Node root;
	Traverse(){
		root = null;
		generateTree();
	}

	void generateTree(){
		int[] arr = {1,4,2,5,6,3,4,6,4};
		for(int i = 0; i < arr.length;i++){
			buildTree(root, arr[i]);
		}
	}

	void buildTree(Node node,int data){
		if(root==null){
			root = new Node();
			root.data = data;
		}else {
			if(data<node.data){
				if(node.left==null){
					Node newNode = new Node();
					newNode.data = data;
					node.left = newNode;
				}else {
					buildTree(node.left, data);
				}
			}else {
				if(node.right==null){
					Node newNode = new Node();
					newNode.data = data;
					node.right = newNode;
				}else {
					buildTree(node.right, data);
				}
			}
		}
	}

	void Mtranverse(Node node){
		if(node!=null) 
		{
			Mtranverse(node.left);
			System.out.print(node.data);
			Mtranverse(node.right);
		}
	}
	
	void Rtranverse(Node node){
		if(node!=null) 
		{
			Rtranverse(node.left);
			Rtranverse(node.right);
			System.out.print(node.data);
		}
	}

	void Ltranverse(Node node){
		if(node!=null) 
		{
			System.out.print(node.data);
			Ltranverse(node.left);
			Ltranverse(node.right);
			
		}
	}
	
	void printAll(){
		Ltranverse(root);System.out.println();
		Mtranverse(root);System.out.println();
		Rtranverse(root);
	}


	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Traverse traverse = new Traverse();
		traverse.printAll();
	}
}

将一个字符串不使用额外容器向左移动M位

如题，好了不说了，直接上代码吧，主要的要求就是在原位操作，不能开辟新的空间

public class MoveLeftM {
	
	public static void reverse(StringBuilder string,int st,int end){
		int step = (end-st+1)/2;
		for(int i = 0; i < step;i++){
			char t = string.charAt(st+i);
			string.setCharAt(st+i, string.charAt(end-i));
			string.setCharAt(end-i, t);
		}
	}
	
	public static void moveLeftM(StringBuilder string,int step){
		int len = string.length();
		reverse(string, 0, step-1);
		reverse(string, step, len-1);
		reverse(string, 0, len-1);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		StringBuilder string = new StringBuilder("abcdefghijklmn");
		MoveLeftM.moveLeftM(string, 6);
		System.out.println(string);
	}
}

关于Fibonacci数的效率的考虑

很容易就可以得到递推公式的斐波那契数列的递归解法，但是又没有考虑过，递归虽然酷，但是效率呢？

int RecursiveFib(int n){
	if(n==0) return 0;
	if(n==1) return 1;
	return RecursiveFib(n-1)+RecursiveFib(n-2);
}

这样的函数会调用巨多次，你会发现算到100根本就算不动了！于是是不是应该记下之前算过的解呢，那么每个N对应的Fib数是一定的，我们可以采用键值对的方式储存，那么这样子，就不会干重复的事情了，这也相当于我们手算时的思路!

import java.util.HashMap;

public class EffectiveFibonnacci {

	HashMap<Integer, Integer> map;
	EffectiveFibonnacci(){
		map = new HashMap<Integer,Integer>();
		map.put(0, 0);
		map.put(1, 1);
	}
	
	int RecursiveFib(int n){
		if(n==0) return 0;
		if(n==1) return 1;
		return RecursiveFib(n-1)+RecursiveFib(n-2);
	}
	
	int EffectiveFib(int n){
		for(int i = 2;i <= n; i++){
			map.put(i, map.get(i-1)+map.get(i-2));
		}
		return map.get(n);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		EffectiveFibonnacci xx = new EffectiveFibonnacci();
//		System.out.println(xx.RecursiveFib(100));
		System.out.println(xx.EffectiveFib(40));
	}
}

反转单链表

如题，入门级算法，来一发吧，回来再写一遍吧，基本思路就是倒转指针，用一个辅助指针先记录下来后驱，总共需要三个辅助指针，代码如下：

public class Size {
	class No{
		public int data;
		public No next;

		public No() {
			// TODO Auto-generated constructor stub
			data = 0;
			next = null;
		}
	}
	
	private No head;
	
	Size(){
		buildList();
	}
	
	public void buildList(){
		head = new No();
		head.data = 0;
		No cur = head;
		for(int i = 0; i < 10;i++){
			No newNode = new No();
			newNode.data = i+1;
			cur.next = newNode;
			cur = newNode;
		}
	}
	
	void reverse(){
		No pre,cur,lat;
		pre = head;
		cur = head.next;
		while(cur!=null){
			lat = cur.next;
			cur.next = pre;
			pre = cur;
			cur = lat;
		}
		head.next = null;
		head = pre;
	}
	
	public void showAll(){
		No pNo = head;
		while(pNo!=null){
			System.out.print(pNo.data);
			pNo = pNo.next;
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		Size size = new Size();
		size.showAll();
		size.reverse();
		size.showAll();
		size.reverse();
		size.showAll();
	}
}

判断一字符串是不是对称的

题目非常简单，如题所示，直接上代码吧，其他的都省略了。

int isSymetrical(char* src){
    int len = strlen(src);
    if(src==NULL || len <= 1) return -1;
    bool ret = 1;
    for(int i = 0; i < len/2;i++){
        if(src[i]!=src[len-i-1]) {
            ret = 0;
            break;
        }
    }
    return ret;
}

判断两个链表是否相交并且返回第一个交点

如题，判断两个链表是否相交并且返回第一个交点，主要的考点在于两个链表交叉后，以后的部分都是一样的，只可能是Y型的交叉而不可能出现X型的交叉
首先定义节点：

struct Node{
	int data;
	Node* next;
};
最笨的方法是遍历所有的节点进行比较，比如
Node* ifCrossed(Node* list1,Node* list2){
	Node* one = list1;Node* two = list2;
	while(one){
		while(two){
			if(two==one) return one;
			two=two->next;
		}
		one=one->next;
	}
	return NULL;
}

如果这么写，那么那么你跪了，面试官肯定会认为你差劲的，而应该如下解决

Node* ifCrossed(Node* list1,Node* list2){
	Node* one = list1;Node* two = list2;
	int len1 = 0,len2 = 0;
	while(one) {len1++;one=one->next;}
	while(two) {len2++;two=two->next;}
	one = list1;two = list2;
	if(len1>len2){
		for(int i = 0; i < len1-len2;i++) one=one->next;
	}else{
		for(int i = 0; i < len2-len1;i++) two=two->next;
	}
	while(one!=two&&one&&two){
		one=one->next;
		two=two->next;
	}
	return one;
}

如果这么写呢，估计面试官就会面带微笑了！

判断单链表是否有环，若有请找出入口

如题，判断单链表是否有环，若有请找出入口。这道题其实是一道脑经急转弯性质的题目，暴力去做是有的，可是要效率哦。

struct Node{
    int data;
    Node *next;
};

Node* checkRing(Node* head,bool &ifExist){
    if(head==NULL){
        ifExist = false;
        return NULL;
    }
    Node* fast = head;
    Node* slow = head;
    while(slow!=fast && fast!=NULL && slow!=NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    if(fast!=slow){
        ifExist = false;
        return NULL;
    }else{
        ifExist = true;
        slow = head;
        while(slow!=fast){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
}

压缩字符串如aaabbbcccc为a3b3c4

如题，好像不是很难，把一串字符串进行压缩，可是要考虑效率哦。

public class CompressString {

	String compress(String src){
		StringBuilder ret = new StringBuilder();
		int p1 = 0;int count = 0;int len = src.length();
		while(p1<len){
			if(p1+1 < len && src.charAt(p1)==src.charAt(p1+1)){
				count = 1;
				int p2 = p1+1;
				while(p2<len&&src.charAt(p2)==src.charAt(p1)){
					count++;
					p2++;
				}
				ret.append(src.charAt(p1));
				ret.append(count);
				p1 = p2;
			}else{
				ret.append(src.charAt(p1));
				ret.append(String.valueOf(1));
				p1++;
			}
		}
		return ret.toString();
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(new CompressString().compress("aaabbbccsscxxaaccbbb"));
	}
}

匹配两个字符串的最大子串

当时写的有点low,使用了Java的contains方法,不断从找寻第二个字符串的子串进行配对,考官勉强给我通过,后面回来自己重写了一下,避免了contains函数,如下

#!/usr/bin/python
def getLongest(str_a,str_b):
	longest = 0
	ret = ""
	for i in range(0,len(str_a)):
		for j in range(0,len(str_b)):
			if(str_a[i]==str_b[j]):
				ast = i+1
				bst = j+1
				count=1
				while(ast<len(str_a) and bst < len(str_b) and str_a[ast]==str_b[bst]):
					ast = ast+1
					bst = bst+1
					count = count+1
				if(count > longest):
					longest = count
					ret = str_a[i:i+count]
	return ret
	
print getLongest("xscmdshit","saojojvocmdsjiso")

输出结果为
cmds

时间复杂度为O(N2),虽然效率不高,但是总算是写了出来,记录一下!

不想敲代码就到我的git来拉一下吧～https://github.com/gordon-rawe/algorithmSummary