热题HOT 100（61-70）
61.请判断一个链表是否为回文链表。
输入: 1->2->2->1
输出: true
简单想法，找到中点，翻转后面的链表，对比两边是否一样！
比如[1, 2, 2, 1]找到第二个2，然后翻转后面的链表
即[1, 2],[1, 2]按位比较即可！
对于找中点位置，细节在代码中~
时间复杂度：O(n)
public boolean isPalindrome(ListNode head) {
if (head==null||head.next==null){
return true;
}
//中
ListNode slow = head;
ListNode fast = head.next;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
//翻转
ListNode pre = slow;
ListNode cur = slow.next;
int count=0;
while (cur!=null){
count++;
ListNode temp = cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
//对比
while (count>0){
if(pre.val!=head.val)
return false;
pre=pre.next;
head=head.next;
count--;
}
return true;
}
62.给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
注意
p,q必然存在树内, 且所有节点的值唯一!!!
递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q直接返回root
表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:
1. 左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
2. 如果左右子树返回值只有一个不为null, 说明只有p和q俩个都存在与左或右子树中, 最先找到的那个节点（也就是返回的这个不为空的节点）为LCA
3. 左右子树返回值均为null,p和q均不在树中, 返回null
public class Solution {//所有的递归的返回值有4种可能性，null、p、q、公共祖先
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {//当遍历到叶结点后就会返回null
return root;
}
if (root == p || root == q) {//当找到p或者q的是时候就会返回p或q
return root;
}
TreeNode left = LowestCommonAncestor(root.left, p, q);//返回的结点进行保存，可能是null
TreeNode right = LowestCommonAncestor(root.right, p, q);//也可能是p或者q，还可能是公共祖先
if (left != null && right != null) {
return root;//如果左右都存在，就说明p和q都出现了，此刻的root就是公共祖先
} else if (left != null) {//由下面返回的公共祖先，并将这个值一路返回到(这层)最表层
return left;
} else if (right != null) {
return right;
}
return null;
}
}
63.给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
输入: [1,2,3,4]
输出: [24,12,8,6]
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
if(len==2)
return new int[]{nums[1],nums[0]};
int[] dp1 = new int[len];
int[] dp2 = new int[len];
dp1[0]=nums[0];
dp2[len-1]=nums[len-1];
for(int i=1;i<len;i++){
dp1[i]=dp1[i-1]*nums[i];
}
for(int i=len-2;i>=0;i--){
dp2[i]=dp2[i+1]*nums[i];
}
int[] res = new int[len];
res[0]=dp2[1];
res[len-1]=dp1[len-2];
for(int i=1;i<len-1;i++){
res[i]=dp1[i-1]*dp2[i+1];
}
return res;
}
64.给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
思路： 遍历数组,
LR为滑窗左右边界 只增不减
双向队列保存当前窗口中最大的值的数组下标 双向队列中的数从大到小排序，
新进来的数如果大于等于队列中的一些数。 则将这些数弹出 再添加
当R-L+1=k时 滑窗大小确定 每次R前进一步L也前进一步 保证此时滑窗中最大值的数组下标在[L，R]中，并将当前最大值记录
举例： nums[1，3，-1，-3，5，3，6，7] k=3
1：L=0，R=0，队列【0】 R-L+1 < k
队列代表值【1】
2: L=0,R=1, 队列【1】 R-L+1 < k
队列代表值【3】
解释：当前数为3 队列中的数为【1】 要保证队列中的数从大到小 弹出1 加入3 ，不加入1
但队列中保存的是值是对应的数组下标 所以队列为【1,2】 窗口长度为2小于3 不添加最大值记录
3: L=0,R=2, 队列【1，2】 R-L+1 = k ,result={3}
队列代表值【3，-1】分别是nums[1]和nums[2]，因为前面弹出1了
解释：当前数为-1 队列中的数为【3】 比队列尾值小 直接加入 队列为【3，-1】
窗口长度为3 添加记录 记录为队首元素对应的值 result[0]=3
4: L=1,R=3, 队列【1，2，3】 R-L+1 = k ,result={3，3}
队列代表值【3，-1,-3】
解释：当前数为-3 队列中的数为【3，-1】 比队列尾值小 直接加入 队列为【3，-1，-3】
窗口长度为4 要保证窗口大小为3 L++ 此时队首元素下标为1 没有失效
添加记录记录为队首元素对应的值 result[1]=3
5: L=2,R=4, 队列【4】 R-L+1 = k ,result={3，3，5}
队列代表值【5】
解释：当前数为5 队列中的数为【3，-1，-3】 保证从大到小 依次弹出添加 队列为【5】
窗口长度为4 要保证窗口大小为3 L++ 此时队首元素下标为4 没有失效
添加记录记录为队首元素对应的值 result[2]=5
依次类推 如果队首元素（它是代表最大值的坐标）小于L说明此时值失效 需要弹出
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if(len<=1){
return nums;
}
LinkedList<Integer> queue = new LinkedList<>();
int[] res = new int[len-k+1];
queue.add(0);
int L=0;
for(int i=1;i<len;i++){
//peekLast()检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null 。
while (!queue.isEmpty()&&nums[i]>nums[queue.peekLast()]){
//pollLast()检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。
queue.pollLast();
}
queue.add(i);
while(i-L+1>=k){
if(queue.peekFirst()>=L){
res[L]=nums[queue.peekFirst()];
L++;
}else{
queue.pollFirst();
}
}
}
return res;
}
65.编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
现有矩阵 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
因为矩阵的行和列是排序的（分别从左到右和从上到下），所以在查看任何特定值时，我们可以修剪
O(m)或O(n)元素。
思路：
首先，我们初始化一个指向矩阵左下角的(row，col)指针。然后，直到找到目标并返回true（或者指针指向矩阵维度之外的(row，col)为止
我们执行以下操作：
如果当前指向的值大于目标值，则可以向上移动一行。
否则，如果当前指向的值小于目标值，则可以移动一列。
不难理解为什么这样做永远不会删减正确的答案；因为行是从左到右排序的，所以我们知道当前值右侧的每个值都较大。 因此，如果当前值已经大于目标值，我们知道它右边的每个值会比较大。也可以对列进行非常类似的论证，因此这种搜索方式将始终在矩阵中找到目标（如果存在）。
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length;
if(m==0){
return false;
}
int n=matrix[0].length;
int i=m-1,j=0;
while(i>=0&&j<n){
if(matrix[i][j]==target){
return true;
}else if(matrix[i][j]>target){
i--;
}else if(matrix[i][j]<target){
j++;
}
}
return false;
}
66.给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
标签：动态规划
首先初始化长度为n+1的数组dp，每个位置都为0
如果n为0，则结果为0
对数组进行遍历，下标为i，每次都将当前数字先更新为最大的结果，即dp[i]=i，比如i=4，最坏结果为4=1+1+1+1即为4个数字
动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i表示当前数字，j*j表示平方数
时间复杂度：O(n*sqrt(n))，sqrt为平方根
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int i=0;i<=n;i++){
dp[i]=i;
}
for(int i=2;i<=n;i++){
for(int j=2;j*j<=i;j++){
dp[i]=Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
67.给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
从左到右遍历，非0数字一次按位排在前面，剩下的全部设为0
public void moveZeroes(int[] nums) {
int len = nums.length;
int i=0,j=0;
while(i<len){
if(nums[i]==0){
i++;
}else{
nums[j]=nums[i];
j++;
i++;
}
}
while (j<len){
nums[j]=0;
j++;
}
}
68.给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n∧2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。
输入: [3,1,3,4,2]
输出: 3
快慢指针思想
本题可以使用数组配合下标，抽象成链表问题。但是难点是要定位环的入口位置。
理解为：
当前数组的值是当前节点的下一个节点的下标
fast和slow是指针,nums[slow]表示取指针对应的元素,nums[nums[slow]]取快指针对应的元素。
举个例子：nums = [2,5, 9 ,6,9,3,8, 9 ,7,1]，构造成链表就是：2->[9]->1->5->3->6->8->7->[9]，也就是在[9]处循环。
注意 nums 数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界),
因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素,
即按照寻找链表环入口的思路来做
public int findDuplicate(int[] nums) {
int slow=0,fast=0;
while(true){
slow = nums[slow];
fast = nums[nums[fast]];
if(slow==fast){//相遇了，但是不是在入环口 根据定律：入环口到相遇点的距离（，即慢指针还需要走的路程到入环点->包含转圈圈的）等于起点到入环口的的距离
fast = 0;
while(nums[fast]!=nums[slow]){
slow=nums[slow];
fast=nums[fast];
}
return nums[slow];
}
}
}
69.给定一个无序的整数数组，找到其中最长上升子序列的长度。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该小于等于 O(n∧2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
动态规划的思路：将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
那么题目要求的，就是这个 dp 数组中的最大者
以数组 [10, 9, 2, 5, 3, 7, 101, 18] 为例：
dp 的值： 1 1 1 2 2 3 4 4
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int[] dp = new int[len];
// 自己一定是一个子序列
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
// 看以前的，比它小的，说明可以接在后面形成一个更长的子序列
// int curMax = Integer.MIN_VALUE; 不能这样写，万一前面没有比自己小的，
// 这个值就得不到更新
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
int res = dp[0];
for (int i = 0; i < len; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
一个O(NlogN)的解法
input: [0, 8, 4, 12, 2]
dp: [0]
dp: [0, 8]
dp: [0, 4]
dp: [0, 4, 12]
public int lengthOfLIS(int[] nums) {
/**
dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数.
由定义知dp数组必然是一个递增数组, 因此可以使用二分搜索,可以用 maxL 来表示最长递增子序列的长度.
对dp数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:
1. num > dp[maxL], 表示num比所有已知递增序列的尾数都大, 将num添加入dp
数组尾部, 并将最长递增序列长度maxL加1
2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]
**/
int maxL = 0;
int[] dp = new int[nums.length];
for(int num : nums) {
// 二分法查找, 也可以调用库函数如binary_search
int lo = 0, hi = maxL;
while(lo < hi) {
int mid = lo+(hi-lo)/2;
if(dp[mid] < num)
lo = mid+1;
else
hi = mid;
}
dp[lo] = num;
if(lo == maxL)
maxL++;
}
return maxL;
}
70.删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。
输入: "()())()"
输出: ["()()()", "(())()"]
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]
输入: ")("
输出: [""]
我们需要记录左边和右边括号个数。
这意味着，如果我们从左到右查看每个括号，一旦遇到右括号，就应该有一个左括号来匹配它。否则表达式将变为无效。如果左括号的数目大于右括号的数目则表达式也无效。
在此题中，解题步骤如下：
我们需要先找出不合法的左括号个数和右括号个数
利用dfs不断删除"（"或者"）"，直到不合法个数为0
检验删除后的括号串是否合法。
public List<String> removeInvalidParentheses(String s){
List<String> result = new ArrayList<>();
if(s.equals("")||s.equals("()")){//特判
result.add(s);
return result;
}
Queue<String> queue = new LinkedList<>();
Set<String> set =new HashSet<>();//用于存储裁剪后的元素，防止重复元素加入队列
boolean isok = false;////判断是否用最少的删除找到了有效字符串
queue.add(s);
while (!queue.isEmpty()){
String cur = queue.poll();
if(isvalue(cur)){
result.add(cur);
isok=true;
}
//因为是找到删除数量最小的，后面的满足要求了就不需要再裁剪更多的括号了。
if(isok==true){
continue;
}
//裁剪过程
for (int i=0,j=cur.length();i<j;i++){
if(cur.charAt(i)=='('||cur.charAt(i)==')'){
String tempstr;
if(i==j-1){
//beginIndex -- 起始索引（包括）, 索引从 0 开始。endIndex -- 结束索引（不包括）。
tempstr = cur.substring(0,i);
}else{
tempstr = cur.substring(0,i)+cur.substring(i+1);
}
if(set.add(tempstr)){
queue.add(tempstr);
}
}
}
}
if(result.isEmpty()){
result.add("");
}
return result;
}
//是否是满足括号的有效字符串
public boolean isvalue(String s){
int left=0,right=0;
for(int i=0,j=s.length();i<j;i++){
if(s.charAt(i)=='('){
left++;
}else if(s.charAt(i)==')'){
if(left>0){
left--;
}else{
return false;
}
}
}
if(left==0)
return true;
else
return false;
}
