-
二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
-
暴力解法：遍历整个二维数组的所有元素进行比较。
时间复杂度O(nm)，空间复杂度O(1)
-
从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。
时间复杂度:O(n + m)，空间复杂度:O(1)
-
-
删除排序数组中的重复项
题目：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
思路：
-
双指针。首先注意数组是有序的，那么重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。考虑用 2 个指针，一个在前记作 p，一个在后记作 q，
算法流程如下：比较 p 和 q 位置的元素是否相等。如果相等，q 后移 1 位如果不相等，将 q 位置的元素复制到 p+1 位置上，p 后移一位，q 后移 1 位重复上述过程，直到 q 等于数组长度。返回 p + 1，即为新数组长度。
时间复杂度：O(n)。空间复杂度：O(1)。
优化：此时数组中没有重复元素，按照上面的方法，每次比较时 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。因此我们可以添加一个小判断，当 q - p > 1 时，才进行复制。
-
-
旋转数组
题目：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。要求使用空间复杂度为 O(1) 的原地算法。
输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4]思路：
-
暴力解法：旋转k次，每次将数组旋转1个元素。
时间复杂度：O(n*k) 。每个元素都被移动 1 步（O(n)） k次（O(k)） 。空间复杂度：O(1) 。没有额外空间被使用。
-
使用额外数组：使用一个新的数组，将元素拷贝到正确的位置。
时间复杂度： O(n) 。空间复杂度： O(n)。
-
使用反转：这个方法基于这个事实：当我们旋转数组 k 次， k%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。
在这个方法中，我们首先将所有元素反转。然后反转前 k 个元素，再反转后面 n-kn−k 个元素，就能得到想要的结果。
假设 n=7 且k=3 。
原始数组 : 1 2 3 4 5 6 7 反转所有数字后 : 7 6 5 4 3 2 1 反转前 k 个数字后 : 5 6 7 4 3 2 1 反转后 n-k 个数字后 : 5 6 7 1 2 3 4 --> 结果时间复杂度：O*(*n) 。 n个元素被反转了总共 3 次。空间复杂度：O(1) 。 没有使用额外的空间。
-
使用环状替换
-
-
存在重复元素
题目：给定一个整数数组，判断是否存在重复元素。如果任意一值在数组中出现至少两次，函数返回
true。如果数组中每个元素都不相同，则返回false。思路：
-
暴力线性查找：挨个查找比较
时间复杂度 : O(n^2)。最坏的情况下，需要检查
(n(n+1)) / 2次。空间复杂度 : O(1)。只使用了常数额外空间。 -
排序：堆排序（堆是完全二叉树），可以在最坏情况下具有 O(nlogn) 的时间复杂度，然后再扫描已排序的数组查找重复元素。
时间复杂度 : 排序的复杂度是 O(nlogn)，扫描的复杂度是 O(n)。整个算法主要由排序过程决定，因此是O(nlogn)。
空间复杂度 : O(1)。这取决于具体的排序算法实现，通常而言，使用
堆排序的话，是 O(1)。
-
-
只出现一次的数字
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
思路：
-
暴力线性查找：挨个比较有没有相等的，如果遇到相等，继续查找下一个元素。
时间复杂度 : O(n^2)。最坏的情况下，需要检查
(n(n+1)) / 2次。空间复杂度 : O(1)。只使用了常数额外空间。 -
哈希表：遍历数组元素，元素作为key，出现的次数作为value，重复则加1，然后再遍历哈希表查找value为1的key。
时间复杂度：O(n)。空间复杂度：O(n)
-
异或^（位运算）：异或满足结合律和交换率，位运算相同则为0，不同则为1，任何数和0异或，都等于它本身。
时间复杂度：O(n)，其中 n是数组长度。只需要对数组遍历一次。空间复杂度：O(1)。
-
-
两个数组的交集
题目：给定两个数组，编写一个函数来计算它们的交集。
-
输入: nums1 = [1,2,2,1], nums2 = [2,2] 。 输出: [2] -
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 。 输出: [9,4]
说明：输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
思路：
-
暴力解法：迭代检查
nums1中的每个值是否也存在于nums2中，如果存在，则将值添加到输出。时间复杂度：O(nm)，n和m分别为
nums1和nums2数组的长度。 -
两个Set：为了线性时间内解决，使用Set这一数据结构，该结构可以提供平均时间复杂度为O(1)的
in/contains操作。先将两个数组转换为集合，这个过程可以去重，然后迭代较小的结合，检查其每个元素是否存在于较大集合中。
时间复杂度：O(n + m)。转换数组的时间分别需要O(n)和O(m)，contains操作只需要O(1)。空间复杂度：O(m+n)。
-
-
两个数组的交集 II
题目：给定两个数组，编写一个函数来计算它们的交集。
-
输入: nums1 = [1,2,2,1], nums2 = [2,2] 。 输出: [2,2] -
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 。 输出: [4,9]
说明：输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。
思路：
-
-
移动零
题目：给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。说明：必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。
思路：
-
双指针：时间复杂度： O(n) 。空间复杂度： O(1)。
public void moveZeroes(int[] nums) { int z = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { int temp = nums[i]; nums[i] = nums[z]; nums[z++] = temp; /*if(z != i) { nums[z] = nums[i]; nums[i] = 0; } z++;*/ } } }
-
-
两数之和
题目：给定一个整数数组
nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
思路：
-
暴力解法：双指针遍历每个元素。
时间复杂度：O(n2)。空间复杂度：O(1)。
-
哈希表：对数组进行迭代，并将元素插入表中，key为nums[i]的值，value为下标，每次都判断
map.containsKey(target - nums[i])，也就是判断差值是否已经存在于标准，如果存在，则取出下标并返回。时间复杂度：O(n)。空间复杂度：O(n)，额外空间取决于存储的元素，最多为n。
-
-
旋转图像
题目：给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
思路：
-
使用辅助数组：对于矩阵中第 i行的第 j个元素，在旋转后，它出现在倒数第 i列的第 j 个位置。我们将其翻译成代码。由于矩阵中的行列从 0 开始计数，因此对于矩阵中的元素 matrix[row] [col]在旋转后，它的新位置为matrix_new[col][n−row−1]。
时间复杂度：O(n2)。空间复杂度：O(n2)。
-
转置加翻转：先转置矩阵，然后翻转每一行。
时间复杂度：O(n2)。空间复杂度：O(1)。
-
翻转代替旋转：先水平翻转，然后主对角线翻转
时间复杂度：O(n2)。空间复杂度：O(1)。
-
反转字符串
题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
思路：
-
双指针：一个左指针指向队首，一个右指针指向队尾，交换两个指针指向的元素，知道两个指针相遇。
时间复杂度：O(n)，空间复杂度：O(1)。
-
-
整数反转
题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
-
输入: 123 输出: 321输入: -123 输出: -321输入: 120 输出: 21
注意：假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
思路：
-
弹出和推入数字 & 溢出前进行检查：
//pop operation: pop = x % 10; x /= 10; //push operation: temp = rev * 10 + pop; rev = temp;
但是，这种方法很危险，因为当
temp=rev⋅10+pop时会导致溢出。幸运的是，事先检查这个语句是否会导致溢出很容易。public int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0; if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0; rev = rev * 10 + pop; } return rev; }
时间复杂度：O(log(x))，xx中大约有log10 (x) 位数字。空间复杂度：O(1)。
-
-
字符串中的第一个唯一字符
题目：给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
思路：
-
暴力解法：挨个遍历后续是否有重复
时间复杂度：O(n2)。空间复杂度：O(1)。
-
哈希表：先便利一遍字符串，将每个字符出现的次数存储在哈希表中。然后再二次遍历字符串，找出第一个在哈希表中出现次数为1的值，返回下标。
时间复杂度：O(n)。空间复杂度：O(n)。
-
-
验证回文字符串
题目：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
思路：
- 首尾指针：依次判断首尾的char是否相等。相等则移动指针。不相等直接返回false。需要注意是，每一个字符判断之前，都需要该字符是不是字母或者数字，不是的话，移动指针判断下一个。
-
最长公共前缀
题目：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串
""。-
输入: ["flower","flow","flight"] 输出: "fl"
思路：
-
水平扫描法：LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)，每两个字符串取公共前缀，得到的结果再与下一个字符串取公共前缀，一旦字符串为""、或者取得的公共前缀为""，则返回""，否则遍历到最后输出的就是结果。
public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; String prefix = strs[0]; for (int i = 1; i < strs.length; i++) while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() - 1); if (prefix.isEmpty()) return ""; } return prefix; }
时间复杂度：O(S)，S为所有字符串的字符数量总和。空间复杂度：O(1)。
-
逐位比较：们从前往后枚举字符串的每一列，先比较每个字符串相同列上的字符，然后再进行对下一列的比较。注意每次判断是否是数组长度临界值，防止角标越界。
时间复杂度：O(S)，S为所有字符串的字符数量总和。空间复杂度：O(1)。
-
-
删除链表中的节点
题目：请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
说明：链表至少包含两个节点。链表中所有节点的值都是唯一的。给定的节点为非末尾节点并且一定是链表中的一个有效节点。
思路：
-
与下一个节点交换：从链表里删除一个节点
node的最常见方法是修改之前节点的next指针，使其指向之后的节点。public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; }
时间复杂度：O(1)。空间复杂度：O(1)。
-
-
删除链表的倒数第N个节点
题目：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
说明：给定的 n 保证是有效的。你能尝试使用一趟扫描实现吗？
思路：
-
两次遍历：首先设置一个虚拟头结点，虚拟头结点用来处理只含有一个节点，或者删除的元素就在头部的问题。在第一次遍历中找到列表的长度L。然后第二次遍历到(L - n)个节点的时候，把(L - n)的节点的next指向(L - n + 2)个节点。
时间复杂度：O(L)。空间复杂度：O(1)。
-
一次遍历：双指针的方式。
start指针和end指针，都指向虚拟头结点。首先start指针向后 n 步，现在两个指针被 n 个节点分开。然后同时移动start指针和end指针，直到start指针到达最后一个节点，也就是 next 节点为null。最后我们将此时的end指针所指向的节点的 next 指向下下个节点。时间复杂度：O(L)。空间复杂度：O(1)。
-
-
反转链表
题目：反转一个单链表。
思路：
-
迭代：遍历列表时，将当前的节点的
next指针改为指向前一个元素。由于节点没有引用其上一个节点，所以需要事先存储其前一个元素。更改引用前还需要另一个指针存储下一个节点，最后返回新的头引用。时间复杂度：O(n)。空间复杂度：O(1)。
-
递归：终止条件是当前节点或者下一个节点==null；在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head。class Solution { public ListNode reverseList(ListNode head) { if(head==null || head.next==null) { return head; } ListNode cur = reverseList(head.next); head.next.next = head; head.next = null; //防止链表循环，需要将head.next设置为空 return cur; //每层递归函数都返回cur，也就是最后一个节点 } }
时间复杂度：O(n)。空间复杂度：O(n)，递归，隐式栈空间，递归深度可能会达到n层。
-
-
合并两个有序链表
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：
-
暴力解法——迭代：创建虚拟头结点，用于返回合并后的结果。维护一个
prev指针，我们需要调整它的next指针。然后，我们重复以下过程，直到l1或者l2指向了null：如果l1当前节点的值小于等于l2，我们就把 l1 当前的节点接在prev节点的后面同时将l1指针往后移一位。否则，我们对l2做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把prev向后移一位。时间复杂度：O(n + m)。空间复杂度：O(1)。
-
递归：我们可以如下递归地定义两个链表里的
merge操作。也就是说，两个链表头部值较小的一个节点与剩下元素的merge操作结果合并。如果l1或者l2一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断l1和l2哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。时间复杂度：O(n + m)。空间复杂度：O(n + m)，栈深度。
-
-
回文链表
题目：请判断一个链表是否为回文链表。
**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路：
-
将值复制到数组后采用双指针法。
时间复杂度：O(n)。空间复杂度：O(n)。
-
递归：
时间复杂度：O(n)。空间复杂度：O(1)。
-
注：DFS用递归的形式，用到了栈结构，后进先出。BFS选取状态用队列的形式，先进先出。
-
二叉树的最大深度
题目：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
思路：
-
递归：分别递归遍历左右子树的高度，取最大值返回。 DFS（深度优先搜索）。
public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int left_height = maxDepth(root.left); int right_height = maxDepth(root.right); return java.lang.Math.max(left_height, right_height) + 1; } }
时间复杂度：O(n)，n为节点数。空间复杂度：O(log(n))，最坏是O(n)，最好是O(log(n))。
-
迭代：利用栈的帮助将上面的递归换成迭代，我们的想法是使用 DFS 策略访问每个结点，同时在每次访问时更新最大深度。所以我们从包含根结点且相应深度为
1的栈开始。然后我们继续迭代：将当前结点弹出栈并推入子结点。每一步都会更新深度。时间复杂度：O(n)，n为节点数。空间复杂度：O(n)。
-
-
验证二叉搜索树
题目：给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数；节点的右子树只包含大于当前节点的数；所有左子树和右子树自身必须也是二叉搜索树。
思路：
-
递归：根据二叉树的特点，节点大于它的左子节点的值，小于它的右子节点的值，那是不是就只需要判断左右子节点是否满足条件即可？其实不对，因为不仅左子节点的值要小于该节点的值，整个左子树的所有节点的值都需要小于该节点；同理又子树所有节点的值都大于该节点。
所以，在比较的同时，不仅比较节点的值，还需要规定子节点值所比较的上下界范围。定义一个递归函数
helper(root, lower, upper)来递归判断，函数表示考虑以root为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。如果root节点的值val不在 (l,r)的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界
upper改为root.val，即调用helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界lower改为root.val，即调用helper(root.right, root.val, upper)。public boolean helper(TreeNode node, Integer lower, Integer upper) { if (node == null) return true; int val = node.val; if (lower != null && val <= lower) return false; if (upper != null && val >= upper) return false; if (!helper(node.right, val, upper)) return false; if (!helper(node.left, lower, val)) return false; return true; } public boolean isValidBST(TreeNode root) { return helper(root, null, null); }
时间复杂度：O(n)，n表示节点个数。空间复杂度：O(n)，n表示最坏情况下栈深度。
-
中序遍历：二叉树的一个特性就是它的中序遍历得到的值构成的序列一定是升序的。这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是，下面的代码我们使用栈来模拟中序遍历的过程。（不需要存储遍历的数组）。中序遍历利用栈结构。
时间复杂度：O(n)，n表示节点个数。空间复杂度：O(n)。
-
-
二叉树的层序遍历
题目：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。
思路：
-
迭代：采用BFS，广度优先搜索，BFS需要采用队列作为辅助结构。由于节点一层一层的挨个进出队列，当一层的节点还未全部出队的时候，下一层的节点已经进队了，所以每次需要记录一下一层的节点数值，然后用for循环控制一层的个数，将同一层的节点遍历结果划分到同一个集合。
时间复杂度：O(n)，n表示节点个数。空间复杂度：O(n)。
-
递归：
-
-
翻转二叉树
题目：翻转一棵二叉树。
思路：
-
递归：递归翻转左右子树
时间复杂度：O(n)。空间复杂度：O(h)，h为书的高度
-
-
最长公共子序列（Longest Common Subsequence，简称 LCS）
题目：给定两个字符串
text1和text2，返回这两个字符串的最长公共子序列的长度。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。
-
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。
思路：
-
-
最长公共子串
题目：
思路：
-
爬楼梯
题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路：