头像

CYa想要速通

UCL统计


访客:5857

在线 


新鲜事 原文

数据结构可视化,图论算法可视化,动态规划可视化 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html



题目描述

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[0]), 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


活动打卡代码 AcWing 846. 树的重心

#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);
        add(a,b);
        add(b,a);
    }
    dfs(1);


    cout<<ans<<endl;


    return 0;
}


新鲜事 原文

试一下iPadOs笔写输入效果
今日一读:贾扬清的故事也有点太顶了。(Caffe创始人tensor flor贡献者等)
清华出来的学霸都是上帝派来的指引者么



#include<bits/stdc++.h>
using namespace std;
int dp[1000050];
int main()
{
    int n,a[1000050];
    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;
}



111.PNG




题目描述

只能进行一次交易(买+卖),要求使利润最大。输出这个最大利润

样例

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

算法1

(DP 贪心) $O(n)$

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;
}

Kadane’s Algorithm

更通用版本
计算prices[i] - prices[i-1] 然后找到一个连续含利润最大值的子数列,
如果maxCur 小于0,重置到0。
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

(DP 贪心) $O(n)$

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;
}

Kadane’s Algorithm

更通用版本
计算prices[i] - prices[i-1] 然后找到一个连续含利润最大值的子数列,
如果maxCur 小于0,重置到0。
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;
    }


活动打卡代码 AcWing 839. 模拟堆

指针定义

堆排序-指代.PNG

交换过程演示

堆排序-交换.PNG

#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[10];
        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[1]);
        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[1]);
        h[1] = h[Size];
        Size --;
        down(1); 上一题输出的最小值 */
    }
    return 0;
}


新鲜事 原文

记录一下键盘上 `INS` 即 `DEL`键上面那个,是切换`|`光标和`_`光标,前者输入时插入,后者输入时修改_所对应的(即当前)数