笔试算法题

可以先对一些简单情形进行手工模拟，查找规律
有时先对数组进行排序可以使运算变得简单，提高效率
字符串问题、括号匹配问题，可以考虑逆向思维，从右往左看
从初态到某一状态A最少需要几步？可以考虑从状态A回到初态的逆过程需要几步
括号匹配，标准匹配正负之和count为0，允许一次交换则count下限调整为-1.
排列组合，组合数，排列数
数字的奇偶性
数的质因数分解
链表判环：快慢指针。链表相交：首尾交错相连，p、q走到相遇为止。
装箱问题，将货物按重量从大到小排序，每次尝试放最大的，放不下就开一个新的箱子。

动态规划

动态规划需要找到递推式，即状态从i转移到j的公式（状态也可能是二维的(i1,j1)->(i2,j2)）
动态规划时，dp数组中存储的不一定是题目的要求，可以是“以每个位置结尾这种思维方式”
动态规划：换钱的最少货币数（p191），换钱的方法数（程序员代码面试指南p196，扩展：每种货币最多拿一次的情况），0/1背包，完全背包，装箱问题

找钱的可能数（组合）：每种钱币0到无穷个，钱币升序排列，for j=1,n:{dp[i] = dp[i] + dp[i-k]};0~1个，钱币降序排列，for j=n,1{dp[i] = dp[i] + dp[i-k]}
走楼梯的方法数（排列）：迭代法

面试算法题

findkth，第k小的元素

先对数组整体排序，再取第k个元
素。时间复杂度O(nlogn)素。时间复杂度O(nlogn)
k次冒泡排序or选择排序。时间复杂度O(kn)
采用partial_sort的思想。不断进行partition操作。平均时间复杂度位O(n)，最坏时间复杂度为O(n2)
详见：
https://www.cnblogs.com/wangkundentisy/p/8810077.html

#include <iostream>
using namespace std;

// arr[]为数组，start、end分别为数组第一个元素和最后一个元素的索引
 // povitIndex为数组中任意选中的数的索引
int partition(int arr[], int start, int end)
{
    int pivot = arr[end];
    int storeIndex = start;
    //这个循环比一般的写法简洁高效，呵呵维基百科上看到的
    for(int i = start; i < end; ++i) {
        if(arr[i] < pivot) {
            swap(arr[i], arr[storeIndex]);
            ++storeIndex;
        }
    }
    swap(arr[storeIndex], arr[end]);
    return storeIndex;
}
int findkth(int arr[],int start, int end,int k){

	int pivot_index = partition(arr,start,end);

	if(pivot_index < k){
		return findkth(arr,pivot_index+1,end,k);
	}
	else if(pivot_index > k){
		return findkth(arr,start,pivot_index-1,k);
	}
	else{
		return arr[pivot_index];
	}
}
double findmid(int arr[],int len){
	if(len%2==1){
		return findkth(arr,0,len-1,(len-1)/2);
	}
	else{
		cout<<"even"<<endl;
		return (findkth(arr,0,len-1,len/2) + findkth(arr,0,len-1,len/2-1))/2.0;
	}
}

找中位数的方法（要求时间复杂度O(1)，空间复杂度O(n)）

用findkth实现

找主元素（出现次数超过一半的数）

打擂台。1.如果擂台上没人，新人成为擂主。2.同一组人上台，擂主战斗力+1。3.不同组的人上台挑战，擂主战斗力-1。4.最后留在台上的是中位数。

partial_sort()

partition一次的时间复杂度，为O(n)。总时间复杂度O(nlogn)

两个有序数组，a[],b[]，大小分别为m，n，求第k 大的数

https://www.cnblogs.com/algorithmic/p/3657623.html

https://blog.csdn.net/lecepin/article/details/50791404（扩展）

top-K问题

全部排序，O(nlogn)
数据规模小，可以完全放到内存中，则可以用partition（但不是partial_sort），平均时间复杂度O(n)，最差时间复杂度O(n2)
对输入内容进行部分排序，即只对前K大的元素进行排序（这K个元素即为所求）。此时我们可以选择冒泡排序或选择排序进行处理，即每次冒泡（选择）都能找到所求的一个元素。这类策略的时间复杂度是O(Kn)。
建立size为k的最小堆，每次遇到新元素则和堆顶元素（前k个元素中最小的那个）比较，如果比他大，则替换他，新元素下沉到合适的位置（O(logk)）。总时间复杂度O(k)+O(nlogk)=O(nlogk).
可以先对数据进行hash分段，每一段生成一个最小堆，再对这些最小堆用优先级队列（多路归并）进行处理。

栈与队列

两个栈实现队列。A栈用于入队列，B栈用于出队列，若B为空，则将A中的所有元素倒入B，再出队列。

两个队列实现栈。如果“栈”非空，则必有一队列非空。如果“栈”空，则

入栈：非空队列入队列操作
出栈：非空队列出队列n-1个，导入另一队列中。将最后一个元素出队列。（完成空/非空队列转换）

最大值栈：用一个max栈来同步存储可能的最大值在栈顶位置。入栈：max(当前最大值（即栈顶元素）,新元素)。出栈：照常。
最大值队列（滑动窗口最大值）：用一个max队列来同步存储可能的最大值在队列头位置。入队列：将max队列尾部比新元素小的元素依次出队列，然后新元素入队列。

出队列：如果出队列的索引值和max队列索引值相同，则出队列。
2-5-3-4
-5--4

（剑指offer都有的，可以去看看）

大数据并发实时排序并求玩家的排名（有玩家ID，求该玩家的排名）

线段树or树形数组（树形分区），累加子分区的排名

http://www.cnblogs.com/weidagang2046/archive/2012/03/01/massive-user-ranking.html

1：战力排行榜，几乎实时得找出前100的玩家。（最大堆和计数排序），不知道有没有修改和查询都是O(1)得算法？树形数组。
a. 一直维持一个size为100的最小堆，外加一个hashmap（存储玩家ID到节点的映射）。
保存堆顶（第100名的战力）的值，其余玩家在更新积分时，如果超过了该值，插入堆（替换堆顶元素，下沉到合适位置）
b. 战力分布集中在某个区间，例如0~200，那么可以用计数排序的思想。使用数组来存储各个战力的玩家，数组的每个元素是一个链表。外加一个hashmap（存储玩家ID到节点的映射）
c. 战力分布很分散。将b中的数组换成链表，链表的每个节点是一个链表。外加一个hashmap（存储玩家ID到节点的映射）。
每次更新战力，只需要沿着链表前后找相邻战力链表，放置到战力链表中合适的位置或者新开一个链表。

小蜜蜂

校招准备系列9-笔试面试算法题