当前位置: 首页 > news >正文

php做动态网站/googleplay官方下载

php做动态网站,googleplay官方下载,上海到北京机票查询,英文网站建设方法算法练习-二分查找 1 代码实现 1.1 非递归实现 public int bsearch(int[] a, int n, int value) {int low 0;int high n - 1;while (low < high) {int mid (low high) / 2;if (a[mid] value) {return mid;} else if (a[mid] < value) {low mid 1} else {high …

算法练习-二分查找

1 代码实现

1.1 非递归实现

public int bsearch(int[] a, int n, int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = (low + high) / 2;if (a[mid] == value) {return mid;} else if (a[mid] < value) {low = mid + 1} else {high = mid - 1;}}return -1;
}

1.2 递归实现

public int bsearch_r(int[] a, int n, int value) {return bsearch(a, 0, n - 1, value);
}public int bsearch(int[] a, int low, int high, int value) {if (low > high) return -1;int mid = (low + high) / 2;if (a[mid] == value) {return mid;} else if (a[mid] < value) {return bsearch(a, mid + 1, high, value);} else {return bsearch(a, low, mid - 1, value);}
}

2 解题技巧

二分查找的正确姿势:

  • 查找区间永远是闭区间[low, high]
  • 循环条件永远是:low < high
  • 对于low == high的情况,必要的时候特殊处理,在while内部补充退出条件
  • 返回值永远是mid,不是low、high
  • low、high的更新永远是low = mid + 1 和 high = mid - 1
  • 对于非确定性查找,使用前后探测法来确定搜索区间
  • 先处理命中目标,再处理左右半部分查找的情况

3 查找第一个等于x、最后一个等于x的元素

3.1 查找第一个等于x的元素

public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] == target) {if ((mid == 0) || (a[mid - 1] != target)) return mid;else high = mid - 1;} else if (a[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return -1;
}

3.2 查找最后一个等于x的元素

public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] == target) {if ((mid == n - 1) || (a[mid + 1] != target)) return mid;else low = mid + 1;} else if (a[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return -1;
}

4 查找第一个大于等于x,最后一个小于等于x的数

4.1 查找第一个大于等于x的数

public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] >= target) {if ((mid == 0) || (a[mid - 1] < target)) return mid;else high = mid - 1;} else {low = mid + 1;}}return -1;
}

4.2 查找最后一个小于等于x的数

public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if ((mid == n - 1) || (a[mid + 1] > target)) return mid;else low = mid + 1;} else {high = mid - 1;}
}
return -1;
}

5 循环有序数组中查找元素x

public int bsearch(int[] a, int n, int target) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (a[mid] == target) return mid;else if (a[low] <= a[mid]) {if (target >= a[low] && target < a[mid]) {high = mid - 1;} else {low = mid + 1;}} else {if (target > a[mid] && target <= a[high]) {low = mid + 1;} else {high = mid - 1;}}}return -1;
}

6 循环有序数组查找最小值

public int bsearch(int[] a, int n) {int low = 0;int high = n - 1;while (low <= high) {int mid = (low + high) / 2;if (low == high) return mid;if ((mid != 0 && a[mid] < a[mid - 1]) || (mid == 0 && a[mid] < a[high]) {return mid;} else if (a[mid] > a[high]) {low = mid + 1;} else {high = mid - 1;}}return -1;
}

7 查找峰值

链接:https://leetcode.cn/problems/find-peak-element

7.1 题目

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1:

输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:

输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。

提示:

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

7.2 题解

class Solution {public int findPeakElement(int[] nums) {int n = nums.length;int low = 0;int high = n - 1;while (low <= high) {int mid = (high + low) / 2;if (mid == 0) {if (n == 1) return 0;else if (nums[mid] > nums[mid + 1]) return mid;else low = mid + 1;} else if (mid == n - 1) {if (nums[mid] > nums[mid - 1]) return mid;else high = mid - 1;} else if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {return mid;} else if (nums[mid] > nums[mid - 1]) {low = mid + 1;} else {high = mid - 1;}}return 0;}
}

8 x的平方根

链接:https://leetcode.cn/problems/sqrtx

8.1 题目

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:

输入:x = 4
输出:2
示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。

8.2 题解

class Solution {public int mySqrt(int x) {if (x == 0) return 0;int low = 1;int high = x / 2 + 1;while (low <= high) {int mid = low + (high - low) / 2;long mid2 = (long)mid * mid;if (mid2 <= x) {long mid22 = ((long)mid + 1) * (mid + 1);if (mid22 <= x) {low = mid + 1;} else {return mid;}} else {high = mid - 1; }}return -1;}
}

相关文章:

算法练习-二分查找(一)

算法练习-二分查找 1 代码实现 1.1 非递归实现 public int bsearch(int[] a, int n, int value) {int low 0;int high n - 1;while (low < high) {int mid (low high) / 2;if (a[mid] value) {return mid;} else if (a[mid] < value) {low mid 1} else {high …...

通用业务平台设计(五):预警平台建设

前言 在上家公司&#xff0c;随着业务的不断拓展(从支持单个国家单个主体演变成支持多个国家多个主体)&#xff0c;对预警的诉求越来越紧迫&#xff1b;如何保障业务的稳定性那&#xff1f;预警可以帮我们提前甄别风险&#xff0c;从而让我们可以在风险来临前将其消灭&#xff…...

Windows openssl-1.1.1d vs2017编译

工具&#xff1a; 1. perl&#xff08;https://strawberryperl.com/&#xff09; 2. nasm&#xff08;https://nasm.us/&#xff09; 3. openssl源码&#xff08;https://www.openssl.org/&#xff09; 可以自己去下载 或者我的网盘提供下载&#xff1a; 链接&#xff1a;…...

【深蓝学院】手写VIO第2章--IMU传感器--笔记

0. 内容 1. 旋转运动学 角速度的推导&#xff1a; 左ω∧\omega^{\wedge}ω∧&#xff0c;而ω\omegaω是在z轴方向运动&#xff0c;θ′[0,0,1]T\theta^{\prime}[0,0,1]^Tθ′[0,0,1]T 两边取模后得到结论&#xff1a; 线速度大小半径 * 角速度大小 其中&#xff0c;对旋转矩…...

网络基础(二)之HTTP与HTTPS

应用层 再谈 "协议" 协议是一种 "约定". socket api的接口, 在读写数据时, 都是按 "字符串" 的方式来发送接收的. 如果我们要传输一些"结构化的数据" 怎么办呢? 为什么要转换呢&#xff1f; 如果我们将struct message里面的信息…...

Python每日一练(20230306)

目录 1. 翻转二叉树 ★★ 2. 最长公共前缀 ★★ 3. 2的幂 ★ 1. 翻转二叉树 翻转一棵二叉树。 示例 1&#xff1a; 输入&#xff1a; 4/ \2 7/ \ / \ 1 3 6 9 输出&#xff1a; 4/ \7 2/ \ / \ 9 6 3 1示例 2&#xff1a; 输入&#xff1a; 1…...

C/C++每日一练(20230305)

目录 1. 整数分解 ☆ 2. 二叉树的最小深度 ★★ 3. 找x ★★ 1. 整数分解 输入一个正整数&#xff0c;将其按7进制位分解为各乘式的累加和。 示例 1&#xff1a; 输入&#xff1a;49 输出&#xff1a;497^2示例 2&#xff1a; 输入&#xff1a;720 输出&#xff1a;720…...

SAS字典的应用

数据字典中常用信息检索DICTIONARY.COLUMNS、DICTIONARY.TABLES以及DICTIONARY.MEMBERS等字典表的内容。在编程实践中&#xff0c;如何以SAS字典表来提高效率。 1、DICTIONARY.COLUMNS 对于当前SAS任务的全部数据集&#xff0c;表格DICTIONARY.COLUMNS包含了诸如变量的名称、类…...

Mysql中的函数和触发器

函数函数是什么&#xff1f;多用于查询语句&#xff0c;实现了某种功能&#xff1b;用途与存储过程不同&#xff0c;但语法是类似的&#xff1b;函数语法create function 函数名([参数列表]) returns 数据类型 begin DECLARE 变量&#xff1b; sql 语句; return 值; end; 设置函…...

分布式架构之(Zookeeper原理)

Zookeeper是一个典型的分布式数据一致性的结局方案&#xff0c;分布式应用程序可以基于它实现注入数据发布、订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master选举、分布式锁和分布式队列等功能&#xff0c; Zookeeper可以保证如下分布式一致性特性&#xff1a; 顺…...

Java框架学习 | MyBatis

问题导向学习MyBatis 为什么要有MyBatis框架&#xff1f; 避免Java开发者直接使用 JDBC重复做数据库操作&#xff0c;同时更便捷地实现想要的数据库相关功能&#xff0c;让Java专注于开发业务。 MyBatis框架如何实现该目的&#xff1f; MyBatis是半自动化持久层ORM框架&#x…...

Cookie+Session详解

文章目录批量删除会话技术简介CookieCookie 查看Cookie 的删除Cookie 使用页面获取 cookie 信息cookie 特点Sessionsession 的使用Session 登录权限验证过滤器简介过滤器的使用WebFilter 注解过滤放行登录权限验证批量删除 servlet 类 dao 层 会话技术 简介 在计算机领域…...

CAPL脚本要注意区分elcount和strlen求数组长度的区别,不然要吃大亏

&#x1f345; 我是蚂蚁小兵&#xff0c;专注于车载诊断领域&#xff0c;尤其擅长于对CANoe工具的使用&#x1f345; 寻找组织 &#xff0c;答疑解惑&#xff0c;摸鱼聊天&#xff0c;博客源码&#xff0c;点击加入&#x1f449;【相亲相爱一家人】&#x1f345; 玩转CANoe&…...

CSS常用选择器

目录 1.CSS是什么 2.CSS的三种写法 2.1内部样式 2.2内联样式 2.3外部样式 3.CSS选择器 3.1标签选择器 3.2类选择器(更好的选择) 3.3ID选择器 3.4后代选择器 3.5子选择器 3.6并集选择器 3.7伪类选择器(复合选择器的特殊用法) 1.CSS是什么 CSS全称Cascding Style Sh…...

Registry与DGC的攻击利用

0x01 2022-02-03写的一篇文章。 0x02 Registry Registry指的是RMI的注册表&#xff0c;攻击的目标是注册表所在的机器&#xff0c;一般注册表和RMI Server在同一个机器上&#xff0c;特殊情况下也会在不同机器上。 在我们通过LocateRegistry#getRegistry获取到目标开启的注…...

赛道持续降温!又一家自动驾驶公司裁员,市值曾超50亿美元

从去年下半年开始&#xff0c;自动驾驶赛道的裁员、倒闭风潮盛行。 本周&#xff0c;美股卡车自动驾驶上市公司Embark Trucks&#xff08;EMBK&#xff09;宣布将裁员70%&#xff0c;同时大幅缩减业务。“痛苦可能还没有结束&#xff0c;”公司首席执行官Alex Rodrigues在给员…...

路径规划 | 图解动态A*(D*)算法(附ROS C++/Python/Matlab仿真)

目录0 专栏介绍1 什么是D*算法&#xff1f;2 D*算法核心概念一览3 D*算法流程图4 步步图解&#xff1a;算法实例5 算法仿真与实现5.1 ROS C实现5.2 Python实现0 专栏介绍 &#x1f525;附C/Python/Matlab全套代码&#x1f525;课程设计、毕业设计、创新竞赛必备&#xff01;详…...

GraphCut、最大流最小割定理

G&#xff08;V&#xff0c;E&#xff09;&#xff1b;V为点集&#xff0c;E为边集&#xff1b; 节点集V中的节点分为&#xff1a; &#xff08;1&#xff09;终端节点。不包含图像像素&#xff0c;用S和T表示。S为源点&#xff0c;T为汇点。图像分割中通常用S表示前景目标&a…...

Word文档的密码忘记了怎么办?

Word文档可以设置两种密码&#xff0c;文件的“限制密码”和“打开密码”&#xff0c;今天来分享一下忘记这两种密码可以如何处理。 如果忘记的是Word文档的“限制密码”&#xff0c;文档就无法编辑及更改了&#xff0c;菜单目录中的相关选项也都是灰色状态&#xff0c;无法点…...

Java分布式事务(二)

文章目录&#x1f525;分布式事务处理_认识本地事务&#x1f525;关系型数据库事务基础_并发事务带来的问题&#x1f525;关系型数据库事务基础_MySQL事务隔离级别&#x1f525;MySQL事务隔离级别_模拟异常发生之脏读&#x1f525;MySQL事务隔离级别_模拟异常发生之不可重复读&…...

游戏项目中的程序化生成(PCG):算法之外的问题与问题

本篇讨论的是什么 从概念上讲&#xff0c;PCG&#xff08;程序化生成&#xff09;的含义很广&#xff1a;任何通过规则计算得到的内容&#xff0c;都可算作是PCG。但在很多游戏项目的资料&#xff0c;包括本篇&#xff0c;讨论PCG时特指是&#xff1a;用一些算法/工具(特别是H…...

【C++】位图+哈希切割+布隆过滤器

文章目录一、位图1.1 位图概念1.2 位图实现1.2.1 把x对应比特位0置11.2.2 把x对应比特位1置01.2.1 查看x对应比特位1.3 位图源码1.4 位图的应用二、哈希切割&#xff08;处理海量数据&#xff09;三、布隆过滤器3.1 布隆过滤器的概念3.2 布隆过滤器的应用场景3.3 布隆过滤器的实…...

python实现网络游戏NPC任务脚本引擎(带限时任务功能)

python实现NPC任务脚本引擎 一、简介二、简单示例三、实现任务限时的功能四、结合twisted示例一、简介 要实现面向对象的网络游戏NPC任务脚本引擎,可以采用以下步骤: 1.定义NPC类:该类应该包括NPC的基本属性和行为,如名字、位置、血量、攻击力等等。NPC还应该有任务的列表…...

C语言的原子操作(待完善)

文章目录一、什么是原子操作二、为什么需要原子操作三、API一、什么是原子操作 原子操作是不可分割的&#xff0c;在执行完毕之前不会被任何其它任务或事件中断&#xff0c;可以视为最小的操作单元&#xff0c;是在执行的过程中、不会导致对数据的并发访问的、最小操作&#x…...

JavaScript Boolean 布尔对象

文章目录JavaScript Boolean 布尔对象Boolean 对象Boolean 对象属性Boolean 对象方法检查布尔对象是 true 还是 false创建 Boolean 对象JavaScript Boolean 布尔对象 Boolean&#xff08;布尔&#xff09;对象用于将非布尔值转换为布尔值&#xff08;true 或者 false&#xff0…...

删除链表元素相关的练习

目录 一、移除链表元素 二、删除排序链表中的重复元素 三、删除排序链表中的重复元素 || 四、删除链表的倒数第 N 个结点 一、移除链表元素 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头…...

3DEXPERIENCE Works 成为了中科赛凌实现科技克隆环境的催化剂

您的企业是否想过实现设计数据的统筹管理&#xff0c;在设计上实现标准化&#xff0c;并把每位设计工程师串联起来协同办公?中科赛凌通过使用3DEXPERIENCE Works 实现了上述内容&#xff0c;一起来看本期案例分享吧!中科赛凌 通过其自主研发的单压缩机制冷技术实现零下190℃制…...

少儿编程 电子学会图形化编程等级考试Scratch一级真题解析(选择题)2022年12月

少儿编程 电子学会图形化编程等级考试Scratch一级真题解析2022年12月 选择题(共25题,每题2分,共50分) 1、小明想在开始表演之前向大家问好并做自我介绍,应运行下列哪个程序 A、 B、 C、 D、 答案:D...

【完整版】国内网络编译,Ambari 2.7.6 全部模块源码编译笔记

本次编译 ambari 2.7.6 没有使用科学上网的工具,使用的普通网络,可以编译成功,过程比 ambari 2.7.5 编译时要顺畅。 以下是笔记完整版。如果想单独查看本篇编译笔记,可参考:《Ambari 2.7.6 全部模块源码编译笔记》 该版本相对 2.7.5 版本以来,共有 26 个 contributors …...

HTML 颜色值

HTML 颜色值 颜色由红 (R)、绿 (G)、蓝 (B) 组成。 颜色值 颜色值由十六进制来表示红、绿、蓝&#xff08;RGB&#xff09;。 每个颜色的最低值为 0 (十六进制为 00 )&#xff0c;最高值为 255 (十六进制为 FF )。 十六进制值的写法为#号后跟三个或六个十六进制字符。 三位…...