LeetCode
- 自用笔记
数组
27.移除元素
- 给你一个数组 nums 和一个值 val，你须要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
- 不要应用额定的数组空间，你必须仅应用 O(1) 额定空间并 原地 批改输出数组。
- 元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素。
- 暴力算法
C
- 剖析：外层循环管制数组判断，内层循环用于笼罩数组元素
int removeElement(int* nums, int numsSize, int val) { int i, j; int len = numsSize; for (i = 0; i < len; i++) { if (nums[i] == val) { j = i+1; while (j < len) { nums[j-1] = nums[j];//j-1是避免下标越界 j++; } len--; i--;//len--的状况下i肯定要-- } } return len;}JAVA
/*工夫复杂度：O(n^2)空间复杂度：O(1)*/public int removeElement(int[] nums, int val) { int n = nums.length; for(int i=0;i<n;i++){ if(nums[i]==val){ for(int j=i+1;j<n;j++){ nums[j-1] = nums[j]; // 小心越界 } i--;// 因为下标i当前的数值都向前挪动了一位，所以i也向前挪动一位 n--; } } return n; }- 双指针法(快慢指针法):
- 通过一个快指针和慢指针在一个for循环下实现两个for循环的工作
C
int removeElement(int* nums, int numsSize, int val){ int solw = 0,fast; for(fast=0;fast<numsSize;fast++){ if(val!=nums[fast]){ nums[solw++] = nums[fast]; } } return solw;}JAVA
// 工夫复杂度：O(n)// 空间复杂度：O(1)public int removeElement2(int[] nums, int val) { int slowIndex = 0; for(int fastIndex = 0; fastIndex< nums.length;fastIndex++){ if(val != nums[fastIndex]){ nums[slowIndex++] = nums[fastIndex]; } } return slowIndex;}
35.搜寻插入地位
- 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按程序插入的地位。
- 你能够假如数组中无反复元素。
- 二分法查找
- C
int searchInsert(int* nums, int numsSize, int target){ int low = 0, high = numsSize-1; int mid; while (low <= high) { mid = low + (high - low) / 2; if (target > nums[mid]) low = mid + 1; else if (target < nums[mid]) high = mid - 1; else return mid; } return high+1;}JAVA
public int searchInsert(int[] nums, int target) { int n = nums.length; int left = 0,right = n -1; // 定义target在左闭右闭的区间里，[left, right] while(left<=right) { // 当left==right，区间[left, right]仍然无效 int mid = left + ((right - left) / 2); // 避免溢出，等价(left+right)/2 if (target < nums[mid]) { right = mid - 1;// target 在左区间，所以[left, middle - 1] } else if (target > nums[mid]) { left = mid + 1; } else { // nums[middle] == target return mid; } } return right+1; /* 别离解决如下四种状况 1.目标值在数组所有元素之前 [0, -1] target = -1,nums = [1,3,5,7] 第一次循环 right = 3,left = 0,mid = 1 target < nums[1] = 3 --> right = mid -1 = 0 第二次循环 right = 0,left = 0,mid = 0 target < nums[0] = 1 --> right = mid -1 = -1 循环完结，返回 right+1 = 0 2.目标值等于数组中某一个元素 return middle; 3.目标值在数组两头 [left, right]，return right + 1 target = 4,nums = [1,3,5,7] 第一次循环 right = 3,left = 0,mid = 1 target > nums[1] = 3 --> left = mid + 1 = 1 第二次循环 right = 3,left = 1,mid = 2 target < nums[2] = 5 --> right = mid -1 = 1 循环完结，返回 right+1 = 2 4.目标值在数组所有元素之后的状况 [left, right]， return right + 1 */ }
209.长度最小的子数组
- 给定一个含有个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的间断子数组[numsl, numsl+1, ..., numsr-1, numsr],并返回其长度。如果不存在符合条件的子数组，返回 0 。 - 暴力算法
剖析：
- 取i到j的区间，而后对该区间求和并判断
- j-i+1是取以后从i到j之间元素个数
- 三元表达式的判断是判断老长度是否比新长度大？，因为求最小长度
C
int minSubArrayLen(int target, int* nums, int numsSize){ int i, j; int sum; int subLen;//用来标识新长度 int result = INT_MAX;//用来标识老长度，这里要取一个最大值 for (i = 0; i < numsSize; i++) { sum = 0; for (j = i; j < numsSize; j++) { sum += nums[j]; if (sum >= target) { subLen = j - i + 1;//获取该sum蕴含的子数组长度 result = result > subLen ? subLen : result;//判断老长度是否大于新长度 break; } } } return result==INT_MAX ? 0:result;//避免全副元素之和都不大于target}JAVA
//暴力解法//工夫复杂度：O(n^2)//空间复杂度：O(1)public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE; // 取一个数组不可能的超过的最大值 int sum = 0; // 子序列的数值之和 int subLength = 0; // 子序列的长度 for(int i=0;i<nums.length;i++){ sum = 0; for(int j=i;j<nums.length;j++){ sum+=nums[j]; if(sum>=target){ subLength = j-i+1; // 取子序列的长度 result = result<subLength?result:subLength; // 与前一次长度作比拟 break; // 因为咱们是找符合条件最短的子序列，所以一旦符合条件就break } } } // 如果result没有被赋值的话，就返回0，阐明没有符合条件的子序列 return result == Integer.MAX_VALUE ? 0:result;}滑动窗口
- 在本题中实现滑动窗口，次要确定如下三点：
1.窗口内是什么？
2.如何挪动窗口的起始地位？
3.如何挪动窗口的完结地位
窗口就是满足和>=target的长度最小的间断子数组；
窗口的起始地位如何挪动：如果以后窗口的值>target，窗口就要向前挪动（即放大窗口）
窗口的完结地位如何挪动：窗口的完结地位即遍历数组的指针，起始地位即数组的起始地位。
- 在本题中实现滑动窗口，次要确定如下三点：
JAVA
//滑动窗口/*滑动窗口的精妙之处在于依据以后子序列和大小的状况，一直调节子序列的起始地位。从而将O(n^2)的暴力解法降为O(n)。 */public int minSubArrayLen_2(int target, int[] nums) {int result = Integer.MAX_VALUE;int sum = 0;//滑动窗口数值之和int i = 0;//滑动窗口起始地位int subLength = 0;//滑动窗口的长度for(int j=0;j< nums.length;j++){ sum+=nums[j]; //应用while，每次更新i（起始地位），并一直比拟子序列是否符合条件 while(sum>=target){ subLength = (j - i + 1);//取子序列的长度 result = result < subLength? result:subLength; sum -= nums[i++];//减去第一个数，窗口内数字个数-1，i滑动到i++地位 }}return result == Integer.MAX_VALUE ? 0 : result;/*nums[] = 2 , 3 , 1 , 2 , 4 , 3 target = 7下标： 0 1 2 3 4 5sum = 0;i = 0;subLength = 0;1. ij(指向下标0) --> sum = 0+2 = 22. i j --> sum = 2+3 = 53. i j --> sum = 5+1 = 64. i j --> sum = 6+2 = 8while-->subLength = j-i+1 = 3-0+1 = 4 -->result = Max < 4 ? Max:4 = 4 -->sum -= nums[i++] = sum - nums[0] = 8-2 = 6 --> i(向前挪动i,即窗口放大) ... ... */}
- C
int minSubArrayLen(int target, int* nums, int numsSize){ int i = 0,j; int result = INT_MAX; int sublen = 0; int sum = 0; for(j=0;j<numsSize;j++){ sum += nums[j]; while(sum>=target){ sublen = j-i+1; result = result > sublen ? sublen:result; sum -= nums[i++]; } } return result==INT_MAX?0:result;}59.螺旋矩阵 II
给你一个正整数 n ，生成一个蕴含 1 到 n2 所有元素，且元素按顺时针程序螺旋排列的 n x n 正方形矩阵 matrix 。
public int[][] generateMatrix(int n) { int[][] nums = new int[n][n]; int startX = 0,startY = 0;//定义每循环一个圈的起始地位，如(0,0),(1,1)... int loop = n / 2;//每个圈循环几次，如n=3为奇数，则loop=1只循环一圈， //矩阵两头的值须要独自解决 int mid = n / 2;//矩阵两头的地位，如n=3，两头地位就是(1,1)，n=5-->(2,2) int count = 1;//给矩阵赋值的变量 int offset = 1;//每一圈循环，须要管制每一条边遍历的长度 int i,j; while(loop--!=0){ i = startX; j = startY; //上面开始的四个for就是模仿转一圈 /* → → ↓ ↑ → ↓ ↑ ← ← */ //上行从左到右 for(j = startY;j<startY+n-offset;j++){ nums[startX][j] = count++; } //右列从上到下 for(i = startX;i<startX+n-offset;i++){ nums[i][j] = count++; } //模仿上行从右到左 for(;j>startY;j--){ nums[i][j] = count++; } //模仿左列从下到上 for(;i>startX;i--){ nums[i][j] = count++; } // 第二圈开始的时候，起始地位要各自加1， //例如：第一圈起始地位是(0, 0)，第二圈起始地位是(1, 1) /* 如n=4时： 第一圈： 0 1 2 3 0 → → → ↓ 1 ↑ ↓ 2 ↑ ↓ 3 ↑ ← ← ← -->则第一圈从(0,0)开始 第二圈： 1 2 1 → ↓ 2 ↑ ← -->则第二圈从(1,1)开始 */ startX++; startY++; // offset 管制每一圈里每一条边遍历的长度 // 如n=4,第一圈第一行长度=4，第二圈第一行长度为4-2=2 /* 第一圈： → → → ↓ ↑ ↓ ↑ ↓ ↑ ← ← ← 第二圈： → ↓ ↑ ← */ offset += 2; } // 如果n为奇数的话，须要独自给矩阵最两头的地位赋值 /* 如n=3,中心点则为(1,1) n=5,中心点则为(2,2) */ if (n % 2==1) { nums[mid][mid] = count; } return nums; }代码手推图
*217.存在反复元素
- 给定一个整数数组，判断是否存在反复元素。如果存在一值在数组中呈现至多两次，函数返回 true 。如果数组中每个元素都不雷同，则返回 false 。
剖析：
- 先对数组进行排序
- 而后只须要判断，数组内相邻元素是否反复
- C
int cmp(const void* _a, const void* _b) { int a = *(int*)_a, b = *(int*)_b; return a - b;}bool containsDuplicate(int* nums, int numsSize) { qsort(nums, numsSize, sizeof(int), cmp);//疾速排序 for (int i = 0; i < numsSize - 1; i++) { if (nums[i] == nums[i + 1]) { return true; } } return false;}53.最长子序列和？
- 给定一个整数数组 nums ，找到一个具备最大和的间断子数组（子数组起码蕴含一个元素），返回其最大和。
剖析：
- 动静布局
C
int maxSubArray(int* nums, int numsSize) { int preSum = 0;//之前和 int maxSum = nums[0];//最大和 for (int i = 0; i < numsSize; i++) { preSum = fmax(preSum + nums[i], nums[i]);//取最大值函数 maxSum = fmax(preSum, maxSum); } return maxSum;}
链表
142.环形链表 II
- 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。留神，pos 仅仅是用于标识环的状况，并不会作为参数传递到函数中。 - 阐明：不容许批改给定的链表。
- 剖析：
判断链表是否有环
- 定义slow，fast指针指向head
- slow指针走一步，fast指针走两步
- 若有环的状况下，fast和slow肯定会相遇；若无环，则存在fast->next = null，即跳出循环
如果有环，如何找到这个环的入口
- 设从 头结点-->环形入口结点 的节点数为x
- 环形入口结点-->相遇结点（fast，slow） 的节点数为y
相遇结点-->环形入口结点 的节点数为z
- 相遇时：slow指针走过节点数=x+y，fast=x+y+n(y+z)
n为fast在环内走了n圈才遇到slow，y+z为环内结点个数 - 又fast = slow*2，即fast走过的个数是slow的两倍
--> （x+y）*2 = x+y+n(y+z)
--> （x+y） = n(y+z)
--> x = n(y+z) - y
--> x = (n-1) (y+z) + z
- 相遇时：slow指针走过节点数=x+y，fast=x+y+n(y+z)
- 当n=1，x=z
- 当n>1，则fast指针在环形转n圈之后遇到slow
代码
public ListNode detectCycle(ListNode head) { ListNode fast = head;//定义快慢指针 ListNode slow = head; while( fast!=null && fast.next!=null){ slow = slow.next;//慢指针走一步 fast = fast.next.next;//快指针走两步量 //快慢相遇 if(slow == fast){ ListNode index1 = fast; ListNode index2 = head; while(index1 != index2){ index1 = index1.next; index2 = index2.next; } return index2; //返回入口 } } return null; }- 代码手推图
203.移除链表元素
- 给你一个链表的头节点 head 和一个整数 val
- 请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
迭代
/* 因为可能会遇到头结点满足条件时，要删除头结点 如：val = 2 head(2)-->1-->4-->null ==> dummyHead-->head(2)-->1-->4-->null 则只需将虚构结点dummyHead指向head.next即可 ==> dummyHead head(2)-->1-->4-->null | ↑ |_____________| */
public ListNode removeElements(ListNode head, int val) { ListNode dummyHead = new ListNode();//设置一个虚构头结点 dummyHead.next = head;//将虚构结点指向头结点 ListNode cur = dummyHead; while(cur.next!=null){ if(cur.next.val==val){ cur.next = cur.next.next; }else{ cur = cur.next; } } //当然，返回的最终链表是从虚构结点的下一个地位开始 return dummyHead.next; }递归
public ListNode removeElements2(ListNode head,int val){ if(head==null){ return head; } head.next = removeElements(head.next, val); return head.val==val?head.next : head;//当条件为真时，返回head.next后的链表 }206.反转链表
- 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
剖析：
- 定义三个指针：pre，curr，temp，别离指向head的前驱结点（null），头结点，curr的后继结点。
- 判断当curr非空时进行反转
- 三个指针同时向后挪动即可
/* 如： null 1----->2----->3----->4 ↑ ↑ ↑ pre curr temp 1. 1<-----2 3----->4 ↑ ↑ ↑ pre curr temp 2. 1<-----2<------3 4 ↑ ↑ ↑ pre curr temp 3. 1<-----2<------3<------4 ↑ ↑ ↑ pre curr temp */代码
public ListNode reverseList(ListNode head) { if(head==null){ return null; } ListNode pre = null; ListNode curr = head;//指向头结点 ListNode temp = null;//保留curr的后一个结点 while(curr!=null){ temp = curr.next; curr.next = pre; pre = curr; curr = temp; } return pre; }
707.设计链表
- 设计链表的实现。您能够抉择应用单链表或双链表。单链表中的节点应该具备两个属性：val 和 next。val 是以后节点的值，next 是指向下一个节点的指针/援用。如果要应用双向链表，则还须要一个属性 prev 以批示链表中的上一个节点。假如链表中的所有节点都是 0-index 的。
在链表类中实现这些性能：
- 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 ListNode {int val;ListNode next;ListNode(int x) { val = x; }}class MyLinkedList{/* public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); linkedList.get(1); linkedList.deleteAtIndex(1); linkedList.get(1); } */ int size; ListNode head;//虚构头结点 public int get(int index) { if(index>=size||index<0) return -1;//返回有效索引 ListNode curr = head; for(int i=0;i<index+1;++i){//遍历到index所指结点 curr = curr.next; } return curr.val; } public void addAtHead(int val) { ListNode curr = new ListNode(val); curr.next = head.next; head.next = curr; size++;//长度自增 } public void addAtTail(int val) { ListNode curr = head.next; ListNode addNode = new ListNode(val); while(curr.next!=null){//遍历到链表尾部 curr = curr.next; } curr.next = addNode; size++;//长度自增 } public void addAtIndex(int index, int val) { if(index>size) return ; if(index<0) index = 0; ListNode curr = head; for(int i=0;i<index;i++){//遍历到index下标之前一个结点 curr = curr.next; } ListNode addNode = new ListNode(val); addNode.next = curr.next; curr.next = addNode; size++; } public void deleteAtIndex(int index) { if(index>=size||index<0){//索引有效 return ; } ListNode curr = head; while(index--!=0){//遍历到待删除结点的前一个结点 curr = curr.next; } curr.next = curr.next.next; size--;//长度自减 }}
19.删除链表的倒数第N个结点
- 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
剖析：
- 应用fast和slow指针，fast先走n步，而后两个指针再同时遍历
- 当fast指向null时，则slow所指元素为待删除结点
- 若应用虚构头节点，则当fast指向null时，slow->next为待删除结点，这样便与间接删除
- JAVA
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummyHead = new ListNode(); dummyHead.next = head;//设置虚构头节点 ListNode fast = dummyHead; ListNode slow = dummyHead; int temp = n; while(temp-- > 0){//fast先走n步 fast = fast.next; } while(fast.next!=null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummyHead.next; }
面试题 02.07.链表相交
- 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
剖析：
- 先遍历长度较长的链表，与较短链表开端对齐
如：
a1->a2->a3->c1->c2->c3b1->b2->c1->c2->c3- 而后两个链表同时往后遍历，若节点相等(非值相等)，则返回；否则为null
JAVA
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; int lenA = 0,lenB = 0; while(curA!=null){//求链表A的长度 lenA++; curA = curA.next; } while(curB!=null){//求链表B的长度 lenB++; curB = curB.next; } curA = headA;//让指针从新指向头节点 curB = headB; int gap = lenA-lenB;//长度差值 if(lenB>lenA){//若链表b长度较大 curB = headA; curA = headB; gap = lenB - lenA; } while(gap-->0){//让curA(长度较大)遍历到，与curB(长度较小)同一终点上（开端地位对齐） curA = curA.next; } while(curA!=null){ if(curA==curB){//节点雷同 return curA; } curA = curA.next; curB = curB.next; } return null; }
哈希表
1.两数之和
- 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
- 你能够假如每种输出只会对应一个答案。然而，数组中同一个元素在答案里不能反复呈现。
- 你能够按任意程序返回答案。
剖析：
- 应用map联合存储，key为值，value为下标
- 判断：若map中存在target-num[i]的值(即另一个数的差值)，则返回map.get(target-nums[i])和i的下标；反之则存入map中。这样能够保障元素不反复。
/* 如： nums = [1,2,3,4] target = 5 1. nums[i] = nums[0] = 1 target-nums[0] = 5-1 = 4(无) map.put(nums[0],0)--> map = {{1,0}} 2. nums[i] = nums[1] = 2 target-nums[1] = 5-2 = 3(无) map.put(nums[1],1)--> map = {{1,0},{2,1}} 3. nums[i] = nums[2] = 3 target-nums[2] = 5-3 = 2(有) return new int[]{map.get(2),2} = {1,2}*/
public int[] twoSum(int nums[],int target){ //map的key是值，value是下标 Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(target-nums[i])){ //返回一个下标数组 return new int[]{map.get(target-nums[i]),i}; } map.put(nums[i],i);//将符合条件的数插入表中 } return new int[0]; }15.三数之和
- 给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不反复的三元组。
- 留神：答案中不能够蕴含反复的三元组。
剖析
- 先对数组进行排序，以不便去反复
- 应用双指针left和right，left指向左端（i+1），right指向右端（length-1）
- 存在三个指针i、left、right，其中后两个指针向对方聚拢，则可进行判断三个指针所指数的和
public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ls = new ArrayList<List<Integer>>(); //数组排序 Arrays.sort(nums); for(int i=0;i<nums.length;i++){ if(nums[i]>0){ return ls; } //去重办法 if(i>0&&nums[i]==nums[i-1]){ continue; } int left = i+1;//左指针 int right = nums.length -1;//右指针 while(left<right){ if(nums[i]+nums[left]+nums[right]>0){//当数值大于零，则示意数较大 right--; }else if(nums[i]+nums[left]+nums[right]<0){//同理，数值较小 left++; }else{ List<Integer> result = new ArrayList<Integer>(); result.add(nums[i]); result.add(nums[left]); result.add(nums[right]); ls.add(result);//增加一个三元组 while(left<right&&nums[right]==nums[right-1]) right--; while(left<right&&nums[left]==nums[left+1]) left++; //双指针同时聚拢 right--; left++; } } } return ls; }202.高兴数
- 编写一个算法来判断一个数 n 是不是高兴数。
- 「高兴数」定义为：
- 对于一个正整数，每一次将该数替换为它每个地位上的数字的平方和。
- 而后反复这个过程直到这个数变为 1，也可能是 有限循环 但始终变不到 1。
- 如果 能够变为 1，那么这个数就是高兴数。
如果 n 是高兴数就返回 true ；不是，则返回 false 。 剖析：
- 将每一次计算的平方和存入HashSet中
- 判断：如果存在反复的sum，则返回false;反之，返回true
public boolean isHappy(int n) { Set<Integer> set = new HashSet<Integer>(); while(true){ int sum = getSum(n);//每一次都会更新sum值 if(sum==1){ return true; } if(set.contains(sum)){//当汇合中存在反复的sum时，此数不是高兴数 return false; }else { set.add(sum); } n = sum; } } //取数值各个位上的复数之和 int getSum(int n){ int sum = 0; while(n>0){ sum += (n%10) * (n%10);//求平方和 n /= 10; } return sum; }
242.无效字母的异位词
- 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
剖析：
- 异位词：字母雷同，排列程序不同，异位词的长度也肯定相等
- 定义record数组，记录串s字符呈现的次数，数组大小为26
遍历串s，记录字母呈现的次数(+1)，arr_s[i] - 'a' 是映射出字母的地位
- 如 'b' - 'a' = 1，即b的下标为1，同理a的下标为0
- 同理，遍历串t，记录字符呈现的次数(-1)
- 判断，record数组元素全为0，则为异位词；反之不是
- 代码
public boolean isAnagram(String s, String t) { if(s.length()!=t.length()){//比拟长度 return false; } int[] record = new int[26];//定义数组，记录串s中字符的次数 char[] arr_s = s.toCharArray(); for(int i=0;i<arr_s.length;i++){ record[arr_s[i] - 'a']++;//映射出字符呈现的次数 /* 如： arr[0] = 'b'; --> record[arr[i] - 'a'] = record['b' - 'a'] = record[1]; record[1]++ = 1; 、 即呈现b在串s中呈现一次，b的下标为1， 同理，a的下标为0 */ } char[] arr_t = t.toCharArray(); for(int i=0;i<arr_t.length;i++){ record[arr_t[i] - 'a']--;//映射出串t中呈现的字符，随之映射在record表中，并-1 } for(int i=0;i<26;i++){ if(record[i] != 0){ //判断数组中若存在不为零的次数，则不是异位词 return false; } } //record中所有元素都为零，则两遍映射相对消，即为异位词 return true; }304.两个数组的交加
- 给定两个数组，编写一个函数来计算它们的交加。
- 示例 1：
输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2] - 示例 2：
输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[9,4] - 输入后果中的每个元素肯定是惟一的。
咱们能够不思考输入后果的程序。
public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); //将数组别离装入汇合中 for(int num:nums1){ set1.add(num); } for(int num:nums2){ set2.add(num); } return getIntersection(set1,set2);}public int[] getIntersection(Set<Integer> set1,Set<Integer> set2){ if(set1.size()>set2.size()){//遍历汇合长度小的那一个 return getIntersection(set2,set1); } Set<Integer> intersectionSet = new HashSet<Integer>(); for(int num:set1){//判断是否有雷同数字 if(set2.contains(num)){ intersectionSet.add(num); } } //将汇合存入数组并返回 int[] intersection = new int[intersectionSet.size()]; int index = 0; for(int num:intersectionSet){ intersection[index++] = num; } return intersection;}
383.赎金信
- 给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 外面的字符形成。如果能够形成，返回 true ；否则返回 false。
- (题目阐明：为了不裸露赎金信字迹，要从杂志上搜寻各个须要的字母，组成单词来表白意思。杂志字符串中的每个字符只能在赎金信字符串中应用一次。)
剖析：
- 建设两个长度为26的数组，将r和m字符串中字母的呈现次数映射到数组中
- 判断：如果r[i]>m[i]，则阐明r不能由m表出
public boolean canConstruct(String ransomNote, String magazine) { int[] ransomNote_record = new int[26];//默认值为0 int[] magazine_record = new int[26]; for(int i=0;i<ransomNote.length();i++){//映射字母表 ransomNote_record[ransomNote.charAt(i)-'a']++; } for(int j=0;j<magazine.length();j++){ magazine_record[magazine.charAt(j)-'a']++; } for(int i=0;i<ransomNote_record.length;i++){//比拟存入的字母次数 //如果r中字母的次数大于m对应的字母次数，则r不能由m表出 if(ransomNote_record[i]>magazine_record[i]){ return false; } } return true; }
454.四数相加 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 。所有整数的范畴在 -228 到 228 - 1 之间，最终后果不会超过 231 - 1 。
剖析：
- 用map，先遍历数组A、B，key为A+B的和，value记录其和呈现的次数
- 再遍历C、D，当原map存在0-[c+d]（c、d为C、D中的元素）的元素时，记录次数即可
- 工夫与空间都为o(n^2)
/* 如： nums1=[1,2] nums2=[2,1] nums3=[-1,1] nums4=[-2,1] map --> {{3,2},{2,1},{4,1}} -->即3呈现两次，2呈现一次，4呈现一次 1. 0-(-1+-2) = 3 -->true temp += 2 = 2 2. 0-(-1+1) = 0 -->false 3. 0-(1-2) = 1 -->true temp += 1 = 3 ......*/
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { //定义map，key寄存a+b和，value寄存a+b呈现的次数 Map<Integer,Integer> map = new HashMap<Integer,Integer>(); //遍历前两个数组 for(int a:nums1){ for(int b:nums2){ //判断a+b是否呈现过：若呈现过则+1；反之，从0开始计数 int count = map.containsKey(a+b) ? map.get(a+b):0; map.put(a+b,count+1); } } int temp = 0;//记录a+b+c+d=0的次数 //遍历后两个数组 for(int c:nums3){ for(int d:nums4){ if(map.containsKey(0-(c+d))){ temp += map.get(0-(c+d));//当找到a+b+c+d=0，则记录相应次数 } } } return temp; }219.存在反复元素 II
- 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
剖析：
- 应用滑动窗口，窗口大小不大于k
- 顺次遍历数组，当窗口长度 >k 时，删除第 i-k 个元素，该元素为以后滑动窗口第一个元素
- JAVA
public boolean containsNearbyDuplicate(int[] nums, int k) { Set<Integer> set = new HashSet<Integer>(); for(int i=0;i<nums.length;i++){ if(set.contains(nums[i])){//存在反复元素 return true; } set.add(nums[i]);//增加元素 if(set.size()>k){//滑动窗口个数>k set.remove(nums[i-k]);//删除元素，i-k为以后第一个元素 } } return false; }字符串
151.翻转字符串里的单词
- 给你一个字符串 s ，一一翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中应用至多一个空格将字符串中的 单词 分隔开。 - 请你返回一个翻转 s 中单词程序并用单个空格相连的字符串。
- 阐明：
输出字符串 s 能够在后面、前面或者单词间蕴含多余的空格。
翻转后单词间该当仅用一个空格分隔。
翻转后的字符串中不应蕴含额定的空格。 - 法一：利用现有办法
public String reverseWords(String s) { //去除结尾和开端的空白字符 s = s.trim(); //正则匹配间断的空白字符作为分隔符切割 List<String> wordList = Arrays.asList(s.split("\\s+")); Collections.reverse(wordList); //依照指定分隔符重组字符串 return String.join(" ",wordList); }- 法二：利用自定义办法
//利用自定义办法public String reverseWords_2(String s) { StringBuilder sb = trimSpaces(s); // 翻转字符串 reverse(sb, 0, sb.length() - 1); // 翻转每个单词 reverseEachWord(sb); return sb.toString();}//去除空格public StringBuilder trimSpaces(String s){ int left = 0,right = s.length()-1; // 去除首部空格 while(left <= right && s.charAt(left)==' '){ ++left;//左指针往右边聚拢 } //去掉尾部空格 while(left<=right && s.charAt(right)==' '){ --right;//右指针往左边聚拢 } //去除多余的空白字符 StringBuilder sb = new StringBuilder(); while(left <= right){ char c = s.charAt(left); if(c != ' '){ sb.append(c); }else if(sb.charAt(sb.length()-1)!=' '){ sb.append(c); } ++left; } return sb;}//反转public void reverse(StringBuilder sb,int left,int right){ while(left < right){ char temp = sb.charAt(left); sb.setCharAt(left++,sb.charAt(right));//首尾调换 sb.setCharAt(right--,temp); }}//反转每个字母public void reverseEachWord(StringBuilder sb){ int n = sb.length(); int start = 0,end = 0; while (start < n) { // 循环至单词的开端 while (end < n && sb.charAt(end) != ' ') { ++end; } // 翻转单词 reverse(sb, start, end - 1); // 更新start，去找下一个单词 start = end + 1; ++end; }}344.字符串反转
- 编写一个函数，其作用是将输出的字符串反转过去。输出字符串以字符数组 char[] 的模式给出。
- 不要给另外的数组调配额定的空间，你必须原地批改输出数组、应用 O(1) 的额定空间解决这一问题。
- 你能够假如数组中的所有字符都是 ASCII 码表中的可打印字符。
public void reverseString(char[] s) { for(int i=0,j=s.length-1;i<j;i++,j--){ char temp = s[i]; s[i] = s[j]; s[j] = temp; } System.out.println(s);}541.字符串反转II
给定一个字符串 s 和一个整数 k，你须要对从字符串结尾算起的每隔 2k 个字符的前 k 个字符进行反转。
- 如果残余字符少于 k 个，则将残余字符全副反转。
- 如果残余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符放弃原样。
- 示例:
输出: s = "abcdefg", k = 2
输入: "bacdfeg" 剖析：
- i作i+=(2*k)的增长速度来遍历
- 判断两种状况即可
public String reverseStr(String s, int k) {for(int i=0;i<s.length();i+=(2*k)){ //1.每隔2k个字符，对前k个字符进行反转 //2.残余字符<2k但>=k，则反转前k个字符 if(i+k<=s.length()){ s = reverse(s,i,i+k-1); continue; } //3.残余字符<k，则将残余字符全副进行反转 s = reverse(s,i,s.length()-1);}return s;}//反转下标为a到b的字符public String reverse(String s,int start,int end){char[] ch = s.toCharArray();for(int i = start,j = end;i<j;i++,j--){ char temp = ch[i]; ch[i] = ch[j]; ch[j] = temp;}return new String(ch);}05.替换空格（剑指offer）
- 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
剖析：
- 建设一个字符数组，其长度为串s的三倍，以确保能装入替换后的字符串
- size用来计算替换后的字符串真正的长度
- i=0开始遍历字符串：当判断到有空格时，顺次存入%20；反之，失常赋值。
public String replaceSpace(String s) { //建设字符数组，确保能装入替换后的容量 char[] ch = new char[s.length()*3]; int size = 0;//计算替换后的字符串长度 for(int i=0;i<s.length();i++){ char c = s.charAt(i); if(c == ' '){//当判断为空格时，顺次存入 ch[size++] = '%'; ch[size++] = '2'; ch[size++] = '0'; }else{//反之，失常赋值 ch[size++] = c; } } //从新初始化新的字符串，该字符串长度为替换后的长度 String result = new String(ch,0,size); return result; }
58.II 左旋转字符串(剑指offer)
- 字符串的左旋转操作是把字符串后面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的性能。
- 比方，输出字符串"abcdefg"和数字2，该函数将返回左旋转两位失去的后果"cdefgab"。
public String reverseLeftWords(String s, int n) { int len = s.length(); char[] arr = new char[s.length()]; //赋值下标为k之前的字符 for(int i=s.length()-n;i<len;i++){ arr[i] = s.charAt(i-len+n); } //赋值下标为k以及k前面的字符 for(int i=n;i<len;i++){ arr[i-n] = s.charAt(i); } String result = new String(arr,0,len); return result; }28.实现 strStr()
- 实现 strStr() 函数。给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串呈现的第一个地位（下标从 0 开始）。如果不存在，则返回 -1 。
JAVA
public int strStr(String haystack, String needle) { if(needle==null){ return -1; } int i=0,j = 0,k=0; while(i<haystack.length() && j<needle.length()){ if(haystack.charAt(i) == needle.charAt(j)){ i++; j++; }else{ j=0; i = ++k; } } if(j>=needle.length()){ return k; }else{ return -1; } }
栈与队列
232.用栈实现队列
- 请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的开端
- int pop() 从队列的结尾移除并返回元素
- int peek() 返回队列结尾的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
剖析：
- 用两个栈来实现队列：一个输出栈和一个输入栈
- 先将元素导入输出栈，如:1 2 3导入后为 (栈顶)←3 2 1←(栈底)
- 再将元素导入输入栈，如:←3 2 1←导入后为 (栈顶)←1 2 3←(栈底)
- 从输入栈Pop则有：1 2 3，从而实现先进先出
public class MyQueue { Stack<Integer> stIn;//用于输出元素的栈 Stack<Integer> stOut;//用于输入元素的栈 //初始化 public MyQueue() { stIn = new Stack<Integer>(); stOut = new Stack<Integer>(); } //模仿入队 public void push(int x) { stIn.push(x);//进栈 } //模拟出队 public int pop() { // 当stOut输入栈为空时，才让stIn中的元素输出 if(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.pop()); } } return stOut.pop();//返回栈顶元素，并删除 } //返回队列头元素 public int peek() { //与模拟出队同理 if(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.pop()); } } return stOut.peek();//返回栈顶元素，但不删除 } //判断队列是否为空 public boolean empty() { //当两个栈都为空时，则队列为空 return stIn.empty() && stOut.empty(); }}225.用队列实现栈
- 请你仅应用两个队列实现一个后入先出（LIFO）的栈，并反对一般栈的全副四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
剖析：
- 应用一个队列，先失常入队
- 再将队列，从队头元素开始，循环插入队尾
- 则能够将队列倒置，造成先进后出的规定
//252.用队列实现栈public class MyStack { Deque<Integer> dq; /** Initialize your data structure here. */ public MyStack() { dq = new LinkedList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { int size = dq.size(); dq.offer(x);//插入队尾 for(int i=0;i<size;i++){ dq.offer(dq.poll());//poll返回最先进入的那个元素，即对头元素 //将这个元素插入队尾 //此办法就是将原始队列倒置，已形成先进后出的准则 } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return dq.poll();//返回队头元素 } /** Get the top element. */ public int top() { return dq.peek();//返回第一个元素，即以后队头元素 } /** Returns whether the stack is empty. */ public boolean empty() { return dq.isEmpty(); }}20.无效的括号
- 给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否无效。
无效字符串需满足：
- 左括号必须用雷同类型的右括号闭合。
- 左括号必须以正确的程序闭合。
剖析：
三种不匹配的状况
左方向的括号多余
~~(~~ [ { } ] ( )括号没有多余，但括号类型没有匹配上
( ~~[~~ { } ~~}~~ )右方向的括号多余
( [ { } ] ) ~~)~~ ~~)~~
三种判断形式
- 第一种状况：已遍历完，但栈不空，则阐明存在多余右括号
- 第二种状况，当匹配右括号时，栈中没有发现匹配的字符
- 第三种状况，栈已空，但串s未遍历完，则阐明存在多余的左括号
Java
public boolean isValid(String s) { Stack<Character> st = new Stack<Character>(); for(int i=0;i<s.length();i++){ //这里入栈右括号是不便间接匹配串s中是否有雷同的括号 if(s.charAt(i)=='(') st.push(')'); else if(s.charAt(i)=='{') st.push('}'); else if(s.charAt(i)=='[') st.push(']'); //第三种状况，栈已空，但串s未遍历完，则阐明存在多余的左括号 //第二种状况，当匹配右括号时，栈中没有发现匹配的字符 else if(st.empty() || st.peek()!=s.charAt(i)) { return false; } /* 隐含的判断胜利： s.charAt(i)=='(' 或 s.charAt(i)=='{' 或 s.charAt(i)=='[' */ else st.pop();} //第一种状况：已遍历完，但栈不空，则阐明存在多余右括号 return st.empty();}1047. 删除字符串中的所有相邻反复项
- 给出由小写字母组成的字符串 S，反复项删除操作会抉择两个相邻且雷同的字母，并删除它们。
- 在 S 上重复执行反复项删除操作，直到无奈持续删除。
- 在实现所有反复项删除操作后返回最终的字符串。答案保障惟一。
剖析：
- 定义一个栈，当判断栈顶元素与该遍历到的元素雷同时，出栈
- 最初再反转即可
public String removeDuplicates(String s){ Stack<Character> st = new Stack<Character>(); for(int i=0;i<s.length();i++){ if(!st.isEmpty()){ //判断是否有相邻元素 if(st.peek()==s.charAt(i)){ st.pop(); continue; } } st.push(s.charAt(i));//入栈 } //栈无元素则返回空 if(st.isEmpty()){ return ""; } char[] ch = new char[st.size()]; //反转 for(int i=ch.length-1;i>=0;i--){//留神：不能用栈的长度，因为每次出栈后会变动 ch[i] = st.pop(); } //重造字符串 String result = new String(ch, 0, ch.length); return result;}
150.逆波兰表达式求值
- 依据 逆波兰表示法，求表达式的值。
- 无效的算符包含 +、-、*、/ 。每个运算对象能够是整数，也能够是另一个逆波兰表达式。
阐明：
- 整数除法只保留整数局部。
- 给定逆波兰表达式总是无效的。换句话说，表达式总会得出无效数值且不存在除数为 0 的状况。
剖析：
- 逆波兰式就是后缀，将后缀转为中断
顺次对数字入栈：
- 当呈现算术符号，出栈两个数
- 替换两数程序(保障正确的程序)
- 将两数与该符号作运算，后果入栈
public int evalRPN(String[] tokens) { Deque<Integer> dq = new LinkedList<Integer>(); for(int i=0;i<tokens.length;i++){ //判断是否为算术符 if(tokens[i].equals("+")||tokens[i].equals("-") ||tokens[i].equals("*")||tokens[i].equals("/")){ int a = dq.pop(); int b = dq.pop(); switch (tokens[i]){ case "+": dq.push(b+a); break; case "-": dq.push(b-a); break; case "*": dq.push(b*a); break; case "/": dq.push(b/a); break; default: } }else{ dq.push(Integer.parseInt(tokens[i]));//字符串转化为数字 } } return dq.peek();}二叉树
递归详解
递归三要素
- 确定递归函数的参数和返回值：即确定递归中的参数，明确每次递归的返回值。
- 确定终止条件：即保障不会栈溢出。
- 确定单层递归的逻辑：确定每一层递归须要解决的信息。
144.二叉树的前序遍历
剖析：
- 前序遍历又称先根，即依照根、左、右的程序来遍历二叉树
C(递归)
void preorder(TreeNode *root,int *res,int *resSize) { if (root != NULL) { //用数组寄存值 res[(*resSize)++] = root->val;//数组自增 preorder(root->left, res, resSize); preorder(root->right, res, resSize); } }int* preorderTraversal(struct TreeNode* root, int* returnSize) { int *res = malloc(sizeof(int) * 2000); *returnSize = 0; preorder(root, res, returnSize); return res;}C(非递归)
int* preorderTraversal(struct TreeNode* root, int* returnSize) { int *result = (int*)malloc(sizeof(int) * 2000);//生成一个后果数组 *returnSize = 0; if (root == NULL) { return result; } struct TreeNode *st[2000];//定义一个栈 struct TreeNode *p = root;//定义一个指针 int top = -1;//初始化栈 st[++top] = root;//入栈根节点 while (top != -1) { p = st[top--];//指针指向以后需遍历的结点(根左右) result[(*returnSize)++] = p->val;//入后果数组 if (p->right != NULL) {//右孩子存在 st[++top] = p->right; } if (p->left != NULL) {//左孩子存在 st[++top] = p->left; } } return result;}
94.二叉树的中序遍历
C(递归)
void inorder(struct TreeNode* root, int *res, int *resSize) { if (root == NULL) { return; } inorder(root->left, res, resSize); res[(*resSize)++] = root->val; inorder(root->right, res, resSize);}int *inorderTraversal(struct TreeNode *root, int *returnSize) { int *res = (int*)malloc(sizeof(int) * 2000); *returnSize = 0; inorder(root, res, returnSize); return res;}- C(非递归)
int* inorderTraversal(struct TreeNode* root, int* returnSize) { int *result = (int*)malloc(sizeof(int) * 2000);//生成一个后果数组 *returnSize = 0; if (root == NULL) { return result; } struct TreeNode *st[2000];//定义一个栈 struct TreeNode *p;//定义一个指针 int top = -1;//初始化栈的指针 p = root;//p指向根节点 while (top != -1 || p != NULL) {//有可能呈现栈空但树未遍历完的状况 while (p != NULL) {//左孩子始终入栈 st[++top] = p; p = p->left; } if (top != -1) {//栈不空时，输入 p = st[top--]; result[(*returnSize)++] = p->val; p = p->right; } } return result;}145.二叉树的后序遍历
- C
void postorder(TreeNode *root, int *res, int *resSize) { if (root == NULL) { return; } postorder(root->left, res, resSize); postorder(root->right, res, resSize); res[(*resSize)++] = root->val;}int* postorderTraversal(struct TreeNode* root, int* returnSize) { int *res = (int*)malloc(sizeof(int) * 2000); *returnSize = 0; postorder(root, res, returnSize); return res;}- C(迭代)
int* postorderTraversal(struct TreeNode* root, int* returnSize) { int *result = (int*)malloc(sizeof(int) * 2000);//后果数组 *returnSize = 0; if (root = NULL) { return result; } struct TreeNode *stack1[2000]; int top1 = 1; struct TreeNode *stack2[2000]; int top2 = -1; struct TreeNode *p = NULL; stack1[++top1] = root;//根节点入栈 while (top1 != -1) { p = stack1[top1--];//指向 stack2[++top2] = p;//再入 if (p->left != NULL) {//反向入栈 stack1[++top1] = p->right; } if (p->right != NULL) { stack1[++top1] = p->left; } } while (top2 != -1) { //再次出栈即为后序遍历 p = stack2[top2--]; result[(*returnSize)++] = p->val; } return result;}226.翻转二叉树
- 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
法一：
- 定义一个结点，作为两头变量
- 顺次递归替换左右子树，当为空时完结
- JAVA
public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } TreeNode temp = root.left; root.left = root.right; root.right = temp; invertTree(root.left); invertTree(root.right); return root; }法二
- 定义两个结点left和right
- 递归遍历，让left指向树的右子树，让right指向树的左子树
- 再让原根结点指向left和right即可
- JAVA
public TreeNode invertTree(TreeNode root) { if(root == null){ return null; } TreeNode left = invertTree(root.right); TreeNode right = invertTree(root.left); root.left = left; root.right = right; return root; }