--day5

本文主要是介绍--day5，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

计算机组成原理:

控制器的基本结构

控制器的功能是解释指令（完成指令）、保证指令的按序执行。

• PC（程序计数器）寄存器保存了当前指令的地址，进行取指令，PC有计数功能。
• IR（指令寄存器）存放当前要执行的指令，将操作码送入CU进行分析。
• CU（控制单元）发出控制信号，控制相对应的部件来执行指令。

leetcode每日一题:

次元门(\\v\\):

接雨水问题 , 三种解法.

NO 1: 单调栈.

        对单调栈的回退(出栈)过程进行模拟 , 就可很明确的得到计算过程. 

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size() , re = 0 , left = 0;
        stack<int>sta;

        for(int i = 0;i < n;i ++){
            while(!sta.empty() && height[i] > height[sta.top()]){
                int cnt = sta.top();
                sta.pop();

                if(sta.empty()) break;

                int left = sta.top();
                int col = i - left - 1;
                int row = min(height[left] , height[i]) - height[cnt];
                re += col * row;

            }
            sta.push(i);
        }

        return re;
    }
};

NO 2: dp 动态规划

        从左往右遍历: 假设最右端存在一个 无限高 的柱子 , 计算每个柱子最多可以积累的水;

        从右往左遍历: 假设最左端存在一个 无限高 的柱子 , 计算每个柱子最多可以积累的水;

        取 min - height 就是该单元格能接的水.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size() , re = 0;
        
        vector<int>dp_left(n , 0);
        int left = height[0];
        vector<int>dp_right(n , 0);
        int right = height[n - 1];

        for(int i = 0;i < n;i ++){
            left = max(left , height[i]);
            dp_left[i] = left;
        }

        for(int i = n - 1;i >= 0;i --){
            right = max(right , height[i]);
            dp_right[i] = right;
        }

        for(int i = 0;i < n;i ++){
            re += min(dp_right[i] , dp_left[i]) - height[i];
        }

        return re;
    }
};

NO 3: 双指针

这篇关于--day5的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！