描述 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益  你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天 如果不能获取到任何利润，请返回0 假设买入卖出均无手续费  示例：  输入：[8,9,2,5,4,7,1] 输出：5，买入2，卖出7  思路1：暴力破解，两两组合 时间复杂度O(n^n)，超时 public class Solution { public int maxProfit (int[] prices) { int ret = ...

描述 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。 要求：时间复杂度 O(nlogn)，空间复杂度 O(1) 思路1：大顶堆 将元素都放入大顶堆，再poll出第K个元素。空间复杂度O(n) public class Solution { public int findKth(int[] a, int n, int K) { //大顶堆 PriorityQueue<Integer> queue = new PriorityQueue<...

描述 比较版本号，版本号按.分割，例如1.02.11，0.1，0.2，忽略前导0  version1>version2返回1 version1<version2返回-1 version1==version2返回0  示例：  1.1==1.1.0 1.1==1.01  思路1：split分割数组，按块比较 空间复杂度O(m+n) public class Solution { public int compare(String version1, String version2) { //需要转义 String[] arr1 = version1.split("\\."); Str...

描述 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。  峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于 假设 nums[-1] = nums[n] = Integer.MIN_VALUE 对于所有有效的 i 都有 nums[i] != nums[i + 1]  数据范围：  1<n<=2x10^5 -2^31<=nums[i]<=2^31-1  思路1：寻找最大值 省略 思路2：遍历左右比较  思路1和思路2，最差的情况坡峰在最后一个值，时间复杂度为O(n)  public cla...

描述 字符串旋转: 给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。 示例：  如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同，返回true。 如果A=‘abcd’，B=‘abcd’，A切成‘abcd’和''（空串），换位后可以得到B，返回true。  思路1：旋转 不断将A的第一个字符放到末尾，比较AB是否相等 思路2：双指针 想象成一圈跑道：A和B起点不同，相距x米。  A先跑x米，到达B的起点处，两者开始一起跑...

描述 给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水  你不能倾斜容器 当n小于2时，视为不能形成容器，请返回0 数据保证能容纳最多的水不会超过整形范围，即不会超过231-1  示例：[1,7,3,2,4,5,8,2,7]，ret=7*7=49 思路1：暴力破解 两两组合，记录最大面积。时间复杂度O(n) public class Solution { public int maxArea (int[] height) { int max = 0; for(int i = 0; i ...

描述 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组 类似题目：最长不含重复字符的子字符串 思路1：滑动窗口  使用left、right双指针表示滑动窗口 每次窗口扩大时，遍历窗口中的元素 如果窗口中包含新元素，则缩小左边界  public class Solution { public int maxLength (int[] arr) { int ret = 0; int left = 0; int right = 0; w...

描述 给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组 注：  A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n 不要返回新数组，将数组 B 的数据合并到 A 里面  示例：A=[1,2,3]，B=[2,5,6]合并后为A=[1,2,2,3,5,6] 难点在于如何移动A数组中原有的元素，如果从前往后插入的话，每次插入时A数组都要整体向后移动。 思路1：新数组+三指针 写法1：A数组和B数组比较，结果暂存到C数组中，最后拷贝回A数组 public class Solution { public void mer...

描述 给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。 字符串回文指该字符串正序与其逆序逐字符一致。 思路1：反转字符串比较 public class Solution { public boolean judge (String str) { StringBuilder sb = new StringBuilder(str); return str.equals(sb.reverse().toString()); } }  思路2：原地比较 public class Solution { public boolean judge...

反转字符串 写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000） 思路1：倒序填入 开辟一个新数组，倒序填入字符 public class Solution { public String solve (String str) { int length = str.length(); char[] arr = new char[str.length()]; for(int i = 0; i < length; i++) { arr[i] = str.charAt(length - 1 - i); } return String.valueOf(arr...

描述 以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。 数据范围：s.length,t.length<=100000，字符串仅由'0'~'9'构成 要求：时间复杂度 O(n) 思路1：模拟加法 从低位开始相加，计算进位 public class Solution { public String solve (String s, String t) { int i = s.length() - 1; int j = t.length() - 1; StringBuilder sb = new StringBuilder(); int flag = 0; while(...

描述 链表相加(二) 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。 给定两个这种链表，请生成代表两个整数相加值的结果链表。 数据范围：0<=n,m<=10000000，链表任意值 0<=val<=9  由于数据范围过大，无法转为int相加  思路1：反转链表相加 public class Solution { public ListNode addInList (ListNode head1, ListNode head2) { if(head1 == null) { return head2; } if(head2 == null)...

链表反转、字符串反转：使用栈、三指针、递归 链表倒数n个节点、链表中的环：使用快慢指针 倒序遍历链表：  使用递归，冒泡阶段处理 使用列表或数组，倒序取出 使用栈，后入先出  涉及到前k大、前k小：使用堆 涉及到排序数组：二分查找

描述 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。 例如：给出的链表为 1->2->3->4->5->NULL，m=2，n=4 返回 1->4->3->2->5->NULL 思路1：两次遍历  遍历找到要反转链表的前一个节点pre，即1 子链表的头节点left=pre.next，即2 遍历找到子链表的后一个节点5 反转链表4->3->2->5，并返回新的头节点 将pre连接上子链表   不足：当m和n相距过大时，反转子链表成本较大...