解法一：纵向扫描 将字符串数组看作一个二维空间，每一次从第一列开始。 确定所有字符子串中第一列字符。 逐层扫描后面每一列，遇到不同字符停止扫描。 图解： Java参考代码： import java.util.*; public class Solution { /** * * @param strs string字符串一维数组 * @return string字符串 */ public String longestCommonPrefix (String[] strs) { // //纵向扫描 ...

解法一：双指针 对数组长度进行特判 排序 num[i]>0说明后面的三数和不可能等于0。 对于重复元素跳过 左指针left=i+1，右指针right = len-1 当nums[i]+nums[left]+nums[right]==0执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 left,right 移到下一位置，寻找新的解. 如果和<0left++; 如果和>0):right--； 图解： Java参考代码： import java.util.*; public class Solution { public Arr...

题意分析： 在不使用额外的内存空间的条件下判断一个整数是否是回文数字 如果使用NC57反转数字 的思路，注意溢出的处理 考虑负数的特判 解法一：数学 一个直观的算法，就是将所给数字反转之后与原来的数字进行比较，如果相等怎么时回文数（当然要考虑负数的情况） 关于如何反转一个数字串，请参考NC57反转数字 C++参考代码： class Solution { public: int reverse(int x){ //用long的原因是避免溢出 long res = 0; //注意细节：这里的终止条件不能是x>0 ...

解法一：回溯 思路步骤： 涉及到搜索所有可能的组合类型时，一般情况下都会想到用回溯法。题目中结果集不能重复，这是一个应该注意的点。 开两个数组rseult，path存储结果与可能的路径集。 处理递归终止情况：sum+=num[i]>target时，终止循环（sum为组合数和） 利用一个num.size()大小的数组used进行去重。 参考图解： C++参考代码： class Solution { private: //回溯函数 vector<vector<int>> result;//原来存储最终结果的数组 vecto...

题意分析： 数据结构基础知识，考察二叉树的三序遍历。 二叉树的三序遍历时基础，不了解或者已经忘记的玩家可以看一下图解二叉树的三序遍历 图解： 解法一：递归 前序遍历： 访问顺序：根节点——>左子树——>右子树的方式遍历这棵树 而在访问左子树或者右子树的时候，我们按照同样的方式遍历. 直到遍历完整棵树。 中序遍历： 访问顺序：左子树——>根节点——>右子树的方式遍历这棵树. 而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。 后序遍历： 访问顺序：左子树——>右子树——>根节点的方式遍历这棵树. 而在访问左子树或者右子...

解法一：暴力 (修正)之前的分析有些错误的地方，没有考虑数组旋转的带来的影响(具体已经在解法二中修正了)。大意的理解为就是给你一个数组和target（目标值）,让寻找与目标值相同的元素并返回对应索引，如果不存在就返回-1；比较典型的二分题目。其实题目中对数组的旋转还是有些坑！！！ 此类问题，首先想到的是暴力搜，可以AC!。 这个很暴力，应该没什么问题。C++参考代码： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums ...

题意分析： 一个原始链表，一个整数x,对该链表进行如下规则的操作。 以x为分界，将链表划分为两部分。val<x和val>=x 两个部分之内的节点之间要保持的原始相对顺序 解法一：模拟（推荐） 思路步骤： 由于要将链表按照规则分割为两部分，可以考虑维护两个链表small和large。同样使用哑节点技巧(smallHead和largeHead) 开始时：smallHead.next = small,largeHead.next = large 遍历原始链表，发现head.val<x。 执行：small.next = head. 否则：large.next = he...

解法一：合并后排序 思路步骤： 对原数组A,B进行合并 将合并后的数组A进行排序 java参考代码： import java.util.*; public class Solution { public void merge(int A[], int m, int B[], int n) { //合并 for(int i=0;i!=n;i++){ A[m+i] = B[i]; } //排序 Arrays.sort(A); } }复杂度分析： 时间复杂度：(平均情况)排序序列长度为 m+n...

解法一：双指针(两次遍历) 思路步骤： 要反转局部链表，可以将该局部部分当作完整链表进行反转 再将已经反转好的局部链表与其他节点建立连接，重构链表 建议使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。 反转前后图示： 配图说明： 反转步骤： Java参考代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @...

题意分析 可以返回任何顺序的答案 IP地址不能包含前导0且仅由'.'分割 由于我们需要找出所有可能复原出的 IP 地址，因此可以考虑使用回溯的方法，对所有可能的字符串分隔方式进行搜索，并筛选出满足要求的作为答案。 也可以暴力，也许能AC。（但是...可以作为一种思路吧） 解法一：回溯+剪枝 思路步骤： 递归参数分析： startIdx 用于记录下一层分割的起始位置，因为不能重复分割 poiintNum用于标记逗点过的数量 递归终止条件分析： 题目要求分为4段，因此段数可以作为终止条件 即是pointNum==4时终止 回溯过程： 递归调用时，piontNum++， 回溯时，...

题意分析 理解什么是子数组？ 要求子数组最大累加和 注意题目对时间复杂度和空间复杂度的要求 时间：O（N） 空间：O（1） 注意备注信息：包含了所给数据的边界范围，这对算法的选择至关重要的。 解法一：暴力解 思路步骤： 常规思路，直接两层for循环暴力枚举 找到符合题意的最大累加和 虽然理论上可行，但是时间复杂度为O(N^2)，实际运行是无法AC的。仅仅作为一种学习思路。 C++参考代码：(超时) class Solution { public: /** * max sum of the subarray * @param arr int整型vector...

分析 注意到本题的要求是，找到所有满足从(根节点)到某个(叶子节)经过的路径上的节点之和等于目标和的路径。核心思想是对树进行一次遍历，在遍历时记录从根节点到当前节点的路径和，以防止重复计算. 解法一：深度优先搜索(DFS) 思路步骤： 该递归一共分为两层 第一层：pathSum(TreeNode root, int sum)，可以理解为路径的起点从哪开始 第二层：helper(TreeNode root, int sum)，在该起点下合法路径的数量 因为整个递归是从上到下的dfs，所以不存在路径重复计算的问题 枚举每一条从root节点到叶子节点的路径 遍历到叶子节点时，计算路径和(注...

分析 求买股票的最佳时期，应该注意的细节： 卖出股票之前必须先买入 卖出的价格>买入时候的价格(得考虑利润) 给一个数组模拟股票，换句话说，就是查找数组中某两个元素差值的最大。 如果无利可图，请return 0 解法一：暴力(常规大循环解决) 思路步骤： 最显而易见的解法，当然可能并不是最优的解法 声明变量ans=0存放最终答案 两层for循环，分别找到数组中最大的差值，表示利润最大化 比较并更新ans的值 返回ans即为答案 Java代码参考： import java.util.*; public class Solution { /** * ...