判断是否为回文字符串
具体做法
step 1：准备两个指针，一个在字符串首，一个在字符串尾。
step 2：在首的指针往后走，在尾的指针往前走，依次比较路过的两个字符是否相等，若是不相等则直接就不是回文。
step 3：直到两指针在中间相遇，都还一致就是回文。因为首指针到了后半部分，走过的正好是尾指针走过的路，二者只是交换了位置，比较相等还是一样的。
import java.util.*; public class Solution { public boolean judge (String str) { //首指针 int left = 0; //尾指针 int right = str.length() - 1; //首尾往中间靠 while (left < right) { //比较前后是否相同 if (str.charAt(left) != str.charAt(right)) return false; left++; right--; } return true; } }
反转字符串
//解法1 import java.util.*; public class Solution { public String solve (String str) { char[] ans = str.toCharArray(); int len = str.length(); for(int i = 0 ; i < len ;i++) { ans[i] = str.charAt(len-1-i); } return new String(ans); } } //解法2 import java.util.*; public class Solution { public String solve (String str) { StringBuffer sb =new StringBuffer(str);//此方法针对的是io流，不能针对字符串。 return sb.reverse().toString(); } }
最长无重复子数组
import java.util.*; public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength(int[] arr) { //用链表实现队列，队列是先进先出的 Queue<Integer> queue = new LinkedList<>(); int res = 0; for (int c : arr) { while (queue.contains(c)) { //如果有重复的，队头出队 queue.poll(); } //添加到队尾 queue.add(c); res = Math.max(res, queue.size()); } return res; } }
这里主要是要理解15行用while不用if和第21行代码，根据上面的用例输入就可以理解了，最后只要有重复的队列里的所有元素都会被弹出去并且只剩下最后一个元素，所以需要21行的代码每次记录最大值，用while也是为了弹出所有队列中的元素
解法二
具体做法
step 1：构建一个哈希表，用于统计数组元素出现的次数。
step 2：窗口左右界都从数组首部开始，每次窗口优先右移右界，并统计进入窗口的元素的出现频率。
step 3：一旦右界元素出现频率大于1，就需要右移左界直到窗口内不再重复，将左边的元素移除窗口的时候同时需要将它在哈希表中的频率减1，保证哈希表中的频率都是窗口内的频率。
step 4：每轮循环，维护窗口长度最大值。
import java.util.*; public class Solution { public int maxLength (int[] arr) { //哈希表记录窗口内非重复的数字 HashMap<Integer, Integer> mp = new HashMap<>(); int res = 0; //设置窗口左右边界 for(int left = 0, right = 0; right < arr.length; right++){ //窗口右移进入哈希表统计出现次数 if(mp.containsKey(arr[right])) mp.put(arr[right],mp.get(arr[right])+1); else mp.put(arr[right],1); //出现次数大于1，则窗口内有重复 while(mp.get(arr[right]) > 1) //窗口左移，同时减去该数字的出现次数 mp.put(arr[left],mp.get(arr[left++])-1); //维护子数组长度最大值 res = Math.max(res, right - left + 1); } return res; } }
贪心算法
盛水最多的容器
知识点1：双指针
双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。
知识点2：贪心思想
贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。
思路
这道题利用了水桶的短板原理，较短的一边控制最大水量，因此直接用较短边长乘底部两边距离就可以得到当前情况下的容积。但是要怎么找最大值呢？
可以利用贪心思想：我们都知道容积与最短边长和底边长有关，与长的底边一定以首尾为边，但是首尾不一定够高，中间可能会出现更高但是底边更短的情况，因此我们可以使用对撞双指针向中间靠，这样底边长会缩短，因此还想要有更大容积只能是增加最短变长，此时我们每次指针移动就移动较短的一边，因为贪心思想下较长的一边比较短的一边更可能出现更大容积。
//优先舍弃较短的边 if(height[left] < height[right]) left++; else right--;
具体做法
step 1：优先排除不能形成容器的特殊情况。
step 2：初始化双指针指向数组首尾，每次利用上述公式计算当前的容积，维护一个最大容积作为返回值。
step 3：对撞双指针向中间靠，但是依据贪心思想，每次指向较短边的指针向中间靠，另一指针不变。
import java.util.*; public class Solution { public int maxArea (int[] height) { //排除不能形成容器的情况 if(height.length < 2) return 0; int res = 0; //双指针左右界 int left = 0; int right = height.length - 1; //共同遍历完所有的数组 while(left < right){ //计算区域水容量 int capacity = Math.min(height[left], height[right]) * (right - left); //维护最大值 res = Math.max(res, capacity); //优先舍弃较短的边 if(height[left] < height[right]) left++; else right--; } return res; } }
合并区间
具体做法
step 1：既然要求重叠后的区间按照起点位置升序排列，我们就将所有区间按照起点位置先进行排序。使用sort函数进行排序，重载比较方式为比较interval结构的start变量。
step 2：排序后的第一个区间一定是起点值最小的区间，我们将其计入返回数组res，然后遍历后续区间。
step 3：后续遍历过程中，如果遇到起点值小于res中最后一个区间的末尾值的情况，那一定是重叠，取二者最大末尾值更新res中最后一个区间即可。
step 4：如果遇到起点值大于res中最后一个区间的末尾值的情况，那一定没有重叠，后续也不会有这个末尾的重叠区间了，因为后面的起点只会更大，因此可以将它加入res。
import java.util.*; public class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { ArrayList<Interval> res = new ArrayList<>(); //去除特殊情况 if(intervals.size() == 0) return res; //重载比较，按照区间首排序 Collections.sort(intervals, new Comparator<Interval>(){ public int compare(Interval o1, Interval o2){ if(o1.start != o2.start) return o1.start - o2.start; else return o1.end - o2.end; } }); //放入第一个区间 res.add(intervals.get(0)); int count = 0; //遍历后续区间，查看是否与末尾有重叠 for(int i = 1; i < intervals.size(); i++){ Interval o1 = intervals.get(i); Interval origin = res.get(count); if(o1.start > origin.end){ res.add(o1); count++; //区间有重叠，更新结尾 }else{ res.remove(count); Interval s = new Interval(origin.start, o1.end); if(o1.end < origin.end) s.end = origin.end; res.add(s); } } return res; } }
分糖果问题
知识点：贪心思想
贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。
思路
要想分出最少的糖果，利用贪心思想，肯定是相邻位置没有增加的情况下，大家都分到1，相邻位置有增加的情况下，分到糖果数加1就好。什么情况下会增加糖果，相邻位置有得分差异，可能是递增可能是递减，如果是递增的话，糖果依次加1，如果是递减糖果依次减1？这不符合最小，因为减到最后一个递减的位置可能不是1，必须从1开始加才是最小，那我们可以从最后一个递减的位置往前反向加1.
具体做法
step 1：使用一个辅助数组记录每个位置的孩子分到的糖果，全部初始化为1.
step 2：从左到右遍历数组，如果右边元素比相邻左边元素大，意味着在递增，糖果数就是前一个加1，否则保持1不变。
step 3：从右到左遍历数组，如果左边元素比相邻右边元素大， 意味着在原数组中是递减部分，如果左边在上一轮中分到的糖果数更小，则更新为右边的糖果数+1，否则保持不变。
step 4：将辅助数组中的元素累加求和。
import java.util.*; public class Solution { public int candy (int[] arr) { int n=arr.length; if(n<=1) return n; int[] nums = new int[n]; //初始化 for(int i = 0; i < n; i++) nums[i] = 1; //从左到右遍历 for(int i = 1; i < arr.length; i++){ //如果右边在递增，每次增加一个 if(arr[i] > arr[i - 1]) nums[i] = nums[i - 1] + 1; } //记录总糖果数 int res = nums[arr.length - 1]; //从右到左遍历 for(int i = arr.length - 2; i >= 0; i--){ //如果左边更大但是糖果数更小 if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) nums[i] = nums[i + 1] + 1; //累加和 res += nums[i]; } return res; } }
主持人调度
思路
我们利用贪心思想，什么时候需要的主持人最少？那肯定是所有的区间没有重叠，每个区间首和上一个的区间尾都没有相交的情况，我们就可以让同一位主持人不辞辛劳，一直主持了。但是题目肯定不是这种理想的情况，那我们需要对交叉部分，判断需要增加多少位主持人。
具体做法
step 1: 利用辅助数组获取单独各个活动开始的时间和结束时间，然后分别开始时间和结束时间进行排序，方便后面判断是否相交。
step 2: 遍历nnn个活动，如果某个活动开始的时间大于之前活动结束的时候，当前主持人就够了，活动结束时间往后一个。
step 3: 若是出现之前活动结束时间晚于当前活动开始时间的，则需要增加主持人。
import java.util.*; public class Solution { public int minmumNumberOfHost (int n, int[][] startEnd) { int[] start = new int[n]; int[] end = new int[n]; //分别得到活动起始时间 for(int i = 0; i < n; i++){ start[i] = startEnd[i][0]; end[i] = startEnd[i][1]; } //单独排序 Arrays.sort(start, 0, start.length); Arrays.sort(end, 0, end.length); int res = 0; int j = 0; for(int i = 0; i < n; i++){ //新开始的节目大于上一轮结束的时间，主持人不变 if(start[i] >= end[j]) j++; else //主持人增加 res++; } return res; } }
动态规划
斐波那契数列
知识点：动态规划
动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。
思路
斐波那契数列初始化第1项与第2项都是1，则根据公式第0项为0，可以按照斐波那契公式累加到第n项。
具体做法
step 1：低于2项的数列，直接返回n。
step 2：初始化第0项，与第1项分别为0，1.
step 3：从第2项开始，逐渐按照公式累加，并更新相加数始终为下一项的前两项。
public class Solution { public int Fibonacci(int n) { //从0开始，第0项是0，第一项是1 if(n <= 1) return n; int res = 0; int a = 0; int b = 1; //因n=2时也为1，初始化的时候把a=0，b=1 for (int i = 2; i <= n; i++){ //第三项开始是前两项的和,然后保留最新的两项，更新数据相加 res = (a + b); a = b; b = res; } return res; } }
跳台阶
知识点：递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
思路
一只青蛙一次可以跳1阶或2阶，直到跳到第nnn阶，也可以看成这只青蛙从n阶往下跳，到0阶，按照原路返回的话，两种方法事实上可以的跳法是一样的——即怎么来的，怎么回去！ 当青蛙在第n阶往下跳，它可以选择跳1阶到n−1，也可以选择跳2阶到n−2，即它后续的跳法变成了f(n−1)+f(n−2)，这就变成了斐波那契数列。因此可以按照斐波那契数列的做法来做：即输入n，输出第n个斐波那契数列的值，初始化0阶有1种，1阶有1种。
具体做法
step 1：低于2项的数列，直接返回n。
step 2：对于当前n，递归调用函数计算两个子问题相加。
public class Solution { public int jumpFloor(int target) { //这里第0项为1，第1项为1 if(target <= 1) return 1; else //递归子问题相加 return jumpFloor(target - 1) + jumpFloor(target - 2); } }
跳台阶和斐波那契数列的答案是一样的，可以用动态规划也可以用递归实现
