三数之和 问题陈述 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例： 1234567给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2]] 思路分析 双指针法思路： 先将数组由小到大排序。 固定3个指针中的一个k，初始化为数组第一个元素索引0, 然后i=k+1，j=nums.length-1。k<nums.length-2,循环遍历。 若nums[k]>0,显然后面元素都大于0，直接break。 若num[i]==nums[++i], 重复元素，直接continue跳过。 循环过程中判断nums[k]+nums[i]+nums[j]==0? 符合加入list，不符合继续遍历，同样对++i，–j，若重复则直接跳到不重复元素处。 代码实现 1234567891011121314151617181920212223 ...

删除链表的倒数第n个结点 问题陈述 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 123给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5. 思路分析 定义一个pre结点，pre.next=head。然后定义两个指针first，second。first先走n步，然后一起走，当first为空跳出，此时second指向了被删结点的前一个结点，执行删除。最后返回pre.next。 代码实现 1234567891011121314151617class Solution{ public ListNode removeNthFromEnd(ListNode head,int n){ ListNode pre=new ListNode(0); pre.next=head; ListNode first=pre,second=pre; while(n!=0){ ...

排序算法汇总 冒泡排序 思路：俩俩交换，大的放在后面，第一次排序后最大值已在数组末尾。需要n-1次排序。 1234567891011121314151617181920212223242526272829303132333435363738394041public class BubbleSort { public void bubbleSort(int[] array){ //装载临时变量 int temp; //记录是否发生了置换，0，没有置换；1，置换了。 int isChange; //记录执行次数 int count=0; //外层循环表示排序的趟数 for(int i=0;i<array.length-1;i++){ //每排序一趟就重新初始化为0 isChange=0; //内层循环表示当前趟需要比较的次数 for(int j= ...

算法思维之二分法 二分查找框架 123456789101112131415int binarySearch(int[] nums, int target) { int left = 0, right = ...; while(...) { int mid = left + (right - left) / 2; if (nums[mid] == target) { ... } else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } return ...;} 示例：寻找一个数。 12345678910111213141516int binarySearch(int[] nums, int ta ...

盛最多水的容器 问题陈述 给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 **说明：**你不能倾斜容器，且 n 的值至少为 2。 思路分析 定义两个指针i，j。i指向容器左壁索引，j指向容器右壁索引，判断谁高度小，然后i小的话i++；j小j–。当i<j时不断获得面积并返回最大值。 代码实现 12345678910class Solution{ public int maxArea(int[] height){ int i=0,j=height.length-1,res=0; while(i<j){ res=height[i]<height[j]? Math.max(res,height[i++]*(j-i)):Math.max(res,height[j--]*(j-i)); ...

整数反转 解法一：转换为字符串进行反转 思路：将整数转换为字符串进行反转，数字溢出使用异常捕获。 12345678910111213141516171819class Solution{ public int reverse(int x){ String str=" "; int res=0; if(x<0){ str="-"+new StringBuffer(String.valueOf(x).substring(1)).reverse().toString(); }else{ str=new StringBuffer(String.valueOf(x)).reverse().toString(); } if(str=" ") return 0; try{ res=Integer ...

最长公共前缀 问题陈述 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例： 12输入: ["flower","flow","flight"]输出: "fl" 问题解决 123456789101112131415class Solution { public String longestCommonPrefix(String[] strs) { if(strs==null||strs.length==0) return "";//判断字符数组是否为空 String prefix=strs[0];//假设第一个字符串就是最长前缀 for(int i=1;i<strs.length;i++){ while(strs[i].indexOf(prefix)!=0){//如果不存在，即起始索引不等于0 ...

最长回文子串 问题陈述 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例一： 123输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。 暴力解法 12345678910111213141516171819202122232425262728293031public class LongPalindrome { public boolean isPalindrome(String s){//判断是否回文 char[] str=s.toCharArray(); for(int i=0;i<str.length/2;i++){ if(str[i]!=str[str.length-i-1]){ return false; } } return true; ...

二叉树的公共祖先 问题陈述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 说明 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。 思路分析 递归解析： 终止条件： 当越过叶节点，则直接返回 null ； 当 root 等于 p, q，则直接返回 root ； 递推工作： 开启递归左子节点，返回值记为 left ； 开启递归右子节点，返回值记为 right ； 返回值： 根据 left和 right ，可展开为四种情况； 当 left和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q，返回 null； 当 left和 right 同时不为空 ：说明 p, q分列在 root的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root； 当 left 为空 ，right 不为空 ：p,q都不在 root的左子树 ...

二叉搜索树的最近公共祖先 问题陈述 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。 示例： 123输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4输出: 2解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 说明 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。 思路分析 由于为二叉搜索树，左结点值小于根结点，右结点值大于根结点。如果p、q结点值小于根，则向左子树遍历；如果p、q结点值大于根，则向右子树遍历；否则，返回当前根结点。具体可以上述荔枝举例看到。 代码实现 123456789101112131415class Solution{ public TreeNode getCommenParent(TreeNode ...