知识点：数组，排序题目要求将0排列在数组左边，将1排列在数组右边，我们可以遍历一次原数组，找出0的个数，之后，将剩余位置全部补1，得到结果数组。Java题解如下 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型一维数组 * @return int整型一维数组 */ public int[] sortCows (int[] cows) { ...

知识点：动态规划对于一个环形的数组，要找到其最大的子数组和，第一想法是进行两轮遍历，但是这种方法有个缺陷，题目要求每一个元素只能出现一次，而我们无法确定第二次遍历是是否包含了同一个元素，故这种方法是行不通的。我们可以换一种思路，对于一个数组来说，最大的子数组和有两种情况：一种是没有跨过环形边界，即不需要考虑环形问题另一种是子数组跨过了环形边界，这种情况下，其实我们可以通过数组和减去未选取部分的子数组和，也就得到了跨边界的子数组和。对于第二种情况，我们需要求得不考虑环形的情况下，我们可以得到的最小子数组和，以确保数组和减去该子数组和能够得到最大的子数组和。还有一个需要注意的点，在于如果整个数组的...

知识点：二维动态规划题目要求只能向下或者向右走，故到达一个点的方式一共有两种，要么是从上方向下，要么是从左方向右，到达当前点的路径数就等于到达上方点的路径数+到达左方点的路径数，若当前点位置为障碍物，则当前点的到达路径数为0，最终，我们可以得出右下角位置的到达路径数。Java题解如下 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型二维数组 * @return...

知识点：双指针，贪心这道题目要求我们找到各个数组之间的重叠部分最少是几个，我们首先要做的就是对数组进行排序，可以按照左端点升序排列，因为我们需要涵盖所有的数组，故我们可以使用贪心的思想，总是去考虑我们的右端点最多能涵盖几个数组。我们可以使用双指针，left指向我们目前没有统计的数组，再看该数组的右端点，是否可以涵盖下一个数组（因为我们之前按左端点排序，故下一个数组一定是最有可能涵盖的），若可以涵盖，则需要更新我们可以到达的右端点，因为我们要涵盖当前的所有数组，故右端点需要取各个数组右端点的最小值。若下一个数组无法被涵盖，则left指针指向下一个未统计的数组，直至所有数组统计完毕。Java题解如...

知识点：二分查找题目要求使用时间复杂度为 O(log n) 的算法。我们就需要使用二分法来查找对应数据，这道题的难点在于对于数组中不存在的元素target，我们如何找到该target应该插入的位置。如果不存在，应该找到它按顺序插入的位置，我们先假设left和right已经相等，此时，我们还并没有找到target，故我们应该在当前位置的下一个位置作为target的插入位置，即mid + 1，也就是最终left所处的位置。Java题解如下 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，...

知识点：二叉树，搜索二叉树首先明确搜索二叉树的定义：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。我们可以使用递归的方式来解决，首先确定终止条件，若当前节点为空，返回true，若不为空，判断其左右节点是否为空，为空则符合搜索二叉树定义，若不为空，则需要判定其节点值是否符合搜索二叉树的定义，即左子节点值小于当前节点值，右子节点值大于当前节点值。若符合条件，则递归向下遍历子树。Java题解如下： import java.util.*; /* * public class TreeNode { * int val = 0;...

知识点：二叉树，层序遍历基本的层序遍历操作：使用队列保存每一层的节点，每次遍历一层的节点，保存所有元素的和，统计该层元素和是否为最大，若为最大，则更新答案，并保存当前层的元素和。遍历完最后一层，得到的最大元素和层即为答案。Java题解如下： import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; ...

知识点：二叉树，层序遍历不同于以往的层序遍历，这道题目要求以Z字型进行元素的遍历，我们可以使用一个标记flag，每隔一层将每层得到的元素进行反转，即可得到Z字型排列的效果。具体来说，我们还是像普通的层序遍历一样，获得每层的元素后，我们进行判定，若为双数层，则将list进行反转，再加入到最终结果中。Java题解如下 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNo...

知识点：快速排序对于时间复杂度为 O(n) 的方法，我们需要使用快速排序的思想。随机选择一个枢轴index，利用快速排序的方法，将大于该weights[index]的值移动到index右边，小于weights[index]的值移动到index左边，这样就做到了index位置的值一定是第index-1小的值。若index大于k-1，则说明第k小的值在左边，只需要递归左侧子数组即可，同理，若index小于k-1，说明第k小的值在右边，则递归右侧子数组。这样只需要遍历一半的空间，提高了时间效率。Java题解如下： import java.util.*; public class Solution...

知识点：数组将数组逆时针旋转90度，如果是使用额外的空间的话，会很好理解，但是题目中要求的是使用原地算法来操作。将数组旋转90度，可以分解为两步：1.将数组按照中间对称反转2.将数组按照斜对角线进行反转完成后，即可得到旋转90度的效果。这是一个经典的题目，第一次遇到不容易想到，属于一种比较投巧的方法。Java题解如下： import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix int整型...

知识点：基本类型只需要按照题目要求的公式进行返回即可，需要注意的是，由于m和n都是int类型，相乘可能会出现溢出的情况，所以要将其转换成long类型返回。Java题解如下： import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return long长整型 */ public long weightA...

知识点：矩阵题目要求若一行或一列内有一个位置的元素为0，则整行或整列的元素都应该修改为-1，要求使用原地算法，故我们可以先使用额外的数组来统计那些行与列的元素为0，具体来说，使用一个行数组和一个列数组，分别记录该行或该列是否有0元素，遍历完成后，进行二次遍历，如当前行或列已经被标记，则需要将数组的元素置为-1。Java题解如下： import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix ...

知识点：二叉树，层序遍历要想得到二叉树每一层的值，需要对二叉树进行层序遍历，也就是广度优先搜索，我们需要使用一个队列来实现。具体来讲，我们对于每一层的节点，都需要加入到队列中，当节点出队时，我们将其左右子节点进行入队操作，在遍历每一层节点时，我们使用一个临时的变量size来约束队列出队的个数，也就是当前层的节点个数，确保不会遍历到下一层。Java题解如下： import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = nu...

知识点：二叉树，递归这道题题解很简单就可以实现，主要的难度在于思路上，如果有了思路，这道题就可以很简单的解决。若想将一个二叉树进行反转，其实很简单，无非是将其左右节点进行反转，也就是使用一个临时节点，将左右节点交换即可。其中的一个问题在于左右子树的结构也需要进行反转的操作，故我们可以直接递归地调用该反转函数，直至到达叶子节点。Java题解如下： import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; *...