- 博客(309)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 算法系列——寻找数组中心下标
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。给你一个整数数组 nums ，请计算数组的 中心下标。
2024-02-28 16:24:28
102
1
原创 判断子序列
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。题目：给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
2024-02-28 15:27:33
120
原创 算法系列——缺失的第一个正整数
题目你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。思路哈希法hash 计数：需要额外的空间。所有出现的数字，hash 值 + 1。第二次从 1 开始查找 hash 表，找不到就是它了。但是这种方案不符合题意，而且 hash 计数这个方案效率也不是最优的。置换法(待补充)代码class Solution { public int firstMissingPositive(int[] n
2022-05-19 18:58:41
275
1
原创 算法系列——接雨水
题目原题链接：https://leetcode.cn/problems/trapping-rain-water给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。思路暴力解法：不断循环，找到height[1,i-1] height[i+1,height.length-2] 两者之间的较小值复杂度：时间复杂度O(n²) 空间复杂度O(1)双指针解法：准备双指针，分别指向数组首尾元素，代表最初的两个边界；指针往中间遍历，遇到更低柱子就
2022-05-18 15:39:41
362
原创 算法系列——删除链表中的节点
题目题目链接：https://leetcode.cn/problems/delete-node-in-a-linked-list请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。题目数据保证需要删除的节点 不是末尾节点 。思路以通过修改node 的next 指针的指向，删除 node 的下一个节点。但是题目要求删除 node，为了达到删除node 的效果，只要在删除节点之前，将 node 的节点值修改为 no
2022-05-12 00:10:27
657
原创 算法系列——链表的奇偶重排
题目给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。题目链接：https://leetcode-cn.com/problems/odd-even-linked-list/思路双指针法，注意指针的指向。代码class Solution { public ListNode oddEvenList(ListNode head) { if
2022-05-06 01:28:53
744
原创 算法系列——重建二叉树
题目输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。思路前序遍历列表：第一个元素永远是 【根节点 (root)】中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】算法思路：通过【前序遍历列表】确定【根节点 (root)】将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】递归寻找【左分支节点】中的【根节点 (left child)】和 【右分
2022-05-05 22:36:10
161
原创 算法系列——字符串旋转
题目字符串旋转:给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。例如：如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同，返回true。再如：如果A=‘abcd’，B=‘abcd’，A切成‘abcd’和’’（空串），换位后可以得到B，返回true。数据范围：A,B字符串长度满足 n \le 1000n≤1000，保证字符串中
2022-04-17 00:25:38
600
原创 算法系列——合并K个升序链表
题目题目链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表思路分治法 子问题为合并两个升序链表；代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListN
2022-04-10 12:41:21
214
原创 算法系列——k个一组翻转链表
题目链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。思路核心过程就是 反转 [a,b) 之间的链表。然后递归调用此过程。代码实现/** * Definition for singly-linked list. * public class
2022-04-10 11:59:14
153
原创 算法系列——二叉树的右视图
题目给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。思路广度优先遍历 输出每一层的最后一个结点即可。代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(
2022-04-09 02:35:38
784
原创 算法系列——左旋字符串(剑指offer)
题目原题连接:https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。示例 1：输入: s = “abcdefg”, k = 2输出: “cdefgab”示例 2：输入: s = “lrloseumgh”, k = 6输出: “umghlrl
2022-03-28 13:15:27
111
原创 算法系列——寻找旋转排序数组中的最小值(剑指offer)
题目已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。给你一个元素值 互不相同 的数组 nu
2022-03-27 01:07:35
1176
原创 算法系列——合并二叉树(Merge Two Binary Trees)
题目题目链接：https://leetcode-cn.com/problems/merge-two-binary-trees给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。思路应用
2022-03-21 16:50:58
1865
原创 算法系列——二叉树深度
题目题目链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。思路题目很简单，求二叉树的最大深度，那么直接套递归解题三部曲模版：找终止条件。什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。找返回值。应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当
2022-03-21 16:27:58
318
原创 算法系列——实现前缀树
题目题目链接:https://leetcode-cn.com/problems/implement-trie-prefix-treeTrie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实现 Trie 类：Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符
2022-03-21 14:32:38
150
原创 算法系列——割绳子(剑指offer)
题目给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。思路dp[n] 表示 长度为n 的绳子 能剪成出的最大乘积。dp[n]=max(dp[n-i]*dp[i]) n>=4为了方便处理 初始化时dp[1]=1; dp[2]=2
2022-03-15 21:46:36
768
原创 算法系列——栈的压入弹出序列(剑指offer)
题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）解题思路程序实现
2022-03-15 15:56:27
112
原创 算法系列——将有序数组转换为二叉搜索树
题目给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。思路代码...
2022-03-15 15:03:01
828
原创 算法系列——缀点成线
题目给定一个数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。链接：https://leetcode-cn.com/problems/check-if-it-is-a-straight-line思路核心思路是判断斜率。代码class Solution { public boolean checkStraightLine(int[][] coord
2022-03-15 14:35:06
294
原创 面试系列——ListView 和 RecyclerView 简要对比分析
使用上ListView：继承重写BaseAdapter类；自定义ViewHolder与convertView的优化；默认不支持单个View 刷新RecyclerView：继承重写RecyclerView.Adapter与RecyclerView.ViewHolder设置LayoutManager，以及layout的布局效果支持局部刷新和动画缓存二级缓存 ：屏幕内View 屏幕外View四级缓存 ：屏幕内View 屏幕外ViewViewCacheExtension(用户自
2022-03-14 13:09:20
2503
原创 面试系列——内存,CPU,帧率采集原理总结
内存 采集原理统计原理：单个进程内存信息：最终都是读取 proc/[pid]/smaps系统内存信息：最终是读取 proc/meminfo统计方法API 层面通过 Debug.getMeminfo 或者 ActivityManager.getProcessMemoryInfo工具命令 adb dumsys meminfo [pid]CPU 采集原理统计原理：jJiffies： 为Linux核心变数(unsigned long)，它被用来记录系统自开机以来，已经过了多
2022-03-11 17:54:45
3745
原创 面试系列——App稳定性问题分析总结
稳定性问题 集中在 应用Crash 和 ANR ，分别作为简要记录。ANR问题概念ANR(Application Not responding)，是指应用程序未响应，Android系统对于一些事件需要在一定的时间范围内完成，如果超过预定时间能未能得到有效响应或者响应时间过长，都会造成ANR。一般地，这时往往会弹出一个提示框，告知用户当前xxx未响应，用户可选择继续等待或者Force CloseANR场景Service Timeout:比如前台服务在20s内未执行完成；(前台会弹框)Broadc
2022-03-10 17:42:48
4273
原创 面试系列——爱奇艺Andromeda 跨进程通信组件分析
优势不需要手动绑定service获取远程服务是同步的自动保持服务进程优先级跨进程事件总线支持支持IPC的Callback不足默认只支持 同App 内的不同进程之间进行通信，无法支持 跨App进行通信；无法在代码层面指定通信进程，只能在gradle脚本中配置 ,不够灵活；整体架构图1. 如何做到不需要手动绑定service ？每个进程初始化时，互换BinderClient 端 到 中间层 通过 Intent 传递Binder //让ServiceDispatcher注册到当
2022-03-08 17:36:36
1046
原创 面试系列——App启动性能优化总结
需求背景衡量启动时间线上统计 attachBaseContext 首页的 onWindowsFocusChanged 方法 上报打点线下adb 脚本 自动化 统计adb shell am start -S -W [intent]找到耗时方法分析耗时 线下method trace 按照耗时进行排序， 问题在于 method trace 拖慢程序运行，JVM 需要增加 额外的开销，获得的时间不是真正执行的时间，只能获得一个相对耗时排行；优化启动耗时分析启动耗时 推动 三方SDK 优化，
2022-03-03 16:39:15
185
原创 面试系列——播报SDK开发和总结概述
播报能力SDK基本能力概述支持TTS 引擎和 MediaPlayer 系统自定义多个引擎切换；支持按照优先级调度，支持打断 ，播报音量定义等；支持组合播报 各种类型内容播报;项目思考和总结设计上 各种设计模式的引入 保证工程结构可扩展；后期维护上，通过埋点上报 ，监控播报热点失败case，比如说 音频模板上线存在问题，存在非标准音频文件；推动语音引擎团队优化TTS 控制逻辑，比如在一些场景下 出现语音模型加载异常，则通过重试逻辑或者降级手段保证播报可用性;一些热点设备，存在资源调度紧
2022-03-02 18:51:42
179
原创 设计模式——总结
创建型概念这些设计模式提供了一种在创建对象的同时隐藏创建逻辑的方式，而不是使用 new 运算符直接实例化对象。这使得程序在判断针对某个给定实例需要创建哪些对象时更加灵活。分类抽象工厂模式构造者模式工厂方式模式原型模式单例模式结构型概念这些设计模式关注类和对象的组合。继承的概念被用来组合接口和定义组合对象获得新功能的方式。分类适配器模式桥接模式组合模式装饰器模式外观模式享元模式代理模式行为型概念这些设计模式特别关注对象之间的通信。分类责任链模式命令模
2022-03-02 11:57:21
114
原创 面试系列——工作技能和思考
如何接手公司商业项目拿到代码如果业务逻辑简单，则直接看代码，如果业务逻辑复杂，则可请教相关团队老人；此阶段注意请教老人要拉下面子 有些老人比较忙/ 态度不好等， 为了快速熟悉业务 要不耻下问，注意方式方法；多加日志通过断点调试等方法 可以快速熟悉新项目;如何看开源项目从使用入口处分析，看类的英文原始注释，一定要多看官方文档；打断点理顺调用流程；分析可以学习到的代码技巧和知识；如何推进项目落地遇到解决不了的问题不要自己消化，向上透传寻求帮助，否则问题将会被阻塞在个人手里；事情如果
2022-03-01 12:04:27
124
原创 面试系列——OkHttp使用和原理分析
OkHttp 框架分析基于OkHttp 3.4.0.支持的协议HTTP 1.1 HTTP2 SPDY_3重要类OkHttpClient构造Call 请求 ， 用来发送Http请求 和 读取返回内容。Request 和 Responserequest 代表一个请求，不可变response 代表一个响应 可变Call 和 RealCall负责请求的调度（同步的话走当前线程发送请求，异步的话则使用OkHttp内部的线程池进行）；同时负责构造内部逻辑责任链，并执行责任链相关的逻辑，直到获
2022-02-28 16:50:43
565
原创 面试系列——Retrofit 框架分析使用总结
Retrofit 框架分析介绍利用各种精巧的设计模式 ，以一种优雅的方式构造网络请求，内部还是利用OkHttp发送网络请求,而不是重写了一个套网络框架。请求过程定义获取Retrofit 实例 ，创建网络接口实例，发送网络请求，获取返回结果。各种设计模式构造者模式Retrofit 实例创建利用Builder模式，简化构建方法。外观模式对外只提供Retrofit 实例 避免对系统的直接访问。代理模式网络接口到实现类的利用到动态代理，简化调用。适配器模式CallAdapter adap
2022-02-18 18:40:39
343
原创 面试系列——录制模块架构设计和思考
背景无法快速支持多路摄像头，增加一路摄像头改造成本高、风险高各种配置融合交叉，配置混乱录制基本功能模块和业务逻辑融合，生命周期维护困难解决方法定义不同摄像头模块 ID，去除前后摄 Boolean值判断梳理各个模块配置开关;录制模块拆分：基础功能：摄像头打开、录制打开、录制关闭、摄像头关闭、YUV 开启与关闭；业务逻辑：视频锁定、埋点上报、日志打印、重试、异常监控等摄像头生命周期梳理...
2022-01-21 15:46:34
355
原创 Android 系统启动过程简析
Android手机开机执行过程图：这里写图片描述 从开机到桌面的过程为：Bootloader ➪Kernel ➪Init进程 ➪ Zygote ➪ SystemServer ➪ ServiceManager ➪ Home Launcher Android服务包括系统服务和应用服务，系统服务是指Android系统在启动过程就已经启动实现了的服务，对于系统服务又分为Java服务
2022-01-13 15:56:02
291
原创 面试系列——直播间消息组件优化
IM 消息组件优化早期业务扩展快，短平快无法 代码耦合度高，自研IM组件 和国外版本的开发 导致切换成本过高 需要重构；直播间 人数较多时，用户反馈 较为明显的卡顿和不问题，一些中低端机明显；定位问题，CPU Profile 发现存在的明显的内存抖动 线下压测不够充分；IM 消息体 属于大对象，持有用户对象实体和各种附加信息，而且不能简单做精简，然后在高频场景下内存需要频繁申请内存；针对此条件做对象池缓存，对象复用，用完立即回收，解决内存抖动问题；线下制作做压测工具开发帧率监控模块自
2022-01-12 12:09:15
322
原创 面试系列——虚拟偶像VR SDK开发和优化总结
项目背景利用摄像头捕捉 人脸动作 驱动本地模型展示二次元偶像形象；利用模型资源文件渲染 用户可以自定义用于展示个人形象；利用 U3D 游戏开发技术，与引擎团队 深度配合，共建客户端虚拟偶像功能；架构设计1. 下载模块根据用户配置 模型 json 下载，按需下载，根据用户开关 决定 是否全量下载；制作编辑页面 模型文件按照用户需求 点击 时下载；2. 渲染模块虚拟偶像 渲染层TextureView View 层 自动侦听 依附的Activity 生命周期 ；做释放操作3. 及时
2022-01-11 18:25:19
692
原创 面试系列——直播模块设计总结和思考
背景支持IOT平台的直播功能，要求低功耗高性能高可用。组件架构设计架构设计接入方： 统一接入标准 函数实现首帧为sps pps 数据，推送数据帧的方法 方便接入和后续扩展；对外：外观模式 对外提供统一接口 业务层访问统一接口不需要跟具体模块交互内部：策略模式 内部提供不同实现，发起时候 动态指定实现类，方便线上做AB test. 或者后期做动态切换。性能优化内存优化1）系统优化 内存Buffer 复用，避免内存频繁分配；2）采用SparseArray 保存 映射3)
2022-01-11 11:35:44
437
原创 算法系列——找出数组的最大公约数
题目如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。输入 a 和 b , 请返回 a 和 b 的最大公约数。进阶：空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)解答辗转相除法。public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
2021-12-30 11:39:45
971
原创 算法系列——判断是否为回文字符串
题目给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:输入: “A man, a plan, a canal: Panama”输出: true解释：“amanaplanacanalpanama” 是回文串示例 2:输入: “race a car”输出: false解释：“raceacar” 不是回文串解答双指针对称遍历， 注意大小写转化 和 删除掉空格字符。class Solution {
2021-12-30 11:16:53
3129
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人