哈希
字母异位词
先将字符数组排序把异位词处理成相同格式，方便分类 getOrDefault(key,new class)方法,当集合中存在相应键值对，则取出相应的值，若没有，则创建新的键值对并返回相应的值
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> reflect=new HashMap<>();
boolean contain =false;
for(String str:strs){
char[] array=str.toCharArray();
Arrays.sort(array);
String key=new String(array);
List<String> list=reflect.getOrDefault(key,new ArrayList<String>());
list.add(str);
reflect.put(key,list);
}
return new ArrayList<List<String>>(reflect.values());
}
}
双指针
盛最多水的容器
设计两个指针指向数组两端，移动较小的那个元素，因为水桶盛水量取决于较小的那一块，每移动一次就舍弃一个元素，因为当前计算结果就是当前以此元素为边的最大容量（不算舍弃过的元素（并不是真的舍弃，只是后续不再使用））
class Solution {
public int maxArea(int[] height) {
int length=height.length,l=0,r=length-1;
int max=0;
while(l<r){
int capacity=Math.min(height[l],height[r])*(r-l);
max=Math.max(capacity,max);
int flag=height[l]>height[r]?--r:++l;
}
return max;
}
}
三数之和等于零
为了防止集合重复，把数组升序排序，并当遇到相同值时跳过， 因为需要找到三个数，且三个数之和等于零，所以第一个数确定时，第二个数越大，第三个数越小，这时候使用双指针从两端找寻second，可以将时间复杂度从O(N³)减小到O(N²)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int n=nums.length;
List<List<Integer>> ans=new ArrayList<List<Integer>>();
for(int first=0;first<n;++first){
if(first>0&&nums[first]==nums[first-1]){
continue;
}
int third=n-1;
int target=-nums[first];
for(int second=first+1;second<n;++second){
if(second>first+1&&nums[second]==nums[second-1]){
continue;
}
while(second<third&&nums[second]+nums[third]>target){
--third;
}
if(second==third){
break;
}
if(nums[second]+nums[third]==target){
List<Integer> list=new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
接雨水问题
将问题分解成多个水桶问题，并将桶深，桶底记录下来以此来计算容量
class Solution {
public int trap(int[] height) {
int base=0,capacity=0,shorter=0;
int n=height.length;
int l=0,r=n-1;
while(l<r){
shorter=Math.min(height[l],height[r]);
for(int i=l+1;i<r;i++){
int now=Math.max(height[i],base);
int nowcapacity=shorter-now;
capacity+=nowcapacity>0?nowcapacity:0;
}
l=height[l]==shorter?l+1:l;
r=height[r]==shorter?r-1:r;
base=Math.max(shorter,base);
}
return capacity;
}
}
滑动窗口
无重复字符的最长字串
使用hashset方便区分重复字符，设置窗口的起始位置，因为终止位置是随着起始位置的递增而递增的（无重复字符的字串依旧无重复），所以我们遍历起始位置时不必重置终止位置，继续向后遍历即可 （滑动窗口技术非常适用于处理数组或字符串等线性数据结构中的连续子集或子序列问题。）
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> occ =new HashSet<Character>();
int n=s.length();
int rk=-1,ans=0;
for(int i=0;i<n;i++){
if(i!=0){
occ.remove(s.charAt(i-1));
}
while(rk+1<n&&!occ.contains(s.charAt(rk+1))){
occ.add(s.charAt(rk+1));
++rk;
}
ans=Math.max(ans,rk-i+1);
}
return ans;
}
}
找到字符串中的所有字母异位词
第一个循环建立窗口并建立模板，因为该题中模板大小固定，所以窗口大小固定
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int slen=s.length(),plen=p.length();
List<Integer> ans=new ArrayList<>();
if(slen<plen){
return ans;
}
int[] scount =new int[26];
int[] pcount=new int[26];
for(int i=0;i<plen;i++){
++scount[s.charAt(i)-'a'];
++pcount[p.charAt(i)-'a'];
}
if(Arrays.equals(scount,pcount)){
ans.add(0);
}
for(int i=0;i<slen-plen;i++){
--scount[s.charAt(i)-'a'];
++scount[s.charAt(i+plen)-'a'];
if(Arrays.equals(scount,pcount)){
ans.add(i+1);
}
}
return ans;
}
}
滑动窗口最大值
采用优先队列（通常采用最大堆或最小堆实现（堆：特殊的完全二叉树）） 该队列会使用比较函数对元素进行比较排列，队首始终是最大值，此时我们只需观察其是否在窗口内，为了方便讨论，我们会现选择性的删除大于当前窗口最大元素的元素
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n=nums.length;
PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] pair1,int[] pair2){
return pair1[0]!=pair2[0]?pair2[0]-pair1[0]:pair2[1]-pair1[1];
}
});
int[] result =new int[n-k+1];
for(int i=0;i<k;i++){
pq.offer(new int[]{nums[i],i});
}
result[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();
}
result[i-k+1]=pq.peek()[0];
}
return result;
}
}
采用单调队列 本题求解由每个窗口内的最大元素组成的数组，因为窗口是连续的滑动，所以当窗口内某个右端元素大于某个左端元素时，在此窗口之后的的所有含有该左端元素的窗口都含有该右端元素，那么当我们构建队列时，当遇到较大的右端元素时，我们可以将所有小于其的左端元素去掉，因为在该右端元素的影响下，其左端元素始终不会是最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n=nums.length;
Deque<Integer> deque =new LinkedList<>();
for(int i=0;i<k;i++){
while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans=new int[n-k+1];
ans[0]=nums[deque.peekFirst()];
for(int i=k;i<n;i++){
while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){
deque.pollLast();
}
deque.offerLast(i);
while(deque.peekFirst()<=i-k){
deque.pollFirst();
}
ans[i-k+1]=nums[deque.peekFirst()];
}
return ans;
}
}
字串
和为k的子数组
与滑动数组不同，该问题一个起点可能有多个答案，且窗口大小没有规律，所以不能使用滑动窗口，因为该数组正负数都存在，所以循环中不能break因为一个起点可能不止一个答案
class Solution {
public int subarraySum(int[] nums, int k) {
int count=0;
for(int i=0;i<nums.length;i++){
int sum=0;
for(int j=i;j<nums.length;j++){
sum+=nums[j];
if(sum==k){
count++;
}
}
}
return count;
}
}
使用前缀和与hashmap,根据字串与其前缀和等于nums【i】的原理（sum【i】-sum【j】=k）
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap < Integer, Integer > mp = new HashMap < > ();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (mp.containsKey(pre - k)) {
count += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
}
普通数组
最大子数组和
使用动态规划（动态规划即将一个问题分解为很多个小问题来一步步解决，适合应用在具有重复子问题和最优子结构的问题）例如本问题将最大子数组和分解为以每个元素结尾的最大子数组和
class Solution {
public int maxSubArray(int[] nums) {
int pre=0,maxans=nums[0];
for(int x:nums){
pre=Math.max(pre+x,x);
maxans=Math.max(maxans,pre);
}
return maxans;
}
}
合并区间
使用匿名内部类
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[] intervals1,int[] intervals2){
return intervals1[0]-intervals2[0];
}
});
/*使用匿名内部类自定义比较器，对二维数组进行排序
List<int[]> merged=new ArrayList<int[]>();
for(int i=0;i<intervals.length;i++){
int L=intervals[i][0],R=intervals[i][1];
if(merged.size()==0||merged.get(merged.size()-1)[1]<L){
merged.add(new int[]{L,R});
}else{
merged.get(merged.size()-1)[1]=Math.max(merged.get(merged.size()-1)[1],R);
}
}
return merged.toArray(new int[merged.size()][]);
}
}
- 数组的二次平方排序
矩阵
搜索二维矩阵(直接搜索)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int[] X:matrix){
for(int x:X){
if(x==target){
return true;
}
}
}
return false;
}
}
因为该矩阵从左到右递增，从上到下递增，所以从右上角开始遍历可以整行整列的排除，当右上角元素大于目标元素，那么可以排除最右边一列，当右上角元素小于目标元素，则可以排除最上边一行，直到找到目标元素
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] == target) {
return true;
}
if (matrix[x][y] > target) {
--y;
} else {
++x;
}
}
return false;
}
}
链表
回文链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
Deque<Integer> ans=new LinkedList<>();
if(head.next==null){
return true;
}
while(head!=null){
ans.offerLast(head.val);
head=head.next;
}
while(!ans.isEmpty()&&ans.peekLast()==ans.peekFirst()){
ans.pollLast();
if(!ans.isEmpty()){
ans.pollFirst();
}
}
if(ans.isEmpty()){
return true;
}else{
return false;
}
}
}
(更简单的方法，将链表反转，然后比较两个链表)
排序链表
采用归并排序(自定向下，采用该递归实现)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode merge(ListNode head1, ListNode head2) {
ListNode node1 = head1, node2 = head2;
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (node1 != null && node2 != null) {
if (node1.val > node2.val) {
curr.next = node2;
curr = curr.next;
node2 = node2.next;
} else {
curr.next = node1;
curr = curr.next;
node1 = node1.next;
}
}
curr.next = (node1 != null) ? node1 : node2;
return dummy.next;
}
public ListNode getMiddle(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode mergeSort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode middle = getMiddle(head);
ListNode nextToMiddle = middle.next;
middle.next = null;
ListNode left = mergeSort(head);
ListNode right = mergeSort(nextToMiddle);
return merge(left, right);
}
public ListNode sortList(ListNode head) {
return mergeSort(head);
}
}
自底向上（迭代归并）
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class Solution {
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
int length = getLength(head);
ListNode dummy = new ListNode(0);
dummy.next = head;
for (int size = 1; size < length; size *= 2) {
ListNode current = dummy.next;
ListNode tail = dummy;
while (current != null) {
ListNode left = current;
ListNode right = split(left, size);
current = split(right, size);
tail.next = merge(left, right);
while (tail.next != null) {
tail = tail.next;
}
}
}
return dummy.next;
}
private int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
private ListNode split(ListNode head, int size) {
for (int i = 1; head != null && i < size; i++) {
head = head.next;
}
if (head == null) return null;
ListNode second = head.next;
head.next = null;
return second;
}
}
LRU缓存机制
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
二叉树
二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}
二叉树的最大深度
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
检查二叉树的对称性
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
二叉树的直径
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root==null){
return 0;
}
int length=0;
if(root.left!=null){
length=length(root.left);
}
if(root.right!=null){
length+=length(root.right);
}
int llength=diameterOfBinaryTree(root.left);
int rlength=diameterOfBinaryTree(root.right);
return Math.max(length,Math.max(llength,rlength));
}
public int length(TreeNode root){
if(root==null){
return 0;
}
int left=length(root.left);
int right=length(root.right);
return Math.max(left,right)+1;
}
}
二叉树的层次遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans=new ArrayList<>();
if(root==null){
return ans;
}
Deque<TreeNode> que=new LinkedList<>();
que.add(root);
while(!que.isEmpty()){
int size=que.size();
List<Integer> ansele=new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode t=que.poll();
ansele.add(t.val);
if (t.left != null) {
que.add(t.left);
}
if (t.right != null) {
que.add(t.right);
}
}
ans.add(ansele);
}
return ans;
}
}
将有序数组转化为二叉搜索树
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
验证二叉搜索树
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer min, Integer max) {
if (node == null) {
return true;
}
if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
return false;
}
return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}
}
二叉树中第k小元素(采取中序遍历)
class Solution {
int count = 0;
int result = 0;
public int kthSmallest(TreeNode root, int k) {
inorderTraversal(root, k);
return result;
}
private void inorderTraversal(TreeNode node, int k) {
if (node == null) {
return;
}
inorderTraversal(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
inorderTraversal(node.right, k);
}
}
二叉树的右视图
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Deque<TreeNode> que=new LinkedList<>();
List<Integer> ans=new ArrayList<>();
if(root==null){
return ans;
}
que.add(root);
while(!que.isEmpty()){
int size=que.size();
for(int i=0;i<size;i++){
TreeNode node=que.poll();
if(node.left!=null){
que.add(node.left);
}
if(node.right!=null){
que.add(node.right);
}
if(i==size-1){
ans.add(node.val);
}
}
}
return ans;
}
}
从前序和中序遍历构建二叉树
class Solution {
int i=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null||preorder.length==0){
return null;
}
TreeNode root=new TreeNode(preorder[0]);
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
int inorderIndex=0;
for(int i=1;i<preorder.length;i++){
int preorderval=preorder[i];
TreeNode node=stack.peek();
if(node.val!=inorder[inorderIndex]){
node.left=new TreeNode(preorderval);
stack.push(node.left);
}else{
while(!stack.isEmpty()&&stack.peek().val==inorder[inorderIndex]){
node=stack.pop();
inorderIndex++;
}
node.right=new TreeNode(preorderval);
stack.push(node.right);
}
}
return root;
}
}
路径之和位定值的个数(穷举法（递归）)
class Solution {
public int pathSum(TreeNode root, long targetSum) {
if(root==null){
return 0;
}
int ans=rootsum(root,targetSum);
ans+=pathSum(root.left,targetSum);
ans+=pathSum(root.right,targetSum);
return ans;
}
public int rootsum(TreeNode root,long targetSum){
int num=0;
if(root==null){
return 0;
}
if(root.val==targetSum){
num++;
}
num+=rootsum(root.left,targetSum-root.val);
num+=rootsum(root.right,targetSum-root.val);
return num;
}
}
二叉树的最近公共父节点 利用深度优先搜索，最近的公共父节点要么是左右子树分别包含两节点，要么是其中一个节点
class Solution {
private TreeNode ans;
public Solution() {
this.ans = null;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}
二叉树最大路径和(若节点都小于零，则为求最大节点值)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
// 递归计算左右子节点的最大贡献值
int leftMax = Math.max(dfs(node.left), 0);
int rightMax = Math.max(dfs(node.right), 0);
// 当前节点的最大路径和
int currentMaxPath = node.val + leftMax + rightMax;
// 更新全局最大路径和
maxSum = Math.max(maxSum, currentMaxPath);
// 返回节点的最大贡献值
return node.val + Math.max(leftMax, rightMax);
}
}
图论
岛屿数量问题 (使用深度优先搜索，并将遍历过的元素更改)
class Solution {
public int numIslands(char[][] grid) {
int m=grid.length;
int n=grid[0].length;
int num=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1'){
num++;
dfs(grid,i,j);
}
}
}
return num;
}
void dfs(char[][] grid,int i,int j){
if(!inArea(grid,i,j)||grid[i][j]=='0'){
return;
}
if(grid[i][j]=='1'){
grid[i][j]='0';
}
dfs(grid,i+1,j);
dfs(grid,i-1,j);
dfs(grid,i,j+1);
dfs(grid,i,j-1);
return;
}
boolean inArea(char[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
}
腐烂的橘子(使用广度优先遍历)
class Solution {
public int orangesRotting(int[][] grid) {
int fresh=0;
int m=grid.length;
int n=grid[0].length;
int time=0;
Deque<int[]> queue=new LinkedList<>();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==2){
queue.add(new int[]{i,j});
}else if(grid[i][j]==1){
fresh++;
}
}
}
if(fresh==0){
return 0;
}
while(!queue.isEmpty()){
int size=queue.size();
for(int k=0;k<size;k++){
int[] now=queue.poll();
int[][] direction={{-1,0},{1,0},{0,-1},{0,1}};
for(int t=0;t<4;t++){
int x=now[0]+direction[t][0];
int y=now[1]+direction[t][1];
if(inArea(grid,x,y)&&grid[x][y]==1){
grid[x][y]=2;
queue.add(new int[]{x,y});
fresh--;
}
}
}
time++;
if(fresh==0){
return time;
}
}
return -1;
}
boolean inArea(int[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
}
回溯
组合总和
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> answer = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
combination(candidates, target, 0);
return result;
}
public void combination(int[] candidates, int target, int startIndex) {
if (target == 0) {
result.add(new ArrayList<>(answer));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (candidates[i] > target) {
continue;
}
answer.add(candidates[i]);
combination(candidates, target - candidates[i], i);
answer.remove(answer.size() - 1);
}
}
}
combination(candidates, target - candidates[i], i);这段代码体现出了回溯的高明之处，
- 形参传值 和 递归调用 的结合使得回溯算法可以保持每一层递归的独立状态，不需要显式地进行状态恢复，这就是回溯的高效和简洁之处。
- 这使得代码逻辑简洁、清晰，并且减少了出错的可能性，因为回溯操作（状态恢复）是由递归自动管理的。
单词搜索
class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
if (check(board, word, i, j, 0)) {
return true;
}
}
}
}
return false;
}
boolean check(char[][] board, String word, int i, int j, int k) {
if (k == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) {
return false;
}
char temp = board[i][j];
board[i][j] = '#';
boolean found = check(board, word, i + 1, j, k + 1) ||
check(board, word, i - 1, j, k + 1) ||
check(board, word, i, j + 1, k + 1) ||
check(board, word, i, j - 1, k + 1);
board[i][j] = temp;
return found;
}
}
需要标记已搜索字母，不然容易重复查询
N皇后
涉及到很多string,Array的操作
- String.copyValueOf(char[])
- String.join(“seperate”,"")
- ident.subString()
- Arrays.fill(char[],‘char’)
- Arrays.sort(int[])
- Collections.nCopies(n,‘char’)
二分查找
循环条件应当设置为left<=right，注意等于号不然某些情况有可能会漏掉
- 搜素旋转排序数组
class Solution {
public int search(int[] nums, int target) {
int n = nums.length - 1;
int left = 0, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// 判断左半部分是否有序
if (nums[0] <= nums[mid]) {
// 左边有序，判断 target 是否在左半部分的范围内
if (nums[0] <= target && nums[mid] > target) {
right = mid - 1; // target 在左边，缩小右边界
} else {
left = mid + 1; // target 不在左边，缩小左边界
}
} else {
// 否则右半部分有序，判断 target 是否在右半部分的范围内
if (nums[n] >= target && nums[mid] < target) {
left = mid + 1; // target 在右边，缩小左边界
} else {
right = mid - 1; // target 不在右边，缩小右边界
}
}
}
return -1; // 未找到，返回 -1
}
}
寻找两个正序数组的中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int total = m + n;
int midIndex = total / 2;
int l = 0, r = 0; // 初始化指针
int current = 0; // 当前指向的值
int previous = 0; // 前一个值
for (int i = 0; i <= midIndex; i++) {
previous = current; // 保存前一个值
if (l < m && (r >= n || nums1[l] <= nums2[r])) {
current = nums1[l];
l++;
} else {
current = nums2[r];
r++;
}
}
// 如果总长度是偶数，返回中位数
if (total % 2 == 0) {
return (previous + current) / 2.0;
} else { // 如果是奇数，返回当前值
return current;
}
}
}
l < m && (r >= n || nums1[l] <= nums2[r])
精髓就在这个条件语句上，只有当l合法，且r不合法或者当前nums1不大于nums2时可以
爱吃香蕉的琪琪
二分查找不一定要查原数组，比如这个查找的是速度，同时这个向上取整(pile + k - 1))就很巧妙
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
for (int pile : piles) {
right = Math.max(right, pile); // 最高速度为最大香蕉堆数
}
while (left < right) {
int mid = left + (right - left) / 2; // 中间速度
if (canFinish(piles, h, mid)) {
right = mid; // 尝试更小的速度
} else {
left = mid + 1; // 尝试更大的速度
}
}
return left;
}
private boolean canFinish(int[] piles, int h, int k) {
int hours = 0;
for (int pile : piles) {
hours += (pile + k - 1) / k; // 计算当前堆需要的小时数（等价于向上取整）
}
return hours <= h; // 检查是否能在 h 小时内吃完
}
}
栈
最小栈
class MinStack {
private List<Integer> arr; // 用于存储栈的元素
private List<Integer> minArr; // 用于存储当前最小值的栈
private int top; // 栈顶索引
public MinStack() {
arr = new ArrayList<>();
minArr = new ArrayList<>();
top = -1;
}
public void push(int val) {
arr.add(val);
top++;
// 如果 minArr 为空或者当前值小于等于最小值，推入 minArr
if (minArr.isEmpty() || val <= minArr.get(minArr.size() - 1)) {
minArr.add(val);
}
}
public void pop() {
int removedVal = arr.remove(top--);
// 如果弹出的元素是当前最小值，从 minArr 中移除
if (removedVal == minArr.get(minArr.size() - 1)) {
minArr.remove(minArr.size() - 1);
}
}
public int top() {
return arr.get(top);
}
public int getMin() {
return minArr.get(minArr.size() - 1);
}
}
minArr.isEmpty() || val <= minArr.get(minArr.size() - 1) 这条条件语句是整个代码的精髓
字符串解析
class Solution {
public String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>(); // 用于存储重复次数
Deque<StringBuilder> stringStack = new ArrayDeque<>(); // 用于存储当前字符串
StringBuilder currentString = new StringBuilder(); // 当前字符串构建器
int num = 0; // 当前数字
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
// 构建数字
num = num * 10 + (ch - '0'); // 处理多位数字
} else if (ch == '[') {
// 将当前字符串和重复次数推入栈中
countStack.addLast(num);
stringStack.addLast(currentString);
num = 0; // 重置数字
currentString = new StringBuilder(); // 重置当前字符串
} else if (ch == ']') {
// 结束当前字符串的重复
StringBuilder previousString = stringStack.removeLast();
int repeatCount = countStack.removeLast();
currentString = previousString.append(currentString.toString().repeat(repeatCount));
} else {
// 处理普通字符
currentString.append(ch);
}
}
return currentString.toString(); // 返回最终字符串
}
}
单调栈
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n=temperatures.length;
int[] result=new int[n];
Deque<Integer> stack=new ArrayDeque<>();
for(int i=0;i<n;i++){
while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
int preIndex=stack.pop();
result[preIndex]=i-preIndex;
}
stack.push(i);
}
return result;
}
}
柱状图中最大矩形
class Solution {
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int result = 0;
for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
int top = stack.pop();
int wide = stack.isEmpty() ? i : i - stack.peek() - 1;
result = Math.max(result, heights[top] * wide);
}
stack.push(i);
}
int i = heights.length;
while (!stack.isEmpty()) {
int top = stack.pop();
int wide = stack.isEmpty() ? i : i - stack.peek() - 1;
result = Math.max(result, heights[top] * wide);
}
return result;
}
}
- 接雨水：需要找到凹陷的区域，使用单调递减栈，当遇到右端的更高柱子时才进行计算。
- 最大矩形：需要在遇到较小柱子时计算前面柱子的矩形区域，使用单调递增栈，保证当前柱子之前的高度都比它低，遇到更低的柱子时开始计算。
目录
相关文章
MySQL
1.1 SQL语句执行流程 先通过连接器校验权限 利用分析器进行SQL语句的词法分析和语法饭呢西，构建解析树 使用优化器选择合适的索引和表连接顺序，最终选择一个最佳的执行计划 利用执行器，调用引擎层查询数据，返回结果集中给客户端 1.2 MYSQL的存储引擎 InnoDB:是mysql默认的存储引擎，支持事务，表级锁和力度更小的行级锁，具有事务提交，回滚和数据崩溃恢复的功能 changebuffer:是Innodb存储引擎中的一个机制，用于暂存对二级索引的插入和更新操作的变更，而不立即去执行，当合适条件时，再写入到二级索引中， changebuffer：提高写入性能，减少对磁盘的频繁写入，批量操作 MyISAM:是之前Mysql的默认引擎，不支持事务和行级锁，支持表级锁，锁的粒度较大，更新性能较差，更适合读多写少的场景 Memory:相较于InnoDB和MyISAM,Memory是存在内存中的，速度更快，但是不具备持久化能力，适合临时存储 1.3 数据排序 1.3.1索引排序 1.3.1.1 索引的数据结构： B+树（又可分为聚簇索引和非聚簇索引）： B+树（所有实际数据（值））都存在叶子节点，所有叶子节点又通过链表连接内部节点不存储数据，用于存储指向子节点的指针和索引信息（关键字（它们通常对应于数据库表中某些字段的值））
定义：聚簇索引是一种将表中的数据行按索引的顺序存储的索引。数据的物理存储顺序与索引顺序相同。
特点：
每个表只能有一个聚簇索引，因为数据只能按一种顺序存放。 主要用于主键（Primary Key）。 查询速度快，因为可以直接访问存储的数据。 例子：在一个员工表中，使用员工ID作为聚簇索引，员工记录将按照员工ID的顺序存储。
定义：非聚簇索引是一种将索引结构与表中的数据分开的索引。索引存储的是指向数据行的指针，而不是数据本身。
特点：
一个表可以有多个非聚簇索引，用于不同的列。 查询时需要先查找非聚簇索引，再通过指针找到实际的数据，速度相对较慢。 例子：在同一个员工表中，如果为姓氏创建非聚簇索引，索引将存储姓氏的值和对应员工ID的指针。
哈希，倒排，R-树
1.3.1.2联合索引 联合索引（Composite Index）是数据库中的一种索引类型，它由多个列组成。与单列索引不同，联合索引可以提高对多个列的查询性能，特别是在涉及到这些列的组合条件时。
特点 由多个列组成：联合索引可以包含两个或更多的列，这使得它适用于复杂查询。 顺序敏感：联合索引中列的顺序非常重要。在创建索引时，最左边的列会影响索引的使用方式。 提高查询性能：联合索引可以加速对涉及多个列的查询，例如，使用WHERE条件的查询、ORDER BY排序等。 1.3.1.2.1 最左前缀匹配原则 1.3.1.2.2 覆盖索引 1.3.1.2.3 索引下推 应用在联合索引上
1.3.2 文件排序 sort_buffer
2024-7-17
Redis
2.1 Redis的应用场景 缓存：用作缓存层，减少数据库负载，提高数据读取速度 实时系统：redis支持快速的数据写入和读取，非常适合实时分析 消息队列：利用Redis的list和pub/sub，可以实现轻量级的消息队列 分布式锁：Redis可以用作分布式锁的实现，确保在分布式系统中资源的安全访问，避免竟态条件 计数器：Redis的原子性操作非常适合用作计数器 2.2 内存存储 2.2.1 redis为什么这么快 reids将数据存储在内存中，提供那个快速的读写速度，相比传统的磁盘数据库，内存访问速度快很多 redis使用单线程事件驱动模型结合I/O多路复用，提高了并发效率（6.0引入多线程：随着数据规模的增长，请求量的增加，redis的执行瓶颈主要在于网络I/O，引入多线程处理可以提高网络I/O的处理效率，减少阻塞） 提供了多种高效数据结构 2.2.2 内存淘汰机制 redis的内存淘汰策略一共由8种
不淘汰数据（默认）： noeviction:当运行内存超过最大设置内存的时候，不会淘汰数据，而是直接返回报错禁止写入 设置了过期事件的数据淘汰 volatile_random:随机淘汰掉设置了过期时间的key volatile-ttl:优先淘汰掉较早过期的key volatile-lfu（3.0之前默认策略）：淘汰掉所有设置了过期时间的，然后醉酒未使用的key volatile-lfu(4.0后新增)：与上面类似，淘汰掉最少使用的key 所有数据的数据淘汰: allkeys-random:随机淘汰掉任意的key allkeys-lru:淘汰掉缓存中最久没有使用的key allkeys-lfu（4.0后新增）：淘汰掉缓存中最少使用的key 2.2.3 过期删除机制 定期删除(每隔一段时间（默认100毫秒）随机检查一定数量的键，如果发现过期键则删除) 惰性删除:只有查询到相关数据才执行检查和删除操作，容易造成内存泄漏 2.2.4 内存碎片化 redis的内存碎片化是指内存使用中出现小块空间被闲置，无法被有效利用
redis默认使用jemalloc作为内存分配器，它是按照固定大小来分配内存的 INFO memory:可以通过INFO memory来查看内存碎片率（mem_fragmentation_ratio） # Memory used_memory:1000000 ## 实际申请的内存空间 used_memory_human:977.54K used_memory_rss:1200000 ##表示实际占用的物理内存空间（含内存碎片） used_memory_rss_human:1.14M mem_fragmentation_ratio:1.20 ratio大于1证明存在内存碎片（过大需要清理），小于一说明已经使用swap用上磁盘空间了。
2024-7-17
心理学与生活
感知与记忆 颜色 *超越视觉 颜色不仅仅是我们对光波的一种感知，更是一种视觉经验 视网膜上对颜色识别起作用的细胞叫视锥细胞
知觉 *超越理解 知觉分为觉察、分辨、确定 知觉特性： 选择性（selectivity） 解释性（comprehension） 整体性（integrality） 恒常性（permanent）
错觉 *超越事实 外界纷繁的刺激，我们丰富的生活，都不断的帮助我们建立一个更好的视觉系统，让它发挥更好的作用 我们视觉系统的建立，伴随着大量的经验堆叠，以及视觉神经元在此过程中建立的联系 我们常说 耳听为虚，眼见为实，但实际上，眼见也未必为实
记忆 *给我一杯忘情水 记忆分为 外显记忆（explicit memory）: 内隐记忆（implicit memory）:不需要意志控制，不需要意志努力
陈述性记忆（declarative memory）：一种依靠语言描述来进行的记忆 程序性记忆（procedural memory）：一种关于怎么做事情的过程、步骤等具体操作的记忆
情景记忆（episodic memory）：一种对于过去经验中时间、地点、过程等的记忆 语义记忆(semantic memory)：一种对抽象符号的记忆
时间
感觉记忆（sensory memory）：0.5~4秒 短时记忆（short-term memory）：5秒到1分 长时记忆（long-term memory）：1分钟以上
最容易遗忘的记忆
语义记忆 外显记忆 陈述性记忆
难以遗忘的记忆
情景记忆 程序性记忆 内隐记忆
重构 *那些不真实的回忆 记忆重构（memory reconstruction） 记忆的存储过程是一个动态过程，在这个过程中一些已经有的经验会发生变化 人们会利用概括、归类等方式来重构信息 重构过程中，信息变得更加简单，不重要的细节完全被忽略，，突出和强调哪些重要的细节，这个故事就变得更加合理、符合背景和常识
2024-7-17
赞赏
Wechat
Alipay
