package com.zhang.reflection.面试.算法模版.回溯模版.模版; import java.util.HashSet; import java.util.Set; /** * 剑指 Offer 38. 字符串的排列 * * 输入一个字符串，打印出该字符串中字符的所有排列。 * * * * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 * * * * 示例: * * 输入：s = "abc" * 输出：["abc","acb","bac","bca","cab","cba"] * ...

package com.zhang.reflection.面试.算法模版.前缀树; /** * 力扣065：单词数组words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足： * * words.length == indices.length * 助记字符串 s 以 '#' 字符结尾 * 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等 * 给定一个单词数组words ，返回成功对 words 进行编码的最小助记字符串 s 的长...

package com.zhang.reflection.面试.算法模版.前缀树; public class 前缀树 { private TreeNode root; static class TreeNode { public int pass;//经过此结点的边的数量 public int end;//以此边为结束 public TreeNode[] nexts; public TreeNode() { this.pass = 0; this.end = 0; ...

package com.zhang.reflection.面试.算法模版.前缀树; /** * 力扣067：给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。 */ public class 最大的异或 { Trie root=new Trie(); static final int HIGH_BIT=30; class Trie{ Trie left=null; Trie right=null; } public int findM...

package com.zhang.reflection.面试.算法模版.前缀和; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * leafee 最近爱上了 abb 型语句，比如“叠词词”、“恶心心” * leafee 拿到了一个只含有小写字母的字符串，她想知道有多少个 "abb" 型的子序列？ * 定义： abb 型字符串满足以下条件： (子序列不要求连续，子串要求连续) * * 字符串长度为 3 。 * 字符串后两位相同。 *...

package com.zhang.reflection.面试.算法模版.前缀和; import java.util.Scanner; /** * 给你一个 n 行 m 列的矩阵 A ，下标从1开始。 * * 接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2 * * 请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和， * * 输入： * 3 4 3（n,m,q） * 1 2 3 4 * 3 2 1 0 * 1 5 7 8 * 1 1 2 2 * 1 1 3 3 * 1 2 3 4 * 输出： * 8...

package com.zhang.reflection.面试.算法模版.前缀和; import java.util.Scanner; /**这道题比较简单，主要用于理解前缀和的应用 * * 给定一个长度为n的数组a_1, a_2,....a_n * 接下来有q次查询, 每次查询有两个参数l, r. * 对于每个询问, 请输出a_l+a_{l+1}+....+a_r的和 * * 输入： * 3 2（n q） * 1 2 4 * 1 2 * 2 3 * 输出： * 3 * 6 */ public class 前缀和 { public static void m...

package com.zhang.reflection.面试.算法模版.跳表; import java.util.Arrays; public class SkipList { /** * 最大层数 */ private static int DEFAULT_MAX_LEVEL = 32; /** * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1 */ private static double DEFAULT_P_FACTOR = 0.25; ...

package com.zhang.reflection.面试.算法模版.LRU; import java.util.HashMap; import java.util.Map; public class LRU { class Node<K,V>{ K key; V value; Node pre; Node next; public Node(){ this.pre=null; this.next=null; } ...

二分查找模版 package com.zhang.reflection.面试.算法模版.二分查找模版; public class 二分查找模版 { /** * 查找满足 x ≥ target 的下界的第一个元素下标，如果不存在返回数组的长度 * 同理找上界，找下界，找特定值第一次出现的位置都可以，前提是数组有序或者部分有序 */ //找下界 public static int LowerBound(int[] nums, int target) { int left=0; int right=nums....

力扣239 package com.zhang.reflection.面试.算法模版.滑动窗口; import java.util.Deque; import java.util.LinkedList; import java.util.PriorityQueue; /** * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。 * 你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。 * * 返回 滑动窗口中的最大值 。 * */ public class 滑动窗口最大值 { /** * 解法一：使用优先队列 ...

力扣第三题 package com.zhang.reflection.面试.算法模版.双指针; import java.util.HashSet; import java.util.Set; /** * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 * * s = "abcabcbb" * * 3 */ public class 双指针 { public int lengthOfLongestSubstring(String s) { //Set集合用来保存已经存在的字符串 Set<Character> ...

题库 package com.zhang.reflection.面试.算法模版.背包问题模版; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 技巧： 如果从需要求字典序最小， dp求解从后往前求 * 即可从前往后推方案。 * 求解出来dp[1][m]就是最大价值 *有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 * * ...

package com.zhang.reflection.面试.算法模版.背包问题模版; import java.util.Arrays; import java.util.Scanner; /** * 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 * * 第 i 件物品的体积是 vi，价值是 wi。 * * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 * * 输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。 * * 输入格式 * 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。...