KMP算法
public class kmp {// KMP 算法// ss: 原串(string) pp: 匹配串(pattern)// " a b c a b c c a b b b c c a b y y// 0 0 0 0 1 2 3 0 1 2 0 0 0 0 1 2 0 0// 不回退原串 回退子串// 构建next数组保存 子串前缀特征 决定失败时回退的位置public static int strStr(String ss, String pp) {if (pp.isEmpty()) return 0;// 分别读取原串和匹配串的长度int n = ss.length(), m = pp.length();// 原串和匹配串前面都加空格，使其下标从 1 开始ss = " " + ss;pp = " " + pp;char[] s = ss.toCharArray();char[] p = pp.toCharArray();// 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）int[] next = new int[m + 1];// 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】for (int i = 2, j = 0; i <= m; i++) {// 匹配不成功的话，j = next(j)while (j > 0 && p[i] != p[j + 1]) j = next[j];// 匹配成功的话，先让 j++if (p[i] == p[j + 1]) j++;// 更新 next[i]，结束本次循环，i++next[i] = j;}// 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】for (int i = 1, j = 0; i <= n; i++) {// 匹配不成功 j = next(j)while (j > 0 && s[i] != p[j + 1]) j = next[j];// 匹配成功的话，先让 j++，结束本次循环后 i++if (s[i] == p[j + 1]) j++;// 整一段匹配成功，直接返回下标if (j == m) return i - m;}return -1;}}
矩阵快速幂
字典序
字典序排序
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
class Solution {
//递归 选择一个基数 然后往上加
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList();
dfs(0, 1, n, ans);
return ans;
}
public void dfs(int base, int start, int n, List<Integer> ans) {
if (base > n) return;
for(int i = start; i < 10; i++) {
int num = i + base;
if(num <= n) {
ans.add(num);
dfs(num*10, 0, n , ans);
}
}
}
}
字典序的第K小数字
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
输入: n: 13 k: 2
输出: 10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
class Solution {
public int findKthNumber(int n, int k) {
long cur = 1; // 当前遍历到的数字，从1（根）出发
k = k - 1; // 从1出发开始往后按字典序从小到大的顺序走k-1步到达的就是 字典序的第K小数字
while(k > 0){
int nodes = getNodes(n, cur);
if(k >= nodes){ // 向右侧节点走：字典序上升nodes位
k = k - nodes;
cur++; // 当前数字 cur = cur + 1
}else{ // 向下往最左孩子节点走:字典序上升1位
k = k - 1;
cur *= 10; // 当前数字 cur = cur * 10
}
}
return (int)cur; // 最后cur停在的数字就是字典序的第K小数字
}
// 计算以cur为根的子树节点数目，所有节点的值必须 <= n
private int getNodes(int n, long cur){
long next = cur + 1; // 当前节点右侧右边节点的值
long totalNodes = 0; // 记录子树中的全部节点数目
while(cur <= n){
totalNodes += Math.min(n - cur + 1, next - cur);
next *= 10;
cur *= 10;
}
return (int)totalNodes;
}
}
最大异或值
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.
//使用哈希表实现
public class Solution {
// 先确定高位，再确定低位（有点贪心算法的意思），才能保证这道题的最大性质
// 一位接着一位去确定这个数位的大小
// 利用性质： a ^ b = c ，则 a ^ c = b，且 b ^ c = a
public int findMaximumXOR(int[] nums) {
int res = 0;
int mask = 0;
for (int i = 30; i >= 0; i--) {
// 注意点1：注意保留前缀的方法，mask 是这样得来的
// 用异或也是可以的 mask = mask ^ (1 << i);
mask = mask | (1 << i);
// System.out.println(Integer.toBinaryString(mask));
Set<Integer> set = new HashSet<>();
for (int num : nums) {
// 注意点2：这里使用 & ，保留前缀的意思（从高位到低位）
set.add(num & mask);
}
// 这里先假定第 n 位为 1 ，前 n-1 位 res 为之前迭代求得
int temp = res | (1 << i);
for (Integer prefix : set) {
if (set.contains(prefix ^ temp)) {
res = temp;
break;
}
}
}
return res;
}
}
//使用Trie树
class Solution {
// static 成员整个类独一份，只有在类首次加载时才会创建，因此只会被 new 一次
static int N = (int)1e6;
static int[][] trie = new int[N][2];
static int idx = 0;
// 每跑一个数据，会被实例化一次，每次实例化的时候被调用，做清理工作
public Solution() {
for (int i = 0; i <= idx; i++) {
Arrays.fill(trie[i], 0);
}
idx = 0;
}
void add(int x) {
int p = 0;
for (int i = 31; i >= 0; i--) {
int u = (x >> i) & 1;
if (trie[p][u] == 0) trie[p][u] = ++idx;
p = trie[p][u];
}
}
int getVal(int x) {
int ans = 0;
int p = 0;
for (int i = 31; i >= 0; i--) {
int a = (x >> i) & 1, b = 1 - a;
if (trie[p][b] != 0) {
ans |= (b << i);
p = trie[p][b];
} else {
ans |= (a << i);
p = trie[p][a];
}
}
return ans;
}
public int findMaximumXOR(int[] nums) {
int ans = 0;
for (int i : nums) {
add(i);
int j = getVal(i);
ans = Math.max(ans, i ^ j);
}
return ans;
}
}
队列模拟栈
class MyStack {
Queue<Integer> q1;
Queue<Integer> q2;
public MyStack() {
q1 = new LinkedList();
q2 = new LinkedList();
}
public void push(int x) {
q2.add(x);
while(!q1.isEmpty()) {
q2.add(q1.poll());
}
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}
设计哈希映射
//链地址法
//拉链法
class MyHashMap {
private static final int BASE = 769;
private LinkedList[] table;
private class Entry {
private int key;
private int value;
public Entry(int key, int value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
public MyHashMap() {
table = new LinkedList[BASE];
for(int i = 0; i < BASE; i++) {
table[i] = new LinkedList();
}
}
public void put(int key, int value) {
int hashCode = hash(key);
Iterator<Entry> iterator = table[hashCode].iterator();
while(iterator.hasNext()) {
Entry entry = iterator.next();
if(entry.getKey() == key) {
entry.setValue(value);
return;
}
}
table[hashCode].addLast(new Entry(key, value));
}
public int get(int key) {
int hashCode = hash(key);
Iterator<Entry> iterator = table[hashCode].iterator();
while(iterator.hasNext()) {
Entry entry = iterator.next();
if(entry.getKey() == key) {
return entry.value;
}
}
return -1;
}
public void remove(int key) {
int hashCode = hash(key);
Iterator<Entry> iterator = table[hashCode].iterator();
while(iterator.hasNext()) {
Entry entry = iterator.next();
if(entry.key == key) {
table[hashCode].remove(entry);
return;
}
}
}
private static int hash(int key) {
return key % BASE;
}
}
前缀和
模版
class Solution {
public void func(int[] nums) {
int n = nums.length;
int[] sum = new int[n + 1];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
}
}
}
若有收获，就点个赞吧
0 人点赞
