前言:昨天技术群里分享了下头条的算法笔数题，感觉上呢头条的笔数题都是你肯定能做出来，考察的是你的编程技巧。下面的文章汇总群里面的讨论意见和我自己的想法。
基础备份：算法是时间复杂度计算方式
头条的笔试题如下：
一、第一题
思路：
- 假设bean（int x，int y）,给定n多边形为list<bean<int,int>>;
- 遍历list，计算周长，并新建list，存储到当前节点的长度信息lengths。
- 根据等分信息循环，判断当前等分节点的长度在lengths的位置，定位到两个节点之间，根据两个节点的坐标性质设置等分节点坐标。
崩废话，上代码
并没有
二、第二题
思路：
- 首先注意是两个单向链表，定义单向链表bean(int value,next bean);
- 遍历链表，定义两个指针，将两个链表转置并记录下长的那个链表是谁。
- 新建一个链表存结果或者以长的链表为准存结果，两个链表一起循环，将对应位置的值相加，注意进位，注意链表可能要扩容。
- 对计算结果再转置一次输出。
崩废话，上代码
并没有
三、第三题 计算积水量
1 第一版思路如下：
-设置左右两个标记节点，左节点满足的条件是：必须下一个节点数比他小；右节点满足的条件是：必须比左节点大并且不是左节点的下一个节点
-遍历数组，从数组0位置开始判断符合条件的左右节点，如果有，进入计算环节
-计算方法是：sum（每个位置的水量=右节点值-左节点值-当前节点值）
-设置右节点为左节点，继续执行上面的操作，直到右节点为数组边界。
算法的问题：只能解决右节点一直比左节点大的计算，如果右节点比左节点大，也能存水，但是上面的方法就计算不出来了。如下图标记的部分，上面的算法是计算不出来的。
2 第二版思路如下：
根据群右说的，其实应该先找到最大节点，然后最大节点的左右分别计算就好了。如图：
所以步骤如下：
设置名词：下一个节点：当前节点右方向的节点；上一个节点：当前节点左方向的节点
注意为了代码复用，我将左右节点换成start、end描述，还是沿用第一版的解题思路
-遍历数组，找到数组中最大节点的位置，标记一下为n。
-1 设置start、end两个标记节点，start节点满足的条件是：必须下一个节点数比他小；end节点满足的条件是：必须比start节点大并且不是start节点的下一个节点
-2 遍历数组，从数组0位置开始判断符合条件的start、end节点，如果有，进入计算环节
-3 计算方法是：sum（每个位置的水量=end节点值-start节点值-当前节点值）
-4 设置end节点为start节点，继续执行上面的操作，直到end节点为n。
-对最大节点右面的数据，相当于计算方向要跟左面的数据计算方式是反着的。可以沿用上面的计算流程，方法能够复用，只是传参不同。
-1 设置start、end两个标记节点，start节点满足的条件是：必须上一个节点数比他小；end节点满足的条件是：必须比start节点大并且不是start节点的上一个节点
-2 遍历数组，从数组最大位置开始判断符合条件的start、end节点，如果有，进入计算环节
-3 计算方法是：sum（每个位置的水量=end节点值-start节点值-当前节点值）
-4 设置end节点为start节点，继续执行上面的操作，直到end节点为n。
3 第三版思路如下：
分析发现计算水量的算法增加了时间复杂度，其实我们不用单写个方法，在遍历过程中我们就能计算出来。
水量是什么？ 水量就是(end值-start值)*(end位置-start位置-1)-sum(当中节点的值)，你对着图比划一下吧，能理解我的意思 哈哈。如算式，我们其实只设置一个sum字段，存储当中节点的值的和就可以了。第二版算法改造如下：
设置名词：下一个节点：当前节点右方向的节点；上一个节点：当前节点左方向的节点
注意为了代码复用，我将左右节点换成start、end描述，还是沿用第一版的解题思路
-遍历数组，找到数组中最大节点的位置，标记一下为n。
-1 设置start、end两个标记节点，start节点满足的条件是：必须下一个节点数比他小；end节点满足的条件是：必须比start节点大并且不是start节点的下一个节点；设置满足条件的中间节点的和的变量为sum。
-2 遍历数组，从数组0位置开始判断符合条件的start节点，如果找到start节点，继续遍历找到end节点，遍历的同时sum+=每个节点的值，直到找到end节点，调用计算公式进行计算水量=(end值-start值)*(end位置-start位置-1)-sum
-3 设置end节点为start节点，继续执行上面的操作，直到end节点为n。
-对最大节点右面的数据，相当于计算方向要跟左面的数据计算方式是反着的。可以沿用上面的计算流程，方法能够复用，只是传参不同。
-1 设置start、end两个标记节点，start节点满足的条件是：必须上一个节点数比他小；end节点满足的条件是：必须比start节点大并且不是start节点的上一个节点
-2 遍历数组，从数组最大位置开始判断符合条件的start节点，如果找到start节点，继续遍历找到end节点，遍历的同时sum+=每个节点的值，直到找到end节点，调用计算公式进行计算水量=(end值-start值)*(end位置-start位置-1)-sum
-3 设置end节点为start节点，继续执行上面的操作，直到end节点为n。
4 计算时间复杂度
遍历一次找最大值o(n)，如果是用最大顶堆算法去找时间复杂度应该能到o(logn)，如果我没记错的话,但是要copy一个新的数组。
计算过程应该也是o(n),所以总的时间复杂度为2*o(n),不知道计算的有没有问题哈。
5 崩废话，上代码
//遍历一遍，找到最大值的位置
static int searchMaxNode(int[] orgVector) {
int position = 0;
for (int i = 0; i < orgVector.length; i++) {
int value = orgVector[i];
if (value > orgVector[position]) {
position = i;
}
}
return position;
}
/**
* 计算水量 最大值的左右两边分别计算
*
* @param orgVector 数组
* @param maxPosition 最大节点位置
* @param isZero 是否从0开始
*/
static int count(int[] orgVector, int maxPosition, boolean isZero) {
int start = 0, end = 0, sum = 0, waterNum = 0;
boolean isStart = false; //是否开始计算
if (isZero) { //从0位置开始搜索
for (int i = 0; i <= maxPosition; i++) {
//查找start节点
if (!isStart) {
if (i + 1 == orgVector.length) { //如果马上就越界了，就退出
break;
}
if (orgVector[i] < orgVector[i + 1]) {
continue;
} else {
start = i;
isStart = true;
continue;
}
}
//查找end节点
if (isStart) {
if (i == start + 1) { //end节点不能是start的下一个节点
sum += orgVector[i];
continue;
} else if (orgVector[i] < orgVector[start]) {
sum += orgVector[i];
continue;
} else if (orgVector[i] >= orgVector[start]) {
end = i;
//水量=max(end值,start值)*(end位置-start位置-1)-sum(当中节点的值)
waterNum += orgVector[start] * (+end - start - 1) - sum;
sum = 0;
if (i + 1 == orgVector.length) { //如果马上就越界了，就退出
break;
}
if (orgVector[i] > orgVector[i + 1]) { //判断当前end节点符不符合start节点的要求
start = end;
isStart = true;
} else {
isStart = false;
}
}
}
if (end == maxPosition) {
break;
}
}
} else {//从最大位置开始
for (int i = orgVector.length - 1; i >= maxPosition; i--) {
//查找start节点
if (!isStart) {
if (i - 1 < 0) { //如果马上就越界了，就退出
break;
}
if (orgVector[i] < orgVector[i - 1]) {
continue;
} else {
start = i;
isStart = true;
continue;
}
}
//查找end节点
if (isStart) {
if (i == start - 1) { //end节点不能是start的上一个节点
sum += orgVector[i];
continue;
} else if (orgVector[i] < orgVector[start]) {
sum += orgVector[i];
continue;
} else if (orgVector[i] >= orgVector[start]) {
end = i;
//水量=max(end值,start值)*(end位置-start位置-1)-sum(当中节点的值)
waterNum += orgVector[start] * (-end + start - 1) - sum;
sum = 0;
if (i - 1 < 0) { //如果马上就越界了，就退出
break;
}
if (orgVector[i] > orgVector[i - 1]) { //判断当前end节点符不符合start节点的要求
start = end;
isStart = true;
} else {
isStart = false;
}
}
}
if (end == maxPosition) {
break;
}
}
}
return waterNum;
}
/**
* 计算水量 最大值的左右两边分别计算，不过复用了循环
*
* @param orgVector 数组
* @param maxPosition 最大节点位置
* @param step 步长：+1/-1
* @param begin 起始位置
*/
static int count(int[] orgVector, int maxPosition, int step, int begin) {
int start = 0, end = 0, sum = 0, waterNum = 0;
boolean isStart = false; //是否开始计算
int i = begin;
while (i != maxPosition+step) {
//查找start节点
if (!isStart) {
if ((i + step == orgVector.length) || (i + step < 0)) { //如果马上就越界了，就退出
break;
}
if (orgVector[i] < orgVector[i + step]) {
i = i + step;
continue;
} else {
start = i;
isStart = true;
i = i + step;
continue;
}
}
//查找end节点
if (isStart) {
if (i == start + step) { //end节点不能是start的下一个节点
sum += orgVector[i];
i = i + step;
continue;
} else if (orgVector[i] < orgVector[start]) {
sum += orgVector[i];
i = i + step;
continue;
} else if (orgVector[i] >= orgVector[start]) {
end = i;
//水量=max(end值,start值)*(end位置-start位置-1)-sum(当中节点的值)
waterNum += orgVector[start] * (step * end - step * start - 1) - sum;
sum = 0;
if ((i + step == orgVector.length) || (i + step < 0)) { //如果马上就越界了，就退出
break;
}
if (orgVector[i] > orgVector[i + step]) { //判断当前end节点符不符合start节点的要求
start = end;
isStart = true;
} else {
isStart = false;
}
}
}
if (end == maxPosition) {
break;
}
i = i + step;
}
return waterNum;
}
static int WaterCount(int[] orgVec) {
int waterNum = 0;
int maxPosition = searchMaxNode(orgVec);
waterNum += count(orgVec, maxPosition, true); //从头
waterNum += count(orgVec, maxPosition, false); //从尾
// waterNum += count(orgVec, maxPosition, +1, 0); //从头
// waterNum += count(orgVec, maxPosition, -1, orgVec.length - 1); //从尾
return waterNum;
}
public static void main(String[] args) {
int[] sampleVec = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println(WaterCount(sampleVec));
int[] sampleVec1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println(WaterCount(sampleVec1));
int[] sampleVec2 = {3, 2, 1, 1, 2, 3};
System.out.println(WaterCount(sampleVec2));
int[] sampleVec3 = {3, 2, 1, 1, 2, 3, 1, 1, 4};
System.out.println(WaterCount(sampleVec3));
int[] sampleVec4 = {3, 2, 1, 1, 1, 2, 4, 1, 1, 3, 2, 1};
System.out.println(WaterCount(sampleVec4));
int[] sampleVec5 = {1, 2, 3, 4, 5, 6};
System.out.println(WaterCount(sampleVec5));
int[] sampleVec6 = {6, 5, 4, 3, 2, 1};
System.out.println(WaterCount(sampleVec6));
}
6另外一种很牛逼的解题视角。是一个群友提出的，如下图：
你横着看，水量是什么？第1行，水量就是数组值是0的个数啊，怎么算第2行呢，玩过俄罗斯方块没，把第1行干掉就行了啊，就是所有数组的值-1，第2行不就下沉到第1行了吗，哈哈 666
崩废话，上代码 这个是c++版哈
#include <iostream>
#include <vector>
//每个数减1,返回是否都为0
bool DescreOne(std::vector<int>& orgVector)
{
bool bAllZero= true;
for(std::size_t i = 0 ; i < orgVector.size(); i++)
{
if(orgVector[i]>0)
{
orgVector[i]--;
bAllZero =false;
}
}
return bAllZero;
}
//左边第一个不为0到右边第一个不为0的数中间一共多少个0
int CountLine(const std::vector<int> orgVector)
{
std::size_t leftNotZeroIndex = 0;
std::size_t rightNotZeroIndex = orgVector.size();
//计算左边的坐标
while(leftNotZeroIndex < orgVector.size())
{
if(orgVector[leftNotZeroIndex]>0)
{
break;
}
leftNotZeroIndex++;
}
//计算右边的坐标
while(rightNotZeroIndex > 0)
{
if(orgVector[rightNotZeroIndex] > 0)
{
break;
}
rightNotZeroIndex--;
}
//数0
int nCount = 0;
while( leftNotZeroIndex < rightNotZeroIndex)
{
if(orgVector[leftNotZeroIndex]==0)
{
nCount++;
}
leftNotZeroIndex++;
}
return nCount;
}
int WaterCount(std::vector<int> orgVec)
{
int nSum = 0;
int nCount = 0;
while(true)
{
nCount = CountLine(orgVec);
nSum += nCount;
if(DescreOne(orgVec))
{
break;
}
}
return nSum;
}
int main(int argc,char * argv[])
{
std::vector<int> sampleVec = {0,1,0,2,1,0,1,3,2,1,2,1};
std::cout<<WaterCount(sampleVec)<<std::endl;
std::vector<int> sampleVec1 = {0,1,0,2,1,0,1,3,2,1,2,1};
std::cout<<WaterCount(sampleVec1)<<std::endl;
std::vector<int> sampleVec2 = {3,2,1,1,2,3};
std::cout<<WaterCount(sampleVec2)<<std::endl;
std::vector<int> sampleVec3 = {3,2,1,1,2,3,1,1,4};
std::cout<<WaterCount(sampleVec3)<<std::endl;
std::vector<int> sampleVec4 = {3,2,1,1,1,2,4,1,1,3,2,1};
std::cout<<WaterCount(sampleVec4)<<std::endl;
return 0;
}
我翻译了java版
//每个数减1,返回是否都为0
static boolean DescreOne(int[] orgVector)
{
boolean bAllZero= true;
for(int i = 0 ; i < orgVector.length; i++)
{
int value = orgVector[i];
if(value>0)
{
orgVector[i] = (value-1);
bAllZero =false;
}
}
return bAllZero;
}
//左边第一个不为0到右边第一个不为0的数中间一共多少个0
static int CountLine(int[] orgVector)
{
int leftNotZeroIndex = 0;
int rightNotZeroIndex = orgVector.length-1;
//计算左边的坐标
while(leftNotZeroIndex < orgVector.length)
{
if(orgVector[leftNotZeroIndex]>0)
{
break;
}
leftNotZeroIndex++;
}
//计算右边的坐标
while(rightNotZeroIndex > 0)
{
if(orgVector[rightNotZeroIndex] > 0)
{
break;
}
rightNotZeroIndex--;
}
//数0
int nCount = 0;
while( leftNotZeroIndex < rightNotZeroIndex)
{
if(orgVector[leftNotZeroIndex]==0)
{
nCount++;
}
leftNotZeroIndex++;
}
return nCount;
}
static int WaterCount(int[] orgVec)
{
int nSum = 0;
int nCount = 0;
while(true)
{
nCount = CountLine(orgVec);
nSum += nCount;
if(DescreOne(orgVec))
{
break;
}
}
return nSum;
}
public static void main(String[] args) {
int[] sampleVec = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(WaterCount(sampleVec));
int[] sampleVec1 = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(WaterCount(sampleVec1));
int[] sampleVec2 = {3,2,1,1,2,3};
System.out.println(WaterCount(sampleVec2));
int[] sampleVec3 = {3,2,1,1,2,3,1,1,4};
System.out.println(WaterCount(sampleVec3));
int[] sampleVec4 = {3,2,1,1,1,2,4,1,1,3,2,1};
System.out.println(WaterCount(sampleVec4));
}
