2020云棲大會編程限時搶答賽 - 早中晚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 < = a r r [ i ] [ j ] < = 100000 n <= 1000 <= arr[i][j] <= 100000 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);//DFS
        	if(way)//有滿足要求的路徑
        	{
        		ans = mid;
        		r = mid-1;
        	}
        	else
        		l = 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阿明），一起加油、一起學習進步！