leetcode最长无重复字符串_直线是一维还是二维

leetcode最长无重复字符串_直线是一维还是二维【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用文章目录【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用在区间范围内统计奇数数目★区域和检索-数组不可变★★子数组异或查询★★定长子串中元音的最大数目★★生存人数★★二维区域和检索-矩阵不可变★★矩阵区域和★★矩形区域不超过K的最大数值和★★★在区间范围内统计奇数数目★1523.在区间范围内统计奇数数目【题目】给你两个非负整数low和high。请你返回low和high之间(包括二者)奇数的数目。【示例】输入:l

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

【LeetCode】﹝前缀和ி﹞一维、二维前缀和应用

在区间范围内统计奇数数目★

1523. 在区间范围内统计奇数数目

题目】给你两个非负整数 lowhigh 。请你返回 lowhigh 之间(包括二者)奇数的数目。

示例

输入:low = 3, high = 7
输出:3
解释:37 之间奇数数字为 [3,5,7]

Jetbrains全家桶1年46,售后保障稳定

解题思路

利用前缀和思想,high之前的奇数数目减去low之前的奇数数目

class Solution { 
   
    public int countOdds(int low, int high) { 
   
        return ((high + 1) >> 1) - (low >> 1);
    }
}

区域和检索 – 数组不可变★★

303. 区域和检索 – 数组不可变

题目】给定一个整数数组 nums,求出数组从索引 ij(i ≤ j)范围内元素的总和,包含i、j 两点。

实现 NumArray 类:

  • NumArray(int[] nums)使用数组nums初始化对象
  • int sumRange(int i, int j) 返回数组nums从索引ij(i ≤ j)范围内元素的总和,包含 i、j 两点(也就是 sum(nums[i], nums[i + 1], ... , nums[j])

提示:

  • 0 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= i <= j < nums.length
  • 最多调用 104 次 sumRange方法

示例

输入:
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出:
[null, 1, -1, -3]
解释:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

解题思路

class NumArray { 
   
    int[] pre;

    public NumArray(int[] nums) { 
   
        int n = nums.length;
        pre = new int[n + 1];
        for (int i = 0; i < n; i++) { 
   
            pre[i + 1] = pre[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) { 
   
        return pre[right + 1] - pre[left];
    }
}

子数组异或查询★★

1310. 子数组异或查询

题目】有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]

对于每个查询 i,请你计算从 LiRiXOR值(即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri])作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

提示

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 10^9
  • 1 <= queries.length <= 3 * 10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] <= queries[i][1] < arr.length

示例

输入:arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出:[2,7,14,8] 
解释:
数组中元素的二进制表示形式是:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

解题思路

可以利用前缀和的前提是异或运算的特点

  • x ^ 0 = x
  • x ^ x = 0
class Solution { 
   
    public int[] xorQueries(int[] arr, int[][] queries) { 
   
        int n = arr.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) { 
   
            pre[i + 1] = pre[i] ^ arr[i];
        }

        int m = queries.length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) { 
   
            res[i] = pre[queries[i][0]] ^ pre[queries[i][1] + 1];
        }
        
        return res;
    }
}

定长子串中元音的最大数目★★

1456. 定长子串中元音的最大数目

题目】给你字符串 s和整数k

请返回字符串 s 中长度为 k的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为(a, e, i, o, u)。

提示:

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • 1 <= k <= s.length

示例

输入:s = "leetcode", k = 3
输出:2
解释:"lee""eet""ode" 都包含 2 个元音字母。
--------------------------------------------
输入:s = "abciiidef", k = 3
输出:3
解释:子字符串 "iii" 包含 3 个元音字母。

解题思路

方法一:滑动窗口

class Solution { 
   
    public int maxVowels(String s, int k) { 
   
        int le = 0, ri = 0;
        int cur = 0, res = 0;
        while (ri < s.length()) { 
   
            cur += check(s.charAt(ri));
            if (le + k - 1 == ri) { 
   
                res = Math.max(res, cur);
                cur -= check(s.charAt(le));
                le++;
            }
            ri++;
        }
        return res;
    }

    private int check(char c) { 
   
        char[] chars = { 
   'a', 'e', 'i', 'o', 'u'};
        for (char ch : chars) { 
   
            if (ch == c) { 
   
                return 1;
            }
        }
        return 0;
    }
}

方法二:前缀和数组

class Solution { 
   
    public int maxVowels(String s, int k) { 
   
        int n = s.length();
        int[] pre = new int[n + 1];
        for (int i = 0; i < s.length(); i++) { 
   
            pre[i + 1] = pre[i];
            pre[i + 1] += check(s.charAt(i));
        }

        int res = 0;
        for (int i = k; i <= n; i++) { 
   
            res = Math.max(res, pre[i] - pre[i - k]);
        }
        return res;
    }

    private int check(char c) { 
   
        char[] chars = { 
   'a', 'e', 'i', 'o', 'u'};
        for (char ch : chars) { 
   
            if (ch == c) { 
   
                return 1;
            }
        }
        return 0;
    }
}

生存人数★★

面试题 16.10. 生存人数

题目】给定 N个人的出生年份和死亡年份,第i个人的出生年份为 birth[i],死亡年份为 death[i],实现一个方法以计算生存人数最多的年份。

你可以假设所有人都出生于 1900 年至 2000 年(含 1900 和 2000 )之间。如果一个人在某一年的任意时期处于生存状态,那么他应该被纳入那一年的统计中。例如,生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。

如果有多个年份生存人数相同且均为最大值,输出其中最小的年份。

提示:

  • 0 < birth.length == death.length <= 10000
  • birth[i] <= death[i]

示例

输入:
birth = { 
   1900, 1901, 1950}
death = { 
   1948, 1951, 2000}
输出: 1901

解题思路

使用前缀和数组,频次统计出生年份+1,死亡年份的后一年-1,之后求前缀和,取存活人数最多的第一个年份即可;

class Solution { 
   
    public int maxAliveYear(int[] birth, int[] death) { 
   
        int[] pre = new int[102];
        for (int i = 0; i < birth.length; i++) { 
   
            pre[birth[i] - 1900]++;
            pre[death[i] - 1900  + 1]--;
        }

        int maxNum = pre[0];
        for (int i = 1; i < 102; i++) { 
   
            pre[i] += pre[i - 1];
            maxNum = Math.max(maxNum, pre[i]);
        }

        int maxYear = 0;
        for (int i = 0; i < 102; i++) { 
   
            if (pre[i] == maxNum) { 
   
                maxYear = 1900 + i;
                break;
            }
        }
        
        return maxYear;
    }
}

二维区域和检索 – 矩阵不可变★★

304. 二维区域和检索 – 矩阵不可变

【题目】给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1),右下角为 (row2, col2)

在这里插入图片描述

上图子矩阵左上角(row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),该子矩形内元素的总和为 8

提示:

  • 你可以假设矩阵不可变。
  • 会多次调用 sumRegion 方法*。*
  • 你可以假设 row1 ≤ row2col1 ≤ col2

【示例】

给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

【解题思路】

二维前缀和图解如下,类似集合的并交补思想

在这里插入图片描述

查询区域和时只需在前缀和数组上采用同样的思路
区 间 和 = 右 下 区 间 和 − 左 端 区 间 和 − 上 端 区 间 和 + 左 上 区 间 和 区间和= 右下区间和-左端区间和-上端区间和+左上区间和 =+

class NumMatrix { 
   
    int[][] pre;

    public NumMatrix(int[][] matrix) { 
   
        int r = matrix.length, c = matrix[0].length;
        pre = new int[r + 1][c + 1];
        for (int i = 0; i < r; i++) { 
   
            for (int j = 0; j < c; j++) { 
   
                pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) { 
   
        return pre[row2 + 1][col2 + 1] - pre[row2 + 1][col1] - 
               pre[row1][col2 + 1] + pre[row1][col1];
    }
}

矩阵区域和★★

1314. 矩阵区域和

题目】给你一个 m * n 的矩阵 mat和一个整数 K,请你返回一个矩阵 answer,其中每个answer[i][j]是所有满足下述条件的元素 mat[r][c]的和:

  • i - K <= r <= i + K, j - K <= c <= j + K
  • (r, c)在矩阵内。

提示

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, K <= 100
  • 1 <= mat[i][j] <= 100

示例

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]

解题思路

同二维区域和检索一样,但要注意查询区间的边界

class Solution { 

public int[][] matrixBlockSum(int[][] mat, int k) { 

int r = mat.length, c = mat[0].length;
int[][] pre = new int[r + 1][c + 1];
for (int i = 0; i < r; i++) { 

for (int j = 0; j < c; j++) { 

pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + mat[i][j];
}
}
int[][] res = new int[r][c];
for (int i = 0; i < r; i++) { 

for (int j = 0; j < c; j++) { 

int to = Math.max(0, i - k);
int bo = Math.min(r - 1, i + k) + 1;
int le = Math.max(0, j - k);
int ri = Math.min(c - 1, j + k) + 1;
res[i][j] = pre[bo][ri] - pre[bo][le] - pre[to][ri] + pre[to][le];
}
}
return res;
}
}

矩形区域不超过 K 的最大数值和★★★

363. 矩形区域不超过 K 的最大数值和

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

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

提示

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

示例

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

解题思路

前缀和数组+暴力查询

class Solution { 

public int maxSumSubmatrix(int[][] matrix, int k) { 

int m = matrix.length, n = matrix[0].length;
int[][] sum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) { 

for (int j = 1; j <= n; j++) { 

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
int res = Integer.MIN_VALUE;
for (int i = 1; i <= m; i++) { 

for (int j = 1; j <= n; j++) { 

for (int p = i; p <= m; p++) { 

for (int q = j; q <= n; q++) { 

int cur = sum[p][q] - sum[i - 1][q] - sum[p][j - 1] + sum[i - 1][j - 1];
if (cur <= k) { 

res = Math.max(cur, res);
}
}
}
}
}
return res;
}
}

其它解法见宫水三叶题解【宫水三叶】优化枚举的基本思路 & 将二维抽象成一维 & 最大化「二分」效益 & 空间优化


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234585.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • TypeScript超详细入门教程(上)「建议收藏」

    TypeScript超详细入门教程(上)「建议收藏」TypeScript超详细入门教程(上) 01开篇词:Hello~TypeScript01开篇词:Hello~TypeScript更新时间:2019-10-3013:49:46 既然我已经踏上这条道路,那么,任何东西都不应妨碍我沿着这条路走下去。——康德 同学你好,我是Lison。很高兴你对TypeScript感兴趣,或许你对TypeScrip…

    2022年10月29日
  • 双线性插值算法推导及代码实现

    双线性插值算法推导及代码实现双线性插值,是一种比较重要的插值方法,尤其在数字图像处理领域。本篇博文分为三个部分:一是双线性插值的算法推导,二是双线性插值的算法实现,三是算法的运行结果。

  • 局域网,园区网,广域网的区别是什么_局域网和互联网的区别与联系

    局域网,园区网,广域网的区别是什么_局域网和互联网的区别与联系局域网局域网LAN(LocalAreaNetwork):一般不大于10公里,而且通常只使用一种传输介质;地域上看局域网通常是用在一座建筑物或一个工厂内,使用上通常是某一单位或某一部门使用,规模上一般不超过几百个用户。(局域网也是相对而言,一栋楼可以看作一个局域网,一个国家性对于世界来说也可以看作一个局域网。多个楼栋,组成的局域网就可以看作一个园区网。)城域网MAN(MetropolitanAreaNetwork):城域网是一种比局域网更大的网,通常覆盖一个城市,从几十公里到100公里不等,可能

  • P2939 [USACO09FEB]改造路Revamping Trails(分层图最短路)「建议收藏」

    P2939 [USACO09FEB]改造路Revamping Trails(分层图最短路)「建议收藏」P2939 [USACO09FEB]改造路Revamping Trails(分层图最短路)

  • 【转】使用 Jmeter 做 Web 接口测试

    【转】使用 Jmeter 做 Web 接口测试

  • 基于 mysql时序_时序数据库简介

    基于 mysql时序_时序数据库简介时间序列数据库简称时序数据库(TimeSeriesDatabase),用于处理带时间标签(按照时间的顺序变化,即时间序列化)的数据,带时间标签的数据也称为时间序列数据。时序数据的几个特点1.基本上都是插入,没有更新的需求。2.数据基本上都有时间属性,随着时间的推移不断产生新的数据。3.数据量大,每秒钟需要写入成千万上亿条数据业务方常见需求1.获取最新状态,查询最近的数据(例如传感器最新…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号