精华内容
下载资源
问答
  • 1. 题目 给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不...矩阵的矩形区域面积必须大于 0。 如果行数远大于列数,你将如何解答呢? 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/prob

    1. 题目

    给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不大于 k 的最大矩形和。

    示例:
    输入: matrix = [[1,0,1],[0,-2,3]], k = 2
    输出: 2 
    解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,
    且 2 是不超过 k 的最大数字(k = 2)。
    
    说明:
    矩阵内的矩形区域面积必须大于 0。
    如果行数远大于列数,你将如何解答呢?
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    2. 解题

    最好在做本题之前,先把下面链接题目读懂

    程序员面试金典 - 面试题 17.24. 最大子矩阵(转成一维最大子序和 DP)

    • 本题说行比较多,那么按列来压扁,两重循环,遍历所有的列组合
    • 对每种列组合,压扁后的 m (行数)个和,先求最大子序和(按照上题方法)
    • 如果最大连续子序和 == k,返回 k,< k 进行下一个组合
    • 如果子序和 > k ,那还需要找是否有 <= k 的呢?将前缀和 prefix 插入set(初始有0,防止prefix 一开始就是 k 的情况)
    • 二分查找 prefix-k 的下限 lb,如果存在,则lb >= prefix-k, 两个前缀和做差就是连续子序列的和 SUM = prefix - lb <= k,更新最大值
    class Solution {
    public:
        int maxSumSubmatrix(vector<vector<int>>& mat, int k) {
        	if(mat.empty() || mat[0].empty())
        		return 0;
        	int m = mat.size(), n = mat[0].size(), i, j1, j2;
        	int sum, tempmax, maxsum = INT_MIN, prefix;
        	vector<int> sumCols(m);
        	for(j1 = 0; j1 < n; ++j1)
        	{
        		sumCols.clear();
        		sumCols.resize(m);
        		for(j2 = j1; j2 < n; ++j2)
        		{	//列的左右边界组合
        			for(i = 0; i < m; ++i)
        				sumCols[i] += mat[i][j2];//行向求和
        			sum = tempmax = INT_MIN;   		
    	    		for(i = 0; i < m; ++i)
    	    		{	//对上面的和,求最大连续子序列和,DP
    	    			if(sum > 0)
    	    				sum += sumCols[i];
    	    			else
    	    				sum = sumCols[i];
    	    			tempmax = max(sum, tempmax);//临时的最大子序列和
                        if(sum <= k)//更新答案
    	    			    maxsum = max(maxsum, sum);
    	    		}
    	    		if(tempmax == k || maxsum==k)
    	    			return k;//找到上限直接返回
    	    		if(tempmax < k)//最大连续子序列和小于 k,进行下一轮
    	    			continue;
    	    		//最大连续子序列和 大于 k,还要继续查找 有可能 <= k 的
    	    		set<int> s;
                    s.insert(0);//第一个就是k的时候,可以找到
                    prefix = 0;//利用前缀和,在set中二分查找
        			for(i = 0; i < m; ++i)
        			{
                        prefix += sumCols[i];
                        auto it = s.lower_bound(prefix-k);
                        s.insert(prefix);
                        if(it != s.end())
                        {
                        	int SUM = prefix-(*it);
                        	if(SUM > maxsum)
                        		maxsum = SUM;
                        }
                        if(maxsum == k)
                        	return k;
                    }
        		}
        	}
        	return maxsum;
        }
    };
    

    60 ms 9.3 MB

    展开全文
  • 矩形区域不超过 K 的最大数值和[Max Sum of Rectangle No Larger Than K][困难]——分析及代码[Java]一、题目二、分析及代码1. 排序 + 二分查找(1)思路(2)代码(3)结果2. 有序集合(1)思路(2)代码(3)结果...

    一、题目

    给你一个 m x n 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

    题目数据保证总会存在一个数值和不超过 k 的矩形区域。

    示例 1:

    输入:matrix = [[1,0,1],[0,-2,3]], k = 2
    输出:2
    解释:矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。
    

    示例 2:

    输入:matrix = [[2,2,-1]], k = 3
    输出:3
    

    提示:

    • m == matrix.length
    • n == matrix[i].length
    • 1 <= m, n <= 100
    • -100 <= matrix[i][j] <= 100
    • -10^5 <= k <= 10^5

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    二、分析及代码

    1. 排序 + 二分查找

    (1)思路

    将矩形各个位置的值按行或列积聚后,由 sum[j] - sum[i] <= k 推导出,在已知 sum[i] 的情况下,需寻找最大且不超过 sum[i] + k 的 sum[j],可结合排序和二分查找方法求出。

    (2)代码

    class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int n = matrix.length, m = matrix[0].length, ans = 200001;//k和答案差值
            for (int up = 0; up < n; up++) {//矩形上边界
                int[] sum = new int[m + 1];//[0,i]左右区间内矩形的和
                Arrays.fill(sum, 0);
                for (int down = up; down < n; down++) {//矩形下边界
                    int num = 0;
                    for (int i = 1; i <= m; i++) {
                        num += matrix[down][i - 1];
                        sum[i] += num;
                    }
                    List<Integer> list = new LinkedList<Integer>();
                    for (int i = 0; i <= m; i++)
                        list.add(sum[i]);
                    Collections.sort(list);
                    for (int i = 0; i < m; i++) {//矩形左边界
                        list.remove(Integer.valueOf(sum[i]));
                        int target = sum[i] + k;//sum[j]-sum[i]<=k -> sum[j]<=sum[i]+k
                        int l = 0, r = list.size();//二分法求最接近的数值和
                        while (l < r - 1) {
                            int mid = (l + r) >> 1;
                            if (list.get(mid) <= target)
                                l = mid;
                            else
                                r = mid;
                        }
                        if (list.get(l) <= target)
                            ans = Math.min(ans, target - list.get(l));
                        if (ans == 0)
                            return k;
                    }
                }
            }
            return k - ans;
        }
    }
    

    (3)结果

    执行用时 :395 ms,在所有 Java 提交中击败了 22.96% 的用户;
    内存消耗 :38.6 MB,在所有 Java 提交中击败了 65.04% 的用户。

    2. 有序集合

    (1)思路

    在上述方法的基础上,可通过有序集合替代排序和二分法进行查找,降低时间复杂度。

    (2)代码

    class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int n = matrix.length, m = matrix[0].length, ans = 200001;//k和答案差值
            for (int up = 0; up < n; up++) {//矩形上边界
                int[] sum = new int[m];//上下边界内第i个位置的和
                Arrays.fill(sum, 0);
                for (int down = up; down < n; down++) {//矩形下边界
                    for (int i = 0; i < m; i++)
                        sum[i] += matrix[down][i];
                    TreeSet<Integer> set = new TreeSet<>();
                    set.add(0);
                    int num = 0;
                    for (int i = 0; i < m; i++) {//矩形右边界
                        num += sum[i];
                        int target = num - k;//num[i]-num[j]<=k -> num[j]>=num[i]-k
                        Integer ceil = set.ceiling(target);
                        if (ceil != null) {
                            ans = Math.min(ans, ceil - target);
                            if (ans == 0)
                                return k;
                        }
                        set.add(num);
                    }
                }
            }
            return k - ans;
        }
    }
    

    (3)结果

    执行用时 :246 ms,在所有 Java 提交中击败了 30.74% 的用户;
    内存消耗 :38.7 MB,在所有 Java 提交中击败了 45.12% 的用户。

    3. 直接查找

    (1)思路

    在上述方法基础上,因为本题中矩阵的长、宽值较小(<=100),也可直接进行查找。

    (2)代码

    class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int n = matrix.length, m = matrix[0].length, ans = Integer.MIN_VALUE;
            for (int left = 0; left < m; left++) {//矩形左边界
                int[] sum = new int[n];//左右边界内第i个位置的和
                Arrays.fill(sum, 0);
                for (int right = left; right < m; right++) {//矩形右边界
                    int maxSum = 0, max = Integer.MIN_VALUE;
                    for (int i = 0; i < n; i++) {
                        sum[i] += matrix[i][right];
                        maxSum = (maxSum > 0) ? maxSum + sum[i] : sum[i];
                        max = Math.max(max, maxSum);
                    }
                    if (max == k)
                        return k;
                    else if (max < k)
                        ans = Math.max(ans, max);
                    else {
                        for (int i = 0; i < n; i++) {
                            int num = 0;
                            for (int j = i; j < n; j++) {
                                num += sum[j];
                                if (num == k)
                                    return k;
                                if (num < k)
                                    ans = Math.max(ans, num);
                            }
                        }
                    }
                }
            }
            return ans;
        }
    }
    

    (3)结果

    执行用时 :38 ms,在所有 Java 提交中击败了 72.43% 的用户;
    内存消耗 :38.1 MB,在所有 Java 提交中击败了 99.21% 的用户。

    三、其他

    暂无。

    展开全文
  • 题目1 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 ...转字符串,直接反转,再通过 stoll 函数转成long long类型,这样保证在范围...

    题目1

    给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

    示例 1:

    输入: 123
    输出: 321
    

     示例 2:

    输入: -123
    输出: -321
    

    示例 3:

    输入: 120
    输出: 21
    

    注意:

    假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

    思路及代码

    转字符串,直接反转,再通过 stoll 函数转成long long类型,这样保证在范围内,最后就是负数的处理和溢出的处理。

    class Solution {
    public:
        int reverse(int x) {
            bool fushu = false;
            string num = std::to_string(x);
            if(x < 0){
                fushu = true;
                num.erase(0,1);
            }
            std::reverse(num.begin(),num.end());
    
            if(fushu == true){
                num = "-" + num;
            }
            
            long long n = stoll(num);
    
            if(n > INT_MAX || n < INT_MIN){
                return 0;
            }
    
            return (int)n;
        }
    };

    题目2

    给定一个二维的矩阵,包含 'X' 和 'O'字母 O)。

    找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

    示例:

    X X X X
    X O O X
    X X O X
    X O X X
    

    运行你的函数后,矩阵变为:

    X X X X
    X X X X
    X X X X
    X O X X
    

    解释:

    被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

    思路及代码

    被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

    所以先用DFS或者BFS从边界进入,把与边界连通的O标记为+,之后所有O变X,+变O

    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            if(board.size() <= 1 || board[0].size() <= 1){
                return;
            }
    
            for(int i=0;i<board.size();i++){
                if(board[i][0] == 'O'){
                    dfs(board,i,0);
                }
                if(board[i][board[0].size()-1] == 'O'){
                    dfs(board,i,board[0].size()-1);
                }
            }
    
            for(int j=0;j<board[0].size();j++){
                if(board[0][j] == 'O'){
                    dfs(board,0,j);
                }
                if(board[board.size()-1][j] == 'O'){
                    dfs(board,board.size()-1,j);
                }
            }
    
            for(int i=0;i<board.size();i++){
                for(int j=0;j<board[0].size();j++){
                    if(board[i][j]=='+'){
                        board[i][j]='O';
                    }else if(board[i][j]=='O'){
                        board[i][j]='X';
                    }
                }
            }
    
        }
    
        void dfs(vector<vector<char>>& board,int row,int col){
            if(row<0||row>=board.size()||col<0||col>=board[0].size()){
                return;
            }
            if(board[row][col]!='O')
                return;
            board[row][col] = '+';
            dfs(board,row+1,col);
            dfs(board,row,col+1);
            dfs(board,row-1,col);
            dfs(board,row,col-1);
        }
    };

    题目3

    给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1


    示例 1:

    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4
    

    示例 2:

    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1
    
    

    提示:

    1. 你可以假设 nums 中的所有元素是不重复的。
    2. n 将在 [1, 10000]之间。
    3. nums 的每个元素都将在 [-9999, 9999]之间。

    思路及代码

    二分查找

    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int len = nums.size();
    
            int i = 0,j = len - 1;
    
            while(i <= j){
                int mid = (i + j) / 2;
                if(nums[mid] == target){
                    return mid;
                }else if(nums[mid] < target){
                    i = mid + 1;
                }else{
                    j = mid - 1;
                }
            }
    
            return -1;
        }
    }; 

     

    展开全文
  • 在数学上,接近最优替代方案的区域由原始优化模型的约束以及将替代方案限制为目标函数值在最佳目标函数值的容许偏差的约束的约束定义。 该存储库中的代码和工具允许用户生成和可视化结构最接近优化问题的区域的...
  • 第2章 数值计算 397 2.1 常见的数学函数 398 2.1.1 求整数的绝对值 398 范例2-1 求整数的绝对值 398 ∷相关函数:abs函数 2.1.2 求长整型整数的绝对值 399 范例2-2 求长整型整数的绝对值 399 ∷相关函数:...
  • 1. 认识lookup()函数: =LOOKUP(找谁,去哪里找,找到后找那行对应的某列的值)...向量形式是指从单行或单列的区域内查找符合条件的数值,并返回第二个单行区域或单列区域中相同位置的数值。数组形式是指在数组...

    1.  认识lookup()函数:

       =LOOKUP(找谁,去哪里找,找到后找那行对应的某列的值)

       在vlookup里,第三个参数是“第几列”,在lookup里,第三参数是“选中的区域”

    Lookup() 从向量或数组中查找符合条件的值。有两种语法形式:向量和数组。向量形式是指从单行或单列的区域内查找符合条件的数值,并返回第二个单行区域或单列区域中相同位置的数值。数组形式是指在数组的首行或首列中查找符合条件的数值,然后返回数组的尾行或尾列中相同位置的数值。

    Lookup(lookup_value,lookup_vector,result_vector)

    Lookup_value为在单行或单列区域内要查找的值,可以是数字、文本、逻辑值或者包含名称的数值或引用。

    Lookup_vector为指定的单行或单列的查找区域。其数值必须按升序排列,文本不区分大小写。

    Result_vector为指定的函数返回值的单元格区域。其大小必须与lookup_vector相同,如果Lookup_value小于Lookup_vector中的最小值,则返回错误值“#N/A

    6. LOOKUP函数模糊匹配

       LOOKUP与VLOOKUP函数的区别:

       VLOOKUP可模糊匹配或精确匹配,LOOKUP只能模糊匹配

    7.  LOOKUP函数 如何 精确匹配

         =LOOKUP(1,0/(区域=查找的值),要找的那行的某列里的数据)   或:

         =LOOKUP(0,0/(区域=查找的值),要找的那行的某列里的数据)

      若 区域=查找的值 则返回真1,否则返回假0 0/0不可能,为不可能的数据不会被匹配,只能匹配为0的数据。且“0/(区域=查找的值”运算会得出“0”和“#DIV/0”!错误。不去找“错误”值,而去找“0/(区域=查找的值”区域里找1,模糊匹配,会找出小于等于1的最大值来匹配。

      要注意,根据条件确定参数里的区域是不是绝对引用

    如:

    8.    个税:

        个税 = (金额-起征点)*税率 - 速算扣除数

    如:

    展开全文
  • 大家整理了,数据分析入门常用的EXCEL在数据分析行业,EXCEL是最基础的、入门级的,也是最常用,最容易上手的工具了。想要学习数据分析的小伙伴可以选择先从EXCEL入手,...RANK:求某一个数值在某一区域内数值排名 R
  • 一切都是对象

    2019-10-03 12:31:33
    堆栈:驻留于常规RAM的区域,编辑器已知数据大小,通过指针移动查找,例如对象句柄等。堆:用于常规用途的RAM区域(内存池),编译器不知道数据大小,例如对象。静态存储:位于RAM中的固定的存储区域,static关键字...
  • ArrayList源码分析

    2019-07-18 03:25:00
    数组是一片连续的内存区域,数组由数值和位置索引组成,所以可以根据索引将内存中的数值取出来,只有类型相同的数据才能一起存储到数组中 数组的优缺点: 顺序存储,存储数据的内存是连续的 查找数据容易,增删数据...
  • 功能: 用于在屏幕范围内查找图片 ; 描述: 允许您在屏幕的某个区域查找指定相似度的图片,并把找到的坐标保存在变量格式中 ; 参数: $iLeft, $iTop, $iRight, $iBottom 屏幕的区域的左、上、右、下界限 ; $szFileName...
  • 自适应坐标系统

    2015-10-27 10:14:31
    在动态曲线的绘制过程中,经常会遇动态曲线的数量级变化较大的情况,这是如果坐标系统是一个固定的范围,就会使曲线的对比度过小,或者超出坐标系统的范围的情况,...在感兴趣区域范围内查找最大,最小值MAX MIN。  
  • 查找一列中最后一个数值 查找重复字符 请教查找替换问题 IF函数替换法总结 查找的函数(查找末位词组) 怎样从原始数据中自动获取最后一个数据 两列数据查找相同值对应的位置 查找数据公式两个(基本查找函数为VLOOK...
  • EXCEL函数公式集

    热门讨论 2010-03-16 03:26:38
    查找一列中最后一个数值 查找重复字符 请教查找替换问题 IF函数替换法总结 查找的函数(查找末位词组) 怎样从原始数据中自动获取最后一个数据 两列数据查找相同值对应的位置 查找数据公式两个(基本查找函数为VLOOK...
  • 2.4.11 RANDBETWEEN——返回某个范围的随机数 91 2.5 三角函数计算 91 2.5.1 DEGREES——将弧度转换为角度 91 2.5.2 RADIANS——将角度转换为弧度 92 2.5.3 SIN——计算给定角度的正弦值 93 2.5.4 ASIN——...
  • EXCEL VBA常用技巧

    2010-02-09 22:28:27
    技巧8 仅复制数值到另一区域 23 8-1 使用选择性粘贴 23 8-2 直接赋值的方法 24 技巧9 单元格自动进入编辑状态 25 技巧10 禁用单元格拖放功能 25 技巧11 单元格格式操作 26 11-1 单元格字体格式设置 26 11-2 设置...
  • 【合并与合计】:可以任意指定两列,对其中一列的数据合并同类项,而另一列对应的数值则求合计,合计结果存放在合并区域中 【建立图片目录】:对指定文件夹下所有图片(GIF、PNG、JPG,JPEG)建立目录,并批量导入 ...
  • 129.在特定的区域内查找文本,返回值是包含查找文本的单元格 130.返回特定区域中最大值的地址 131.删除表格中使用范围内的所有空白单元格 132.返回数组中有多少个指定的字符串 133.返回当前工作表中引用了指定的单元...
  • linux_c API函数大全

    2013-12-02 23:19:10
    strcoll(采用目前区域的字符排列次序来比较字符串) 43 5.17 43 strcpy(拷贝字符串) 43 5.18 44 strcspn(返回字符串中连续不含指定字符串内容的字符数) 44 5.19 44 strdup(复制字符串) 44 5.20 45 strlen...
  • 162 将区域中的文本串联 323 163 为公式添加说明 324 164 用简易图表表示销量情况 326 ◎文本合并比较函数 327 165 在数值结果左侧添加“¥”符号 327 166 在身份证号码中提取员工的出生年月信息 329 ...
  • 慧办公 H6.61

    2014-10-23 14:21:11
    4、1秒钟,断开指定区域或所有工作表的公式【还可以转换为数值格式或所见值】 5、1秒钟,显示/删除 N个或全部隐藏的工作表【不必在一个一个去点了】 6、1秒钟,删除所有的 链接 或 批注 或 图片 7、1秒钟,将...
  • • XY散点折线图的插值计算 • 自选图形种类 • 插入自选图形 • 添加文本 • 自选图形绘制线条和连接符 • 旋转和翻转 • 对齐和分布 • 自动靠齐 • 设置叠放次序 • 设置组合 • 设置阴影 • 设置三维效果 • ...
  • 【合并与合计】:可以任意指定两列,对其中一列的数据合并同类项,而另一列对应的数值则求合计,合计结果存放在合并区域中 【建立图片目录】:对指定文件夹下所有图片(GIF、PNG、JPG,JPEG)建立目录,并批量导入 ...
  • VBA常用技巧

    2013-03-25 21:10:12
    技巧8仅复制数值到另一区域28 8-1使用选择性粘贴28 8-2直接赋值的方法29 技巧9单元格自动进入编辑状态30 技巧10禁用单元格拖放功能30 技巧11单元格格式操作31 11-1单元格字体格式设置31 11-2设置单元格内部格式33 11...
  • Excel百宝箱9.0无限制破解版

    热门讨论 2012-02-03 19:05:29
    【合并与合计】:可以任意指定两列,对其中一列的数据合并同类项,而另一列对应的数值则求合计,合计结果存放在合并区域中 【建立图片目录】:对指定文件夹下所有图片(GIF、PNG、JPG,JPEG)建立目录,并批量导入 ...
  • Excel百宝箱

    2012-10-27 17:09:21
    【合并与合计】:可以任意指定两列,对其中一列的数据合并同类项,而另一列对应的数值则求合计,合计结果存放在合并区域中 【建立图片目录】:对指定文件夹下所有图片(GIF、PNG、JPG,JPEG)建立目录,并批量导入 ...
  • VBA编程技巧大全

    2013-08-05 09:03:19
    技巧8 仅复制数值到另一区域 30 8-1 使用选择性粘贴 30 8-2 直接赋值的方法 31 技巧9 单元格自动进入编辑状态 32 技巧10 禁用单元格拖放功能 32 技巧11 单元格格式操作 33 11-1 单元格字体格式设置 33 11-2 设置...
  • │ │ 技巧90 快速比较不同区域数值1.xls │ │ 技巧91 快速比较不同区域数值2.xls │ │ 技巧92 自动醒目的小计.xls │ │ 技巧93 在工作日历中突显周休日.xls │ │ 技巧94 突显活动单元格的坐标.xls │ ...
  • EXCEL 2007 宝典 10/10

    2012-03-31 22:37:02
     第13章 创建查找数值的公式  第14章 创建简单财务应用公式 第3部分 Excel 2007图表  第15章 图表创建入门  第16章 高级图表制作  第17章 使用图形和图片增强工作表效果 第4部分 Excelc2007数据分析  第18...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 178
精华内容 71
关键字:

查找区域内数值