零成本游戏网站开发,佛山提供网站设计方案公司,河池市住房和城乡建设厅网站,wordpress系统那个主题好用文章目录1. 云栖大会限时抢答赛 - 早间场2. 云栖大会限时抢答赛 - 午间场3. 云栖大会限时抢答赛 - 晚间场1. 云栖大会限时抢答赛 - 早间场
题目链接
该场次题目在 LeetCode 上有原题#xff0c;题解链接如下#xff1a;
LeetCode 862. 和至少为 K 的最短子数组#xff08…
文章目录1. 云栖大会限时抢答赛 - 早间场2. 云栖大会限时抢答赛 - 午间场3. 云栖大会限时抢答赛 - 晚间场1. 云栖大会限时抢答赛 - 早间场
题目链接
该场次题目在 LeetCode 上有原题题解链接如下
LeetCode 862. 和至少为 K 的最短子数组前缀和deque单调栈
2. 云栖大会限时抢答赛 - 午间场
题目 滑动拼图
描述
在一个3x3的网格中放着编号1到8的8块板以及一块编号为0的空格。 一次移动可以把空格0与上下左右四邻接之一的板子交换。 给定初始和目标的板子排布返回到目标排布最少的移动次数。 如果不能从初始排布移动到目标排布返回 -1.
样例1 输入:
[[2,8,3],[1,0,4],[7,6,5]
]
[[1,2,3],[8,0,4],[7,6,5]
]
输出:
4解释:
[ [[2,8,3], [2,0,3],[1,0,4], -- [1,8,4],[7,6,5] [7,6,5]
] ][ [[2,0,3], [0,2,3],[1,8,4], -- [1,8,4],[7,6,5] [7,6,5]
] ][ [[0,2,3], [1,2,3],[1,8,4], -- [0,8,4],[7,6,5] [7,6,5]
] ][ [[1,2,3], [1,2,3],[0,8,4], -- [8,0,4],[7,6,5] [7,6,5]
] ]样例 2
输入:
[[2,3,8],[7,0,5],[1,6,4]]
[[1,2,3],[8,0,4],[7,6,5]]
输出:
-1跟 LeetCode 773. 滑动谜题BFS 地图状态转换的最短距离 几乎一模一样
稍微改改上面的代码就可以了
广度优先搜索把3x3的地图压缩成字符串记录状态不要重复访问
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};int m, n, i, j, k, step 0, size, x, y;
public:/*** param init_state: the initial state of chessboard* param final_state: the final state of chessboard* return: return an integer, denote the number of minimum moving*/int minMoveStep(vectorvectorint board, vectorvectorint final_state) {m board.size(), n board[0].size();string ans, state;for(i 0; i 3; i)for(j 0; j 3; j)ans 0final_state[i][j];int x0, y0, xi, yi;pairint,int xy0;//0的坐标queuestring q;unordered_setstring visited;//访问标记集合state boardToString(board);//初始状态if(state ans)return step;q.push(state);visited.insert(state);while(!q.empty()){step;size q.size();while(size--){xy0 stringToBoard(q.front(), board);//还原地图并得到0的坐标q.pop();x0 xy0.first;y0 xy0.second;for(k 0; k 4; k){ //0可以4个方向交换xi x0dir[k][0];yi y0dir[k][1];if(xi0 xim yi0 yin){swap(board[xi][yi], board[x0][y0]);//交换state boardToString(board);//新的状态if(state ans)return step;if(!visited.count(state))//没有出现过该地图{visited.insert(state);q.push(state);}swap(board[xi][yi], board[x0][y0]);//还原现场}}}}return -1;}string boardToString(vectorvectorint board) { //地图转成字符串string s;for (i 0; i m; i)for(j 0; j n; j)s.push_back(board[i][j]0);return s;}pairint,int stringToBoard(string s, vectorvectorint board){ //字符串还原成地图并return 0的坐标方便下次挪动for (i m-1; i 0; i--)for(j n-1; j 0; j--){board[i][j] s.back()-0;s.pop_back();if(board[i][j] 0)x i, y j;}return make_pair(x, y);}
};1106ms C
3. 云栖大会限时抢答赛 - 晚间场
题目地图跳跃
描述:
给定n×n的地图每个单元都有一个高度每次你只能够往相邻的单元格移动并且要求这两个单元格的高度差不超过target。 你不能走出地图之外。 求出满足从左上角(0,0)走到右下右下角(n-1,n-1)最小的 target
n1000arr[i][j]100000n 1000 arr[i][j] 100000n1000arr[i][j]100000
例 1:
输入:[[1,5],[6,2]],
输出:4,
解释:
有2条路线:
1. 1 - 5 - 2 这条路线上target为4。
2. 1 - 6 - 2 这条路线上target为5。
所以结果为4例 2:
输入:[[1,5,9],[3,4,7],[6,8,1]],
输出:6解题
二分查找答案DFS 判断是否有 一条路径其上的每个相邻点之间的差的绝对值 target
class Solution {vectorvectorint dir {{1,0},{0,1},{-1,0},{0,-1}};int n;
public:/*** param arr: the map* return: the smallest target that satisfies from the upper left corner (0, 0) to the lower right corner (n-1, n-1)*/int mapJump(vectorvectorint arr) {// Write your code here.if(arr.empty()) return 0;n arr.size();int l 0, r 100000, mid, ans;bool way false;while(l r){mid (l r)/2;way false;vectorvectorbool vis(n, vectorbool(n, false));vis[0][0] true;ok(arr, 0, 0, vis, mid, way);//DFSif(way)//有满足要求的路径{ans mid;r mid-1;}elsel mid1;}return ans;}void ok(vectorvectorint arr, int x, int y, vectorvectorbool vis, int target, bool way){if(way) return;if(xn-1 yn-1) {way true;return;}int i, j, k;for(k 0; k 4; k){i x dir[k][0];j y dir[k][1];if(i 0 i n j 0 j n !vis[i][j] abs(arr[i][j]-arr[x][y])target){vis[i][j] true;ok(arr,i,j,vis,target,way);}}}
};101ms C
类似题目LeetCode 1102. 得分最高的路径优先队列BFS/极大极小化 二分查找 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
