文章目錄

• • 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 {vector<vector<int>> 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(vector<vector<int>> &board, vector<vector<int>> &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 += '0'+final_state[i][j];int x0, y0, xi, yi;pair<int,int> xy0;//0的坐標queue<string> q;unordered_set<string> 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 = x0+dir[k][0];yi = y0+dir[k][1];if(xi>=0 && xi<m && yi>=0 && yi<n){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(vector<vector<int>>& board) { //地圖轉成字符串string s;for (i = 0; i < m; i++)for(j = 0; j < n; j++)s.push_back(board[i][j]+'0');return s;}pair<int,int> stringToBoard(string &s, vector<vector<int>>& 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

$n<=1000<=arr[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 {vector<vector<int>> 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(vector<vector<int>> &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;vector<vector<bool>> vis(n, vector<bool>(n, false));vis[0][0] = true;ok(arr, 0, 0, vis, mid, way);//DFSif(way)//有滿足要求的路徑{ans = mid;r = mid-1;}elsel = mid+1;}return ans;}void ok(vector<vector<int>> &arr, int x, int y, vector<vector<bool>>& vis, int target, bool& way){if(way) return;if(x==n-1 && y==n-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阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的2020云栖大会编程限时抢答赛 - 早中晚3场题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。