Monthly Archives: May 2017

LeetCode Brick Wall

LeetCode Brick Wall There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks. The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right. If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks. Example:

Input:
[[1,2,2,1],
 [3,1,2],
 [1,3,2],
 [2,4],
 [3,1,2],
 [1,3,1,1]]
Output: 2
Explanation:

Note:
  1. The width sum of bricks in different rows are the same and won’t exceed INT_MAX.
  2. The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.

hihoCoder 1494-一面砖墙完全一样的题,不解释。 代码如下: [cpp] class Solution { public: int leastBricks(vector<vector<int>>& wall) { int height = wall.size(); unordered_map<int, int> cnt; int maxedges = 0; for (int i = 0; i < height; ++i) { int len = 0; for (int j = 0; j < wall[i].size() – 1; ++j) { len += wall[i][j]; ++cnt[len]; maxedges = max(maxedges, cnt[len]); } } return height – maxedges; } }; [/cpp] 本代码提交AC,用时46MS。]]>

LeetCode Subarray Sum Equals K

560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

给定一个数组,问有多少个子数组的和等于k。
暴力方法$O(n^3)$肯定不行,这种连续子数组的问题,肯定会用到数组的前缀和,所以先把前缀和求出来sum[i],这样任意区间[i,j]之间的和都可以用sum[i]-sum[i-1]求到。不过还是需要$O(n^2)$的时间,代码如下:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n == 0)
            return 0;
        vector<int> sum(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            sum[i] = sum[i – 1] + nums[i – 1];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (sum[j] – sum[i] == k)
                    ++ans;
            }
        }
        return ans;
    }
};

本代码提交AC,用时533MS。

看了下tag要用map来做。我们把所有前缀和及其频率存到一个map中,假设当前前缀和为sum,则如果sum-k也在map中,说明由产生sum-k前缀和的位置到当前位置的和是k。
比如样例[1,1,1],遇到第一个1时,前缀和为1,之前没有前缀和为1的情况,所以map[1]=1。当加到最后一个数时,前缀和sum=3,sum-k=1也在map中,正好说明从1开始到结束的位置的和为2,如果map[1]=2,说明有两个前缀和等于1的位置,也就有两个连续和为2的子数组。
代码如下,注意只能在遍历的同时求ans,不能等map都构建好了再求ans,这样保证前缀和为sum-k的位置肯定在i前面,也就是我们统一前缀和为k的结束位置为i,做到不重不漏。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n == 0)
            return 0;
        int ans = 0, sum = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < n; ++i) {
            ++cnt[sum];
            sum += nums[i];
            ans += cnt[sum – k];
        }
        return ans;
    }
};

本代码提交AC,用时36MS。

二刷。思路同上,但不把sum=0插入到map中,会不会更好理解一些:

class Solution {
public:
	int subarraySum(vector<int>& nums, int k) {
		int i = 0, j = 0, n = nums.size();
		map<int, int> sum_cnt;
		int sum = 0, ans = 0;
		for (int i = 0; i < n; ++i) {
			sum += nums[i];
			if (sum == k)++ans;
			if (sum_cnt.find(sum - k) != sum_cnt.end()) {
				ans += sum_cnt[sum - k];
			}
			++sum_cnt[sum];
		}
		return ans;
	}
};

本代码提交AC,用时56MS。

LeetCode Subtree of Another Tree

LeetCode Subtree of Another Tree Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s:
     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.
判断二叉树t是否是二叉树s的子树。如果t是s从node0开始的子树,则t必须和node0子树完全一样,node0不能有多余的孩子,比如样例2中node0的子树多有一个节点0,所以是False。 首先写一个子程序check判断子树s和t是否相等,然后在主程序中使用先序遍历s,如果发现s的某个节点node0的值和t的根节点相等,则可以进入check(node0,t)判断node0子树是否和t相等。 代码如下: [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; queue<TreeNode*> q; q.push(s); while (!q.empty()) { TreeNode *tmp = q.front(); q.pop(); if (tmp->val == t->val) { if (check(tmp, t))return true; } if (tmp->left != NULL)q.push(tmp->left); if (tmp->right != NULL)q.push(tmp->right); } return false; } }; [/cpp] 本代码提交AC,用时29MS。 还有一种更简洁漂亮的解法。如果t是s的子树,有三种情况,t要么和s完全相等check(s,t),要么等于s的某个左子树isSubtree(s->left,t),要么等于s的某个右子树isSubtree(s->right,t)。所以主程序和子程序都可以递归。 代码如下: [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; if (check(s, t))return true; return isSubtree(s->left, t) || isSubtree(s->right, t); } }; [/cpp] 本代码提交AC,用时32MS。]]>

LeetCode Can I Win

LeetCode Can I Win In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100. Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally. You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300. Example

Input:
maxChoosableInteger = 10
desiredTotal = 11
Output:
false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

又是一道博弈论的题。两个人从1~n中拿数字,问哪个人拿到的数字之和先大于等于desiredTotal。 边界条件是,如果n大于等于desiredTotal,则A开始拿最大数肯定能赢;另一种情况是,如果n个数之和都小于desiredTotal,则无论怎么拿都不可能超过desiredTotal,A不能获胜。 我们用一个长度为n的字符串表示n个数字被拿的状态,’0’表示没被拿,’1’表示被拿了,当然可以用int和位运算来表示,我这里用string是偷懒了。 再用一个hash[string][bool]表示当n个数字的状态为string时A获胜的情况。那么每次A可以从string中为’0’的位置拿数字,如果此时sum + i >= desiredTotal则A肯定获胜;或者sum + i < desiredTotal但是下一轮B没有获胜,即 !win(sum + i, desiredTotal, visited, result),A也是获胜的。 代码如下: [cpp] class Solution { private: bool win(int sum, int &desiredTotal, string &visited, unordered_map<string,bool>& result) { if (result.find(visited) != result.end())return result[visited]; for (int i = 1; i < visited.size(); ++i) { if (visited[i] == ‘0’) { visited[i] = ‘1’; if (sum + i >= desiredTotal || !win(sum + i, desiredTotal, visited, result)) { visited[i] = ‘0’; //reset result[visited] = true; return true; } visited[i] = ‘0’; //reset } } result[visited] = false; return false; } public: bool canIWin(int maxChoosableInteger, int desiredTotal) { if (maxChoosableInteger >= desiredTotal)return true; int sum = (1 + maxChoosableInteger)*maxChoosableInteger / 2; if (sum < desiredTotal)return false; string visited(maxChoosableInteger + 1, ‘0’); unordered_map<string, bool> result; return win(0, desiredTotal, visited, result); } }; [/cpp] 本代码提交AC,用时309MS。]]>

LeetCode Predict the Winner

LeetCode Predict the Winner Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins. Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score. Example 1:

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
  1. 1 <= length of the array <= 20.
  2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
  3. If the scores of both players are equal, then player 1 is still the winner.

有关博弈论的题。有两个人A和B,每个人每次能从数组开始或结束位置拿掉一个数,A先拿,谁拿的数字之和越大获胜,问A是否可以获胜。 因为每个人都尽最大的努力想要获胜,所以如果A拿了num[0],那么B从剩余的nums[1~n-1]拿数字的过程相当于A从nums[0~n-1]拿数字的过程,所以最优化拿数字的过程是一样的。 假设子问题为A从区间nums[s,…,e]拿数字尽量使自己赢,那么如果s==e,只有一个元素,则A拿到的元素和就为这个元素nums[s]。否则A可以尝试拿首元素nums[s],此时B尽力从nums[s+1,…,e]中拿使B自己赢,所以A的收益就是nums[s]减去B从nums[s+1,…,e]拿到的收益;A也可以拿尾元素nums[e],此时B尽力从nums[s,…,e-1]中拿使B自己赢,所以A的收益就是nums[e]减去B从nums[s,…,e-1]拿到的收益。A的最大收益就是拿首元素或尾元素获得的收益的较大值,如果大于等于0,说明A可以获胜。 递归代码如下: [cpp] class Solution { private: int helper(vector<int>& nums, int s, int e) { if (s == e)return nums[s]; else return max(nums[s] – helper(nums, s + 1, e), nums[e] – helper(nums, s, e – 1)); } public: bool PredictTheWinner(vector<int>& nums) { int n = nums.size(); return helper(nums, 0, n – 1) >= 0; } }; [/cpp] 本代码提交AC,用时96MS。 还有一种更清晰的DP方法。假设dp[s][e]为A从区间nums[s,…,e]拿获得的最大收益,如果A拿首元素nums[s],则获得的收益为nums[s]-dp[s+1][e],因为B要从剩余的nums[s+1,..,e]拿尽量使自己赢,就相当于A从nums[s+1,…,e]要使自己赢,所以过程都是一样的,dp[s+1][e]就是B的收益。类似的,如果A拿尾元素,则获得的收益为nums[e]-dp[s][e-1]。所以有: $$!dp[s][e]=max(nums[s]-dp[s+1][e],nums[e]-dp[s][e-1])$$ 因为大区间的dp[s][e]会用到较小区间的dp[s+1][e]和dp[s][e-1],所以可以区间长度进行DP,先求出小区间的值,求大区间时直接用小区间的值就好了。 代码如下: [cpp] class Solution { public: bool PredictTheWinner(vector<int>& nums) { int n = nums.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i)dp[i][i] = nums[i]; // 长度为0 for (int len = 1; len < n; ++len) { for (int s = 0; s + len < n; ++s) { dp[s][s + len] = max(nums[s] – dp[s + 1][s + len], nums[s + len] – dp[s][s + len – 1]); } } return dp[0][n – 1] >= 0; } }; [/cpp] 本代码提交AC,用时3MS。比递归版本快了很多。]]>

LeetCode Friend Circles

LeetCode Friend Circles There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends. Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are directfriends with each other, otherwise not. And you have to output the total number of friend circles among all the students. Example 1:

Input:
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
Example 2:
Input:
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
  1. N is in range [1,200].
  2. M[i][i] = 1 for all students.
  3. If M[i][j] = 1, then M[j][i] = 1.

给定一个矩阵,M[i][j]=1表示i和j有直接关系,如果i和j有直接关系,j和k有直接关系,则i和k有间接关系。问这个矩阵共有多少个关系网。 简单题,有两种解法。第一种解法是DFS或者BFS,每次把能搜索到的点标记为一个新的关系网,直到所有点都属于一个关系网。但是无论DFS还是BFS,复杂度都比较高。 这种题应该条件反射想到并查集,只要M[i][j]=1,则把i和j union起来,最后看一下有多少个代表就好了。这种解法非常简单,代码如下: [cpp] class Solution { private: int n; vector<int> parent; void init() { parent.resize(n); for (int i = 0; i < n; ++i) { parent[i] = i; } } int find_set(int x) { if (parent[x] != x) parent[x] = find_set(parent[x]); return parent[x]; } void union_set(int u, int v) { parent[find_set(u)] = find_set(v); } public: int findCircleNum(vector<vector<int>>& M) { n = M.size(); init(); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (M[i][j] == 1) { union_set(i, j); } } } set<int> circles; for (int i = 0; i < n; ++i)circles.insert(find_set(i)); // 注意最后还要find一下找到代表 return circles.size(); } }; [/cpp] 本代码提交AC,用时19MS。]]>

LeetCode Distribute Candies

LeetCode Distribute Candies Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain. Example 1:

Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies.
Example 2:
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies.
Note:
  1. The length of the given array is in range [2, 10,000], and will be even.
  2. The number in given array is in range [-100,000, 100,000].

分糖果问题。给定一个糖果数组,不同数字表示不同种糖果,同一种糖果可能有多个。现在要把这些糖果等数量的分给哥哥和妹妹,问妹妹最多能分到多少种类型的糖果。 简单题,把所有糖果hash一下,看看一共有多少种类型的糖果,如果糖果类型数超过一半,则可以把所有不同类型的糖果拿出来给妹妹,则妹妹得到的糖果类型最多,是n/2。否则有多少种类型的糖果,妹妹最多也只能得到多少中类型的糖果。 代码如下: [cpp] class Solution { public: int distributeCandies(vector<int>& candies) { int n = candies.size(); unordered_map<int, int> table; for (int i = 0; i < n; ++i)++table[candies[i]]; if (table.size() >= n / 2)return n / 2; else return table.size(); } }; [/cpp] 本代码提交AC,用时282MS。]]>

LeetCode Reshape the Matrix

LeetCode Reshape the Matrix In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data. You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively. The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were. If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix. Example 1:

Input:
nums =
[[1,2],
 [3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 2:
Input:
nums =
[[1,2],
 [3,4]]
r = 2, c = 4
Output:
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
Note:
  1. The height and width of the given matrix is in range [1, 100].
  2. The given r and c are all positive.

把一个n*m的矩阵按行重新组织为r*c的矩阵,相当于MATLAB的reshape函数。 简单题,新矩阵中第cnt个数,在原矩阵中的位置是(cnt/m,cnt%m)。 代码如下: [cpp] class Solution { public: vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) { int n = nums.size(), m = nums[0].size(); if (n*m != r*c)return nums; vector<vector<int>> ans(r, vector<int>(c, 0)); for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { int cnt = i*c + j; ans[i][j] = nums[cnt / m][cnt % m]; } } return ans; } }; [/cpp] 本代码提交AC,用时62MS。]]>

hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

#1519 : 逃离迷宫II

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi被坏女巫抓进里一间有N x M个格子组成的矩阵迷宫。 有些格子是小Hi可以经过的,我们用’.’表示;有些格子上有障碍物小Hi不能经过,我们用’#’表示。小Hi的起始位置用’S’表示,他需要到达用’T’表示的格子才能逃离迷宫。 麻烦的是小Hi被坏女巫施了魔法,他只能选择上下左右某一个方向,沿着这个方向一直走,直到遇到障碍物或者迷宫边界才能改变方向。新的方向可以是上下左右四个方向之一。之后他还是只能沿着新的方向一直走直到再次遇到障碍物或者迷宫边界…… 小Hi想知道他最少改变几次方向才能逃离这个迷宫。

输入

第一行包含两个整数N和M。  (1 <= N, M <= 500) 以下N行每行M个字符,代表迷宫。

输出

一个整数代表答案。如果小Hi没法逃离迷宫,输出-1。
样例输入
5 5
S.#.T
.....
.....
.....
.....
样例输出
2

给定一个迷宫,S表示起点,T表示终点,#表示障碍物。行走的时候,只能沿着直线走,直到遇到障碍物或者碰壁,问从S到T,最少需要改变多少次方向。 我一开始是用DFS做的,每次朝一个方向DFS下去,但是因为每次DFS时走了一长条直线,所以回溯的时候需要把之前走过的直线复位。代码如下: [cpp] #include<iostream> #include<vector> #include<climits> #include<algorithm> #include<set> #include<unordered_set> #include<unordered_map> #include<cmath> using namespace std; const int MAXN = 505; int n, m; int startx, starty, endx, endy; int ans = INT_MAX; vector<vector<char>> maze(MAXN, vector<char>(MAXN, ‘0’)); vector<vector<char>> visited(MAXN, vector<char>(MAXN, ‘0’)); vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向 bool ok(int x, int y) { if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != ‘#’)return true; return false; } void dfs(int sx,int sy, int step) { for (int i = 0; i < 4; ++i) { int newx = sx + dirs[i][0], newy = sy + dirs[i][1]; if (ok(newx, newy) && visited[newx][newy] == ‘0’) { visited[newx][newy] = ‘1’; bool done = false; while (ok(newx, newy)) { visited[newx][newy] = ‘1’; if (newx == endx&&newy == endy) { done = true; break; } newx = newx + dirs[i][0], newy = newy + dirs[i][1]; } if (done) { ans = min(ans, step); } else { dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1); // 往回走一步再递归 } while (!(newx == sx&&newy == sy)) { if (ok(newx, newy))visited[newx][newy] = ‘0’; // 复位 newx = newx + opdirs[i][0], newy = newy + opdirs[i][1]; } } } } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); char c; for (int i = 0; i < n; ++i) { scanf("%c", &c); for (int j = 0; j < m; ++j) { scanf("%c", &maze[i][j]); if (maze[i][j] == ‘S’) { startx = i; starty = j; } else if (maze[i][j] == ‘T’) { endx = i; endy = j; } } } visited[startx][starty] = ‘1’; dfs(startx, starty, 0); if (ans == INT_MAX)printf("-1\n"); else printf("%d\n", ans); return 0; } [/cpp] 本代码提交TLE,很明显会TLE,因为DFS必须把所有方案都走一遍才能得到最小值。 比赛的时候脑子短路,这种搜索问题要求最短XX的肯定用BFS比DFS快呀,因为第一次BFS到的方案肯定就是最优方案呀。只不过这题判断距离用的是转弯次数,以前都是算走过的步数。 对于这题,用BFS也是一样的,BFS的下一个点肯定就是走直线走到无法再走的那个拐角点(cornor)。不过为了防止死循环,要把以前走过的拐角都记录下来,只走那些以前没走过的拐点。 代码如下: [cpp] #include<iostream> #include<vector> #include<climits> #include<algorithm> #include<set> #include<unordered_set> #include<unordered_map> #include<cmath> #include<queue> using namespace std; const int MAXN = 505; int n, m; int startx, starty, endx, endy; typedef struct P { int x, y, step; P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {}; }; vector<vector<char>> maze(MAXN, vector<char>(MAXN, ‘0’)); vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向 set<int> points; bool ok(int x, int y) { if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != ‘#’)return true; return false; } int id(int x, int y) { return x*n + y; } int bfs() { queue<P> q; P p(startx, starty, 0); q.push(p); while (!q.empty()) { p = q.front(); q.pop(); points.insert(id(p.x, p.y)); for (int i = 0; i < dirs.size(); ++i) { int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1]; while (ok(newx, newy)) { if (newx == endx&&newy == endy) { return p.step; } newx = newx + dirs[i][0], newy = newy + dirs[i][1]; } int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步 if (points.find(id(cornorx, cornory)) == points.end()) { P tmp(cornorx, cornory, p.step + 1); q.push(tmp); } } } return -1; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); char c; for (int i = 0; i < n; ++i) { scanf("%c", &c); for (int j = 0; j < m; ++j) { scanf("%c", &maze[i][j]); if (maze[i][j] == ‘S’) { startx = i; starty = j; } else if (maze[i][j] == ‘T’) { endx = i; endy = j; } } } printf("%d\n", bfs()); return 0; } [/cpp] 本代码提交AC,用时718MS。]]>

hihoCoder 1518-最大集合

hihoCoder 1518-最大集合

#1518 : 最大集合

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个1-N的排列A[1], A[2], … A[N],定义集合S[K] = {A[K], A[A[K]], A[A[A[K]]] … }。 显然对于任意的K=1..N,S[K]都是有限集合。 你能求出其中包含整数最多的S[K]的大小吗?

输入

第一行包含一个整数N。(1 <= N <= 100000) 第二行包含N个两两不同的整数,A[1], A[2], … A[N]。(1 <= A[i] <= N)

输出

最大的S[K]的大小。
样例输入
7
6 5 1 4 2 7 3
样例输出
4

给定一个1~N的排列A,然后定义关于k的集合S[K] = {A[K], A[A[K]], A[A[A[K]]] … },要求最大的S[K]的大小。 分析一下样例,当k=1时,S[1]={6,7,3,1,6…},循环节是{6,7,3,1},然后又从6开始循环,但是S是集合,所以|S[1]|=4。当k=2时,S[2]={5,2,5…},循环节是{5,2},所以|S[2]|=2。当k=3时,S[3]={1,6,7,3,1…},发现规律了吗,根据集合的无序性,S[3]==S[1]的。 其实这有点像置换群,6开始的循环节中,对于{6,7,3,1}中的任意一个数K,都有S[K]=4。同理对于另一个循环节{2,5}中的任意一个数K,都有S[K]=2。所以其实我们不需要对A中的所有数都求S[K],只需要求出一个循环节之后,其循环内的所有K的S[K]都相等,这样可以节省很多重复计算。 最后从多个不相交的循环中求最大的S[K]即可。 代码如下: [cpp] #include<iostream> #include<vector> #include<climits> #include<algorithm> #include<set> #include<unordered_set> #include<unordered_map> #include<cmath> using namespace std; unordered_map<int, int> result; void solve(vector<int>& A, int start) { unordered_set<int> si; si.insert(start); int last = start; while (si.find(A[last]) == si.end()) { si.insert(A[last]); last = A[last]; } int ans = si.size(); unordered_set<int>::iterator it = si.begin(); while (it != si.end()) { result[*it] = ans; // 循环内的所有S[K]都相等 ++it; } } int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d", &n); vector<int> A(n + 1, 0); for (int i = 1; i <= n; ++i)scanf("%d", &A[i]); for (int i = 1; i <= n; ++i) { if (result.find(A[i]) == result.end())solve(A, A[i]); } int ans = 0; for (unordered_map<int, int>::iterator it = result.begin(); it != result.end(); ++it)ans = max(ans, it->second); printf("%d\n", ans); return 0; } [/cpp] 本代码提交AC,用时271MS。]]>