思路： 思路1：暴力法，找到当前点左右两个最高点left、right，然后用二者较小值减去当前值，就是当前柱子最多存储的雨水 思路1优化，两次遍历数组，先通过一次遍历找到每个点的左右最高点，然后再次遍历，计算当前对应柱子可以存储的雨水，降低了时间复杂度 思路1的优化2，无需两次遍历，因为发现左右端点高度中总有一个没有用到，若左端点小于右端点，则当前点的蓄水高度以左端点为准，反之同理 思路2，其实无需找到该节点的左右两个最大端点，若当前点高于前一个点，其实前一个点的蓄水量已经可以计算，就是当前点和前一个节点的再前一个节点中的较小值减去前一个节点的高度，再乘对应的宽度所以可以用非递...

思路： 分析该问题可以发现问题的解即最长公共子串具有一个特点，那就是若子串a1a2a3a4a5，是最长公共子串，则a去掉最后一个字符a5应该是以a4结尾的最长子串，也就是说最终问题的解包含子问题的解，具有最优子结构，所以可以用动态规划法解决。用cnt[i][j]代表以str1的第i个，str2的第j个结尾的最长公共子串的长度（从1开始计数）。之后寻找当前结果与前一个结果的关系，若当前字符相等，则cnt[i][j]=cnt[i-1][j-1]+1；否则cnt[i][j]=0。边界条件是若选择0个，则公共子串的长度为0。 实现上述思路后进行空间优化，因为以当前字符结束的最长公共子串和原二维数组的左...

思路： 先动态规划求出最长公共子序列的长度，然后逆向找到相同字符。 详细解释 代码： import java.util.*; public class Solution { /** * longest common subsequence * @param s1 string字符串 the string * @param s2 string字符串 the string * @return string字符串 */ public String LCS (String s1, String s2) { // wr...

两种思路解决，首先大思路肯定是递归法，因为要得到所有合法的排列组合。 思路： 经典的递归实现加剪枝，用map存储当前剩余的左右括号数，然后递归过程中添加括号，并事实更新当前组合的括号情况，用cnt来代表，左括号就为cnt+1，右括号cnt-1，cnt为0说明当前是合法组合，递归终止的条件是字符串长度等于2*n，接着判断若cnt为0就加入结果集中。可以加入剪枝若cnt已经小于0，说明当前字符串必然不是合法组合（因为左括号数小于右括号），此时其实可以去掉递归判断的cnt==0加入结果集条件。 不用map存储括号数，直接用两个参数传递此时剩余的括号，节约空间，同时由于不用遍历map集合，效率要高于...

import java.util.*; public class Solution { /** * * @param n int整型 the n * @return int整型 */ int count; Set<Integer> column = new HashSet<Integer>(); //标记列不可用 Set<Integer> posSlant = new HashSet<Integer>();//标记正斜线不可用 Set<Integer&gt...

思路： 这题是两数之和为某个值的改版，首先要理解两数之和为target的解法，然后在此基础上这题就好理解了。 思路1：因为题目要求不能重复，所以可以先对数组排序，然后三指针法暴力遍历数组解决，时间复杂度为O(nlog2n)+O(n3)=O(n3)。但思考上面的过程发现排序只是用来去除相同的解，没能利用到升序的特性，所以优化可得到思路2. 思路2：可以想到先遍历数组，同时找基准值，然后每个基准值就相当于target，利用双指针法，一个指向基准值的后一个元素，一个指向数组尾端，二者之和为sum，若sum>target，右指针左移(说明此时和太大，需要减小sum，就需要一个更小的数)，若小于，...

思路： 可以在快排的基础上解决，快排其实就是将某个数放到它在数组中的正确位置上，左边都小于它，右边都大于它，本题中无需使整个数组有序，只要找到排序后位置在k+1的数字即可，此时由左到该数字刚好是最小的k个数字。 用长度为k的大顶堆解决，堆顶存放最大值，若当前数字小于堆顶元素，则替换堆顶元素，由于大顶堆的排序规则，堆中的最大值总会被放到堆顶，所以最后堆中存放的就是最小的k个数。 代码： import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solutio...

思路： 思路1：首先想到的是暴力法，对每个窗口进行遍历，找到其最大值，在此基础上进行优化，并不会每次都遍历窗口，只有在左边界等于最大值时才重新遍历窗口，即代码1。 思路2：在利用指针遍历窗口时，发现指针遍历有3中可能。 若遍历位置i的值大于i-1的值，则i-1位置的值便无存在的意义，因为若i-1还在窗口，则最大值已经不可能是i-1位置的值，若i-1不在窗口（因为位置i-1总是比位置i先出窗口），则位置i-1同样不可能是窗口中的最大值 但若位置i的值小于i-1，则位置i的值应该保留，这样位置i-1出窗口后最大值可能是位置i的值，不会丢失下一个窗口的最大值； 若位置i的值等于位置i-1的值，则保...

二分法，时间击败98% 思路： 由于题目所给数组是非递减数组经过一定变化得到的，可以将其看为两部分，每部分都满足非递减的特点，所以也可以使用二分法实现，常用的二分查找是比较array[mid]和target的大小关系进而移动左右边界，此题中没有target，但由于要找最小值，由数组特点可知最小值是两个非递减数组的分界线，所以可以通过比较array[mid]和端点值判断最小值在左半部分还是右半部分，我比较的是右端点，若array[mid]>右端点，说明mid~右端点是非递减数组，最小值必然在左半部分，移动右边界；若小于说明分界线在右半部分，对应最小值必然在右半部分，移动左边界。 特殊情况：...

思路： hashMap解决 数组长度为n，所以最小的未出现正整数必然在[1~n]之间，尝试将数字x放入对应x-1的索引处，即可利用现有数组实现等效哈希表，映射规则即是索引x对应数字x+1，最后再次遍历数组，若索引x对应的数字不是x+1，说明该处的数字未出现。 代码： import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 ...

思路：双指针法，一个指向当前节点，一个指向下一个不等于当前节点的节点。时间击败100% 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @return ListNode类 */ public ListNode deleteDuplicates (ListNode ...

两个思路： 1，利用一个公共变量然后递归回溯实现，公共变量pre从前向后遍历链表，递归到列表尾部后开始回溯，从后往前遍历链表，将pre和回溯到的节点比较。 注意的点： 返回boolean的值 输入参数，当前节点head 递归终止条件：head==null，此时返回true，因为递归中若前一个比较不相等，后面没有比较的必要，所以比较放在if语句中 2，反转后半部分链表，比较，反转利用快慢指针法找到中间节点，这一部分建议自己画个链表试一下，分为单数和双数的情况，你就能明白我的slow和fast的初始化了。 代码： import java.util.*; /* * public class ...

时间超过97%，内存超过95%。 思路：遍历链表用ArrayList数组保存链表的数，然后对数组排序，选择快速排序实现，排序后再次遍历数组生成结果链表。 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 the head node * @return ListNode类 */ ...