力扣:1227. 飞机座位分配概率

2024-02-03 01:20

本文主要是介绍力扣:1227. 飞机座位分配概率,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

1、其实这道题有点小巧妙

首先排除特殊情况,只有一位乘客,此时,他只能坐自己的位置,所以返回1。

如果第一位乘客坐了自己的位,那么由题意可以知道第n位乘客必然是能坐在自己的座位上。

现在再来看第一位乘客坐错了位置。

那么我们可以认为第一位乘客所坐的就是第二位乘客的位置。

或许有人问,为什么呢?这里解释一下。

如果第一位乘客坐的是第三位乘客的位置,那么第二位乘客就必然能坐在自己的位置上,此时第二位乘客的存在与结果之间没有任何联系,那么我们是否就可以假设没有这第二位乘客和他的那个位置呢?答案是肯定的,去掉第二位乘客,问题将变成求第n-1位乘客是否能坐在自己的位置上,而原来的第三位乘客就变成了第二位乘客。

同理类推,我们就可以认为第一位乘客所坐的就是第二位乘客的位置。

同理,我们也可以认为第二位乘客所坐的就是第三位乘客的位置。(证明和前面一样)

以此类推,最后一位乘客必然无法坐在自己的座位上。

得出结论,如果第一位乘客坐在自己的位置上,那么最后一位乘客将坐在自己的座位上,反之,最后一位乘客将不会坐在自己的座位上,所以结果为1/2;

ps:另一种理解,根据上面的证明,我们可以直接假设第一位乘客所坐的就是最后一位乘客的位置,那么中间那些乘客都可以忽略,最终变成了n为2的问题,答案为1/2;

class Solution {
public:double nthPersonGetsNthSeat(int n) {if(n==1) return n;else return 0.5;}
};

这篇关于力扣:1227. 飞机座位分配概率的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/672583

相关文章

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节,字符串小于等于15直接保存在栈上,超过之后才会使用new分配。

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

操作系统是怎么为不同的程序分配所需的内存空间的

操作系统为不同的程序分配内存空间的过程涉及多个关键步骤,确保每个程序都有其所需的内存资源,同时避免程序之间的冲突。以下是操作系统如何为程序分配内存空间的详细过程: 1. 内存管理的基础概念 虚拟内存:现代操作系统使用虚拟内存机制来为程序提供隔离的内存空间。每个程序运行在其独立的虚拟地址空间中,这使得程序间的内存互不干扰。物理内存:实际的 RAM(随机存取存储器),由操作系统和硬件共同管理。虚拟

利用PL/SQL工具如何给指定用户分配权限

选中指定的表--右键--编辑--就出现右边的内容了,选择权限,分配用户某个权限就行了;

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1