程序员面试金典17.*
文章目录
- 17.01 不用加号的加法
- 17.04 消失的数字
- 17.05字母与数字
- 17.06 2出现的次数
- 17.07 婴儿名字
- 17.08 马戏团人塔
- 17.09 第k个数
- 17.10 主要元素
- 17.11 单词距离
- 17.12 BiNode
- 17.13 恢复空格(未做,字典树+dp)
- 17.14 最小K个数
- 17.15 最长单词
- 17.16按摩师
- 17.17 多次搜索
- 17.18 最短超串
- 17.19 消失的两个数
- 17.20 连续中值
- 17.21 接雨水
- 后面的太难了,不想写了,换书刷了
- 17.22 单词转换
- 17.23最大黑方阵
- 17.24 最大子矩阵
- 17.25 单词矩阵
- 17.26 稀疏相似度
17.01 不用加号的加法
好像是计算机组成原理的知识,完全不会。
class Solution {public static int add(int a, int b) {int sum = 0, carry = 0;while(b != 0) {sum = a ^ b; // 异或计算未进位的部分carry = (a & b) << 1; // 进位部分a = sum; // 保存未进位部分,再次计算b = carry; // 保存进位部分,再次计算}return a; // 最后无进位,异或的结果即加法结果}
}
17.04 消失的数字
异或运算,利用xx=0,x0=x,x^y= y^x的性质,简单说就是一个萝卜一个坑(下标和数组里的数),然后找没有萝卜的那个坑。
int missingNumber(vector<int>& nums)
{int sum = 0;for (int i = 0; i < nums.size(); i++){sum ^= i;sum ^= nums[i];}sum ^= nums.size();return sum;
}
17.05字母与数字
定义一个差分数组diff, 后面直接对diff数组进行操作。来确定截取范围。
class Solution {public String[] findLongestSubarray(String[] array) {int[] diff=new int[array.length+1];HashMap<Integer,Integer> first=new HashMap<>();for(int i=0;i<array.length;i++){diff[i+1]=(array[i].charAt(0)>>6 &1 )*2-1 +diff[i];}int start=0,end=0;for(int i=0;i<diff.length;i++){int j=first.getOrDefault(diff[i],-1);if(j<0){first.put(diff[i],i);}else if(i-j>end-start){start=j;end=i;}}String[] ans=new String[end-start];System.arraycopy(array, start, ans, 0, ans.length);return ans;}
}
17.06 2出现的次数
class Solution {public int numberOf2sInRange(int n) {if (n < 2) return 0;int high = n, pow = 1, low = 0;while (high > 9) {low += high % 10 * pow;pow *= 10;high /= 10;}if (high == 1) return numberOf2sInRange(pow - 1) + numberOf2sInRange(low);if (high == 2) return numberOf2sInRange(2 * pow - 1) + numberOf2sInRange(low) + low + 1;return pow + high * numberOf2sInRange(pow - 1) + numberOf2sInRange(low);}
}
n=358
high=3
low=58
pow=100
ans=100+3func(99)+func(58)
200多里面的2 + 0-99里面的3 + 201-258里面的2
17.07 婴儿名字
使用并查集,而不是让所有都指向一个祖宗。
class Solution {public String[] trulyMostPopular(String[] names, String[] synonyms) {HashMap<String,Integer> map = new HashMap<>();HashMap<String,String> unionmap=new HashMap<>();for(int i=0;i<names.length;i++){ //对names进行简单处理int idx1=names[i].indexOf('(');int idx2=names[i].indexOf(')');int frequency=Integer.valueOf(names[i].substring(idx1+1,idx2));map.put(names[i].substring(0,idx1),frequency);}for(String pair:synonyms){int idx=pair.indexOf(',');String name1=pair.substring(1,idx);String name2=pair.substring(idx+1,pair.length()-1);//找祖宗节点while(unionmap.containsKey(name1)){name1=unionmap.get(name1);}while(unionmap.containsKey(name2)){name2=unionmap.get(name2);}if(!name1.equals(name2)){int frequency=map.getOrDefault(name1,0)+map.getOrDefault(name2,0);String s1= name1.compareTo(name2)<0 ? name1:name2;String s2=name1.compareTo(name2)<0 ?name2:name1;unionmap.put(s2,s1);map.remove(s2);map.put(s1,frequency);}}String[] ans=new String[map.size()];int index=0;for(String name:map.keySet()){StringBuilder s1=new StringBuilder(name);s1.append('(');s1.append(map.get(name));s1.append((')'));ans[index++]=s1.toString();}return ans;}
}
17.08 马戏团人塔
关于Arrays.binarySearch
要理解为什么先按身高升序排,再按体重降序排。
height[] 1 2 2 3 4
weight[] 1 4 3 5 7
这样从前到后,先输入4,然后输入3,最后在dp[]中定格的是3
class Solution {public int bestSeqAtIndex(int[] height, int[] weight) {int len = height.length;int[][] person = new int[len][2];for (int i = 0; i < len; ++i)person[i] = new int[]{height[i], weight[i]};Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);int[] dp = new int[len];int res = 0;for (int[] pair : person) {int i = Arrays.binarySearch(dp, 0, res, pair[1]);if (i < 0)i = -(i + 1);dp[i] = pair[1];if (i == res)++res;}return res;}
}
17.09 第k个数
三指针问题,三个指针,然后分别进行操作,取最小值即可。
public int getKthMagicNumber(int k) {int [] result = new int[k];result[0] = 1;// 定义三个 指针,分别表示 resultA、B、C 的下标int point3 = 0;int point5 = 0;int point7 = 0;for (int i = 1; i < k; i++) {int resultN = Math.min(Math.min(result[point3] * 3, result[point5] * 5), result[point7] * 7);if (resultN % 3 == 0) {point3++;}if (resultN % 5 == 0) {point5++;}if (resultN % 7 == 0) {point7++;}result[i] = resultN;}return result[k - 1];}
}
17.10 主要元素
数组中占比超过一半的元素称之为主要元素。
先用摩尔投票法筛出一个元素,然后再判断这个元素的占比是否大于一半。
17.11 单词距离
单纯遍历一遍,记录即可
17.12 BiNode
中序遍历过程中,将当前节点的左节点置空,并将当前节点置为上一结点的右节点。pre始终指向当前节点的上一结点,在遍历时不断的移动。
一定要把pre声明出一个变量。
class Solution {TreeNode pre=null;public TreeNode convertBiNode(TreeNode root) {if(root==null) return null;TreeNode ans=root;while(ans.left!=null) ans=ans.left;inorder(root);return ans;}public void inorder(TreeNode root){if(root==null) return;inorder(root.left);root.left=null;if(pre!=null) pre.right=root;pre=root;inorder(root.right);}}
17.13 恢复空格(未做,字典树+dp)
字典树插入时要逆序插入。这样遍历sentence的时候方便向前查找
class Solution {public int respace(String[] dictionary, String sentence) {int n = sentence.length();Trie root = new Trie();for (String word: dictionary) {root.insert(word);}int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for (int i = 1; i <= n; ++i) {dp[i] = dp[i - 1] + 1;Trie curPos = root;for (int j = i; j >= 1; --j) {int t = sentence.charAt(j - 1) - 'a';if (curPos.next[t] == null) {break;} else if (curPos.next[t].isEnd) {dp[i] = Math.min(dp[i], dp[j - 1]);}if (dp[i] == 0) {break;}curPos = curPos.next[t];}}return dp[n];}
}class Trie {public Trie[] next;public boolean isEnd;public Trie() {next = new Trie[26];isEnd = false;}public void insert(String s) {Trie curPos = this;for (int i = s.length() - 1; i >= 0; --i) {int t = s.charAt(i) - 'a';if (curPos.next[t] == null) {curPos.next[t] = new Trie();}curPos = curPos.next[t];}curPos.isEnd = true;}
}
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/re-space-lcci/solution/hui-fu-kong-ge-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
17.14 最小K个数
1.用最大堆
class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);int[] ans = new int[k];if (k == 0) return ans;for (int i : arr) {if (q.size() == k && q.peek() <= i) continue;if (q.size() == k) q.poll();q.add(i);}for (int i = k - 1; i >= 0; i--) ans[i] = q.poll();return ans;}
}
2.用快速排序的思想,因为题目要求是返回无序的数组即可。
17.15 最长单词
先排序,按字符串长度从大到小,然后按字典序。 全塞进set集合里,不停的remove并且判断。
public class Solution {public static String longestWord(String[] words) {Arrays.sort(words, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {if(o1.length()==o2.length()){return o1.compareTo(o2);}else{return Integer.compare(o2.length(),o1.length());}}});//参数要collection,所以用了Arrays.asList()进行转换Set<String>set=new HashSet<>(Arrays.asList(words));for(String word:words){set.remove(word);if(find(set,word)) return word;}return "";}public static boolean find(Set<String>set,String word){if(word.length() == 0)return true;for(int i = 0; i < word.length(); i++){if(set.contains(word.substring(0,i+1)) && find(set,word.substring(i+1)))return true;}return false;}public static void main(String[] args) {Scanner sc=new Scanner(System.in);ArrayList<String> array1=new ArrayList<>();//使用hasNext的重载方法,让其停下。while(!sc.hasNext("#")){String s1=sc.nextLine();array1.add(s1);}String[] s1=array1.toArray(new String[array1.size()]);String ans=longestWord(s1);System.out.println(ans);}
}
17.16按摩师
直接动态规划,可以将数组压成常数。
public class Solution {public int massage(int[] nums) {if(nums.length==0) return 0;int n=nums.length;int[][] dp=new int[n][2];dp[0][0]=0;dp[0][1]=nums[0];for(int i=1;i<n;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);dp[i][1]=nums[i]+dp[i][0];}return Math.max(dp[n-1][0],dp[n-1][1]);}
}
17.17 多次搜索
前缀树Trie;
思路
trie中记录smalls中的字符串,末尾记录字符串,方便后面遍历。
trie中的search用于搜索字符串,将搜索到的字符串存入返回值中。
遍历big长字符串,将其与trie匹配。
按smalls顺序输出最终结果
17.18 最短超串
labuladong算法小抄里面滑动窗口C++解法的java版。
1.把[left,right]称为一个窗口;
2.先右移右指针扩大窗口,直到窗口中的数字满足small数组要求;
3.满足要求时,停止增加right,转而增加left缩小窗口,直到不满足要求
4.重复2,3步直到right走到big尽头
17.19 消失的两个数
两个数,先算出一个数
方法一:求和算出a+b的和,然后在[1,(a+b)/2] 中可以找到一个数,然后用(a+b)减去这个数即可
方法二:用位运算算出t=a^b,然后用diff=t & (-t)可以找出a和b所相差的二进制最低位不一样的位数,则可以根据此将输入数组和[1.n+2]分为两组。比如一组这一位都是0,则这一组全异或(输入数组和[1,n+2]中这一位全是0的),则可以获得a,然后b=t ^ a;
17.20 连续中值
利用一个大顶堆一个小顶堆,中位数可以看作是隔开两个数组的分位线,这样左端用大顶堆,右端用小顶堆,最后两个堆(奇数个是一个)的peek求平均即可。
class MedianFinder {PriorityQueue<Integer> left, right;boolean isLeft;/** initialize your data structure here. */public MedianFinder() {left = new PriorityQueue<>((x, y) -> y - x);right = new PriorityQueue<>();}public void addNum(int num) {//注意这一行不能省略,目的是为了维护左边的值永远小于右边的值,所以要先扔进左堆,再拿出来放进右堆left.offer(num);right.offer(left.poll());if (left.size() < right.size())left.offer(right.poll());}public double findMedian() {if (left.size() > right.size())return left.peek();return (left.peek() + right.peek()) / 2.0;}
}
17.21 接雨水
复杂度:O(N)
解题思路:只有凹的地方能存水,存水量遵循短板原则,所以用每个位置左右两侧最大值中的较小者减当前位置的值即可得到当前位置储水量。
解题方法:先倒叙遍历,用数组记录每个位置其右侧最大值max右,再正序遍历,时刻记录并更新当前位置左侧的最大值max左,然后当前位置存水量c=Min(max左,max右)-当前值,如果c<=0则表示没有水,抛弃即可,最后每个位置的c累加一起的和即为总储水量。
class Solution {public int trap(int[] height) {int size1=height.length;if(size1==0) return 0;int []maxRight=new int[size1];int []maxLeft=new int[size1];maxLeft[0]=height[0];for(int i=1;i<size1;i++){maxLeft[i]=Math.max(height[i],maxLeft[i-1]);}maxRight[size1-1]=height[size1-1];for(int i=size1-2;i>=0;i--){maxRight[i]=Math.max(height[i],maxRight[i+1]);}int ans=0;for(int i=1;i<size1-1;i++){ans+=Math.min(maxLeft[i],maxRight[i])-height[i];}return ans;}
}
后面的太难了,不想写了,换书刷了
17.22 单词转换
17.23最大黑方阵
17.24 最大子矩阵
17.25 单词矩阵
17.26 稀疏相似度
相关文章:

程序员面试金典17.*
文章目录 17.01 不用加号的加法17.04 消失的数字17.05字母与数字17.06 2出现的次数17.07 婴儿名字17.08 马戏团人塔17.09 第k个数17.10 主要元素17.11 单词距离17.12 BiNode17.13 恢复空格(未做,字典树dp)17.14 最小K个数17.15 最长单词17.16…...

【瑞吉外卖项目复写】基本部分复写笔记
Day1 瑞吉外卖项目概述 mysql的数据源配置 spring:datasource:druid:driver-class-name: com.mysql.cj.jdbc.Driverurl: jdbc:mysql://localhost:3306/regie?serverTimezoneAsia/Shanghai&useUnicodetrue&characterEncodingutf-8&zeroDateTimeBehaviorconvertTo…...

用html+javascript打造公文一键排版系统15:一键删除所有空格
现在我们来实现一键删除所有空格的功能。 一、使用原有的代码来实现,测试效果并不理想 在这之前我们已经为String对象编写了一个使用正则表达式来删除所有空格的方法: //功能:删除字符串中的所有空格 //记录:20230726创建 Stri…...

苍穹外卖day12(完结撒花)——工作台+Spring_Apche_POI+导出运营数据Excel报表
工作台——需求分析与设计 产品原型 接口设计 工作台——代码导入 将提供的代码导入对应的位置。 工作台——功能测试 Apache POI_介绍 应用场景 Apache POI_入门案例 导入坐标 <!-- poi --><dependency><groupId>org.apache.poi</groupId><ar…...
SQL与NoSQL概念(详细介绍!!)
先搞清楚全称 SQL全称为Structured query language ,即结构化查询语言,可以把他理解为一门特殊的编程语言。 那么nosql是什么意思呢?这里的no并不仅是not,而是not only的意思,所以nosql全称应该是Not Only Structure…...
node debian 镜像 new Date 获取时间少 8 小时问题
问题 在 node debian 镜像中,用 (new Date()).getHours() 与系统时间(东 8 区)少了 8 小时 系统时间 $ node > (new Date()).getHours() 11容器中的时间 $ node > (new Date()).getHours() 3原 Dockerfile FROM node:20.5-bullsey…...

【N32L40X】学习笔记13-软件IIC读写EEPROM AT24C02
AT24C02 8个字节每页,累计32个页 通讯频率MAX 400K AT24C02大小 2K 芯片地址 对于at24c02 A2A1A0 这三个引脚没有使用 写时序 由于设备在写周期中不会产生ACK恢复,因此这可用于确定周期何时完成(此特性可用于最大限度地提高总线吞吐量)…...

JVM 调优
点击下方关注我,然后右上角点击...“设为星标”,就能第一时间收到更新推送啦~~~ JVM调优是一项重要的任务,可以提高Java应用程序的性能和稳定性。掌握JVM调优需要深入了解JVM的工作原理、参数和配置选项,以及历史JVM参数的调整和优…...

DP-GAN剩余代码
在前面计算完损失后,该进行更新: 1:netEMA是模型的生成器: 遍历生成器的state_dict,将每一个键对应的值乘以EMA_decay。 接着根据当前迭代步数计算num_upd,每1000,2500,10000代倍数就执行一次。 当num…...

在word的文本框内使用Endnote引用文献,如何保证引文编号按照上下文排序
问题 如下图所示,我在word中插入了一个文本框(为了插图),然后文本框内有引用,结果endnote自动将文本框内的引用优先排序,变成文献[1]了,而事实上应该是[31]。请问如何能让文本框内的排序也自动…...

SpringBoot项目上传至服务器
1.服务器安装JDK1.8 通过包管理器安装 2.服务器安装数据库 参考链接: CentOS 7 通过 yum 安装 MariaDB - 知乎 1. 安装之后没有密码,所以需要设置密码,使用下面的语句 set password for rootlocalhost password(111111); 2.在数据库中建…...
C++中实现多线程的三种方式
目录 1 背景2 方法 1 背景 力扣1116题 打印零和奇偶数。 2 方法 方法1:原子操作 class ZeroEvenOdd { private:int n;atomic<int> flag 0; public:ZeroEvenOdd(int n) {this->n n;}// printNumber(x) outputs "x", where x is an integer.…...

程序员副业指南:怎样实现年入10w+的目标?
大家好,这里是程序员晚枫,全网同名。 今天给大家分享一个大家都感兴趣的话题:程序员可以做什么副业,年入十万? 01 推荐 程序员可以从事以下副业,以获得一年收入10w: 兼职编程:可…...
excel 计算 分位值
_XLFN.QUARTILE.EXC(Result 1!G:G,2) 和 PERCENTILE 都可以用来计算一组数据的分位数,但是它们的计算方式略有不同。 _XLFN.QUARTILE.EXC(Result 1!G:G,2) 是 Excel 中的一个函数,在计算一个数据集的四分位数时使用。其中,第一个参数 Result…...

一个SpringBoot 项目能处理多少请求?
这篇文章带大家盘一个读者遇到的面试题哈。 根据读者转述,面试官的原问题就是:一个 SpringBoot 项目能同时处理多少请求? 不知道你听到这个问题之后的第一反应是什么。 我大概知道他要问的是哪个方向,但是对于这种只有一句话的…...
Shell编程基础(十)读取多行文本到数组 写入多行文本到文件
读取多行文本到数组 & 写入多行文本到文件 读取多行文本到数组写入多行文本到文件 读取多行文本到数组 创建一个文本文件,内容如下 1 zhangsan 男 10 2 liis 女 12 3 wangwu 男 17读取这个文件中所有人的信息 #!/bin/bash while read u do echo $u done <…...
MyBatis学习笔记2
CRUD 1.namespace namespace中的包名要和mapper接口的包名一致! 2.select 选择查询语句 id:就是对应的namespace中的方法名; resultType:Sql语句执行的返回值! parameterType:参数类型 增删改必须提交事务&…...

spring总结
目录 什么是Spring? Spring的优缺点? 优点: 缺点: Spring IOC的理解 Spring AOP的理解 事务的边界为什么放在service层? Spring Bean的生命周期 什么是单例池?作用是什么? 单例Bean的优势 Bean…...

记录--说一说css的font-size: 0
这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助 平常我们说的font-size:0;就是设置字体大小为0对吧,但是它的用处不仅仅如此哦,它还可以消除子行内元素间额外多余的空白! 问题描述ÿ…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...

python可视化:俄乌战争时间线关键节点与深层原因
俄乌战争时间线可视化分析:关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一,自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具,系统分析这场战争的时间线、关键节点及其背后的深层原因,全面…...
标注工具核心架构分析——主窗口的图像显示
🏗️ 标注工具核心架构分析 📋 系统概述 主要有两个核心类,采用经典的 Scene-View 架构模式: 🎯 核心类结构 1. AnnotationScene (QGraphicsScene子类) 主要负责标注场景的管理和交互 🔧 关键函数&…...

vxe-table vue 表格复选框多选数据,实现快捷键 Shift 批量选择功能
vxe-table vue 表格复选框多选数据,实现快捷键 Shift 批量选择功能 查看官网:https://vxetable.cn 效果 代码 通过 checkbox-config.isShift 启用批量选中,启用后按住快捷键和鼠标批量选取 <template><div><vxe-grid v-bind"gri…...