剑指 Offer 05. 替换空格
字符串替换
//
题目链接-来源：力扣（LeetCode）
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1：
输入：s = “We are happy.”输出：”We%20are%20happy.”
思路：字符串替换，可以用 StringBuilder 类轻松实现。对空格所在的指针 i 进行删除与插入操作即可。时间复杂度：O(n)空间复杂度：O(n)
实现：12345678910111213class Solution { public String replaceSpace(String s) { StringBuilder sb = new StringBuilder(s); for (int i = 0; i < sb.length(); i++) { if (sb.charAt(i) == ' ') { sb.deleteCharAt(i); sb.inser ...
剑指 Offer 04. 二维数组中的查找
有序矩阵查询
//
题目链接-来源：力扣（LeetCode）
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路：观察后可发现，对于某个矩阵元素，可以确定大小关系的是下侧（大于）和左侧（小于）。那么从右上角出发，与 target 相比较，target 较大则下移，反之左移，到达边界后如还未找到，即可返回 false。时间复杂度：O(m + n) m n为矩阵长度和宽度空间复杂度：O(1)
实现：123456789101112131415161718class So ...
剑指 Offer 03. 数组中重复的数字
先刷完剑指，再刷力扣主站。
//
题目链接-来源：力扣（LeetCode）
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3
思路：越简单的题越要警惕执行效率。找出重复数字，需要O(1)复杂度的方案，容易想到用哈希表存储访问过的元素，之后碰见表中相同元素返回即可。时间复杂度：O(1)空间复杂度：O(N)
实现：123456789101112class Solution { public int findRepeatNumber(int[] nums) { Set<Integer> s = new HashSet<>(); for (int item : nums) { if (s.contains(item)) { ...