梦会绽放

题解

/ 注册

全部文章 / 题解（共16篇）

Java实现#寻找峰值#

从此题中得到的小感悟：充分把握题意方能选用更合适的解题方法（类二分法）此题难度中等，很容易想到思路1，但是仅此的话，不符合“中等”的标签；另外，题中要求时间复杂度为 O(log n)，这让我们很自然地联想到二分法，我们所熟悉的二分法是基于有序表，这道题目数组并不一定有序，那又如何和二分法产生关...

Java 数组二分查找

2022-02-10

3 602

Java实现字符串变形

思路：不使用语言中的 API，而是自己编写对应的函数。将字母大小写转换后，反转整个字符串，再反转每个单词。注意JAVA的字符串不可变，对于字符串不可变的语言，首先得把字符串转化成其他可变的数据结构.。注意下标不要越界。复杂度：时间复杂度 O(n) ,需要 O(n) 的空间来存储字符串...

Java 字符串

2022-02-09

3 1042

题解 | Java版快排《单链表的排序》

思路：快速排序。要求时间复杂度为 O(nlogn)，对我们选取的排序算法做出了限制，我们知道时间复杂度为 O(nlogn)的算法有快排、堆排序、归并排序。这里考虑使用快排。复杂度平均时间复杂度O(nlog n),空间发复杂度O(n) 图示代码（JAVA实现） public class ...

Java 递归链表快排

2022-01-31

14 896

题解 | #<比较详细了吧>求平方根#

思路1：二分法。初始low=1, high的初始化有讲究：若x大于4，high初始化为x/2; 若x<=4，high初始化为x. 至少这样可加速查找过程。（证明很简单，见下图）若mid*mid <= x,接着判断 (1)若(mid+1)^2>x,则返回mid; ...

Java 数学二分查找二分法迭代

2022-01-30

2 596

题解 | #<图示详解>在旋转过的有序数组中寻找目标值#

思路：二分法我们知道二分法适用于有序数组，并且题中告诉我们数组严格升序，只是经过了旋转，经过一番思考，我们可以充分利用好以上性质，写出让面试官想要的代码。旋转后的数组分为两部分，[low...mid]和[mid...high]，这两部分必有一个是有序数组，我们考虑每次都处理有序的那部分，...

Java 分治数组二分查找

2022-01-29

1 498

题解 | #排序(快排）#

思路：快排。复杂度：平均时间复杂度O(nlog n),最坏时间复杂度O(n^2),空间复杂度O(n) 代码（JAVA实现） public class Solution { public int[] MySort (int[] arr) { if(arr==null||arr.le...

Java 数组递归排序快排

2022-01-29

0 342

题解 | #(JAVA实现)大数加法#

思路：模拟。注意到题中len(s),len(t)≤100000，若先转换为int，会超出整型范围。考虑模拟手算过程。复杂度：时间复杂度O(n), 空间复杂度O(n) 代码（JAVA实现） public class Solution { public String solve (String...

Java 字符串模拟

2022-01-28

0 387

题解 | #(JAVA实现) 连续子数组的最大和(二)#

思路：滑动窗口。空间复杂度 O(1)（不包含用于结果返回的数组），遍历一遍数组，时间复杂度 O(n) 代码（Java实现） public class Solution { public int[] FindGreatestSumOfSubArray (int[] array) { ...

Java 滑动窗口数组双指针

2022-01-27

3 681

题解 | #《剑指offer》把字符串转换成整数(atoi)#

思路：模拟，注意对题目转换算法的理解即可，理清各种情况空间复杂度 O(1)，时间复杂度 O(n) 代码（JAVA实现） public class Solution { public int StrToInt (String s) { int len=s.length();//给定的字...

Java 字符串模拟

2022-01-26

8 1284

题解 | #剑指offer JZ74 和为S的连续正数序列#

* 思路1：穷举。题目中的连续正数序列即为公差为1的等差递增数列，在此对应的求和公式为：Sn=(a1+an)(an-a1+1)/2；由于序列要求至少包括两个数，序列内按照从小至大的顺序；我采取的策略是每次遍历的时候固定a1（首项），寻找符合条件的an（尾项）；注意观察到符合条件的最后一组序...

Java 滑动窗口

2022-01-25

1 533