面试经典150题【31-40】

文章目录

  • 面试经典150题【31-40】
    • 76.最小覆盖字串
    • 36.有效的数独
    • 54.螺旋矩阵
    • 48.旋转图像
    • 73.矩阵置零
    • 289.生命游戏
    • 383.赎金信
    • 205.同构字符串
    • 290.单词规律
    • 242.有效的字母异位词

面试经典150题【31-40】

76.最小覆盖字串

在这里插入图片描述
基本思路很简单,就是先移动右边到合适位置。再移动左边到破戒,再移动位置到合适位置。
判断合适位置是 count0, 此时need[] 里面也都是0 或 <0 的元素。

public class LC76 {public String minWindow(String s, String t) {if(s == null || s.isEmpty() ||t==null || t.isEmpty()){return "";}int []need=new int[128];for(int i=0;i<t.length();i++){need[t.charAt(i)]++;}//l是当前左边界,r是当前右边界,size记录窗口大小,count是需求的字符个数,start是最小覆盖串开始的indexint l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;//如果need[]<0,说明无关紧要。如果need[]==0,则说明是被需要关注的元素while(r<s.length()){//对右边进行处理char c=s.charAt(r);if(need[c]>0){  //是值得关注的元素count--;}need[c]--;if(count==0){ //已经塞满了关注的元素了//移动左指针while(l<r && need[s.charAt(l)]<0){need[s.charAt(l)]++;l++;}//此时need==0,说明又满足了,开始统计if(r-l+1<size){size = r-l+1;start = l;}//又要向右移动,但是肯定和最小值无关了,开始破戒need[s.charAt(l)]++;l++;count++;}r++;}return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);}
}

36.有效的数独

一定是9×9的,
在第 i 个行中是否出现过
在第 j 个列中是否出现过
在第 j/3 + (i/3)*3个box中是否出现过.
定义三个数组,int [][]row, row[i][j], i代表第几行,j代表出现的元素。
box[i][j], i代表第几个小格子,j代表出现的元素。
在这里插入图片描述

class Solution {public boolean isValidSudoku(char[][] board) {int[][] row = new int[9][10];int[][] col = new int[9][10];int[][] box = new int[9][10];for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {continue;}int curNum = board[i][j] - '0';if (row[i][curNum] == 1) {return false;}if (col[j][curNum] == 1) {return false;}if (box[j / 3 + (i / 3) * 3][curNum] == 1) {return false;}row[i][curNum] = 1;col[j][curNum] = 1;box[j / 3 + (i / 3) * 3][curNum] = 1;}}return true;}
}

54.螺旋矩阵

在这里插入图片描述

class Solution {public List<Integer> spiralOrder(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;int up = 0;int down = m - 1;int left = 0;int right = n - 1;List<Integer> ans = new ArrayList<>();while (true) {for (int i = left; i <= right; i++)ans.add(matrix[up][i]);if (++up > down)break;for (int i = up; i <= down; i++)ans.add(matrix[i][right]);if (--right < left)break;for (int i = right; i >= left; i--)ans.add(matrix[down][i]);if (--down < up)break;for (int i = down; i >= up; i--)ans.add(matrix[i][left]);if (++left > right)break;}return ans;}
}

48.旋转图像

关键是找到公式: matrix[i][j] -> matrix[j][n-1-i]
在这里插入图片描述

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n / 2; i++) {for (int j = 0; j < (n + 1) / 2; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[n - 1 - j][i];matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];matrix[j][n - 1 - i] = tmp;}}}
}

73.矩阵置零

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
还是用两个辅助数组,一个判断某一行,一个判断某一列。舒服。

289.生命游戏

暴力模拟就行。dxdy代表你移动的旁边的8个位置。

int[] dx = { -1, 1, 0, 0, -1, -1, 1, 1 };
int[] dy = { 0, 0, -1, 1, -1, 1, -1, 1 };for (int k = 0; k < 8; k++) {int nx = x + dx[k];int ny = y + dy[k];if (nx < 0 || nx >= m || ny < 0 || ny >= n)continue;// 如果这个位置为 0,代表当前轮是死的,不需要算进去// 如果这个位置为 1,代表当前轮是活得,需要算进去// 如果这个位置为 2,代表当前轮是死的(状态10,下一轮是活的),不需要算进去// 如果这个位置为 3,代表是当前轮是活的(状态11,下一轮也是活的),需要算进去cnt += (board[nx][ny] & 1);
}

383.赎金信

int[] a = new int[26]; 用这个做个小哈希表就行

205.同构字符串

每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上。
要满足最后一条,应该建立两个hash表, m ->t ; t->m
如果只建立一个hash表, abb -> rrr 会成立,但是其应该不成立。

290.单词规律

也是典型的双射问题,两个哈希表就解决了。
如果两个字符串完全不一样,也可以只用一个哈希表。利用hashmap的put操作的返回值的特性。
如果key不存在,插入成功,返回null;如果key存在,返回之前对应的value。
先将字符串截断 String[] words = str.split(" ");
然后用map.put(words[i],i) 与 map.put(s[i],i)判等就行

242.有效的字母异位词

也是hashmp,第一个字符串遍历去++,第二个字符串遍历去–。
最后判断是否所有元素均为0即可。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2812548.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

网络安全与IP安全网络安全

网络安全与IP安全网络安全 网络安全 是指网络系统的硬件&#xff0c;软件以及系统中的数据收到的保护。 保护的基本属性为&#xff1a;机密性&#xff0c;身份认证&#xff0c;完整性和可用性&#xff1b; 基本特征&#xff1a;相对性&#xff0c;时效性&#xff0c;相关性…

[面试]我们常说的负载均衡是什么东西?

什么是负载均衡 如果用户量很多, 服务器的流量也随之增大, 此时出现两个问题, 软件性能下降 容易出现单点故障 为了解决这些问题, 引入了集群化架构, 也就是把一个软件同时部署在多个服务器上 集群化架构出现的问题 架构改变后又出现了两个问题 如何将请求均匀的发送到多…

大疆无人机视频删了怎么恢复?尝试这些恢复技巧

无人机拍摄的视频已经成为许多飞行爱好者和专业人士珍贵的记忆与资料。然而&#xff0c;误删视频是许多人都可能遇到的问题。当您不慎删除了大疆无人机中的视频时&#xff0c;不必过于焦虑。本文将为您详细介绍如何恢复这些误删的视频&#xff0c;帮助您找回宝贵的回忆。 图片来…

Laravel03 路由到控制器与连接数据库

Laravel03 路由到控制器与连接数据库 1. 路由到控制器2. 连接数据库 1. 路由到控制器 如下图一些简单的逻辑处理可以放在web.php中&#xff0c;也就是路由的闭包函数里面。但是大的项目&#xff0c;我们肯定不能这么写。 为什么保证业务清晰好管理&#xff0c;都应该吧业务逻辑…

【Linux深入剖析】进程优先级 | 命令行参数 | 环境变量

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.进程优先级2.Linux…

[C++]使用C++实现监控文件是否被修改

软件开发过程中经常会用到配置文件,某些应用场景要求在软件运行时动态修改配置文件,此时就需要监控配置文件是否被修改,下面我们就来看看如何使用C实现这一功能吧 软件开发过程中经常会用到配置文件&#xff0c;某些应用场景要求在软件运行时动态修改配置文件&#xff0c;此时…

国产服务器操作系统

为何记录 最近的开发工作经常接触到国产服务器操作系统的业务&#xff0c;经常被x86、arm、龙芯、鲲鹏、欧拉...搞得一脸懵逼&#xff0c;遂记之&#xff01; 操作系统 这里按照应用场景分&#xff1a; 桌面操作系统&#xff1a;主要用于pc&#xff0c;如Windows、macOS、Li…

MES系统生产订单管理:多角度全面解析

一、MES系统生产订单管理概述 MES中的生产订单管理涉及到订单的接收、处理、执行和跟踪等多个方面。MES系统生产订单管理旨在确保生产过程中的订单信息准确无误、生产进度可控&#xff0c;从而实现高效、有序的生产。 二、生产订单管理的核心功能 订单接收与处理&#xff1a;…

30-k8s集群的七层代理-ingress资源(进阶知识)

一、ingress概述 1&#xff0c;引发问题 目前使用svc资源做网络暴露&#xff0c;使用nodeport类型&#xff0c;一个业务对应一个宿主机端口&#xff0c;那么如果业务多了&#xff0c;所占用的宿主机端口也就多了&#xff0c;虽然说宿主机端口一般情况下都是够用的&#xff0c;…

Android Jni的介绍和简单Demo实现

Android Jni的介绍和简单Demo实现 文章目录 Android Jni的介绍和简单Demo实现一、JNI的简单介绍JNINDKJni的开发背景&#xff1a;**JNI在 Android 开发里的主要应用场景&#xff1a;** 二、JNI的简单Demo1、Demo主要界面和效果展示2、CMake编译加载文件add_library 指令的加载库…

主从复制实现Redis集群

主从复制实现Redis集群实验 (一主二从): 实验环境: 使用Docker 搭建 Redis 版本 5.0.5 打开一个终端窗口&#xff0c;在其中运行如下命令创建一个名为redis-master的Redis容器。注意&#xff0c;它的端口是6379 (本地的端口:映射到容器的端口) docker run -itd--name redis-m…

深入理解 JavaScript 对象原型,解密原型链之谜(下)

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

VScode连接远端服务器一直输入密码解决方法

文章目录 1 关闭远程连接2打开命令面板3 输入remote-ssh: kill vs code server on host… 1 关闭远程连接 2打开命令面板 3 输入remote-ssh: kill vs code server on host… remote-ssh: kill vs code server on host… 然后一路回车(选中出问题的主机)&#xff0c;输一遍密码…

缓存一致性问题的解决策略

缓存一致性问题的背景和概念介绍 在一个系统中&#xff0c;我们通常使用数据库来存储数据&#xff0c;以保证数据的持久性。但是&#xff0c;由于数据库的读写速度相对较慢&#xff0c;如果每次请求都直接访问数据库&#xff0c;会降低系统的响应速度。为了提高系统的性能&…

《TCP/IP详解 卷一》第7章 防火墙和NAT

7.1 引言 NAT通常改变源IP和源端口&#xff0c;不改变目的IP和目的端口。 7.2 防火墙 常用防火墙&#xff1a; 包过滤防火墙&#xff08;packet-filter firewall&#xff09; 代理防火墙&#xff08;proxy firewall&#xff09; 代理防火墙作用&#xff1a; 1. 通过代理服务…

Spring全面精简总结

Spring两大核心功能&#xff1a;IOC控制反转、AOP面向切面的编程 控制反转(loC&#xff0c;Inversion of Control)&#xff0c;是一个概念&#xff0c;是一种思想。指将传统上由程序代码直接操控的对象调用权交给容器&#xff0c;通过容器来实现对象的装配和管理。控制反转就是…

雾锁王国Enshrouded服务器几核几G够用?

雾锁王国/Enshrouded服务器CPU内存配置如何选择&#xff1f;阿里云服务器网aliyunfuwuqi.com建议选择8核32G配置&#xff0c;支持4人玩家畅玩&#xff0c;自带10M公网带宽&#xff0c;1个月90元&#xff0c;3个月271元&#xff0c;幻兽帕鲁服务器申请页面 https://t.aliyun.com…

three中界面交互gui.js库的使用

gui.js库(可视化改变三维场景) dat.gui.js说白了就是一个前端js库&#xff0c;对HTML、CSS和JavaScript进行了封装&#xff0c;学习开发的时候&#xff0c;借助dat.gui.js可以快速创建控制三维场景的UI交互界面&#xff0c;你打开课件中案例源码体验一下就能感受到。 学习dat…

C++笔记(二)--- 继承和组合

目录 C三种继承方式 构造函数 析构 继承 public继承 protected继承 private继承 组合 访问权限 构造/析构函数调用顺序 初始化 总结 C三种继承方式 C有三种继承方式&#xff1a;public protected private 属性方式为 class [派生类名称] : [继承方式] [继…

嵌入式驱动学习第一周——git的使用

前言 本文主要介绍git的使用&#xff0c;包括介绍git&#xff0c;gitee&#xff0c;以及使用gitee创建仓库并托管代码 嵌入式驱动学习专栏将详细记录博主学习驱动的详细过程&#xff0c;未来预计四个月将高强度更新本专栏&#xff0c;喜欢的可以关注本博主并订阅本专栏&#xf…