程序员面试金典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对吧,但是它的用处不仅仅如此哦,它还可以消除子行内元素间额外多余的空白! 问题描述ÿ…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...