leetcode hot100特殊题型

1️⃣4️⃣ 技巧(特殊题型、数学、位运算等)

136. 只出现一次的数字

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

题解:

  • 涉及数字的要求线性时间的, 一般尝试能不能用位运算实现

  • 只出现一次的数字, 多个数字异或, 两个相同的数字异或为0, 那么最终剩下的就是只出现一次的数字

  • class Solution {public int singleNumber(int[] nums) {int n = nums.length;if(n==1){return nums[0];}int res = nums[0];for(int i=1;i<n;i++){res = res^nums[i];}return res;}
    }
    

169. 多数元素

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。

题解:

  • 第一种, 使用哈希表存储每个元素出现的个数, 超过n/2的即为多数元素, 多数元素只可能有一个, 所以找到即可return

  • 第二种, 由于多数元素总是>n/2的, 因此排序后索引值n/2处必定是多数元素.

  • class Solution {public int majorityElement(int[] nums) {// int n = nums.length;// int cnt=0;// Map<Integer,Integer> map = new HashMap<>();// for(int i=0;i<n;i++){//     map.put(nums[i],map.getOrDefault(nums[i],0)+1);//     if(map.getOrDefault(nums[i],0)>(n>>1)){//         return nums[i];//     }// }// return cnt;Arrays.sort(nums);return nums[nums.length/2];}
    }
    

75. 颜色分类荷兰国旗问题

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

题解:

  • 只有三个元素, 那么遇到红色插入0后, 遇到蓝色插入2前即可

  • class Solution {public void sortColors(int[] nums) {int n = nums.length;int l=0,r=n-1;int idx=0;while(idx<n&&idx<=r){if(nums[idx]==0){int temp = nums[l];nums[l] = nums[idx];nums[idx] = temp;l++;idx++;}else if(nums[idx]==2){int temp = nums[r];nums[r] = nums[idx];nums[idx] = temp;r--;//遇到蓝色索引不能增加, 因为现在还未处理交换而来的尾部的新数据}else{idx++;}}}
    }
    

31. 下一个排列

题目太长了,简单来说就是给定一个整型数组, 找出当前排列代表数字的下一个大于它的最小数组.例: [1,2,3] 下一个就是[1,3,2], 如果当前即为数组能代表的最大数字, 那么返回最小排列,例: [3,2,1], 下一个就是[1,2,3]

题解:

  • 数组排列, 寻找移动的规律:

    • 从后至前找到第一个小于当前数字的数字, 比如1,3,4,5,2,1, 找到的就是4
    • 然后在尾部的降序数组中找到最小的能够刚好大于当前数字的数字, 上述找到的就是5,
    • 交换两个数字,变为1,3,5,4,2,1 然后反转尾部降序的数组即可
    • 变为1,3,5,1,2,4
  • class Solution {public static int findMinLarge(int[] nums,int start, int end,int target){int res = Integer.MAX_VALUE;int idx=0;for(int i=start;i<=end;i++){if(nums[i] > target){if(nums[i]<=res){res = nums[i];idx = i;}}}return  idx;}public static void swap(int[] nums,int tag1,int tag2){int temp = nums[tag1];nums[tag1] = nums[tag2];nums[tag2] = temp;}public static void reverse(int[] nums, int start,int end){while(start <= end){int temp = nums[start];nums[start++] = nums[end];nums[end--] = temp;}}public void nextPermutation(int[] nums) {int n = nums.length;// int flag = 0;for(int i=n-1;i>=1;i--){if(nums[i-1]<nums[i]){int idx = findMinLarge(nums,i,n-1,nums[i-1]);swap(nums,i-1,idx);reverse(nums,i,n-1);// flag=1;return;}}// if(flag==0){reverse(nums,0,n-1);// }}}
    

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

题解:

  • 对于0-n的索引的值, 都会指向1-n, 那么必然会有存在0~n有两个或者多个索引的值是重复的, 由于值不会是0, 那么0必然会作为一个外部指向内部的指针, 内部就是1~n的循环指向

  • 那么既然这是一个环, 重复元素肯定是环的入口, 使用快慢指针即可得到快慢指针相遇点

  • 经由前面快慢指针的题可以知道, slow到入口的长度=0索引到入口的长度,二者相遇点即为环的入口就是重复值

  • class Solution {public int findDuplicate(int[] nums) {int fast=0,slow=0;while(true){fast = nums[nums[fast]];slow = nums[slow];if(slow==fast){fast=0;while(nums[slow] != nums[fast]){fast = nums[fast];slow = nums[slow];}return nums[slow];}}}
    }
    

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34518.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

开源链动 2+1 模式 AI 智能名片 S2B2C 商城小程序助力社群发展中榜样影响力的提升

摘要&#xff1a;本文深入剖析了社群发展进程中榜样所承载的关键影响力&#xff0c;并对开源链动 21 模式 AI 智能名片 S2B2C 商城小程序在增强这一影响力方面所具备的潜力进行了全面探讨。通过对不同类型社群&#xff0c;如罗辑思维社群和 007 不出局社群中灵魂人物或意见领袖…

《交互式线性代数》

《交互式线性代数》 *Interactive Linear Algebra*由Dan Margalit和Joseph Rabinoff编写&#xff0c;是一本聚焦线性代数的教材。本书旨在教授线性代数的核心概念、方法及其应用&#xff0c;通过代数与几何相结合的方式&#xff0c;帮助读者深入理解线性代数的本质&#xff0c…

CSS -属性值的计算过程

目录 一、抛出两个问题1.如果我们学过优先级关系&#xff0c;那么请思考如下样式为何会生效2.如果我们学习过继承&#xff0c;那么可以知道color是可以被子元素继承使用的&#xff0c;那么请思考下述情景为何不生效 二、属性值计算过程1.确定声明值2.层叠冲突3.使用继承4.使用默…

生活中的可靠性小案例11:窗户把手断裂

窗户把手又断了&#xff0c;之前也断过一次&#xff0c;使用次数并没有特别多。上方的图是正常的把手状态&#xff0c;断的形状如下方图所示。 这种悬臂梁结构&#xff0c;没有一个良好的圆角过渡&#xff0c;导致应力集中。窗户的开关&#xff0c;对应的是把手的推拉&#xff…

怎么解决在Mac上每次打开文件夹都会弹出一个新窗口的问题

在Mac上每次打开文件夹都会弹出一个新窗口的问题&#xff0c;可以通过以下方法解决‌ ‌调整Finder设置‌&#xff1a; 打开Finder&#xff0c;点击“Finder”菜单&#xff0c;选择“偏好设置”。在偏好设置中&#xff0c;选择“通用”标签。取消勾选“在标签页中打开文件夹”或…

HOT100——栈篇Leetcode739. 每日温度

文章目录 题目&#xff1a;Leetcode160. 相交链表原题链接思路代码 题目&#xff1a;Leetcode160. 相交链表 给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &#xff0c;其中 answer[i] 是指对于第 i 天&#xff0c;下一个更高温…

C++ 返回值优化(Return Value Optimization)

Intro 返回值优化(Return Value Optimization, RVO)是 C中的一种编译器优化技术, 它允许编译器在某些情况下省略临时对象的创建和复制/移动操作, 从而提高程序性能. RVO 主要应用于函数返回值的场景. 两种形式的 RVO 假定我们有这样一个类: class MyClass {std::string nam…

C++内存管理(复习)

1.动态申请多个某类型的空间并初始化 //动态申请10个int类型的空间并初始化为0到9int* p new int[10]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; delete[] p; //销毁 2.new/delete new:开空间构造函数 delete:析构函数释放空间 new和delete是用户进行动态内存申请和释放的操作符&#…

计算机视觉——深入理解卷积神经网络与使用卷积神经网络创建图像分类算法

引言 卷积神经网络&#xff08;Convolutional Neural Networks&#xff0c;简称 CNNs&#xff09;是一种深度学习架构&#xff0c;专门用于处理具有网格结构的数据&#xff0c;如图像、视频等。它们在计算机视觉领域取得了巨大成功&#xff0c;成为图像分类、目标检测、图像分…

Java数据结构第二十三期:Map与Set的高效应用之道(二)

专栏&#xff1a;Java数据结构秘籍 个人主页&#xff1a;手握风云 目录 一、哈希表 1.1. 概念 1.2. 冲突 1.3. 避免冲突 1.4. 解决冲突 1.5. 实现 二、OJ练习 2.1. 只出现一次的数字 2.2. 随机链表的复制 2.3. 宝石与石头 一、哈希表 1.1. 概念 顺序结构以及平衡树中…

OSPF | LSDB 链路状态数据库 / SPF 算法 / 实验

注&#xff1a;本文为 “OSPF | LSDB / SPF ” 相关文章合辑。 LSDB 和 SPF 算法 潇湘浪子的蹋马骨汤 发布 2019-02-15 23:58:46 1. 链路状态数据库 (LSDB) 链路状态协议除了执行洪泛扩散链路状态通告&#xff08;LSA&#xff09;以及发现邻居等任务外&#xff0c;其第三个任…

Android Framework 之了解系统启动流程二

Android Framework 源码阅读系列篇章有&#xff1a; 系统启动流程一之init进程和zygote进程启动分析系统启动流程二之SystemServer进程启动分析 1. SystemServer 进程启动分析 在 系统启动流程一之init进程和zygote进程启动分析 中分析 zygote 进程时&#xff0c;我们知道了…

阿里云企业邮箱出现故障怎么处理?

阿里云企业邮箱出现故障怎么处理&#xff1f; 以下是处理阿里云企业邮箱故障的详细分步指南&#xff0c;帮助您快速定位问题并恢复邮箱正常使用&#xff1a; 一、初步排查&#xff1a;确认故障范围与现象 确定影响范围 全体用户无法使用 → 可能为阿里云服务端故障或网络中断。…

Python----数据分析(Pandas二:一维数组Series,Series的创建,Series的属性,Series中元素的索引与访问)

一、一维数组Series Series&#xff1a;一维数组,与Numpy中的一维array类似。它是一种类似于一维数组的对象&#xff0c;是由一组数据(各种 NumPy 数据类型)以及一组与之相关的数据标签(即索引)组成。 仅由一组数据也可产生简单的 Series 对象&#xff0c;用值列表生成 Series …

小程序配置

注册小程序账号和安装开发工具 参考文档&#xff1a;注册小程序账号和安装开发工具https://blog.csdn.net/aystl_gss/article/details/127878658 HBuilder新建项目 填写项目名称&#xff0c;选择UNI-APP&#xff0c;修改路径&#xff0c;点击创建 manifest.json 配置 需要分别…

前端UI编程基础知识:基础三要素(结构→表现→行为)

以下是重新梳理的前端UI编程基础知识体系&#xff0c;结合最新技术趋势与实战要点&#xff0c;以更适合快速掌握的逻辑结构呈现&#xff1a; 一、基础三要素&#xff08;结构→表现→行为&#xff09; 1. HTML5 核心能力 • 语义化标签&#xff1a;<header>, <nav&g…

【eNSP实战】将路由器配置为DHCP服务器

拓图 要求&#xff1a; 为 office100 和 office200 分别配置地址池 AR1接口配置 interface GigabitEthernet0/0/0ip address 192.168.100.1 255.255.255.0 # interface GigabitEthernet0/0/1ip address 192.168.200.1 255.255.255.0 AR1路由器上创建office100地址池 [AR1…

Stable Diffusion 模型具体如何设置参数?

基础参数设置 随机种子&#xff08;seed&#xff09;&#xff1a;设置一个固定的随机种子值&#xff0c;可以确保在相同文本提示下生成相同的图像。如果设置为-1&#xff0c;则每次生成的图像都是随机的。 num_inference_steps&#xff1a;控制模型推理的步数。步数越多&#…

阿里云服务器购买及环境搭建宝塔部署springboot和vue项目

云服务器ECS_云主机_服务器托管_计算-阿里云 一、前言 对于新手或者学生党来说&#xff0c;有时候就想租一个云服务器来玩玩或者练练手&#xff0c;duck不必花那么多钱去租个服务器。这些云服务厂商对学生和新手还是相当友好的。下面将教你如何快速搭建自己的阿里云服务器&…

ABAP语言的动态编程(4) - 综合案例:管理费用明细表

本篇来实现一个综合案例&#xff1a;管理费用明细表。报表在实际项目中&#xff0c;也有一定的参考意义&#xff0c;一方面展示类似的报表&#xff0c;比如管理费用、研发费用等费用的明细&#xff0c;使用业务比较习惯的展示格式&#xff1b;另一方面正好综合运用前面学习的动…