面试题打卡——C++版

文章目录

二进制手表

二进制手表顶部有 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;
	}
};
上一篇:为Dynamics 365写一个简单程序实现解决方案一键迁移


下一篇:8.7下周黄金空头趋势是否延续?黄金多单被套怎么解?