走迷宫
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8
C++
#include<iostream> #include<cstring> using namespace std; typedef pair<int, int> PII; const int N = 110; int n, m; int g[N][N]; // 记录输入的矩阵 int d[N][N]; // 记录当前的距离 PII q[N * N]; // 这里是数组来模拟队列 int bfs() { int hh = 0, tt = 0; // 数组的头和尾 q[0] = {0, 0}; // 初始化 最开始还没有走的 点的坐标是（x, y）= （0，0） // 把这个第一个坐标入队 memset(d, -1, sizeof(d)); // 把这个当前距离的数组初始化为-1 代表还没有走过 d[0][0] = 0; // 这个是最开始第一个点还没有走过 所以距离是0 int dx[4] = { -1, 0, 1, 0 }; // 这里记录了4个方向的坐标(-1,0),(1,0),(0,1),(0,-1) int dy[4] = { 0, 1, 0, -1 }; // 通过分别对四个方向坐标的相加 判断 可以知道是否应该 往这个方向走 while (hh <= tt) // 判断队列是否为空 { auto t = q[hh++]; // 取队首， 并队首元素出队 for (int i = 0; i < 4; i++) { int x = t.first + dx[i], y = t.second + dy[i]; // 枚举向每个方向移动的情况 if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) // 这里的判断条件的含义是 尝试这个当前这个方向之后的得到的 x, y值 // 没有过边界 而且新的这条路g[x][y] == 0表示可以走 // d[x][y] == -1表示这条路还没有走过 { d[x][y] = d[t.first][t.second] + 1; // 然后路的长度 + 1 q[++tt] = {x, y}; // 把新的坐标入队 } } } return d[n - 1][m - 1]; } int main() { cin >> n >> m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> g[i][j]; } } cout << bfs() << endl; return 0; }
Java
import java.io.*; import java.util.*; class Pair{ int x; int y; public Pair(int x, int y) { this.x = x; this.y = y; } } public class Main { static int n, m; static int N = 110; static int [][] map = null; static int [][] d = null; static void bfs() { Queue<Pair> q = new LinkedList<Pair>(); int [] dx = {-1, 0, 1, 0}; int [] dy = {0, 1, 0, -1}; q.offer(new Pair(0, 0)); while(!q.isEmpty()) { Pair pair = q.poll(); if (pair.x == n - 1 && pair.y == m - 1) break; for (int i = 0; i < 4; ++ i) { int x = pair.x + dx[i]; int y = pair.y + dy[i]; if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0 && d[x][y] == 0) { q.offer(new Pair(x, y)); d[x][y] = d[pair.x][pair.y] + 1; } } } System.out.println(d[n - 1][m - 1]); } public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String [] nums = reader.readLine().split(" "); n = Integer.parseInt(nums[0]); m = Integer.parseInt(nums[1]); map = new int [n][m]; d = new int [n][m]; for (int i = 0; i < n; ++ i) { String [] inputs = reader.readLine().split(" "); for (int j = 0; j < m; ++ j) { map[i][j] = Integer.parseInt(inputs[j]); } } bfs(); } }
每天一道算法题
最长连续不重复子序列
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5
1 2 2 3 5
输出样例：
3
提交代码
#include<bits/stdc++.h> using namespace std; const int N = 100010; int a[N], s[N]; int n, res; int main() { cin >> n; for (int i = 0; i < n; ++ i) cin >> a[i]; for (int i = 0, j = 0; i < n; ++ i) { s[a[i]] ++; // 记录下a[i]出现的次数 while(s[a[i]] > 1) // 一点碰见两个重复的元素后 { s[a[j]] --; // 这里要主要的一点是这个算法是没有回溯的 // 不要被for循环里面的条件误导以为会回溯、 // 现在遇到两个相同的元素了 // ！！！ 现在是这个算法最厉害的地方 // 这个j代表的是 j可以到达最左的地方 所以在j左边的 // 元素的个数就需要都-- 这点很妙 // 每次求的是 j到i之间的符合条件的最大值 j ++; // 然后j++ } res = max(res, i - j + 1); // 这个res的含义是 在i这个位置、 // 可以达到的符合题目条件的最大长度 } cout << res; return 0; }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ Scanner in = new Scanner(System.in); int n = in.nextInt(); int [] a = new int [n + 10]; int [] s = new int [n + 10]; int res = 0; for (int i = 0; i < n; ++ i) a[i] = in.nextInt(); for (int i = 0, j = 0; i < n; ++ i) { s[a[i]] ++; while(s[a[i]] > 1) { s[a[j]] --; j ++; } res = Math.max(res, i - j + 1); } System.out.println(res); } }
