文章目录
二进制手表
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。小时不会以零开头：例如，“01:00” 是无效的时间，正确的写法应该是 “1:00” 。分钟必须由两位数组成，可能会以零开头：例如，“10:2” 是无效的时间，正确的写法应该是 “10:02”
题解：
1.给定亮起的灯的数量，求所有的时间，排列组合问题 -> 回溯法
2.分析时钟：分别有 1 2 4 8 四种灯，因此循环的开始是1，并且每次增加的是自身
3.分析分钟： 分别有 1 2 4 8 16 32 六种灯，循环的开始是1，并且每次增加自身
4.时钟的递归构建：
a.递归终止条件:灯的数量超过了给定的数量
b.时间超过了规定的时间(11点)
5.分钟的递归构建:
a.递归终止条件:灯的数量超过了给定的数量(给定的灯 - 时钟用去的灯 )
b.时间超过了规定的时间(59分钟)
class Solution {
public:
void Watchminute(vector<string>& ret,int hours,int minute,int count,int num,int sub)
{
if(minute>59||count>num)//时间超了
return;
if(count==num)//灯数量到了
{
//将对应的时间保存起来
string temp;
temp+=to_string(hours);
temp+=":";
if(minute<10)
{
temp+=to_string(0);
}
temp+=to_string(minute);
ret.push_back(temp);
return;
}
for(int i=sub;i<=32;i+=i)
{
minute+=i;//时间增加
count++;//灯数量增加
Watchminute(ret,hours,minute,count,num,sub+=sub);//sub+=sub相同的灯只可出现一次
minute-=i;
count--;
}
}
void Watchhours(vector<string>&ret,int hours,int count,int num,int sub)
{
if(count>num||hours>11||num==0)//灯的数量超了或者小时数超了
return;
Watchminute(ret,hours,0,0,num-count,1);
for(int i=sub;i<=8;i+=i)
{
count++;//灯数量计数器
hours+=i;
Watchhours(ret,hours,count,num,sub+=sub);
hours-=i;
count--;
}
}
vector<string> readBinaryWatch(int turnedOn) {
//整数，表示亮着的LED数量，所有可能的时间
//一个灯表示的小时: 1 2 4 8
//一个灯表示的分钟:1 2 4 8 16 32 -> 循环从1开始，每次翻倍自身
int num=0;
vector<string> ret;
if(turnedOn==0)
{
string temp("0:00");
ret.push_back(temp);
return ret;
}
Watchhours(ret,0,0,turnedOn,1);
return ret;
}
};
打开转盘锁
题解1：
采用bfs的搜索办法，每一个位置有两种变化，即加1或者减1，如果变化之后的字符串没有访问过或者没有在死亡数组里面，则将其添加至下一层的队列
当队列为空时，说明达到不了目的地
如果出队的元素等于目标字符串，那么返回当前元素所在层数即可
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
int count=0;
queue<string> qe;
string str="0000";
unordered_set<string> st;//死亡数组
unordered_set<string> st2;//记录这个数字是否出现过
for(auto&e:deadends)
{
st.insert(e);
}
if(st.find(str)!=st.end())//第一个就是死亡数字
return -1;
if(target==str)//第一个就是密码
return count;
qe.push(str);
st2.insert(str);
int size=1;//记录每一层的数字的个数
while(!qe.empty())
{
//从队列之中取出数字
str=qe.front();
qe.pop();
size--;
if(str==target)
return count;
//将数字添加到队列之中
for(int i=0;i<str.size();i++)
{
//当前数字+1
if(str[i]=='9')
str[i]='0';
else
str[i]=str[i]+1;
if(st.find(str)==st.end()&&st2.find(str)==st2.end())//不是锁定数字
{
qe.push(str);
st2.insert(str);
}
//恢复原来模样
if(str[i]=='0')
str[i]='9';
else
str[i]=str[i]-1;
//当前数字-1
if(str[i]=='0')
str[i]='9';
else
str[i]=str[i]-1;
if(st.find(str)==st.end()&&st2.find(str)==st2.end())//不是锁定数字
{
qe.push(str);
st2.insert(str);
}
if(str[i]=='9')
str[i]='0';
else
str[i]=str[i]+1;
}
if(size==0)//当前层的数字全部用完了
{
count++;
size=qe.size();
}
}
return -1;
}
};
题解2：
方法1中，假设没有死亡数组，每一个位置有两种变化，即每一个数字对应八种变化，对应的增长是很恐怖的，因此可以用双向bfs的方法进行优化
给两个队列，两个哈希表，一个队列从“0000”出发 一个队列从target出发，如果两个队列相遇了，说明找到了最短的路径，此时的路径长度为 count1+count2
搜索的顺序，可以是谁的队列元素少，谁就去进行搜索，这样才能保证平衡
class Solution {
public:
void bfs(unordered_set<string> &dead, queue<string> &qe, unordered_map<string, int> &mp1,
unordered_map<string, int> &mp2, int &count, int &ret)
{
int size = qe.size();//获取当前层的队列的元素个数
while (size)
{
//取出元素
string str = qe.front();
qe.pop();
size--;
//将下一层的元素添加至队列之中
for (int i = 0; i<4; i++)
{
//拷贝
string add(str);
string sub(str);
//数字加1
if (add[i] == '9')
add[i] = '0';
else
add[i] = add[i] + 1;
//数字减1
if (sub[i] == '0')
sub[i] = '9';
else
sub[i] = sub[i] - 1;
if (mp2.find(add) != mp2.end() )//对端已经访问过了
{
ret = count + 1 +mp2[add];
return;
}
if (mp2.find(sub) != mp2.end())
{
ret = count + 1+ mp2[sub];
return;
}
//不在死亡列表之中，且没有出现过
if (dead.find(add) == dead.end() && mp1.find(add) == mp1.end())
{
qe.push(add);
mp1[add] = count + 1;//表示这个字符串，出现在第几层
}
if (dead.find(sub) == dead.end() && mp1.find(sub) == mp1.end())
{
qe.push(sub);
mp1[sub] = count + 1;//表示这个字符串，出现在第几层
}
}
}
count++;//下一次访问的层数
}
int openLock(vector<string>& deadends, string target) {
queue<string> qe1;
queue<string> qe2;
string str = "0000";
unordered_set<string> dead;//记录死亡数字
unordered_map<string, int> mp1;//记录搜索到的节点，并且记录当前节点是第几层
unordered_map<string, int> mp2;
for (auto&e : deadends)
{
dead.insert(e);
}
if (dead.find(str) != dead.end())//第一个就是死亡数字
return -1;
if (target == str)//第一个就是密码
return 0;
//一个从起点搜索，一个从终点开始搜索
qe1.push(str);
qe2.push(target);
int count1 = 0;
int count2 = 0;
mp1[str] = count1;
mp2[target] = count2;
while (!qe1.empty() && !qe2.empty())//两个都不为空，有一个为空说明过不去
{
int ret = -1;
if (qe1.size() <= qe2.size())
bfs(dead, qe1, mp1, mp2, count1, ret);
else
bfs(dead, qe2, mp2, mp1, count2, ret);
if (ret != -1)
return ret;
}
return -1;
}
};
滑动谜题
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
题解：
1.和上一题的本质是一样的，都是用双向bfs来进行解题
2.首先将二维数组转换成字符串，比较好操作
3.在一次bfs之中，首先找到0的位置，再用0的位置与上下左右进行交换
4.当与左边交换的时候，左边坐标 sub>=0 && sub!=2 ，等于2时，是从下一层跳到了上一层
5.当与右边交换的时候，右边左边 sub<str.size() && sub !=3，等于3时，是从上一层跳到了下一层
6.当sub-3>=0 || sub +3 <str.size() 表示可以与上面或者下面进行交换
class Solution {
public:
void bfs(queue<string>&qe,unordered_map<string,int>&mp1,unordered_map<string,int>&mp2,int &count,int &ret)
{
int size=qe.size();
while(size)
{
//去除字符串
string str=qe.front();
qe.pop();
size--;
//添加下一层的字符串
int sub=0;
for(int i=0;i<str.size();i++)//找到0的位置
{
if(str[i]=='0')
{
sub=i;
break;
}
}
if(sub-1>=0&&sub-1!=2)//和左边进行交换
{
string left=str;
left[sub-1]=str[sub];
left[sub]=str[sub-1];
if(mp2.find(left)!=mp2.end())//在另外一边出现过了
{
ret=count+1+mp2[left];
return;
}
if(mp1.find(left)==mp1.end())//没有出现过
{
mp1[left]=count+1;
qe.push(left);
}
}
if(sub+1<str.size()&&sub+1!=3)//和右边进行交换
{
string right=str;
right[sub+1]=str[sub];
right[sub]=str[sub+1];
if(mp2.find(right)!=mp2.end())//在另外一边出现过了
{
ret=count+1+mp2[right];
return;
}
if(mp1.find(right)==mp1.end())//没有出现过
{
mp1[right]=count+1;
qe.push(right);
}
}
if(sub-3>=0)//和上面进行交换
{
string up=str;
up[sub-3]=str[sub];
up[sub]=str[sub-3];
if(mp2.find(up)!=mp2.end())//在另外一边出现过了
{
ret=count+1+mp2[up];
return;
}
if(mp1.find(up)==mp1.end())//没有出现过
{
mp1[up]=count+1;
qe.push(up);
}
}
if(sub+3<str.size())//和下面进行交换
{
string down=str;
down[sub+3]=str[sub];
down[sub]=str[sub+3];
if(mp2.find(down)!=mp2.end())//在另外一边出现过了
{
ret=count+1+mp2[down];
return;
}
if(mp1.find(down)==mp1.end())//没有出现过
{
mp1[down]=count+1;
qe.push(down);
}
}
}
count++;
}
int slidingPuzzle(vector<vector<int>>& board) {
//首先转换成字符串(哈希表无法直接处理二维数组)
string end_str="123450";
string str;
for(int i=0;i<2;i++)
{
for(int j=0;j<3;j++)
{
str+=to_string(board[i][j]);
}
}
if(str==end_str)//相等了，不用进行变化
return 0;
queue<string> qe1;
queue<string> qe2;
unordered_map<string,int>mp1;
unordered_map<string,int>mp2;
int count1=0;
int count2=0;
qe1.push(str);
qe2.push(end_str);
mp1[str]=0;
mp2[end_str]=0;
int ret=-1;
while(!qe1.empty()&&!qe2.empty())//两个都不为空
{
if(qe1.size()<qe2.size())
bfs(qe1,mp1,mp2,count1,ret);
else
bfs(qe2,mp2,mp1,count2,ret);
if(ret!=-1)
return ret;
}
return -1;
}
};
堆盘子
堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
题解：
1.用一个数组来保存栈
2.需要操作的时候，就是操作最后一个栈，下标即为数组的大小-1
3.当栈为空的时候，在数组中将这个栈去除掉
4.插入的时候，如果栈满了，则用rsize在后面增加一个
5.注意cap==0时，此时不能进行任何操作
class StackOfPlates {
public:
StackOfPlates(int cap)
:_cap(cap)
{}
void push(int val) {//入栈
if(_cap==0)
return ;
int sub=st.size()-1;
if(sub<0||st[sub].size()==_cap)//没有栈，或者栈满了
{
st.resize(st.size()+1);
sub++;
}
st[sub].push(val);
}
int pop() {
if(_cap==0)
return -1;
int sub=st.size()-1;
if(sub<0)//没有栈
return -1;
int num=st[sub].top();
st[sub].pop();
if(st[sub].empty())//为空
st.erase(st.begin()+sub);
return num;
}
int popAt(int index) {//指定栈进行pop操作,index是栈的下标
if(_cap==0)
return -1;
if(index>=st.size())//不存在这个栈
return -1;
int num=st[index].top();
st[index].pop();
if(st[index].empty())//为空删除
st.erase(st.begin()+index);
return num;
}
vector<stack<int>> st;
int _cap;
};
直线上最多的点数
题解：
1.双重for循环，以每一个节点为基点，计算在当前节点所在直线的节点的个数
2.用map保存每次的斜率
3.由于精度的问题，因此斜率用字符串表示，字符串之中，保存的是约定的斜率
class Solution {
public:
int maxchild(int y, int x)//求最大公约数
{
if (x == 0)//分子为0
return 1;
int c = y%x;
while (c)
{
y = x;
x = c;
c = y%x;
}
return x;
}
int maxPoints(vector<vector<int>>& points) {
int max = 0;
for (int i = 0; i<points.size(); i++)
{
unordered_map<string, int> mp;//用string来保存斜率
int x1 = points[i][0];
int y1 = points[i][1];
for (int j = i + 1; j<points.size(); j++)
{
int x2 = points[j][0];
int y2 = points[j][1];
int y = y2 - y1;
int x = x2 - x1;
int flag = 1;
if (x*y<0)//算符号
flag = -1;
y = abs(y);
x = abs(x);
int num = maxchild(y, x);//得到最大公约数
//约分处理
y /= num;
x /= num;
//得到斜率
string k;
if (flag == -1)
k += '-';
k += to_string(y);
k += to_string(x);
if (x == 0)//此时为竖线
mp[to_string(abs(x2))]++;
else
mp[k]++;//该斜率上增加一个点
}
for (auto&e : mp)
{
max = fmax(e.second, max);
}
}
return max+1;
}
};