杂题

中大

1. 不连续1的子串

题目描述

串只包含0或者1，给定一个数字，输出以此为长度的01串不含连续1的串的个数。
如输入3，则输出5，因为长度为3的01串不含连续1的串包括000, 001, 010, 100, 101。

解题思路

思路1：

(暴力，较复杂)

1. 将0-n的数转成二进制数，用数组存储此二进制数；
2. 遍历此数组，判断1后有没有跟1，若有则break，遍历下一个数；若遍历完数组没有break，则num++。

思路2：将’1’或’0’放置在长度固定为n的数组中，不能有连续的’1’，看有多少种放法。

1. 若放i个’1’，则另外有n-i个0，相当于在i-1个’0’的周围放’1’，有多少种放法；等于组合数C(n-i+1, i)。
2. 遍历i从0-n，累加种数即可。

源代码

思路1：

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdlib.h>
using namespace std;
char a[32] = {
    0};
char* toRadix(int i)
{
    
	itoa(i, a, 2);
	return a;
}
int main()
{
    
	int len, n;
	int count = 0;
	cin >> len;
	n = pow(2, len);
	for(int i = 0; i < n; i++)
	{
    
		char* radix = toRadix(i);
		for(int j = 0; j < 30; j++)
		{
    
			if(radix[j] == '1')
			{
    
				if(radix[j+1] == '1')
				{
    
					break;
				}
			}
			if(j == strlen(radix))
			{
    
				count++;
			}
		}
	}
	cout << count << endl;
	return 0;
} 

思路2：

#include<iostream>
#include<cstdio>
using namespace std;
int Fac(int n){
    
	if(0==n||1==n){
    
		return 1;
	}else{
    
		return n*Fac(n-1);
	}
}
int main(){
    
	int n,res=0,maxNum;
	cin>>n;
	//maxNum=n%2==0?n/2:(n+1)/2;
	maxNum=(n+1)/2;
	for(int i=0;i<=maxNum;i++){
    
		int t=(n-i+1);
		res+=Fac(t)/(Fac(i)*Fac(t-i));
	}
	printf("%d\n",res);
	return 0;
} 

题型分析

1. 字符串题。
2. itoa(value, str, radix)函数可用于进制转换。
3. strlen(可获得字符串的长度)。

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

1. 暴力求解可求得，但效率不高。

此类题模板代码

1. 进制转换。

char a[32] = {
    0};
char* toRadix(int i)
{
    
	itoa(i, a, 2);
	return a;
}

2. 排列组合数

res+=Fac(t)/(Fac(i)*Fac(t-i));

int Fac(int n){
    
	if(0==n||1==n){
    
		return 1;
	}else{
    
		return n*Fac(n-1);
	}
}

2. 循环移位

题目描述

给出字符串A和B，判断A是否是B的进行循环移位得到的子串。
如A = “ABC”，B = “BCDEFA”， 则是。
注意：
循环移位：将最左边的字符移到最右边。

解题思路

思路1：

1. 设A的长度为lenA，B的长度为lenB，对B进行模式匹配，若匹配到则输出"是"。若(i+j > lenb-1)，从B串倒数第i+j-lenb的位置开始匹配，若能匹配到A串，则"是"，否则输出"否"。
   思路2.：
   1.将B串 = B+B，其包含所有通过旋转从A得到的子串；此时只需要判断A是否为B的子串即可，不需要判断是否超出B的长度了，更加简单。

源代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdlib.h>
using namespace std;
int main() {
    
	string A = "cdeeb";
	string B = "abcde";
	int lena = A.length();
	int lenb = B.length();
	for(int i = 0; i < lenb; i++) 
	{
    
		if(B[i] == A[0]) 
		{
    
			int j;
			for(j = 1; j < lena; j++) 
			{
    
				if(i+j > lenb-1) 
				{
    
					if(B[i+j-lenb] == A[j]) 
					{
    
						continue;
					} 
					else 
					{
    
						break;
					}
				}
				if(B[i+j] == A[j]) 
				{
    
					continue;
				} 
				else 
				{
    
					break;
				}
			}
			if(j == lena) 
			{
    
				cout << "true" << endl;
				return 0;
			}
		}

	}
	cout << "false" << endl;
	return false;
	return 0;
}

题型分析

1. 字符串循环比较题。
2. 常规纸上画图就能解决。
   {c,d,e,a,b}
   {a,b,c,d,e}

下次遇到此类题我要注意的地方

	易	中	难
紧		1.字符串循环比较题，记得可以将字符串拼接起来。
般
必

1. string类型获取长度：length()是函数。
2. string类型可通过下标获取某char型字符。

此类题模板代码

for(int i = 0; i < lenb; i++) 
	{
    
		if(B[i] == A[0]) 
		{
    
			int j;
			for(j = 1; j < lena; j++) 
			{
    
				if(i+j > lenb-1) 
				{
    
					if(B[i+j-lenb] == A[j]) 
					{
    
						continue;
					} 
					else 
					{
    
						break;
					}
				}
				if(B[i+j] == A[j]) 
				{
    
					continue;
				} 
				else 
				{
    
					break;
				}
			}
			if(j == lena) 
			{
    
				cout << "true" << endl;
				return 0;
			}
		}

	}

3. 完全平方数

题目描述

https://leetcode-cn.com/problems/perfect-squares/

解题思路

思路1：

1. 使用一个数组a，从2开始遍历其下标，value值=它所需要的完全平方数个数。
2. for循环从1到i-1遍历j，a[i]=min(a[i-1] + 1, a[i-j^2] + 1)。
3. 输出a[n]。

源代码

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
    
	int n;
	cin >> n;
	int *a = (int *)calloc(n + 1, sizeof(int)); 
	a[1] = 1;
	for(int i = 2; i <= n; i++)
	{
    
		a[i] = a[i-1] + 1;
		for(int j = 1; j < i; j++)
		{
    
			if(i - j * j >= 0)
			{
    
				a[i] = min(a[i], a[i - j * j] + 1);
			}
		}
	} 
	cout << a[n] << endl;
} 

题型分析

动态规划题

1. 充分利用数组下标表示数，并遍历。
2. 理清上一个数与下一个数的的关系，在此题中则是若i=一个数m+另一个数j的平方，则它可能更短；令a[i] = min(a[i], a[i - j * j] + 1)即可。

下次遇到此类题我要注意的地方

	易	中	难
紧		1.理清上一个数与下一个数的的关系，在此题中则是若i=一个数m+另一个数j的平方，则它可能更短；令a[i] = min(a[i], a[i - j * j] + 1)即可。
般
必

1. 可利用min()函数。
2. 充分利用数组下标。
3. 此类动态规划题的关键是：找到下一个数+1的条件，即if(i - j * j >= 0)，满足此条件的则需要判断。

此类题模板代码

1. 动态规划

for(int i = 2; i <= n; i++)
	{
    
		a[i] = a[i-1] + 1;
		for(int j = 1; j < i; j++)
		{
    
			if(i - j * j >= 0)
			{
    
				a[i] = min(a[i], a[i - j * j] + 1);
			}
		}
	} 

4. 摆动排序

题目描述

解题思路

思路1：

sort()排序，时间复杂度为nlogn

1. 将nums数组赋值给工作数组a。
2. 将a数组排序。
3. 将a数组分为两部分，一部分是a数组前一半的数，另一部分是后一半的数。
4. 将两部分数组倒序，相间地插入到nums数组中。

思路2：三分法。

源代码

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    
	vector<int> nums = {
    1, 5, 1, 1, 6, 4};
	// 值的传递，不是地址的传递 
	vector<int> a = nums;
	sort(a.begin(), a.end());
	int len = nums.size();
	int sidenum, innum;
    if(len % 2 == 0)
    {
    
        sidenum = innum = len / 2;
    }
    else
    {
    
        sidenum = len / 2 + 1;
        innum = sidenum - 1;
    }
	int j = len-1;
	int m = sidenum - 1;
	for(int i = 0; i < len; i++)
	{
    
		nums[i] = i & 1 ? a[j--] : a[m--];
	}
	
}

题型分析

1. 排序题

下次遇到此类题我要注意的地方

	易	中	难
紧		1.记得要倒序插入。2.sort()排序法。
般
必

此类题模板代码

5. 通过删除字母匹配到字典里最长单词

题目描述

https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/

解题思路

思路1：

1. 两个for循环，一个在外层遍历d[i]，一个在里层遍历s。
2. 里层for里比较的字符为d[i][j]，匹配成功一个字符则计数器加1，当计数器=字符串d[i]的大小时，表示d[i]能够找到。
3. 比较d[i]与当前找到的最大最长且字典序最小的字符串，决定要不要替换。

思路2：引入当前最大变量，和满足题意的先置条件

1. 定义一个字符串curstr=""，表示当前最长字典序最小的字符串。
2. 遍历d，若d[i].length < curstr.length || (d[i].length == curstr.length && strcmp(d[i], curstr) >= 0)，则直接跳过，continue。
3. 若没有满足2中条件，则判断d[i]是不是s的子串，若是的话，则更新curstr。

源代码

#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
using namespace std;

bool isZiChuan(string target, string s)
{
    
	cout << target << endl;
	int j = 0;
	int len1 = target.length();
	int len2 = s.length();
	for(int i = 0; i < len2; i++)
	{
    
		if(j < len1 && target[j] == s[i])
		{
    
			j++; 
		}
	}
	// 判断是否遍历完 
	return j == target.length();
}

int main()
{
    
	string s = "abpcplea", d[] = {
    "ale","apple","monkey","plea"}; 
	string curstr = "";	
	for(int i = 0; i < sizeof(d)/sizeof(string); i++)
	{
    
		if(d[i].length() < curstr.length() || (d[i].length() == curstr.length() && d[i].compare(curstr) >= 0))
		{
    
			continue;
		}
		if(isZiChuan(d[i], s))
		{
    
			curstr = d[i];
		}
	}
	cout << curstr << endl;
	return 0;
} 

题型分析

1. 字符串比较题。
2. 注意引用当前最适合的变量string curstr = “”;并满足题意的先置条件，可跳过一些不必要的比较字符串，提高结题的效率。

	if(d[i].length() < curstr.length() || (d[i].length() == curstr.length() && d[i].compare(curstr) >= 0))
		{
    
			continue;
		}

下次遇到此类题我要注意的地方

	易	中	难
紧		1.判断是否比较完字符串。2利用先知条件跳过一些解。
般
必

1. 利用当前最适合的变量和跳过一些不必要的字符串，提高结题的效率。
2. 判断是否比较完字符串，可比较完之后用等号来解决。
3. strcmp(char *, char *)可比较字符数组char a[] = {“aa”}之间的大小，不可用来比较string类型的大小。
4. str.compare(str2)可用来比较string之间的大小。若str1小于str2，则返回负数；若相等，则返回0；若str1大于str2，则返回正数。

此类题模板代码

1. 判断是否比较完字符串

// 判断是否遍历完 
	return j == target.length();

2. 跳过先置条件

	if(d[i].length() < curstr.length() || (d[i].length() == curstr.length() && d[i].compare(curstr) >= 0))
		{
    
			continue;
		}

5. 对称图形

题目描述

小贝有一个矩形板，矩形板由N行M列的单位方块组成，每个单位方块要么是白色的要么是黑色的.小贝想知道矩形板是否是水平对称或者竖直对称的，你能帮助她吗？
所固水平对称，是指如果将矩形板治着其水平中轴线翻转，得到的矩形板和原来一样.具体地说，如果N是奇数，水平中轴线是指第（N+1/2行方块的中线；如果N是偶数，水平中轴线是指在第/2行和第N/2+1行方块之间的直线.竖直对称的定义类似.

解题思路

思路1：

1. 水平对称a[i][j] == a[i][M-1-j]
2. 垂直对称a[i][j] == a[N-1-i][j]

源代码

#include<iostream>
#include <string>
using namespace std;
char a[51][51];
int main()
{
    
	int count, n, m;
	
	cin >> count;
	for(int i = 0; i < count; i++)
	{
    
		int hor = 0, sym = 0;
		cin >> n >> m;
		for(int p = 0; p < n; p++)
		{
    
			for(int q = 0; q < m; q++)
			{
    
				cin >> a[p][q];
			}
		}
		//是否水平对称 
		int p, q;
		for(p = 0; p < n; ++p)
		{
    
			for(q = 0; q < m/2; q++)
			{
    
				if(a[p][q] != a[p][m-1-q])
				{
    
					break;
				}
			}
		}
		if(p == n && q == int(m/2))
		{
    
			hor = 1;
		}
		//垂直对称 
		for(p = 0; p < m/2; p++)
		{
    
			for(q = 0; q < n; q++)
			{
    
				if(a[p][q] != a[n-1-p][q])
				{
    
					break;
				}
			}
		}
		if(p == int(m/2) && q == m)
		{
    
			sym = 1;
		}
		if(sym && hor)
		{
    
			cout << "both" << endl;
		}
		else if(hor == 1)
		{
    
			cout << "hor" << endl;
		}
		else if(sym == 1)
		{
    
			cout << "sym" << endl;
		}
		// 不满足了才不进入循环了嘛，所以for循环结束后，p=n。 
		//cout << p << endl;
	}
} 

题型分析

1. 非常基础题，注意地图要定义成字符数组类型。char a[51][51]，不要定义成int类型。

下次遇到此类题我要注意的地方

	易	中	难
紧		1.very基础题。注意要定义成char a[][]。
般
必

此类题模板代码

6. 重新安排行程

题目描述

https://leetcode-cn.com/problems/reconstruct-itinerary/

解题思路

思路1：

1. 定义一个行程二维数组，代表最优的行程，初始化为空。
2. 定义一个深度优先函数，先比较其与当前最优行程的自然序，若比其小，则进入继续，否则continue。
3. 通过行程的终点，找到下一躺行程的出发地和；定义visited数组，表示该地有没有来过。

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

7. 验证二叉树

题目描述

https://leetcode-cn.com/problems/validate-binary-search-tree/

解题思路

思路1：

使用二叉树的**中序遍历算法**；中序遍历时，是一个升序的过程，若不满足升序，则不是二叉搜索树。

模拟二叉树思考的过程的解法

1. 从根节点开始DFS，按照中序遍历的规则，依次将结点push到找到二叉树最左的结点。

思路2：上下边界+DFS。引入上下边界，并根据情况变化上下边界。

1. DFS函数中，若根节点为null，则return true。否则，进入2。
2. 根节点val不满足：大于low，小于high，则return false。否则，进入3。
3. 对左右结点都调用DFS。return DFS(root->left, low, root->value) && DFS(root->right, root->value, high)

1…根节点的左节点仅上边界变化(若其不满足：大于low，小于val，则return false。)。
2…根节点的右节点仅下边界变化(若其不满足：大于val，小于high，则return true。)。

思路3：

源代码

思路2：

#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
/**
 * 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:
	    long long high = 10000000000;
	    long long low = -10000000000;
	
	    int count = 0;
	    bool DFS(TreeNode* root, long long low, long long high)
	    {
    
	        count++;
	        if(root == NULL)
	        {
    
	            return true;
	        }
	        
	        if((root->val <= low || root->val >= high))
	        {
    
	            return false;
	        }
	        return DFS(root->left, low, root->val) && DFS(root->right, root->val, high);
	    }
	    bool isValidBST(TreeNode* root) {
    
	        //结构体的指针和结构体
	        if(root == NULL)
	        {
    
	            return true;
	        }
	        return DFS(root, low, high);
	    }
};

int main()
{
    
	Solution sol;
	sol.isValidBST(NULL);
}

题型分析

1. 二叉树+DFS题。
   

下次遇到此类题我要注意的地方

	易	中	难
紧		1.上下边界+DFS。2.前序、中序、后序遍历二叉树(结构体)。
般
必

1. 对于结构体的取值。
2. ->用于结构体指针TreeNode* root，root->val使用其成员。
3. .用于结构体使用其成员。
4. 一个cpp文件一定要有一个main()，新建其他类的对象，调用函数。

此类题模板代码

1. 对于二叉树类题，可考虑用变换上下边界，然后DFS调用其子树解决问题。

if((root->val <= low || root->val >= high))
{
    
	return false;
}
return DFS(root->left, low, root->val) && DFS(root->right, root->val, high);

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码

题目描述

解题思路

思路1：

源代码

题型分析

下次遇到此类题我要注意的地方

	易	中	难
紧
般
必

此类题模板代码