代码组件库

创始人

2024-06-02 06:45:13

0次

学习精要：路线-思想-组件
算法思想：容器-算法-容器

数据装配

ListListListToStringStringString

public class ListToString {public static void main(String[] args) {List integers = new ArrayList<>();String str="";for(int item=0;itemstr+=integers.get(item);}}
}

StringStringStringTointintint

public class floatToString {public static void main(String[] args) {String str="123456";for(int i=0;iint num = str.charAt(i)-'0';}}
}

数组

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = (right - left) / 2 + left;int num = nums[mid];if (num == target) {return mid;} else if (num > target) {right = mid - 1;} else {left = mid + 1;}}return -1;}
}

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

class Solution {public int removeElement(int[] nums, int val) {int n = nums.length;int left = 0;for (int right = 0; right < n; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;}
}

有序数组的平方长度最小的子数组

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

class Solution {public int[] sortedSquares(int[] nums) {int[] ans = new int[nums.length];for (int i = 0; i < nums.length; ++i) {ans[i] = nums[i] * nums[i];}Arrays.sort(ans);return ans;}
}

螺旋矩阵II

给你一个正整数 n ，生成一个包含 1 到 n2n^2n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

class Solution {public int[][] generateMatrix(int n) {int maxNum = n * n;int curNum = 1;int[][] matrix = new int[n][n];int row = 0, column = 0;int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上int directionIndex = 0;while (curNum <= maxNum) {matrix[row][column] = curNum;curNum++;int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向}row = row + directions[directionIndex][0];column = column + directions[directionIndex][1];}return matrix;}
}

数组:有多少小于当前数字的数字数组:有效的山脉数组

数组:独一无二的出现次数数组:移动零

数组:旋转数组

数组:寻找数组的中心索引

数组:在排序数组中查找元素的第一个和最后一个位置

数组:按奇偶排序数组II

数组:搜索插入位置

链表

移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}head.next = removeElements(head.next, val);return head.val == val ? head.next : head;}
}
//时间复杂度:o(n),空间复杂度O(n)

设计链表翻转链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点。

//单链表
class ListNode {int val;ListNode next;public ListNode(int val) {this.val = val;}
}class MyLinkedList {int size;ListNode head;public MyLinkedList() {size = 0;head = new ListNode(0);}public int get(int index) {if (index < 0 || index >= size) {return -1;}ListNode cur = head;for (int i = 0; i <= index; i++) {cur = cur.next;}return cur.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;}index = Math.max(0, index);size++;ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}ListNode toAdd = new ListNode(val);toAdd.next = pred.next;pred.next = toAdd;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}pred.next = pred.next.next;}
}

class MyLinkedList {int size;ListNode head;ListNode tail;public MyLinkedList() {size = 0;head = new ListNode(0);tail = new ListNode(0);head.next = tail;tail.prev = head;}public int get(int index) {if (index < 0 || index >= size) {return -1;}ListNode curr;if (index + 1 < size - index) {curr = head;for (int i = 0; i <= index; i++) {curr = curr.next;}} else {curr = tail;for (int i = 0; i < size - index; i++) {curr = curr.prev;}}return curr.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;}index = Math.max(0, index);ListNode pred, succ;if (index < size - index) {pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}succ = pred.next;} else {succ = tail;for (int i = 0; i < size - index; i++) {succ = succ.prev;}pred = succ.prev;}size++;ListNode toAdd = new ListNode(val);toAdd.prev = pred;toAdd.next = succ;pred.next = toAdd;succ.prev = toAdd;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode pred, succ;if (index < size - index) {pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}succ = pred.next.next;} else {succ = tail;for (int i = 0; i < size - index - 1; i++) {succ = succ.prev;}pred = succ.prev.prev;}size--;pred.next = succ;succ.prev = pred;}
}class ListNode {int val;ListNode next;ListNode prev;public ListNode(int val) {this.val = val;}
}

两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = head.next;head.next = swapPairs(newHead.next);newHead.next = head;return newHead;}
}

删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int length = getLength(head);ListNode cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur.next;}cur.next = cur.next.next;ListNode ans = dummy.next;return ans;}public int getLength(ListNode head) {int length = 0;while (head != null) {++length;head = head.next;}return length;}
}
//时间复杂度：o(L),空间复杂度o(1)

链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set visited = new HashSet();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;}
}

环形链表ll

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode pos = head;Set visited = new HashSet();while (pos != null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos = pos.next;}return null;}
}

哈希表

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char[] str1 = s.toCharArray();char[] str2 = t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);}
}

两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set set1= new HashSet();Set set2= new HashSet();for(int i:nums1){set1.add(i);}for(int i:nums2){if(set1.contains(i)){set2.add(i);}}return set2.stream().mapToInt(x->x).toArray(); }
}

快乐数

编写一个算法来判断一个数 n 是不是快乐数。
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。

class Solution {private int getNext(int n) {int totalSum = 0;while (n > 0) {int d = n % 10;n = n / 10;totalSum += d * d;}return totalSum;}public boolean isHappy(int n) {Set seen = new HashSet<>();while (n != 1 && !seen.contains(n)) {seen.add(n);n = getNext(n);}return n == 1;}
}

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

class Solution {public int[] twoSum(int[] nums, int target) {Map hashtable = new HashMap();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}

四数相加ll

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

class Solution {public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {Map countAB = new HashMap();for (int u : A) {for (int v : B) {countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);}}int ans = 0;for (int u : C) {for (int v : D) {if (countAB.containsKey(-u - v)) {ans += countAB.get(-u - v);}}}return ans;}
}

赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()) {return false;}int[] cnt = new int[26];for (char c : magazine.toCharArray()) {cnt[c - 'a']++;}for (char c : ransomNote.toCharArray()) {cnt[c - 'a']--;if(cnt[c - 'a'] < 0) {return false;}}return true;}
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

class Solution {public List> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List> ans = new ArrayList>();// 枚举 afor (int first = 0; first < n; ++first) {// 需要和上一次枚举的数不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third = n - 1;int target = -nums[first];// 枚举 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚举的数不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保证 b 的指针在 c 的指针的左侧while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 bbreak;}if (nums[second] + nums[third] == target) {List list = new ArrayList();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}

四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

class Solution {public List> fourSum(int[] nums, int target) {List> quadruplets = new ArrayList>();if (nums == null || nums.length < 4) {return quadruplets;}Arrays.sort(nums);int length = nums.length;for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
}

字符串

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

class Solution {public void reverseString(char[] s) {int n = s.length;for (int left = 0, right = n - 1; left < right; ++left, --right) {char tmp = s[left];s[left] = s[right];s[right] = tmp;}}
}

反转字符串Ⅱ

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

class Solution {public String reverseStr(String s, int k) {int n = s.length();char[] arr = s.toCharArray();for (int i = 0; i < n; i += 2 * k) {reverse(arr, i, Math.min(i + k, n) - 1);}return new String(arr);}public void reverse(char[] arr, int left, int right) {while (left < right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}
}

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"

class Solution {public String replaceSpace(String s) {int length = s.length();char[] array = new char[length * 3];int size = 0;for (int i = 0; i < length; i++) {char c = s.charAt(i);if (c == ' ') {array[size++] = '%';array[size++] = '2';array[size++] = '0';} else {array[size++] = c;}}String newStr = new String(array, 0, size);return newStr;}
}

翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。
输入：s = “the sky is blue”
输出：“blue is sky the”

class Solution {public String reverseWords(String s) {// 除去开头和末尾的空白字符s = s.trim();// 正则匹配连续的空白字符作为分隔符分割List wordList = Arrays.asList(s.split("\\s+"));Collections.reverse(wordList);return String.join(" ", wordList);}
}

左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

class Solution {public String reverseLeftWords(String s, int n) {return s.substring(n, s.length()) + s.substring(0, n);}
}

实现字符串匹配

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

//KMP算法
class Solution {public int strStr(String haystack, String needle) {int n = haystack.length(), m = needle.length();if (m == 0) {return 0;}int[] pi = new int[m];for (int i = 1, j = 0; i < m; i++) {while (j > 0 && needle.charAt(i) != needle.charAt(j)) {j = pi[j - 1];}if (needle.charAt(i) == needle.charAt(j)) {j++;}pi[i] = j;}for (int i = 0, j = 0; i < n; i++) {while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {j = pi[j - 1];}if (haystack.charAt(i) == needle.charAt(j)) {j++;}if (j == m) {return i - m + 1;}}return -1;}
}

重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

class Solution {public boolean repeatedSubstringPattern(String s) {return (s + s).indexOf(s, 1) != s.length();}
}

双指针算法

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

class Solution {public int removeElement(int[] nums, int val) {int n = nums.length;int left = 0;for (int right = 0; right < n; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;}
}

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

class Solution {public void reverseString(char[] s) {int n = s.length;for (int left = 0, right = n - 1; left < right; ++left, --right) {char tmp = s[left];s[left] = s[right];s[right] = tmp;}}
}

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

class Solution {public String replaceSpace(String s) {int length = s.length();char[] array = new char[length * 3];int size = 0;for (int i = 0; i < length; i++) {char c = s.charAt(i);if (c == ' ') {array[size++] = '%';array[size++] = '2';array[size++] = '0';} else {array[size++] = c;}}String newStr = new String(array, 0, size);return newStr;}
}

翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。

class Solution {public String reverseWords(String s) {// 除去开头和末尾的空白字符s = s.trim();// 正则匹配连续的空白字符作为分隔符分割List wordList = Arrays.asList(s.split("\\s+"));Collections.reverse(wordList);return String.join(" ", wordList);}
}

翻转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int length = getLength(head);ListNode cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur.next;}cur.next = cur.next.next;ListNode ans = dummy.next;return ans;}public int getLength(ListNode head) {int length = 0;while (head != null) {++length;head = head.next;}return length;}
}

链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set visited = new HashSet();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;}
}

环形链表lI

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode pos = head;Set visited = new HashSet();while (pos != null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos = pos.next;}return null;}
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

class Solution {public List> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List> ans = new ArrayList>();// 枚举 afor (int first = 0; first < n; ++first) {// 需要和上一次枚举的数不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third = n - 1;int target = -nums[first];// 枚举 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚举的数不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保证 b 的指针在 c 的指针的左侧while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 bbreak;}if (nums[second] + nums[third] == target) {List list = new ArrayList();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}

四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

class Solution {public List> fourSum(int[] nums, int target) {List> quadruplets = new ArrayList>();if (nums == null || nums.length < 4) {return quadruplets;}Arrays.sort(nums);int length = nums.length;for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
}

栈和队列

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

class MyQueue {Deque inStack;Deque outStack;public MyQueue() {inStack = new ArrayDeque();outStack = new ArrayDeque();}public void push(int x) {inStack.push(x);}public int pop() {if (outStack.isEmpty()) {in2out();}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {in2out();}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}private void in2out() {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}
}

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

class MyStack {Queue queue1;Queue queue2;/** Initialize your data structure here. */public MyStack() {queue1 = new LinkedList();queue2 = new LinkedList();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue temp = queue1;queue1 = queue2;queue2 = temp;}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll();}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}

有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

class Solution {public boolean isValid(String s) {int n = s.length();if (n % 2 == 1) {return false;}Map pairs = new HashMap() {{put(')', '(');put(']', '[');put('}', '{');}};Deque stack = new LinkedList();for (int i = 0; i < n; i++) {char ch = s.charAt(i);if (pairs.containsKey(ch)) {if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {return false;}stack.pop();} else {stack.push(ch);}}return stack.isEmpty();}
}
//时间复杂度o(n),空间复杂度o(n+|E|),E表示字符集

删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
输入：“abbaca”
输出：“ca”

class Solution {public String removeDuplicates(String s) {StringBuffer stack = new StringBuffer();int top = -1;for (int i = 0; i < s.length(); ++i) {char ch = s.charAt(i);if (top >= 0 && stack.charAt(top) == ch) {stack.deleteCharAt(top);--top;} else {stack.append(ch);++top;}}return stack.toString();}
}

通过栈进行算数运算

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9

class Solution {public int evalRPN(String[] tokens) {Deque stack = new LinkedList();int n = tokens.length;for (int i = 0; i < n; i++) {String token = tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 = stack.pop();int num1 = stack.pop();switch (token) {case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;default:}}}return stack.pop();}public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));}
}
//时间复杂度o(n),空间复杂度o(n)

滑动窗最大值前K个高频元素

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;PriorityQueue pq = new PriorityQueue(new Comparator() {public int compare(int[] pair1, int[] pair2) {return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];}});for (int i = 0; i < k; ++i) {pq.offer(new int[]{nums[i], i});}int[] ans = new int[n - k + 1];ans[0] = pq.peek()[0];for (int i = k; i < n; ++i) {pq.offer(new int[]{nums[i], i});while (pq.peek()[1] <= i - k) {pq.poll();}ans[i - k + 1] = pq.peek()[0];}return ans;}
}
//时间复杂度：o(nlogn)，空间复杂度o(n)

前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

class Solution {public int[] topKFrequent(int[] nums, int k) {Map occurrences = new HashMap();for (int num : nums) {occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数PriorityQueue queue = new PriorityQueue(new Comparator() {public int compare(int[] m, int[] n) {return m[1] - n[1];}});for (Map.Entry entry : occurrences.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {if (queue.peek()[1] < count) {queue.poll();queue.offer(new int[]{num, count});}} else {queue.offer(new int[]{num, count});}}int[] ret = new int[k];for (int i = 0; i < k; ++i) {ret[i] = queue.poll()[0];}return ret;}
}
//时间复杂度：o(nlogn)，空间复杂度o(n)

二叉树

2.二叉树的递归遍历

3.二叉树的迭代遍历

4.二叉树的统——送代法

5.二叉树的层序遍历

6.翻转二叉树

7.二叉树周末总结

8.对称二叉树

9.二叉树的最大深度

10.二叉树的最小深度

11.完全二叉树的节点个数

12.平衡二叉树

13.二叉树的所有路径

14.二叉树周末总结

15.左叶子之和

16.找树左下角的值

17.路径总和

18.从中序与后序遍历序列构造二叉树

19.最大二叉树

20.二叉树周末总结

21.合并二叉树

22.二叉搜索树中的搜索

23.验证二叉搜索树

24.二叉搜索树的最小绝对差

25.二叉搜索树中的众数

26.二叉树的最近公共祖先

27.二叉树周末总结

28.二叉搜索树的最近公共祖先

29.二叉搜索树中的插入操作

30.删除二叉搜索树中的节点

31.修剪二叉搜索树

32.将有序数组转换为二叉搜索树

33.把二叉搜索树转换为累加树

回溯算法

2.组合问题

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

class Solution {List temp = new ArrayList();List> ans = new ArrayList>();public List> combine(int n, int k) {dfs(1, n, k);return ans;}public void dfs(int cur, int n, int k) {// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 tempif (temp.size() + (n - cur + 1) < k) {return;}// 记录合法的答案if (temp.size() == k) {ans.add(new ArrayList(temp));return;}// 考虑选择当前位置temp.add(cur);dfs(cur + 1, n, k);temp.remove(temp.size() - 1);// 考虑不选择当前位置dfs(cur + 1, n, k);}
}

在这里插入图片描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

class Solution {List temp = new ArrayList();List> ans = new ArrayList>();public List> combine(int n, int k) {Scanner scanner= new Scanner(System.in);int[] nums= new int[n+1]; for(int i=1;i<=n;i++){nums[i]=i;}dfs(nums,1, n, k);return ans;}public void dfs(int[] nums,int cur, int n, int k) {// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 tempif (temp.size() + (n - cur + 1) < k) {return;}// 记录合法的答案if (temp.size() == k) {ans.add(new ArrayList(temp));return;}// 考虑选择当前位置temp.add(nums[cur]);dfs(nums,cur + 1, n, k);temp.remove(temp.size() - 1);// 考虑不选择当前位置dfs(nums,cur + 1, n, k);}
}

3.组合（优化)

4.组合总和II

5.电话号码的字母组合

6.回溯周末总结

7.组合总和

8.组合总和II

9.分割回文串

10.复原IP地址

11.子集问题

12.回溯周末总结

13.子集Ⅱ

14.递增子序列

15.全排列

16.全排列II

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

class Solution {boolean[] vis;public List> permuteUnique(int[] nums) {List> ans = new ArrayList>();List perm = new ArrayList();vis = new boolean[nums.length];Arrays.sort(nums);backtrack(nums, ans, 0, perm);return ans;}public void backtrack(int[] nums, List> ans, int idx, List perm) {if (idx == nums.length) {ans.add(new ArrayList(perm));return;}for (int i = 0; i < nums.length; ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}perm.add(nums[i]);vis[i] = true;backtrack(nums, ans, idx + 1, perm);vis[i] = false;perm.remove(idx);}}
}

在这里插入图片描述

18.回溯算法去重问题的另—种写法

19.重新安排行程

20.N皇后

21.解数独

动态规划算法-基础题目

509.麦波那契数

70.爬楼梯

746.使用最小花费爬楼梯

62.不同路径

63.不同路径||

343.整数拆分

96.不同的二叉搜索树

动态规划算法-背包问题

动态规划算法-背包问题-01背包

01背包理论基础（滚动数组）

0416.分割等和子集

1049,最后一块石头的重量II

l0494.目标和

0474.一和零

动态规划算法-背包问题-完全背包

0518.零钱兑换ll

0377.组合总和IV

0070.爬楼梯（完全背包解法）

0322.零钱兑换

0279.完全平方数

0139.单词拆分

动态规划算法-背包问题-多重背包

（无题）

动态规划算法-打家劫舍

198.打家劫舍

213.打家劫舍Il

337.打家劫舍Ⅲ

动态规划算法-股票问题

121.买卖股票的最佳时机I(只能买卖一次)

122.买卖股票的最佳时机II(可以买卖多次)

123.买卖股票的最佳时机III〔最多买卖两次)

188,买卖股票的最佳时机Ⅳ〔最多买卖k次)

309.最佳买卖股票时机含冷冻期（买卖多次，卖出有一天冷冻期）

714.买卖股票的最佳时机含手续费（买卖多次，每次有手续费）

动态规划算法-子序列问题

动态规划算法-子序列问题-子序列(不连续)

300.最长上升子序列

1143.最长公共子序列

1035.不相交的线

动态规划算法-子序列问题-子序列(连续)

674.最长连续递增序列

718.最长重复子数组

53.最大子序和

动态规划算法-子序列问题-编辑问题

392.判断子序列

115.不同的子序列

583.两个字符串的删除操作

72.编辑距离

动态规划算法-子序列问题-回文

647.回文子串

516.最长回文子序列

单调栈

1.每日温度

2.下一个更大元素I

3.下—个更大元素II

4.接雨水

5.柱状图中最大的矩形

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：multiprocessing-python-多进程的介绍与用法

下一篇：MySQL 基础教程[3]