 CYa想要速通

UCL统计

CYa想要速通
22分钟前

CYa想要速通
11小时前

### 题目描述

On a 2-dimensional grid, there are 4 types of squares:

1. 1 represents the starting square. There is exactly one starting square.
2. 2 represents the ending square. There is exactly one ending square.
3. 0 represents empty squares we can walk over.
4. -1 represents obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

#### 样例

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)


### 算法1

##### (暴力DFS回溯) $O(mn)$

First find out where the start and the end is.
Also We need to know the number of empty cells.

We we try to explore a cell,
it will change 0 to -2 and do a dfs in 4 direction.

If we hit the target and pass all empty cells, increment the result.

#### Python 代码

def uniquePathsIII(self, A: List[List[int]]) -> int:
self.res = 0
m, n, empty = len(A), len(A), 1
for i in range(m):
for j in range(n):
if A[i][j] == 1:
x, y = (i, j)
elif A[i][j] == 0:
empty += 1

def dfs(x, y, empty):
if not (0 <= x < m and 0 <= y < n and A[x][y] >= 0): return
if A[x][y] == 2:
self.res += empty == 0
return
A[x][y] = -2
dfs(x + 1, y, empty - 1)
dfs(x - 1, y, empty - 1)
dfs(x, y + 1, empty - 1)
dfs(x, y - 1, empty - 1)
A[x][y] = 0
dfs(x, y, empty)
return self.res


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1e5+10;

//用链表结构存储每个点的边

int h[N];   //h[]用于存储每个点的头节点
int e[2*N];   //用于存储元素    因为是无向图 所以是双向边 应该乘2
int ne[2*N];    //存储链表的next值
int idx=0;
int n;
int ans=N;  //记录重心子树的最小值

bool st[N];  //记录该点是否已经查找过

void add(int a,int b)       //将b插入a中 a作为根 所以处在链表的最后
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u)       //dfs过程寻找根的连通的点
{
int size=0;    //存放连通块中点的个数的最大值

st[u]=true;  //  该点已经走过

int sum=0;       //sum用于记录根子树的个数

for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
int s=dfs(j);
size=max(size,s);
sum+=s;
}
}
size=max(size,n-sum-1);  //通过画图可得n-m 即总的节点-根的子树 即为剩余的连通节点值
//而size为当前为根的子树的个数 通过比较确认连通块中点的最大数
ans=min(ans,size);
return sum+1;        //return sum+1 是因为sum初始化为0 而当前这个点即根也算是该连通块内的一点

}

int main()
{
memset(h,-1,sizeof h);  //初始化h[]表 -1表示空

scanf("%d",&n);

for(int i=0;i<n-1;i++)  //注意这里应该n-1，
{               //有些奇怪但是 仔细想想就明白 n是表示点的个数 而每行是输入两个点之间的边所以只需输入n-1行即可
int a,b;
scanf("%d%d",&a,&b);
}
dfs(1);

cout<<ans<<endl;

return 0;
}


#include<bits/stdc++.h>
using namespace std;
int dp;
int main()
{
int n,a;
cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
}
for(int i=0;i<n;++i){
for(int j=0;j<=i;++j){
if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
}
}
int ans=-1;
for(int i=0;i<n;++i)ans=max(ans,dp[i]);
cout<<ans+1;
return 0;
} ### 题目描述

#### 样例

[7,1,5,3,6,4]
Output: 5


### 算法1

#### C++ 代码

int maxProfit(vector<int> &prices) {
int maxPro = 0;
int minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}


1. calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array,
2. and find a contiguous subarray giving maximum profit.
3. If the difference falls below 0, reset it to zero.

int maxProfit(vector<int> &prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.size(); i++) {
maxCur = max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = max(maxCur, maxSoFar);
}
return maxSoFar;
}


### 题目描述

#### 样例

[7,1,5,3,6,4]
Output: 5


### 算法1

#### C++ 代码

int maxProfit(vector<int> &prices) {
int maxPro = 0;
int minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}


1. calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array,
2. and find a contiguous subarray giving maximum profit.
3. If the difference falls below 0, reset it to zero.

int maxProfit(vector<int> &prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.size(); i++) {
maxCur = max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = max(maxCur, maxSoFar);
}
return maxSoFar;
}


## ### 交换过程演示 #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;
int h[N], ph[N], hp[N], Size;
//详见图解，就是指针和堆里面对应的互换，
void heap_swap(int a, int b){
swap(ph[hp[a]], ph[hp[b]]); // ph 第一是 p指针 指向 h堆。
swap(hp[a], hp[b]); //注: hp 意思是h堆 指向 p 指针，
swap(h[a], h[b]); //之前写错了不小心写成swap(a,b)了 实际应是换堆里的元素，h[a]与h[b]
}

void down(int u){
int Min = u;
if (u * 2 <= Size && h[u * 2] < h[Min]) Min = u * 2;
//判断有左二子 2x比总大小小，并且判断左二子小于t，那么t等于左二子
if (u * 2 + 1 <= Size && h[u * 2 + 1] < h[Min]) Min = u * 2 + 1;
if (u != Min){ //跟根节点比一下谁是最小值
heap_swap(u, Min);
down(Min);
}
}

void up(int u){
while (u / 2 && h[u / 2] > h[u]){
heap_swap(u / 2, u);
u /= 2;
}
}

int main(){
int n, m = 0;
scanf("%d", &n);
while (n--){
char op;
int k, x;
scanf("%s", op);
if (!strcmp(op, "I")){
scanf("%d", &x);
h[++Size] = x;
m++;
ph[m] = Size, hp[Size] = m;
up(Size);
}
else if (!strcmp(op, "PM")) printf("%d\n", h);
else if(!strcmp(op, "DM")){
heap_swap(1, Size);
Size --;
down(1);
}
else if(!strcmp(op, "D")) {
scanf("%d", &k);
k = ph[k];
heap_swap(k, Size--);
down(k), up(k);
}
else{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
down(k), up(k);
}

/*for (int i = n / 2; i > 0; i--) down(i); //O(n) 递推。从n/2 down到1
printf("%d ", h);
h = h[Size];
Size --;
down(1); 上一题输出的最小值 */
}
return 0;
}