刷题小分队——第四周
发布日期:2021-07-26 10:17:44 浏览次数:8 分类:技术文章

本文共 8496 字,大约阅读时间需要 28 分钟。

字符串

题目地址(435. 无重叠区间)

https://leetcode-cn.com/problems/non-overlapping-intervals/

题目描述

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。示例 1:输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1解释: 移除 [1,3] 后,剩下的区间没有重叠。示例 2:输入: [ [1,2], [1,2], [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:输入: [ [1,2], [2,3] ]输出: 0解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

前置知识

公司

  • 暂无

思路

关键点

代码

  • 语言支持:Java

Java Code:

class Solution {    public int eraseOverlapIntervals(int[][] intervals) {        Arrays.sort(intervals, (o1, o2) -> (o1[1]-o2[1]));//拉姆达表达式        int right = intervals[0][1];        int res = 1;        int n = intervals.length;        for(int i=1; i
= right){ right = intervals[i][1];//如果可以衔接上 就更新最右端的数值 res++; } } return n - res; }}

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

题目地址(118. 杨辉三角)

https://leetcode-cn.com/problems/pascals-triangle/

题目描述

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。在杨辉三角中,每个数是它左上方和右上方的数的和。示例:输入: 5输出:[     [1],    [1,1],   [1,2,1],  [1,3,3,1], [1,4,6,4,1]]

前置知识

公司

  • 暂无

思路

关键点

代码

  • 语言支持:Java

Java Code:

class Solution {    public List
> generate(int numRows) { // List
> yang = new ArrayList
>(); List
> yang = new ArrayList
>(); for(int i=0; i
hui = new ArrayList
(); for(int j=0; j<=i; j++){ if(numRows >= 3 && j != 0 && j != i){ // hui.add(yang[i][j-1] + yang[i-1][j]); // hui.add(hui.get(j-1) + yang.get(i-1).get(j));和自己一开始手写的一样 想错了 hui.add(yang.get(i-1).get(j-1) + yang.get(i-1).get(j)); } else{ hui.add(1); } } yang.add(hui); } return yang; }}

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n^2)

题目地址(119. 杨辉三角 II)

https://leetcode-cn.com/problems/pascals-triangle-ii/

题目描述

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。在杨辉三角中,每个数是它左上方和右上方的数的和。示例:输入: 3输出: [1,3,3,1]进阶:你可以优化你的算法到 O(k) 空间复杂度吗?

前置知识

公司

  • 暂无

思路

关键点

代码

  • 语言支持:Java

Java Code:

class Solution {    public List
getRow(int rowIndex) {//1个数组+倒着走 List
yang = new ArrayList
(); for(int i=0; i<=rowIndex; i++){ yang.add(0); for(int j=i; j>=0; j--){ if(j != 0 && j != i){ yang.set(j, yang.get(j-1) + yang.get(j)); } else{ yang.set(j, 1); } } } return yang; } public List
getRow2(int rowIndex) {//滑动数组+1维数组 List
yang = new ArrayList
(); for(int i=0; i<=rowIndex; i++){ List
hui = new ArrayList
(); for(int j=0; j<=i; j++){ if(j != 0 && j != i){ hui.add(yang.get(j-1) + yang.get(j)); } else{ hui.add(1); } } yang = hui; } return yang; } public List
getRow1(int rowIndex) {//2维数组+1维数组 List
> yang = new ArrayList
>(); for(int i=0; i<=rowIndex; i++){ List
hui = new ArrayList
(); for(int j=0; j<=i; j++){ if(rowIndex >= 2 && j != 0 && j != i){ hui.add(yang.get(i-1).get(j-1) + yang.get(i-1).get(j)); } else{ hui.add(1); } } yang.add(hui); } return yang.get(rowIndex); }}

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

题目地址(67. 二进制求和)

https://leetcode-cn.com/problems/add-binary/

题目描述

给你两个二进制字符串,返回它们的和(用二进制表示)。输入为 非空 字符串且只包含数字 1 和 0。 示例 1:输入: a = "11", b = "1"输出: "100"示例 2:输入: a = "1010", b = "1011"输出: "10101" 提示:每个字符串仅由字符 '0' 或 '1' 组成。1 <= a.length, b.length <= 10^4字符串如果不是 "0" ,就都不含前导零。

前置知识

  • 位运算 字符串

关键点

  • 2个0或者1相加得到a,a%2是当前的位的值m,a/2是判断有无进位,即大于等于2吗?

代码

  • 语言支持:Java

Java Code:

class Solution {    public String addBinary(String a, String b) {        StringBuilder ans = new StringBuilder();    //答案        int i = a.length() - 1, j = b.length() - 1; //从最后开始遍历(个位),最左边是第0位        int t = 0;  //进位        while(i >= 0 || j >= 0 || t != 0) { //如果没有遍历完两个数,或者还有进位            if(i >= 0) t += a.charAt(i--) - '0';    //如果a还有数            if(j >= 0) t += b.charAt(j--) - '0';    //如果b还有数            ans.append(t % 2);  //加入当前位的和取模 0:0, 1:1 0和1没有进位 就在当前位, 2:0            t /= 2; //进位  0:0, 1:0, 2:1 2有进位 进到下一位了        }        return ans.reverse().toString();    //由于计算之后是个位在第一位,所以要反转    }}// 时间复杂度:O(max(n + m))// 空间复杂度:O(1)// 空间复杂度:O(max(n, m))??》?》 不是

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

题目地址(20. 有效的括号)

https://leetcode-cn.com/problems/valid-parentheses/

题目描述

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 示例 1:输入:s = "()"输出:true示例 2:输入:s = "()[]{}"输出:true示例 3:输入:s = "(]"输出:false示例 4:输入:s = "([)]"输出:false示例 5:输入:s = "{[]}"输出:true 提示:1 <= s.length <= 104s 仅由括号 '()[]{}' 组成

前置知识

思路

关键点

代码

  • 语言支持:Java

Java Code:

class Solution {    public boolean isValid(String s) {        int n = s.length();        Map
map = new HashMap
(); map.put(")", "("); map.put("}", "{"); map.put("]", "["); if (n % 2 == 1) { return false; } // if(n==1){ // return false; // } Stack sk = new Stack(); sk.push(s.charAt(0)); for(int i=1; i

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

题目地址(605. 种花问题)

https://leetcode-cn.com/problems/can-place-flowers/

题目描述

假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。给你一个整数数组  flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示种植了花。另有一个数 n ,能否在不打破种植规则的情况下种入 n 朵花?能则返回 true ,不能则返回 false。 示例 1:输入:flowerbed = [1,0,0,0,1], n = 1输出:true示例 2:输入:flowerbed = [1,0,0,0,1], n = 2输出:false 提示:1 <= flowerbed.length <= 2 * 104flowerbed[i] 为 0 或 1flowerbed 中不存在相邻的两朵花0 <= n <= flowerbed.length

代码

  • 语言支持:Java

Java Code:

class Solution {
public static boolean canPlaceFlowers(int[] flowerbed, int n) {
if (flowerbed == null || flowerbed.length == 0) return n == 0; int countOfZero = 1; // 当前全0区段中连续0的数量,刚开始预设1个0,因为开头花坛的最左边没有花,可以认为存在一个虚无的0 int canPlace = 0; // 可以种的花的数量 for (int bed : flowerbed) {
if (bed == 0) {
// 遇到0,连续0的数量+1 countOfZero++; } else {
// 遇到1,结算上一段连续的0区间,看能种下几盆花:(countOfZero-1)/2 canPlace += (countOfZero-1)/2; if (canPlace >= n) return true; countOfZero = 0; // 0的数量清零,开始统计下一个全0分区 } } // 最后一段0区还未结算: countOfZero++; // 最后再预设1个0,因为最后花坛的最右边没有花,可以认为存在一个虚无的0 canPlace += (countOfZero-1)/2; return canPlace >= n; }}

复杂度分析

令 n 为数组长度。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

题目地址(229. 求众数 II)

https://leetcode-cn.com/problems/majority-element-ii/

给定一个大小为 n 的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。 示例 1:输入:[3,2,3]输出:[3]示例 2:输入:nums = [1]输出:[1]示例 3:输入:[1,1,1,3,3,2,2,2]输出:[1,2] 提示:1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109

代码

  • 语言支持:Java

Java Code:

class Solution {
public List
majorityElement(int[] nums) {
int n = nums.length; int times = 1; int res = 0; List
list = new ArrayList<>(); Arrays.sort(nums); for(int i=0; i
n){
list.add( nums[i] ); } times = 1; } } if(times*3 > n){
list.add( nums[n-1] ); } return list; } public List
majorityElement2(int[] nums) {
// 创建返回值 List
res = new ArrayList<>(); if (nums == null || nums.length == 0) return res; // 初始化两个候选人candidate,和他们的计票 int cand1 = nums[0], count1 = 0; int cand2 = nums[0], count2 = 0; // 摩尔投票法,分为两个阶段:配对阶段和计数阶段 // 配对阶段 for (int num : nums) {
// 投票 if (cand1 == num) {
count1++; continue; } if (cand2 == num) {
count2++; continue; } // 第1个候选人配对 if (count1 == 0) {
cand1 = num; count1++; continue; } // 第2个候选人配对 if (count2 == 0) {
cand2 = num; count2++; continue; } count1--; count2--; } // 计数阶段 // 找到了两个候选人之后,需要确定票数是否满足大于 N/3 count1 = 0; count2 = 0; for (int num : nums) {
if (cand1 == num) count1++; else if (cand2 == num) count2++; } if (count1 > nums.length / 3) res.add(cand1); if (count2 > nums.length / 3) res.add(cand2); return res; }}

复杂度分析

令 n 为数组长度。

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
  • 空间复杂度: O ( n ) O(n) O(n)

转载地址:https://blog.csdn.net/qq_39555841/article/details/117884526 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:qt在window下配置git的详细步骤
下一篇:刷题小分队——第三周

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月13日 13时48分11秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

Java怎么比较4数字大小,怎么判断四个数不成比例-判断4个数值相等-数学-古残夷同学... 2019-04-21
mysql建立索引 性能测试_MySQL分区和索引性能测试 2019-04-21
数据结构java实验 刘小晶_数据结构实例解析与实验指导:Java语言描述 2019-04-21
java实现 k nn算法_java-C中的k-NN示例问题(OpenCV) 2019-04-21
java接口的理解_Java接口的理解 - rabbit_mom的个人空间 - OSCHINA - 中文开源技术交流社区... 2019-04-21
java重用名快捷键_Eclipse 最常用的 10 组快捷键,个个牛逼! 2019-04-21
java streamencoder_[求助]关于apcche与tomcat 2019-04-21
golang mongodb mysql_分享一个golang+mongodb+vuejs开发的博客程序 gocms 2019-04-21
hive java insert_hive表insert报错 2019-04-21
java 调试dll jna_Java调用dll的实现,JNA框架 | 学步园 2019-04-21
ios php上传视频文件_IOS上传图片 PHP服务器接收并上传 2019-04-21
php redis zrevrange,Redis Zrevrange 命令 2019-04-21
php利用word模板导出excel文件,php生成导出word doc和excel文件实例 2019-04-21
java 边缓存边播放,java动态缓存技术:WEB缓存应用 2019-04-21
matlab数据大小不兼容,MATLAB无法执行赋值,因为左侧的索引与右侧的大小不兼容。 求解... 2019-04-21
editor.md使用php,editor.md 配置参数和使用方法 2019-04-21
python mod,mod_python的安装 2019-04-21
python分析彩票数据,这波太炸了!Python脚本可视化居然可以这么玩 2019-04-21
简单的mysql重置root密码,重置mysql的root密码最简单的方法 2019-04-21
用matlab仿真mmc环流抑制器,一种基于准PR控制原理的MMC阀组环流抑制方法 2019-04-21