LeetCode 笔记
一 二叉树
T.102 二叉树层序遍历
- 调用队列 queue 记录每一层的节点
- push到一个一维vector中
- 记录每一层的节点个数 按照节点个数for 循环遍历当前层的节点
- 最后push 到二维vector中
T.98 验证二叉搜索树
使用中序遍历 左子树->根节点->右子树 应有序排列
- 左子树递归
- 保存一个prev节点 将根节点与prev的值比较 比较完后更新prev
- 右子树递归
T.199 二叉树的右视图
二叉树的右视图可以看作是层次遍历每次只取每一层的最右边的元素
T.113 路径总和
回溯法
用tempList保存现有的路径
查看现有tempList是否符合条件，若符合，则添加到res中，若不符合，则继续深度搜索 递归
每次搜索 都弹出tempList中的元素
##二 排序
T.75 颜色分类
原地排序
双指针，将0和2交换到数组前一部分和后一部分，中间则为1
三 哈希表
T.169 多数元素
unordered_map统计出现频率
删除字符串中出现次数最少的字符
int mi=a[s[0]-'a'];//出现最少的字符次数
for(int i=1;i<n;++i)
{
if (a[s[i]-'a']<mi)
{
mi=a[s[i]-'a'];//出现最少的字符次数
}
}
for(int i=0;i<n;++i)
{
if (a[s[i]-'a']>mi)
cout<<s[i];
}T.136 只出现一次的数字
两个相同的数异或的结果为 0，对所有数进行异或操作，最后的结果就是单独出现的那个数。
T.260 不重复的两个元素
两个不相等的元素在位级表示上必定会有一位存在不同。
将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。
diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。
T.461 统计两个数的二进制表示有多少位不同
对两个数进行异或操作，位级表示不同的那一位为 1，统计有多少个 1 即可。
int z = x ^ y;
int cnt = 0;
while(z != 0) {
if ((z & 1) == 1) cnt++;
z = z >> 1;
}
return cnt;4.字符串排序
1.英文字母从 A 到 Z 排列，不区分大小写
同一个英文字母的大小写同时存在时，按照输入顺序排列。
将字符转化为数字0-26存在vector中
for(int j=0;j<26;j++)
{
for(int i=0;i<n;i++){
if(s[i]-'a'==j||s[i]-'A'==j){
res.push_back(s[i]);}
}
}
//即完成了排序//再将转到字符串中
for(int i=0,k=0;(i<n)&&k<res.size();i++)
{
if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
s[i]=res[k++];
}5.最长有效括号
/*在此方法中，我们利用两个计数器 \textit{left}left 和 \textit{right}right 。首先，我们从左到右遍历字符串，对于遇到的每个 \text{‘(’}‘(’，我们增加 \textit{left}left 计数器，对于遇到的每个 \text{‘)’}‘)’ ，我们增加 \textit{right}right 计数器。每当 \textit{left}left 计数器与 \textit{right}right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 \textit{right}right 计数器比 \textit{left}left 计数器大时，我们将 \textit{left}left 和 \textit{right}right 计数器同时变回 00。
这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。
解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：
当 \textit{left}left 计数器比 \textit{right}right 计数器大时，我们将 \textit{left}left 和 \textit{right}right 计数器同时变回 00
当 \textit{left}left 计数器与 \textit{right}right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串
这样我们就能涵盖所有情况从而求解出答案。*/
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = max(maxlength, 2 * right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (int i = (int)s.length() - 1; i >= 0; i--) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxlength;
}6.计算出识别码，并输出完整的ISBN码
首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。
int main()
{
string a;
int s = 0;
vector<int> temp;
getline(cin, a);
if (a.size() != 11) {
cout << "ERROR" << endl; return 0;
}
for (int i = 0; i<11; i++) {
if (i == 1 || i == 5) {
if (a[i] != '-') { cout << "ERROR" << endl; return 0; }
}
else {
if (a[i]>'9' || a[i]<'0') { cout << "ERROR" << endl; return 0; }
}
}
int j = 0;
for (int i = 0; i < a.size(); i++) {
if (isdigit(a[i]))
temp.push_back(a[j]);
}
int k = 1;
for (auto n: temp) {
s += n*k;
k++;
}
cout << a << "-";
if (s % 11 == 10) cout << 'X' << endl;
cout << s % 11 << endl;
system("pause");
return 0;
}7.字符串算式
class Solution {
public:
int calculate(string s) {
//stack<int> st;
int res = 0, n = s.size(), sign = 1;
for (int i = 0; i<n; i++) {
int num = 0;
if (s[i] >= '0') {
while (i<n && s[i] >= '0') {
num = num * 10 + (s[i] - '0');
i++;
}
i--;
res += sign * num;
}
else if (s[i] == '+') sign = 1;
else if (s[i] == '-') sign = -1;
/*else if (s[i] == '(') {
st.push(res);
st.push(sign);
res = 0;
sign = 1;
}*/
/*else if (s[i] == ')') {
res *= st.top(); st.pop();
res += st.top(); st.pop();
}*/
}
return res;
}
};
int main()
{
cout << Solution().calculate("32+23-2") << endl; // 2
return 0;
}8.重复字符最长串
题目描述：给定一串字符，里面有些字符有连续出现的特点，请寻找这些连续出现字符中最长的串，如果最长的串有多个，请输出字符ASCII码最小的那一串。
例如：输入aaabbbbbcccccccczzzzzzzz，输出cccccccc。
解答：利用两个长度为2的数组，一个存放当前字符及其连续重复长度，另一个存放历史最长重复的字符及其长度值。只要做好逻辑思路就应该能轻松做完：
#include <iostream>
using namespace std;
#include <string>
int main()
{
string s;
getline(cin, s);
char c[2] = { s.at(0) };
int num[2] = { 1 };
for (int i = 1; i < s.length(); i++) {
if (s.at(i) == c[0])
num[0]++;
else {
if (num[0] > num[1] || (num[0] == num[1] && c[0] < c[1])) {
c[1] = c[0];
num[1] = num[0];
}
c[0] = s.at(i);
num[0] = 1;
}
}
if (num[0] > num[1] || (num[0] == num[1] && c[0] < c[1])) {
c[1] = c[0];
num[1] = num[0];
}
for (int i = 0; i < num[1]; i++)
cout << c[1];
return 0;
}
9.小镇广告牌
题目描述：已知某小镇的房子沿直线分布，给定一个有序整数数组arr，里面的每个镇代表小镇每栋房子的一维坐标点。现在需要建N个广告牌，广告牌只能建立在这些坐标点上，使得每个坐标点离广告牌的总距离最短，求这个最短的总距离。
输入描述：输入最后一个为N值，其余的为arr值，需要考生自行处理。
例如：输入1 2 3 4 5 1000 2，输出6。
#include <iostream>
using namespace std;
int main()
{
int arr[100] = { 0 };
int m = 0, n; //m：小镇个数；n：广告牌个数
int x, dis[100][100] = { 0 };
int total[100][100] = { 0 };
while (cin >> x)
arr[m++] = x;
n = arr[--m];
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
for (int k = i; k <= j; k++)
dis[i][j] += abs(arr[(i + j) / 2] - arr[k]);
}
}
for (int i = 0; i < m; i++)
total[i][1] = dis[i][m - 1];
for (int i = 2; i <= n; i++) {
for (int j = 0; j < m; j++) {
for (int k = j; k <= m-i; k++)
total[j][i] = dis[j][k] + total[k + 1][i - 1];
}
}
cout << total[0][n] << endl;
return 0;
}
10.IP地址交集判断
#include<stdio.h>
#include<stdlib.h>
#include<cassert>
using namespace std;
int *dec2bin(int decnum)
{
int i, a, *b = { 0 };
a = decnum;
for (i = 7; i >= 0; i--)
{
b[i] = a % 2;
a = a / 2;
}
return b;
}
int ipToInt(char *ipString)
{
assert(ipString != NULL);
int i = 0, j, n, count = 0, return_num = 0;
char *tmp;
int *tmp_num=NULL, *num=NULL, *d2b;
char *s = ipString, *s_tmp=NULL;
if (*s == '.')
count++;
count++;
if (count != 4)
return 0;
while (*s != '\0')
{
if (*s != '.')
{
n = s - s_tmp;
tmp = (char*)malloc(n*sizeof(char));
memcpy(tmp, s, n);
tmp_num[i] = atoi(tmp);
d2b = dec2bin(tmp_num[i]);
for (j = 0; j<8; j++)
num[8 * i + j] = d2b[j];
s++;
i++;
s_tmp = s;
}
s++;
}
if (*s = '\0')
{
n = s - s_tmp;
tmp = (char*)malloc(n*sizeof(char));
memcpy(tmp, s, n);
tmp_num[i] = atoi(tmp);
d2b = dec2bin(tmp_num[i]);
for (j = 0; j<8; j++)
num[8 * i + j] = d2b[j];
}
for (j = 0; j<32; j++)
return_num = return_num * 2 + num[j];
return return_num;
}
int main(void)
{
char *s1, *s2, *s3, *s4;
s1 = new char;
s2 = new char;
s3 = new char;
s4 = new char;
cin >> s1 >> s2 >> s3 >> s4;
int n1, n2, n3, n4, i;
n1 = ipToInt(s1);
n2 = ipToInt(s2);
n3 = ipToInt(s3);
n4 = ipToInt(s4);
if (n4<n1 || n3>n2)
cout << "No Overlap IP" << endl;
else
cout << "Overlap IP" << endl;
system("pause");
return 0;
}
查看7道真题和解析