1.求x的n次方
首先我们想到最简单的算法，写个循环
public int fun1(int x,int n){int ans = 1;for(int i = 0; i < n; ++i){ans = ans * x;}return ans;}
这么一看挺简单哈，但是时间复杂度是O(n),要求时间复杂度是O（logn）怎么办呢,用递归完成
public int fun2(int x, int n){if(n == 0){return 1;}if(n % 2 == 1){return fun2(x,n/2)*fun2(x,n/2)*x;}return fun2(x,n/2)*fun2(x,n/2);}
仔细看一下，看似递归次数少了，但是每次递归都调用了两次函数。所以时间复杂度还是没变。再改进一下
public int fun3(int x, int n){if(n == 0){return 1;}int temp = fun(x,n/2);if(n % 2 == 1){return temp*temp*x;}return temp*temp;}
总结：如果一次递归里面有重复的函数调用，看能不能给提取出来。
3.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
这个算法题可以使用两层循环来完成，一层循环用来遍历数组，一层循环用来移动数组，当找到要移除的元素后就循环后面的元素向后移。但是这样用到两层循环，毫无疑问时间复杂度是O(n^2)
用指针法的时间复杂度是O（n）
双指针法
public int[] removeVal(int[] arr, int val){int slowIndex = 0;int fastIndex = 0;for(; fastIndex < arr.length;++fastIndex){if(arr[fastIndex] != val){ //如果快速指针对应元素不是目标元素就将元素赋值到慢指针位置，否则就不赋值arr[slowIndex] = arr[fastIndex];slowIndex++;}}return arr;}
总结：双指针法可以有效的降低时间复杂度，将原本的两次循环用双指针代替了，双指针法真好用。
4.有序数组的平方再排序
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
最先想到的肯定是先平方，再来个快速排序，时间复杂度O（n+nlogn）=O（nlogn），但是想想就没那么简单呀，这里是有序数组，最大值肯定是两端的平方，肯定不是中间的，从两端向中间肯定元素的平方肯定越来越小。所以用双指针法从两边向中间遍历，可以看原理图
双指针法
public int[] arrayPowSort(int[] arr){int length = arr.length;int[] ans = new int[length]; //新数组来装返回值int leftIndex = 0;int rightIndex = length - 1;int k = length - 1;while(k > 0){if(arr[leftIndex]*arr[leftIndex] > arr[rightIndex]*arr[rightIndex]){ans[k] = arr[leftIndex]*arr[leftIndex];leftIndex++;}else{ans[k] = arr[rightIndex]*arr[rightIndex];rightIndex--;}k--;}return ans;}
总结：此题的思想是有序数组的平方两端向中间一定是递减的，所以从两端开始寻找最大数，我只能说双指针法yyds！
5.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
有效的方法是滑动窗口法，滑动窗口法就是不断调整窗口的起始位置和中止位置，从而得到我们想要的效果。
滑动窗口法：
public int maxSublenth(int[] arr,int target){int ans = Integer.MAX_VALUE; //用来存放最后的结果int sublength = 0; //用来存放每次的结果//j是滑动窗口中止指针，i是起始指针int i = 0;int sum = 0; //记录子数组的总和for(int j = 0; j < arr.length; ++j){sum += arr[j];while(sum >= target){sublength = j - i + 1;if(sublength < ans){ans = sublength;}sum -= arr[i];i++;}}return ans;}
总结：一般要找到子数组之类的，放弃使用暴力法，可以考虑滑动窗口法，滑动窗口就是不断的移动起始指针和终止指针，找到最优解，也算是双指针的一种。
6.螺旋矩阵
题目地址：https://leetcode-cn.com/problems/spiral-matrix-ii/ 给定一个正整数 n，生成一个包含 1 到 n 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ] ]
此题的难度在于要用一个统一的规则来进行循环，像下图中每一行或每一列都是两个元素，左闭右开。
此外，还要考虑奇数和偶数的情况，循环次数应该是n/2
public int[][] spiralMaxtrix(int n){int[][] arr = new int[n][n];int startX = 0;int startY = 0;int offset = 1; //左闭右开int loop = n/2;int mid = n%2; //当n是奇数的时候单独处理正中间的点int count = 1;while(loop > 0){for(int i = startY; i < n-offset; ++i){arr[startX][i] = count++;}for(int j = startX; j < n-offset; ++j){arr[j][n-offset] = count++;}for(int i = n-offset; i > startY; --i){arr[n-offset][i] = count++;}for(int j = n-offset; j > startX; --j){arr[j][startY] = count++;}loop--;startX++;startY++;offset++;}if(n%2 == 1){arr[mid][mid] = count;}return arr;}
总结：本题难点是用一个统一规则去遍历数组，防止一行遍历三个，一列又只遍历两个或一个的情况，统一规则之后方便来定义startX,startY，offset这几个关键变量，然后用统一的规则++或—；
7.移除链表中节点
移除链表的节点是很常用到的操作，时间复杂度为O（n）,空间复杂度为O（1）
有两种操作方式来进行删除节点，一种是通过加入一个虚拟的头结点来删除，一种不加虚拟头节点。如果不加虚拟头节点的话如果头结点是要删除的那个节点则需要单独的处理逻辑，加了虚拟头结点的话则不用。
不加虚拟头节点：
public ListNode removeNode(ListNode head,int target){while(head != null && head.val == target){ //这里用while主要是考虑到头几个节点全是目标值head = head.next;}if(head == null){return head;}//到这一步头结点肯定不是目标节点了ListNode pre = head;ListNode cur = head.next;while(cur != null){if(cur.val == target){pre.next = cur.next;}else{pre = cur;}cur = cur.next;}return head;}
不加虚拟头结点
public ListNode removeNode1(ListNode head,int target){ListNode dummy = new ListNode(-1);dummy.next = head;//到这一步头结点肯定不是目标节点了ListNode pre = dummy;ListNode cur = dummy.next;while(cur != null){if(cur.val == target){pre.next = cur.next;}else{pre = cur;}cur = cur.next;}return dummy.next;}
总结：在删除节点的时候，优先考虑到添加虚拟头结点，添加虚拟头结点能够不用考虑删除头结点的情况，最后返回虚拟头结点的下一个节点即可。此题的难点在于循环的中止条件，我第一次写的终止条件是cur.next != null;
8.设计链表功能
https://leetcode-cn.com/problems/design-linked-list/
题意：
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
public class MyLinkedList {int size;ListNode head;public MyLinkedList(){size = 0;head = new ListNode(-1); //虚拟头结点}//得到相应索引值的节点的值public int get(int index){if(index < 0 || index > size){return -1;}ListNode currentNode = head;for(int i = 0; i <= index; ++i){currentNode = currentNode.next;}return currentNode.val;}public void addAtHead(int val){addAtIndex(0,val);}public void addAtTail(int val){addAtIndex(size,val);}//在某位置插入节点public void addAtIndex(int index,int val){if(index > size){return;}if(index < 0){index = 0;}size++;ListNode newNode = new ListNode(val);ListNode pre = head;for(int i = 0; i < index; ++i){pre = pre.next;}ListNode cur = pre.next;pre.next = newNode;newNode.next = cur;}//在某位置删除节点public void deleteAtIndex(int index){if(index >= size || index < 0){return;}size--;ListNode pre = head;for(int i = 0; i < index; ++i){pre = pre.next;}ListNode cur = pre.next;pre.next = cur.next;}}
遇到问题：在该题目中，遇到一点问题，在get(index)的时候想遍历链表然后判断index==i，这样做多此一举，不如在处理之前先判断index是否无效，这也是因为没有利用到size这个变量。
总结：插入和删除节点都是利用当前索引节点和前一个节点来操作的。
引申出疑问：在链表插入和删除节点的时候也要先找到节点，这样一来时间复杂度就是O(n)了。所说的删除时间复杂度应该指的是删除的动作相对于数组而言，数组删除元素之后还要将整体数组移位。所以时间复杂度是O(n)。 同样数组查找元素的时间复杂度也并不是O(1)，正确的表述的，数组按照下标随机访问的时间复杂度为O(1)。同样对于链表而言，如果已知待删除节点的先驱节点那么删除节点的时间复杂度为O(1)。9.反转链表
这道题很多企业都会考，让我先写一遍我自己写的代码
public ListNode reverseList(ListNode head){if(head == null || head.next == null){return head;}ListNode pre = head; //记录前一个节点ListNode cur = head.next; //当前节点ListNode next = cur.next; //下一个节点，如果将当前节点指向了上一个节点，那么就无法继续遍历，所以需要这么一个变量while(next != null){cur.next = pre;pre = cur;cur = next;next = next.next;}cur.next = pre; //因为最后判断的是next是否为空，所以还差一步完成。head.next = null;return cur;}
自我感觉缺点：写得太繁琐，一次循环无法完成全部功能。需要单独处理一个节点的情况。
改进代码：下一个节点用一个临时节点来保存。public ListNode reverseList1(ListNode head){ListNode pre = null;ListNode cur = head;ListNode next = null;while(cur != null){next = cur.next; //用来保存下一个节点，方便遍历cur.next = pre;pre = cur;cur = next;}return pre;}
代码清晰明了
还可以使用递归完成，基本思想都是一样的public ListNode reverseList2(ListNode pre,ListNode cur){if(cur == null){return pre;}ListNode next = cur.next; //先保存下一个变量cur.next = pre;pre = cur;cur = next;return reverseList2(pre,cur);}
总结：我之前遇到的问题是用next=next.next来遍历下一个变量，导致循环结束条件达到了但还剩节点尚未处理，并且链表头还需要单独处理，指向null。改进方法后，只是将next作为临时变量，每次循环cur=next来继续使用cur遍历。
10.交换两两节点
https://leetcode-cn.com/problems/swap-nodes-in-pairs/
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
例如: 1,2,3,4 —> 2,1,4,3
此题可以用两种方法来做，一种加上虚拟头节点，循环完成，主要记住两个关键位置，一个pre
，一个cur(head)，还要记住head.next.next这个节点作为临时节点，不然head.next.next指向换了之后没办法遍历到它了。
加上虚拟头结点public ListNode changeTwoNode(ListNode head){ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;while(pre.next != null && pre.next.next != null){ //偶数个节点，后面没有节点或者奇数个节点最后没有节点了ListNode temp = head.next.next;pre.next = head.next;head.next.next = head;head.next = temp;pre = head;head = temp;}return dummy.next;}
不加虚拟头结点使用递归
public ListNode changeTwoNode1(ListNode head){if(head == null || head.next == null){ //如果当前节点和下个节点为空return head;}ListNode next = head.next;ListNode newNode = changeTwoNode1(next.next);next.next = head;head.next = newNode;return next;}
这个的递归函数看成一个整体，返回的是交换后的新表头。
总结：链表相关的题目不论是交换，插入删除，都要记住考虑pre节点，当前节点以及下一个节点，下一个节点通常作为临时节点。还有要考虑加入虚拟头，这样会少考虑单独表头的特殊情况。11.删除链表中倒数第N个节点
题目链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。n是小于节点个数的。
进阶：你能尝试使用一趟扫描实现吗？
用双指针，fast指针先走N步，然后慢指针开始走，直到fast指针走到null。public ListNode deleteNNode(ListNode head,int n){ListNode dummy = new ListNode(-1);dummy.next = head;ListNode slow = dummy;ListNode fast = dummy;for(int i = 0 ; i < n; ++i){fast = fast.next;}while(fast.next != null){ //此时得到的slow节点是待删除节点的前一个fast = fast.next;slow = slow.next;}ListNode pre = slow;pre.next = slow.next.next;return dummy.next;}
12.找到相交的节点
题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
示例 1：
输入：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
分析：一个节点可以被多个节点指向，但是只能指向一个节点，所以如果两个节点相同的话说明其剩余节点都一样。
可以看出有一部分节点是相同的，所以现将链表对齐，从b2开始和a1进行比较。首先就要找到b2，所以要找到两个链表的长度，然后对齐，然后再一个一个节点进行对比。public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lengthA = 0;int lengthB = 0;while(curA != null){lengthA++;curA = curA.next;}while(curB != null){lengthB++;curB = curB.next;}if(lengthA > lengthB){int gap = lengthA - lengthB;for(int i = 0; i < gap; ++i){headA = headA.next;}}else if(lengthA < lengthB){int gap = lengthB - lengthA;for(int i = 0; i < gap; ++i){headB = headB.next;}}//现在表头对齐了while(headA != null){if(headA == headB){return headA;}headA = headA.next;headB = headB.next;}return null;}
13.有效的字母异位词
https://leetcode-cn.com/problems/valid-anagram/
注意：若_s_和_t_中每个字符出现的次数都相同，则称_s_和_t_互为字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。
这题一开始想到用hashmap，但因为一共只涉及到26个字母，可以用数组来代替hashmap，数组记录s中每个字母出现的次数，然后减去t中每个字母出现的次数，如果是异位词的话数组中每个元素应该为0；public boolean isAnagram(String s, String t) {//存放26个字母出现的次数int[] alphabet = new int[26];for(char c: s.toCharArray()){alphabet[c-'a'] += 1;}for(char c: t.toCharArray()){alphabet[c-'a'] -= 1;}for(int i : alphabet){if( i != 0){return false;}}return true;}
总结：这道题开始让我想到hashmap，但实际中用数组就可以解决，重要的是想清楚为什么要用hashmap，hashmap的原理，从而可以找到可代替的更简单的方案。
14.查找常用字符
https://leetcode-cn.com/problems/find-common-characters/
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
【示例一】 输入：[“bella”,”label”,”roller”] 输出：[“e”,”l”,”l”]
【示例二】 输入：[“cool”,”lock”,”cook”] 输出：[“c”,”o”]
思路：
依然用数组来代替hashmap。public List<String> commonChars(String[] words) {int[][] num = new int[words.length][26];for(int i = 0; i < words.length; ++i){for(char c : words[i].toCharArray()){num[i][c-'a'] += 1;}}//记录字符串中每个字符的最小值,i是代表字符串，k代表字符，num[i][k]是第i个字符串中第k个字符的数量。int[] minNum = new int[26];for(int k = 0; k < minNum.length; ++k){minNum[k] = num[0][k];for(int i = 0; i < words.length; ++i){if(num[i][k] < minNum[k]){minNum[k] = num[i][k];}}}List<String> list = new ArrayList<String>();for(int n = 0; n < minNum.length; ++n){if(minNum[n] != 0){for(int i = 0; i < minNum[n]; ++i){char a = (char)('a'+n);list.add(Character.toString(a));}}}return list;}
总结：过程中遇到的困难就是要理清楚字符串和字符，理清每个字符串中出现字符的字符数，找到每个字符在所有字符串中出现的最小次数，然后输出。
15.两个数组的交集
https://leetcode-cn.com/problems/intersection-of-two-arrays/
题意：给定两个数组，编写一个函数来计算它
们的交集。
分析：一个hashset可以存储无重复的元素，用两个hashset，一个存放数组1的元素，这时已经把重复给去掉了，再判断数组2中元素是否在第一个hashset中出现过，如果出现过就添加到第二个hashset中
public int[] intersection(int[] nums1, int[] nums2) {HashSet<Integer> set1 = new HashSet<>();HashSet<Integer> set2 = new HashSet<>();for(int i : nums1){set1.add(i);}for(int j : nums2){if(set1.contains(j)){set2.add(j);}}int[] num = new int[set2.size()];int index = 0;for(int j : set2){num[index++] = j;}return num;}
总结：遇到个小问题，hashset是无序的，所以不能获取hashset的第n个元素，只能通过增强for循环或者迭代器获取或者foreach，但是数组是需要下标的，所以外面创建了一个下标，每遍历一个元素让下标加1。
16.判断快乐数
https://leetcode-cn.com/problems/happy-number/
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
思路：如果一个数字重复出现了那就说明该数不可能变到1。
public boolean isHappy(int n) {HashSet<Integer> set = new HashSet<Integer>();int sum = 0;while(sum != 1) {sum = 0;while (n != 0) {sum += (n % 10) * (n % 10);n = n / 10;}if(set.contains(sum)){return false;}else{set.add(sum);}n = sum;}return true;}
17.两数之和
https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路：
用暴力法很简单，但是时间复杂度O(n^2)，这样做显然不行
用hashmap，key来装数值，value来装所在位置，遍历数组，把nums中元素都装进去，在装的过程寻找target-num[i]是否在map中了。
public int[] twoSum(int[] nums, int target) {HashMap<Integer,Integer> map = new HashMap<>();int[] two = new int[2];for(int i = 0; i < nums.length; ++i){int temp = target - nums[i];if(map.containsKey(temp)){two[0] = i;two[1] = map.get(temp);}map.put(nums[i],i);}return two;}
总结：开始还想把全部数组元素put到map中再开始寻找两数之和，殊不知就是在put过程中寻找两数之和。
18.四数之和
https://leetcode-cn.com/problems/4sum-ii/
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如:
输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出: 2 解释: 两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
思路：
这次要求的是有多少种组合，而不用列出每个组合，我们可以两两为一对。
1.遍历A组和B组，新建map，key放a+b的值，value放该值出现的次数。
2.遍历C组合D组，寻找0-（c+d）在map中出现的次数，用一个变量记录。
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer,Integer> map = new HashMap<>();int length = nums1.length;for(int i = 0; i < length; ++i){for(int j = 0; j < length; ++j){int temp = nums1[i]+nums2[j];if(map.containsKey(temp)){map.put(temp,map.get(temp)+1);}else{map.put(nums1[i]+nums2[j],1);}}}int count = 0;for(int i = 0; i < length; ++i){for(int j = 0; j < length; ++j){int temp = 0-(nums3[i]+nums4[j]);if(map.containsKey(temp)){count += map.get(temp);}}}return count;}
总结：这题时间复杂度O（n^2），做题过程中，学会遇到map重复的key将value值+1。两个步骤，判断是否包含，然后再提取出value+1重新put到map中。
19.赎金信
https://leetcode-cn.com/problems/ransom-note/
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
思路：这题说白了就是ransom里面的字符在magazine都有，如果ransom的字符magazine里面没有的话就返回false，注意每个字符只能用一次。所以先统计magazine中各个字符出现的次数，再减去ransom出现的字符数，如果出现小于0的情况说明ransom不能由magazine中字符串组成。
public boolean canConstruct(String ransomNote, String magazine) {int[] table = new int[26];for(int i = 0; i < magazine.length(); ++i){table[magazine.charAt(i) - 'a'] += 1;}for(int j = 0; j < ransomNote.length(); ++j){table[ransomNote.charAt(j) - 'a'] -= 1;if(table[ransomNote.charAt(j) - 'a'] < 0){return false;}}return true;}
20.反转字符串
https://leetcode-cn.com/problems/reverse-string/
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：
输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
思路：双指针法，第一个和最后一个元素进行交换。
public void reverseString(char[] s) {int index1 = 0;int index2 = s.length-1;while(index1 < index2){char temp = s[index1];s[index1] = s[index2];s[index2] = temp;index1++;index2--;}}
21.替换空格
https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1： 输入：s = “We are happy.”
输出：”We%20are%20happy.”
思路：只需要一个字符串容器，遇到空格替换成相应的字符串即可。
public String replaceSpace(String s) {StringBuilder sb = new StringBuilder();for(int i = 0; i < s.length(); ++i){if(s.charAt(i) == ' '){sb.append("%20");}else{sb.append(s.charAt(i));}}return sb.toString();}
总结：StringBuilder或者StringBuffer都是可变长度的字符串容器，底层还是数组。
22.单词倒数
https://leetcode-cn.com/problems/reverse-words-in-a-string/
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路：此题为中等难度，有三步
1.去除多余空格；2.反转所有的字符串；3.反转每个字符串
public String reverseWords(String s) {//1.去除多余空格，为了时间复杂度为O(n)，使用双指针法。StringBuilder sb = new StringBuilder();int index2 = s.length()-1;int index1 = 0;//去除前后空格while(s.charAt(index1) == ' '){index1++;}while(s.charAt(index2) == ' '){index2--;}//现在去除中间空格while(index1 <= index2){char c = s.charAt(index1);//只要来的不是空格或者来的是空格但是放入的前一个不是空格，这样就是保证了只有一个空格if(c != ' ' || sb.charAt(sb.length() - 1) != ' '){sb.append(c);}index1++;}//现在开始反转字符串int i = 0;int j = sb.length() - 1;while(i < j){char temp = sb.charAt(i);sb.setCharAt(i,sb.charAt(j));sb.setCharAt(j,temp);i++;j--;}//现在反转每个单词int index3 = 0;int index4 = 0;while(index4 < sb.length()){if(sb.charAt(index4) == ' '){reverseInterval(sb,index3,index4-1);index3 = index4+1;}else if(index4 == sb.length()-1){reverseInterval(sb,index3,index4);}index4++;}return sb.toString();}public void reverseInterval(StringBuilder sb, int start, int end){while(start < end){char temp = sb.charAt(start);sb.setCharAt(start,sb.charAt(end));sb.setCharAt(end,temp);start++;end--;}}
总结：去除多余空格这一块，我想得太多，就是需要把前后的空格先去除然后再去除中间的空格，中间的空格这里他直接用一个判断就做到了，就是若是普通字符就放入，若来的是空着则判断已放入的前一个是不是空格，秒蛙。StringBuilder还有个方法是setCharAt用来设置索引位置的字符; 判断单词
23.填充完美二叉树的右节点指针
题目链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {int val;Node *left;Node *right;Node *next;}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
思路：用队列法做层序遍历，队列里面的节点是有顺序的，指向下一个就好了
public void perfertTraverse(TreeNode node){Queue<TreeNode> queue = new LinkedList<>();queue.offer(node);while(!queue.isEmpty()){int size = queue.size();for(int i = 0; i <size; ++i){TreeNode t = queue.poll();if(t.left != null){queue.offer(t.left);}if(t.right != null){queue.offer(t.right);}if(i != size - 1){t.next = queue.peek();}}}}
总结：程序遍历的队列法很是使用，在遇到统计每层个数还是计算每层平均值在基础上稍微改动即可，这里要指向每层的右边节点用queue.peek()获取即可。复习一下queue.poll()弹出第一个节点并从队列中删除，queue.peek()弹出第一个元素，如果queue为空就弹出空，queue.element()则相反，若为空则报错。queue.offer()添加数据。
24.翻转二叉树
题目地址：https://leetcode-cn.com/problems/invert-binary-tree/
翻转一棵二叉树。
递归法思路：只要把每个节点的左子节点交换一下就可以了，用递归的方法遍历每个节点，递归法要用整体的思想去看，不然很容易把自己给绕进去。递归三步走：1.缺点函数参数返回值。2.确定递归的中止条件。3.确定单层递归逻辑。
public void reverseTree(TreeNode root){if(root == null){return;}//用前序遍历，先翻转TreeNode temp = root.left;root.left = root.right;root.right = temp;reverseTree(root.left);reverseTree(root.right);}
递归法总结：这个题递归法不能用中序遍历，因为先翻转了，再reverseTree(root.right);找到的依然是左边节点。
24.快速排序法
快速排序法的思路是先用一个temp存储数组的第一个元素，然后最后的值与其比较，如果小于该值就把值放到前面，然后又比较前边的值，如果大于temp就放后边，最后直到前指针和后指针相遇的时候就把temp放进去，然后返回该点位置，在重复的对前部分和后部分用相同方法比较。
public void quickSort(int[] array, int start, int end){if(start < end) {int index = getIndex(array, start, end);quickSort(array, 0, index);quickSort(array, index + 1, end);}}public int getIndex(int[] array, int start, int end){int temp = array[start];while(start < end){while(start < end && temp <= array[end]){end--;}array[start] = array[end];while(start < end && temp >= array[start]){start++;}array[end] = array[start];}array[start] = temp;return start;}
遇到问题：做题过程中temp
若有收获，就点个赞吧
0 人点赞
