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

笔试算法题

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

动态规划

构建递推关系式是动态规划的核心任务；在动态规划时需要注意的是：dp数组中存储的不一定是题目的直接答案；可以理解为以每个位置结尾的状态思维方式；例如：换钱问题中的最少货币数（常见于算法题库p191）；换钱的方法数（如《程序员代码面试指南》p196及其扩展版本）；0/1背包问题与完全背包问题的区别在于物品是否可以重复选取；而装箱问题是将物品分配到有限容量的箱子中的典型问题

找零钱的方式数目（组合）：每枚硬币的数量可以从零到无限，并按面值高低顺序排列，则动态规划的状态转移方程为：对于j从1到n遍历\{dp[i] += dp[i - k]\}；若从n downto 1遍历，则动态规划的状态转移方程为\{dp[i] += dp[i - k]\}。登楼梯的方式数目（排列）：递推法

面试算法题

shuffle洗牌算法

<>

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

进行擂台赛。规则如下：1.若擂台上无人，则新加入者自动成为擂主；2.同一组人员依次上台，则当前擂主的战斗力提升一个单位；3.来自不同小组的人员上台挑战，则当前擂主的战斗力减少一个单位；4.最终留下的将是所有参赛者的中位数

partial_sort()

作者：Nestler
来源：
原文：<>
具体实现思路如下：首先将区间范围[first, middle)内的数据构建为一个最大堆结构；随后依次将[middle, last]区间内的每个数据与第一个区域的所有数据进行比较操作；其中第一个区域的元素即为该最大堆的顶点节点。若发现被比较数据小于当前顶点值，则需立即对该(first, middle)区间重新调整以维持最大堆的性质；每次交换发生后都需要对(first, middle)区间内部的数据重新构建最大堆以保证其有效性和完整性；最终还需对该(first, middle)范围的所有数据执行一次排序操作sort_heap()以完成从小到大的顺序排列过程；需要注意的是，在此过程中heap序列与sorted序列之间存在本质区别。
时间复杂度分析如下：该算法的时间复杂度主要由以下几个部分构成：初始建立最大堆所需的时间为O(k)，随后处理剩余n-k个数据插入到max-heap中所需的时间总和为O(nlogk)，最后对(first, middle)范围的数据再次执行heapify操作的时间消耗为O(klogk)，因此总的计算复杂度可表示为O(nlogk)。

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

该文介绍了基于深度学习的图像识别算法实现，并详细讨论了其在实际应用中的表现

top-K问题(和findkth相似)

1. 完全排序的时间复杂度为O(nlogn)。
2. 基于交换或选择的排序策略用于提取前k个最小元素：每次操作都能确定一个目标元素，在k次操作后即可完成筛选。
3. 当数据量较小时可全部放入内存：通过不断执行partition操作（非STL partial_sort），平均时间复杂度为O(n)，最坏情况复杂度为O(n²)。
4. 构建一个大小为k的最小堆：对于每个新元素进行比较（与当前k小元素堆顶），若大于堆顶则替换之（时间复杂度O(logk)）。总时间复杂度为O(k + nlogk)，即O(nlogk)。
5. 可先对数据进行hash分段处理：对每段生成最小堆后再利用优先级队列（多路归并）完成合并处理。

partition方法解决top-k问题

详见：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实现

栈与队列

基于两个栈的数据结构实现队列。其中A栈作为入队操作的数据存储区域,B栈作为出队操作的数据存储区域,当B为空时,则需将A中的所有元素转移至B中以完成出队操作.即可完成出队操作.

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

• 压入：当源序列为空时不再执行该操作。
  • 弹出：当源序列不为空时会执行以下步骤：
    1. 移除目标序列的前n-1个元素
    2. 将这些被移除的元素附加到目标序列的末尾
    3. 最后一步是将目标序列中的最后一个元素弹出至源序列尾部。
  • 转换完成

最大值栈用于同步存储可能的最大值于栈顶位置。
入栈操作采用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

战力排行榜实时追踪系统能够快速追踪前100名玩家的状态。（基于最大堆与计数排序），不确定是否存在一种算法可以在更新操作中同时实现O(1)的时间复杂度？树形数组是一种有效的解决方案。
a. 我们持续维护一个容量固定的最小堆（大小固定为100），并配合使用一个哈希表（存储玩家ID与节点之间的映射关系）。为了获取当前排名第十的玩家战力值（即堆顶元素），我们始终记录堆顶的最大值即可。当玩家战力更新超过该阈值时，则将其插入到堆中（通过替换堆顶元素并调整后续节点位置）。
b. 如果战力值主要集中在特定范围内（例如0至200分），则可以通过计数排序的思想进行优化。具体而言，在每个可能的分数点上设置一个列表来存储对应的玩家信息，并配合使用哈希表完成快速查找操作。
c. 当战力分布较为分散时，则建议采用链表结构替代数组存储方式（类似第b项方案）。此外，在这种情况下我们需要额外增加一个哈希表来完成键值对到节点位置的映射关系。