siukwan – 第4页 – 我的经验分享

(hiho编程练习赛1) 九宫

1.题目要求判断给出一个幻方，只有一种解法则输出解放，否则输出Too Many；

2.采用深度搜索即可，并且每行，每列，每条对角线的和为15，如果填充后任意一个和不等于15，直接进行剪枝。

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小Hi准备将一个三阶幻方（不一定是上图中的那个）中的一些数组抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一组解。

而你呢，也被小Hi交付了同样的任务，但是不同的是，你需要写一个程序~

输入

输入仅包含单组测试数据。

每组测试数据为一个3*3的矩阵，其中为0的部分表示被小Hi抹去的部分。

对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。

输出

如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。

样例输入

0 7 2
0 5 0
0 3 0

样例输出

6 7 2
1 5 9
8 3 4

AC代码：


//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<bitset>
//#include "siukwanAlloctor.h"
using namespace std;
bool check(vector<vector<int>>&a)
{
	vector<int> row(3, 0);
	vector<int> col(3, 0);
	vector<int> angle(2, 0);

	//计算行总和
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			if (a[i][j] == 0)
			{
				row[i] = 0;
				break;
			}
			else
				row[i] += a[i][j];
		}
		if (row[i] != 0 && row[i] != 15) return false;
	}

	//计算列总和
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			if (a[j][i] == 0)
			{
				col[i] = 0;
				break;
			}
			else
				col[i] += a[j][i];
		}
		if (col[i] != 0 && col[i] != 15) return false;
	}

	//计算对角线
	if (a[0][0] != 0 && a[1][1] != 0 && a[2][2] != 0)
		angle[0] = a[0][0] + a[1][1] + a[2][2];

	if (angle[0] != 0 && angle[0] != 15) return false;

	if (a[2][0] != 0 && a[1][1] != 0 && a[0][2] != 0)
		angle[1] = a[2][0] + a[1][1] + a[0][2];

	if (angle[1] != 0 && angle[1] != 15) return false;

	return true;

}

void dfs(vector<vector<int>>&a, int need, vector<bool>&used,vector<vector<vector<int>>>&result)
{
	if (result.size() >= 2) return;
	if (need == 0)
	{
		if (result.size()==0)
		result.push_back(a);
		else
		{
			for (int i = 0; i < 3; ++i)
			{
				for (int j = 0; j < 3; ++j)
				{
					if (result[0][i][j] != a[i][j])
					{
						result.push_back(a);
						return;
					}
				}
			}
			return;
		}
	}
	for (int k = 1; k < used.size(); ++k)
	{
		if (!used[k])
		{
			used[k] = true;
			for (int i = 0; i < 3; ++i)
			{
				for (int j = 0; j < 3; ++j)
				{
					if (a[i][j] == 0)//需要填充
					{
						a[i][j] = k;//填充为k
						if (check(a))//检测矩阵
							dfs(a, need - 1, used, result);
						a[i][j] = 0;//填充为k
					}
				}
			}
			used[k] = false;
		}
	}
}


int main()
{
	int need = 0;
	vector<vector<int>> a(3, vector<int>(3, 0));
	vector<bool> used(10,false);
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			scanf("%d", &a[i][j]);
			if (a[i][j] == 0) need++;
			used[a[i][j]] = true;
		}
	}

	vector<vector<vector<int>>> result;
	dfs(a, need, used, result);
	if (result.size()>1)
		cout << "Too Many" << endl;
	else
	{
		for (int i = 0; i < 3; ++i)
		{
			for (int j = 0; j < 3; ++j)
			{
				cout << result[0][i][j];
				if (j != 2)
					cout << " ";
				else
					cout << endl;
			}
		}
	}

	return 0;
}

(hiho)1105 : 题外话·堆

思路：
纯粹是堆的建立和push、pop操作，这次没有使用priority_queue，自己编写了堆。

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Ho有一个糖果盒子，每过一段时间小Ho都会将新买来的糖果放进去，同时他也会不断的从其中挑选出最大的糖果出来吃掉，但是寻找最大的糖果不是一件非常简单的事情，所以小Ho希望能够用计算机来他帮忙计算这个问题！

提示：吃糖果吃多了会变胖的！

输入

每个测试点（输入文件）有且仅有一组测试数据。

在一组测试数据中：

第1行为1个整数N，表示需要处理的事件数目。

接下来的M行，每行描述一个事件，且事件类型由该行的第一个字符表示，如果为’A’，表示小Ho将一粒糖果放进了盒子，且接下来为一个整数W，表示这颗糖果的重量；如果为’T’，表示小Ho需要知道当前盒子中最重的糖果的重量是多少，在知道这个值之后，小Ho会将这颗糖果从盒子中取出并吃掉。

对于100%的数据，满足1<=N<=10^5, 1<=w<=10^5。<>

对于100%的数据，满足没有2颗糖果的重量是相同的，最开始的时候小Ho的糖果盒子是空的，且每次小Ho想要取出一颗糖果的时候盒子里一定至少有一颗糖果。

输出

在一组测试数据中：

对于每个类型为’T’的时间，输出1个整数W_MAX，表示在这一时刻，盒子中最重的糖果的重量。

样例输入

样例输出

AC代码：

#include<stdio.h>

int arr[100002] = { 0 };
int size = 0;

int pop()
{
	if (size == 0) return 0;
	int result = arr[0];//获取栈顶元素
	int x = arr[--size];//把队尾元素提到0号位置
	int i = 0;
	int a = i * 2 + 1;//左孩子
	int b = i * 2 + 2;//右孩子

	while (a<size)
	{
		if (b<size&&arr[a]<arr[b])
			a = b;//右孩子比左孩子大
		if (x<arr[a])//孩子的值比父亲大，提上来
			arr[i] = arr[a];
		else//父亲的值比孩子大，停止操作
			break;
		i = a;
		a = i * 2 + 1;
		b = a + 1;
	}
	arr[i] = x;
	return result;
}
void push(int x)
{
	int i = size++;
	int p = (i - 1) / 2;//父亲节点
	while (x>arr[p])
	{//孩子节点的值比父亲的值大
		arr[i] = arr[p];
		i = p;
		if (i == 0) break;
		p = (i - 1) / 2;
	}
	arr[i] = x;
}


int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		char c[10];
		scanf("%s", c);
		if (*c == 'A')
		{
			int x;
			scanf("%d", &x);
			push(x);
		}
		else
			printf("%d\n", pop());
	}
	return 0;
}

House Robber III

1.题目告诉我们相邻的两个父子节点不能同时被偷取，求出最大能偷取的金额。

2.这个题目是典型的树形DP，我们定义了两个DP，一个是被偷取的DP1，一个是不偷取的DP2。然后进行深度优先搜索，计算每一个节点的DP1和DP2，最后输出根节点中DP1和DP2的较大者。

House Robber III

Difficulty: Medium

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

AC代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
        map<TreeNode*,int> dp1;
        map<TreeNode*,int> dp2;
    int rob(TreeNode* root) {
        dfs(root);
        return max(dp1[root],dp2[root]);
    }
    void dfs(TreeNode* root)
    {
        if(root == NULL) return;
        
        dfs(root->left);
        dfs(root->right);
        
        //偷这个节点
        dp1[root]=root->val+dp2[root->left]+dp2[root->right];
        //不偷这个节点
        dp2[root]=max(max(dp1[root->left]+dp1[root->right],dp2[root->left]+dp2[root->right]),
                    max(dp2[root->left]+dp1[root->right],dp1[root->left]+dp2[root->right]));
    }
};

拓扑结构相同子树（KMP应用）

对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。

给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。

解题思路：

1.我们可以对于A树的每一个节点，进行判断，看是否和B相等，但是这样的时间复杂度为O(M*N)，设A的节点数为M，B的节点数为N。

2.另外一种思路就是，我们先把两个树序列化，然后判断strA是否含有strB的子串，判断子串的时候，我们采用KMP算法，这样时间复杂度就可以降为O(M+N)。其中，我们需要采用前序遍历（或后序遍历），确保子树的序列化是连续的。中序遍历会由于插入中间值，导致序列化后不一致。

3.序列化的时候，我们需要对空的叶子节点进行插入特殊符号（数值）操作，这是用于判断只有一个叶子节点的节点的结构，如：

//需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
//如–A—–A
//—/———-\
//–B———-B
//如树1，A的左节点为B，右节点为空
//树2，A的做节点为空，右节点为B
//如果不加叶子节点，那么前序遍历均为AB
//加上叶子节点后，分别为AB###和A#B##，可以判断
AC代码：

       //需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
            //如  A        A
            //   /          \
            //  B            B
            //如果不加叶子节点，那么前序遍历均为AB
            //加上叶子节点后，分别为AB###和A#B##，可以判断
 
/*
对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树
*/
//前序遍历+KMP
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class IdenticalTree {
public:
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        if (B == NULL) return true;
        else if (A == NULL) return false;
        vector<int> pattern;
        vector<int> str;
        dfs(A, str);
        dfs(B, pattern);
        if (str.size()<pattern.size()) return false;
        //构建next数组
        vector<int> next(pattern.size() + 1, 0);
        for (int i = 1; i<pattern.size(); ++i)
        {
            int j = next[i];
            while (j>0 && pattern[i] != pattern[j])
                j = next[j];
            if (pattern[i] == pattern[j])
                next[i + 1] = j + 1;//求next[i+1]的值，所以比较的是p[i]和p[j]
        }
        //使用KMP
        int j = 0;
        for (int i = 0; i<str.size(); ++i)
        {
            while (j>0 && str[i] != pattern[j])
                j = next[j];
            if (str[i] == pattern[j])
                j++;//比较下一个值
            if (j == pattern.size())
            {
                //匹配到字串了，返回真
                return true;
            }
        }
        //没找到，false
        return false;
    }
    //进行前序遍历
    void dfs(TreeNode* root, vector<int>&preOrder)
    {
        if (root == NULL){
            //需要加上叶子节点，加上叶子节点是为了判断当某个节点只有一个叶子节点时，能够知道是左孩子还是右孩子
            //如  A        A
            //   /          \
            //  B            B
            //如果不加叶子节点，那么前序遍历均为AB
            //加上叶子节点后，分别为AB###和A#B##，可以判断
            preOrder.push_back(INT_MAX);
            return;
        }
        preOrder.push_back(root->val);
        dfs(root->left, preOrder);
        dfs(root->right, preOrder);
    }
};

shell sort 希尔排序

希尔排序的核心思想是，利用一个增量序列H[k]（大小为n），其中H[0]=1，对数组进行n次H[k]排序。每次H[k]排序，arr[H[k]]及其后面的元素分别有序地放置在arr[i-n*increment]中。

下面为实现的算法：

void shellSort(vector<int>&arr)
{
	//使用希尔增量序列,Hibbard增量序列为2^n-1
	for (int increment = arr.size() / 2; increment >= 1; increment /= 2)
	{
		for (int i = increment; i < arr.size(); ++i)
		{//把increment及后面的数,排序到 j-2I,j-I,j中。。。
			int x = arr[i];
			int j = i;
			for (j = i; j >= increment; j -= increment)
			{
				if (x < arr[j - increment])//小于,则x应该前移
					arr[j] = arr[j - increment];//把前面的数复制给j
				else
					break;//已经找到合适的位置
			}
			//把x放到合适的位置
			arr[j] = x;
		}
	}
}

nextval数组求法

next数组的求法

1.在KMP字符串匹配算法中，我们需要先求出next数组，由于过程比较抽象，现在一步一步来讲解。

2.next数组的求法：首先next[0]=0，next[1]=1，这个是基础。假设字符串为str，当前位为i，则判断str[i-1]是否等于i-1上对应的next值对应的内容，即str[next[i-1]-1]，为什么还需要把next的值减1？因为next数组的计算，是把字符串按照1，2，3，4。。。。从1开始的规则来计算的。

如果str[i-1]==str[next[i-1]-1]，那么next[i]=next[i-1]+1；

如果不等，我们令j=next[i-1]，判断str[i-1]是否等于str[next[j-1]-1]，如果不等于，我们令j=next[j-1]，继续判断str[i-1]是否等于str[next[j-1]-1]，一直循环判断，直到相等，则next[i]=next[j-1]+1。

我们来看看数组

KMP序号: 1 2 3 4 5 6 7 8 9 10 11 12
string： a b a b a a a b a b a a
next数组：0 1 1 2 3 4 2 2 3 4 5 6
数组idx： 0 1 2 3 4 5 6 7 8 9 10 11

我们从第三位开始分析，

注意下面涉及到的str[i]，是按照正常的string获取位置，不是按照KMP序号，即str为str[0,1,2,3…..10,11]，next为next[0,1,2,3…..10,11]。

第三位i=2：前一位str[1]=’b’，next[1]=1，str[next[1]-1]=’a’，’b’!=’a’，所以再往前一步已经无字符，所以next[2]=1;

第四位i=3：前一位str[2]=’a’，next[2]=1，str[next[2]-1]=’a’，相等，所以next[3]=next[2]+1=2;

第五位i=4：前一位str[3]=’b’，next[3]=2，str[next[3]-1]=str[1]=’b’，相等，所以next[4]=next[3]+1=3;

第六位i=5：前一位str[4]=’a’，next[4]=3，str[next[4]-1]=str[2]=’a’，相等，所以

next[5]=next[4]+1=4;

第七位i=6：前一位str[5]=’a’，next[5]=4，str[next[5]-1]=str[3]=’b’，与str[5]不相等，所以继续看前一个next，即next[next[5]-1]=next[3]，str[next[3]-1]=str[1]=’b’，依然不相等，继续往前看next[next[3]-1]=next[1]，str[next[1]-1]=str[0]=’a’，相等，则next[6]=next[1]+1=2;

第八位i=7：前一位str[6]=’a’，next[6]=2，str[next[6]-1]=str[1]=’b’，与str[6]不相等，所以继续看前一个next，即next[next[6]-1]=next[1]，str[next[1]-1]=’a’，与str[6]相等，所以next[7]=next[1]+1=2;

第九位i=8：前一位str[7]=’b’，next[7]=2，str[next[7]-1]=str[1]=’b’，与str[7]相等，所以next[8]=next[7]+1=3;

第十位i=9：前一位str[8]=’a’，next[8]=3，str[next[8]-1]=str[2]=’a’，与str[8]相等，所以next[9]=next[8]+1=4;

第十一位i=10：前一位str[9]=’b’，next[9]=4，str[next[9]-1]=str[3]=’b’，与str[9]相等，所以next[10]=next[9]+1=5;

第十二位i=11：前一位str[10]=’a’，next[10]=5，str[next[10]-1]=str[4]=’a’，与str[10]相等，所以next[11]=next[10]+1=6;

至此，next数组求取完毕。

初步代码如下：

next[0] = 0;
next[1] = 1;
for (int i = 2; i < str.size(); ++i)
{
	if (str[i - 1] == str[next[i - 1] - 1])
	next[i] = next[i - 1] + 1;
	else
	{
		int j = next[i - 1];
		while (j>0 && str[i - 1] != str[j - 1])
		{
			j = next[j - 1];
		}
		next[i] = next[j] + 1;
	}
}

优化后的代码如下：

next[0] = 0;
next[1] = 1;
for (int i = 2; i < str.size(); ++i)
{
int j = i;
	while (j>1 && str[i - 1] != str[next[j - 1] - 1])
		j = next[j - 1];
	next[i] = next[j - 1] + 1;
}

42. Trapping Rain Water(Hard)

思路：

1.使用两个指针，从两端往内遍历。

2.如果左边的高度小于右边的高度，那么左边的高度则可以填充雨水，但是填充为多少呢？这个时候，需要看左边的左边的最大高度maxL（简称为左边的最大高度），我们可以把雨水填充为左边的最大高度maxL。为什么能够填充为左边的最大高度maxL？

因为在遍历过程中，我们需要左边的高度小于右边的高度才会进行更新最大高度的操作，在这个过程中，我们可以保证存在一个height[right]在maxL的右边，且height[right]>maxL，因此，我们可以填充为左边的最大高度maxL。

3.右边同理。

4.时间复杂度为O(n)，空间复杂度为O(1)。

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

AC代码：

class Solution {
public:
	int trap(vector<int>& height) {
		int left = 0; int right = height.size() - 1;
		int maxL = 0, maxR = 0;
		int result = 0;
		while (left<right)
		{
			if (height[left]<height[right])             {
				if (height[left]>maxL)
					maxL = height[left];//遇到新的高度，则无法填充雨水
				else//height[left]<=maxL                     
					result+=maxL-height[left];                 
				left++;             
			}            
			else             
			{                 
				if(height[right]>maxR)
					maxR = height[right];//遇到新的高度，无法填充雨水
			else
				result += maxR - height[right];
				right--;
			}
		}

		return result;
	}
};

求1+2+3+…+n（不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C））

题目描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

1.这道题目比较有意思，不能使用循环，判断语句。
2.从方法上进行判断，那么有循环和递归，而题目要求不能使用循环，那么可以从递归方面入手。
3.递归需要一个终止条件，而这个终止条件使用了if判断语句，那么我们有没有别的方式不适用if语句判断呢？
4.当然是有的，我们可以使用利用&&符号，如果左边为假，那么右边就不再进行判断。

AC代码如下：

class Solution {
public:
    int Sum_Solution(int n) {
        int sum = n;
        //当sum为0时，不会执行后半个处理
        sum && (sum += Sum_Solution(n - 1));
        return sum;
    } 
};

127. Word Ladder(Hard)

1.分析题目后，我们发现需要找出一条路径，而这条路径的限制是每次只改变一个字母。因此，这也可以理解为求单元最短路径。

2.我们可以考虑采用DFS或者BFS进行搜索。先看看DFS，DFS每次找出一条到达目标点的路径，但是不确定这条路径是否为最短，所以需要遍历完所有的节点才确定到最终解。

3.而BFS相当于一层一层地往外搜索，所以一旦遇到目标点，那么其记录的路径长度就是最短长度，经过上面的分析，我们可以初步使用BFS进行求解。

4.最初的思路是构建好各个单词的邻居，要构建邻居关系，需要对每个单词遍历一次单词表，时间复杂度为O(n*n)，而BFS的复杂度为O(n)，实际我刚开始也是这么做的，结果超时了。单词量能上到2000以上。

5.为了解决构建邻居超时的问题，我换了一种方法，就是事先不构建邻居，而是在BFS中，通过原来的单词进行字母变换，构建出一个新单词，再去判断这个单词是否在wordList中，假设单词长度为k，每个字母替换26次，BFS的复杂度为O(n)，则总的复杂度为（26*k*n）。这样编写程序能够顺利通过测试，耗时460ms。

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

AC代码：

class Solution {
public:

	int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
		map<string, bool> visited;
		int wordSize = beginWord.size();
		
		int length = 1;
		queue<string> q;
		q.push(beginWord);
		visited[beginWord] = true;
		int count1 = 1;
		int count2 = 0;

		while (!q.empty())
		{
			length++;
			for (int i = 0; i < count1; ++i)
			{
				string head = q.front();
				q.pop();
				string tmp = head;

				//替换每个单词的每个字母，看看是否能够在wordList中找到
				for (int j = 0; j < wordSize; ++j)
				{
					tmp = head;
					for (int k = 0; k < 26; k++)
					{
						tmp[j] = 'a' + k;
						if (wordList.find(tmp) != wordList.end()&&!visited[tmp])
						{//找到邻居
							visited[tmp] = true;
							q.push(tmp);
							count2++;
						}
						if (tmp == endWord)
							return length;
					}
				}
			}
			count1 = count2;
			count2 = 0;
		}
		return 0;

	}
};