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

算法通过村第十三关-术数|白银笔记|术数高频问题

文章目录

  • 前言
  • 数组实现加法专题
    • 数组实现整数加法
    • 字符串加法
    • 二进制加法
  • 幂运算专题
    • 求2的次幂
    • 求3的次幂
    • 求4的次幂
  • 总结


前言


提示:人心本易趋死寂,苦难之后,焕然重建,激荡一阵,又趋麻木。 --苏枕书《有鹿来》

我们继续看几个数学与数字相关的重要题目,数学的问题有很多,力扣上面也有很多练习,通过这些练习你可以掌握很多技巧,真的如果你不练习,你真的不知道其实还可以这么做。所以算法也是一个累计的过程,积累经验才能以后游刃有余。

数组实现加法专题

数字加法,可以说是老生常谈了,但是让你用数组表示一个数,你需要如何去实现呢?今天我们就来挑战一下。

这里提前说一下,你会遇到很多棘手的问题,例如:A[0]位置时发现如果进位要怎么办?

再拓展一下,如果给定两个数,一个数用数组存储,另外一个是普通的整数,又该如何处理呢?

在拓展,如果两个整数是用字符串表示的呢? 如果是二进制表示的呢?加法的规则怎么处理?

数组实现整数加法

参考题目介绍:66. 加一 - 力扣(LeetCode)

在这里插入图片描述
在这里插入图片描述

这个看似很简单?从后向前一次加就行了,如果有进位就标记一下,但是如果到头了也要进位要怎么办?

例如:digits=[9,9,9],从后面向前加的时候,到了A[0]的位置计算为0,需要再次进位,但是数组却不能保存,这里该怎么办?

这里的关键是A[0] 在什么时候出现进位的情况,我们直到此时一定是9, 99, 999, …这样的结构才会出现加1之后再次进位,而进位之后的结果一定是10,100,1000这样的结构,由于Java中数组默认初始化为0,所以我们此时只需要再次申请一个空间比A[]大一个数的数组B[],然后将B[0]设置为1就可以。代码写起来也很简洁。

   /*** 整数加一* @param digits* @return*/public static int[] plusOne(int[] digits) {int len = digits.length;for (int i = len - 1; i >= 0; i--) {digits[i]++;digits[i] %= 10;// 注意这里 提前出去的条件if (digits[i] != 0) {return digits;}}// 9 99 999等 // 这里比较巧妙digits = new int[len + 1];digits[0] = 1;return digits;}

字符串加法

我们继续看将数组存储再字符串中的情况:字符串加法就是使用字符串表示数字,然后计算他们的和。具体要求如下:给定两个字符串形式的非负整数num1和num2,计算他们的和并同样以字符串形式返回。你不能使用内建的用于处理大整数的库(比如BigInteger),也不能直接将输入的字符串转换成整数形式。

我们写个例子:

例如:
输入:num1 = "456" , num2 = "77"
输出:"533"

我们先想一下小学里面的加法是如何实现两个数的计算的。经典的竖式加法:
在这里插入图片描述
从低位到高位逐步相加,如果当前位和超过10,则向高位进一位。

因此我们只要将这个过程用代码表示出来就可以了。先定义两个指针 i 和 j 分别指向 num1 和num2 的末尾,也就是最低位,同样定义一个变量 add 维护当前是否需要进位,然后从末尾到开头诸位累加。

这里有个问题,两个数字位数不同该怎么处理?很简单,补0就可以了,我们看看具体要怎么做吧:

    /***  两个字符串相加* @param num1* @param num2* @return*/public static String addStrings(String num1, String num2) {// 准备工作int len1 = num1.length(), len2 = num2.length();StringBuffer ans = new StringBuffer();int add = 0;// 注意循环条件处理while(len1 >= 0||len2 >= 0 || add != 0){// 缺位补0int x = len1 >= 0 ? num1.charAt(len1) - '0' : 0;int y = len2 >= 0 ? num2.charAt(len2) - '0' : 0;int result = x + y + add;ans.append(result % 10);add = result / 10;len1--;len2--;}// 计算完毕后记得反转ans.reverse();return  ans.toString();}

二进制加法

参考题目介绍:67. 二进制求和 - 力扣(LeetCode)

在这里插入图片描述

在这里插入图片描述

我们看看二进制怎么处理吧!这个题目也是用字符串表示数据的,也要先转为字符数组。我们熟悉的十进制,是从个位开始,逐步到高位,达到10就进位,而对于二进制判断相加之后是否为2,就可以决定是否发生进位了。如果是就进位。所以思路大致一样,也是由于字符串的操作原因,不确定左后移位是否出现进位,这里提供两个办法处理

  • 第一种:在进行计算时直接拼接字符串,得到一个反向字符,最后再翻转回来。(10进制一样)
  • 第二种:按照位置给结果字符赋值,最后如果有进位,则在前方进行字符串拼接加进位

我们这里就采用第二种做:

    /*** 两个字符串二进制相加* @param a* @param b* @return*/public static String addBinary(String a, String b) {// 准备工作int len1 = a.length(), len2 = b.length();StringBuffer ans = new StringBuffer();int add = 0;for (int i = len1 - 1, j = len2 - 1; i >= 0 || j >= 0; i--, j--) {int sum = add;sum += i >= 0 ? a.charAt(i) - '0' : 0;sum += j >= 0 ? b.charAt(j) - '0' : 0;ans.append(sum % 2);add = sum / 2;}ans.append(add == 1 ? add : "");return ans.reverse().toString();}

当然有人回想,这里转成十进制,计算完成后再转成二进制不也行吗?这么实现很容易,而且可以使用语言的特性直接转换,但是面试的时候也不行,用不了,但是工程里可以这么做,稳定(算法不行,不能这么干)

幂运算专题

幂运算也是常见的数学运算,其形式为ab,也就是a的b次方呗,其中a称为底数,b称为指数,ab的合法运算(不会出现a == 0 且 b <= 0 的情况)。幂运算满足底数和指数都是实数。根据具体情况,底数和指数的数据类型和取值范围也各不相同,例如有的说是,底数是正整数,指数为非负数,有的问题中,底数为实数,指数是整数。

力扣中,幂运算相关的问题主要判断一个数是不是特定正整数的整数次幂,以及快速处理幂。

求2的次幂

参考题目介绍:231. 2 的幂 - 力扣(LeetCode)

在这里插入图片描述
在这里插入图片描述

本题目的解决思路还是很清晰的,我们可以用除的方法来逐步缩小n的值,另外一个就是使用位运算。

逐步缩小的方法就是:如果n是2的幂数, 则 n > 0,且存在非负整数 k 是的 n = 2 ^ k。

首先判断 n 是否是正整数,如果 n 是 0 或者 负整数,则 n 一定不是 2 的幂。

当 n 是整数时,为了判断 n 是否是 2 的幂, 可以连续对 n 进行除以 2 的操作,直到 n 不能被 2 整除。此时如果 n = 1,那么 n 就是 2 的幂数,否则 n 不是 2 的幂。

代码如下:

    /*** 是否为2的幂* @param n* @return*/public static boolean isPowerOfTwo(int n) {if ( n <= 0){return false;}while (n % 2 == 0){n /= 2;}return n == 1;}

当然这种方法效率不高,容易超时。(但是我们有法宝 位运算加强🥰

如果采用位运算,该方法与我们之前说的统计数字转换二进制数以后1的个数思路一致。当 n > 0 时,考虑 n 的二进制表示。如果存在非负整数k 使得 n = 2 ^ k ,则n 的二进制表示为 1 后面跟着 k 个 0 。由此可以看出,正整数 n 是 2 的幂,当且仅当 n 的二进制表示中只有最高位是 1 ,其余位 都是 0, 此时满足 n & ( n - 1) = 0。此时代码就简单多了。

   public boolean isPowerOfTwo(int n) {return (n > 0) && (n &(n - 1)) == 0;}

注意:考虑优先级问题

求3的次幂

参考题目介绍:326. 3 的幂 - 力扣(LeetCode)

在这里插入图片描述

在这里插入图片描述
逐步缩小的方法对此也适用:

如果n是 3 的幂数, 则 n > 0,且存在非负整数 k 是的 n = 3 ^ k。

首先判断 n 是否是正整数,如果 n 是 0 或者 负整数,则 n 一定不是 3 的幂。

当 n 是整数时,为了判断 n 是否是 3 的幂, 可以连续对 n 进行除以3 的操作,直到 n 不能被 2 整除。此时如果 n = 1,那么 n 就是 3 的幂数,否则 n 不是 3 的幂。

    public boolean isPowerOfThree(int n) {if(n <= 0){return false;}while(n % 3 == 0){n /= 3;}return n == 1;}

这个技巧和上面的一样,这里提供另一个思路:

由于输入 n 是 int 型, 其最大值为 2 ^ 31 - 1。因此在int 型的数据范围内存在最大的 3 的幂,不会超过2 ^ 31 - 1,最大的 3 的幂是 3 ^ 19 = 1162261467。所以在 1 ~ 2 ^ 31 - 1内的数,如果是 3 的幂数,那么一点是1162261467的除数,所以这里就可以这样写:

    public boolean isPowerOfThree(int n) {return n > 0 && 1162261467 % n == 0;}

当然这个解法只是扩展思路的,没必要记住这个1162261467这个数字。

思考一下:这里换成4,5,6,7,8,9可以嘛?如果不可以,那如果只是针对素数3,5,7,11, 13 可以嘛?

求4的次幂

参考题目介绍:342. 4的幂 - 力扣(LeetCode)

在这里插入图片描述

在这里插入图片描述
上述同样的方法这里也可行,推荐换一种判断负数的方式

    public boolean isPowerOfFour(int n) {while(n != 0 && n % 4 == 0){n /= 4;}return n == 1;}

试想一下,这个题还能怎么优化,是否可以利用2的次幂呢?

这里留一个作业💕

当然除了幂运算,指数计算的思路与之类似,感兴趣也可以尝试下

50. Pow(x, n) - 力扣(LeetCode)

那这个题练练手


总结

提示:数组加法专题;字符串加法;二进制加法;幂运算;幂运算优化;


如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/

如有不理解的地方,欢迎你在评论区给我留言,我都会逐一回复 ~

也欢迎你 关注我 ,喜欢交朋友,喜欢一起探讨问题。

在这里插入图片描述

相关文章:

算法通过村第十三关-术数|白银笔记|术数高频问题

文章目录 前言数组实现加法专题数组实现整数加法字符串加法二进制加法 幂运算专题求2的次幂求3的次幂求4的次幂 总结 前言 提示&#xff1a;人心本易趋死寂&#xff0c;苦难之后&#xff0c;焕然重建&#xff0c;激荡一阵&#xff0c;又趋麻木。 --苏枕书《有鹿来》 我们继续看…...

Java 线程的生命周期

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

Vue页面监听键盘按键的多种方法

在Vue页面中&#xff0c;可以使用多种方法来监听键盘按键。以下是至少五种常用的方法&#xff1a; 使用keydown或keyup指令来绑定键盘按键事件。 <template><div><input type"text" keydown.enter"handleEnterKey" /></div> <…...

解析硬件连通性测试的重要性及测试方法

在现代科技世界中&#xff0c;硬件设备的复杂性和多样性已经达到了前所未有的水平。无论是计算机、智能手机、物联网设备还是嵌入式系统&#xff0c;各种硬件组件的协同工作对于设备的正常运行至关重要。硬件连通性测试是确保这些组件相互配合无误的重要步骤。 一、硬件连通性测…...

Hive窗口函数回顾

1.语法 1.1 基于行的窗口函数 Hive的窗口函数分为两种类型&#xff0c;一种是基于行的窗口函数&#xff0c;即将某个字段的多行限定为一个范围&#xff0c;对范围内的字段值进行计算&#xff0c;最后将形成的字段拼接在该表上。 注意&#xff1a;在进行窗口函数计算之前&#…...

flink自定义窗口分配器

背景 我们知道处理常用的滑动窗口分配器&#xff0c;滚动窗口分配器&#xff0c;全局窗口分配器&#xff0c;会话窗口分配器外&#xff0c;我们可以实现自己的自定义窗口分配器&#xff0c;以实现我们的自己的窗口逻辑 自定义窗口分配器的实现 package wikiedits.assigner;i…...

iOS CGRect CGPoint NSRange等结构体的NSLog打印输出

iOS的UIKit里提供了UIGeometry.h内有各结构体转换成NSString的方法&#xff0c;可用于打印输出&#xff1b; UIKIT_EXTERN NSString *NSStringFromCGPoint(CGPoint point); UIKIT_EXTERN NSString *NSStringFromCGVector(CGVector vector); UIKIT_EXTERN NSString *NSStringFr…...

Viper FTP Mac/ftp管理工具

Viper FTP 是一个用于文件传输和管理的 Mac 应用程序。它允许用户上传、下载和管理远程服务器上的文件&#xff0c;以及在不同本地文件夹之间传输文件。 Viper FTP 支持广泛的文件传输协议&#xff0c;包括 FTP、SFTP、WebDav、Amazon S3、Google Drive 等。它还包括文件同步、…...

web漏洞-xml外部实体注入(XXE)

web漏洞-xml外部实体注入&#xff08;XXE&#xff09; 目录 web漏洞-xml外部实体注入&#xff08;XXE&#xff09;概念危害检测方法利用方法漏洞利用xxe-lab有回显情况无回显情况 pikachu靶场有回显内容无回显 修复方案 概念 xml可拓展标记语言&#xff1a; xml是一种可拓展的标…...

Impeller-Flutter的新渲染引擎

Impeller是什么&#xff1f;它本质上是怎样运行的&#xff1f; Impeller是Flutter的新的渲染引擎&#xff0c;直到现在Flutter正在用一个叫做Skia的渲染引擎。 问题是Skia不是为了Flutter量身定做的。它有为范围广阔的设备构建的一大堆的渲染特性&#xff0c;这意味着它并不总…...

python 面试算法题

1.第一题 题目描述:给定两个字符串, s 和 goal。如果在若干次旋转操作之后&#xff0c;s 能变成 goal &#xff0c;那么返回 true 。 s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 例如, 若 s abcde&#xff0c;在旋转一次之后结果就是bcdea 。 示例一: 输入: s &quo…...

Python中的yield关键字

基本概念 yield 是 Python 中的一个关键字&#xff0c;主要在定义生成器函数时使用。使用 yield 的函数在调用时返回一个特殊的迭代器&#xff0c;称为生成器。不同于常规的函数返回一个单一的值&#xff08;如数字、字符串或其他对象&#xff09;&#xff0c;带有 yield 的函…...

怎么压缩pdf文件?分享缩小pdf文件的简单方法

在我们的日常生活和工作中&#xff0c;往往需要处理大量的PDF文件&#xff0c;而很多时候这些文件的大小会成为传输和存储的难题。为了解决这个问题&#xff0c;下面我们将介绍三种方法来压缩PDF文件&#xff0c;一起来看看吧~ 一、嗨格式压缩大师 首先&#xff0c;最简单也是…...

51单片机可调幅度频率波形信号发生器( proteus仿真+程序+原理图+报告+讲解视频)

51单片机可调幅度频率信号发生器( proteus仿真程序原理图报告讲解视频&#xff09; 讲解视频1.主要功能&#xff1a;2.仿真3. 程序代码4. 原理图4. 设计报告5. 设计资料内容清单&&下载链接***[资料下载链接](https://docs.qq.com/doc/DS1daV1BKRXZMeE9u)*** 51单片机可…...

Vuex的介绍

介绍 :::warning 注意 在阅读此文章之前请确保你已经掌握了组件中的选项 data、计算属性 computed、methods 方法等相关知识。 ::: 什么是 Vuex&#xff1f; Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。它采用集中式存储管理应用的所有组件的状态&#xff0c;并以…...

mysql基础语法速成版

mysql基础语法速成版 一、前言二、基础语法2.1 数据库操作2.2 MySQL数据类型2.3 表操作2.3.1 表的创建、删除&#xff0c;及表结构的改变2.3.2表数据的增删改查2.3.4 like模糊查询2.3.5 UNION 操作符2.3.6 order by排序2.3.7 group by分组2.3.8 join连接2.3.9 null处理2.3.10 m…...

Docker镜像 配置ssh

安装 1.安装ssh 2.设置root密码 RUN echo root:123456 | chpasswd 3.设置sshd config RUN echo Port 22 >> /etc/ssh/sshd_config RUN echo PermitRootLogin yes >> /etc/ssh/sshd_config4.设置开机启动 RUN mkdir /var/run/sshd #没有这个目录&#xff0c;s…...

12.2 实现键盘模拟按键

本节将向读者介绍如何使用键盘鼠标操控模拟技术&#xff0c;键盘鼠标操控模拟技术是一种非常实用的技术&#xff0c;可以自动化执行一些重复性的任务&#xff0c;提高工作效率&#xff0c;在Windows系统下&#xff0c;通过使用各种键盘鼠标控制函数实现动态捕捉和模拟特定功能的…...

《DevOps 精要:业务视角》- 读书笔记(七)

DevOps 精要:业务视角&#xff08;七&#xff09; DevOps历程什么是企业体系的DevOps&#xff1f;DevOps的目标是什么&#xff1f; DevOps的知识体系规范敏捷持续交付IT服务管理以TPS理念为基础 DevOps团队角色流程主管&#xff08;Process Master&#xff09;服务主管&#xf…...

【随想】每日两题Day.12(实则一题)

题目&#xff1a;15. 三数之和 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...