题目
找出加密后的字符串
给你一个字符串 s 和一个整数 k。请你使用以下算法加密字符串：
对于字符串 s 中的每个字符 c，用字符串中 c 后面的第 k 个字符替换 c（以循环方式）。
返回加密后的字符串。
示例 1：
输入： s = “dart”, k = 3
输出： “tdar”
解释：
对于 i = 0，‘d’ 后面的第 3 个字符是 ‘t’。
对于 i = 1，‘a’ 后面的第 3 个字符是 ‘d’。
对于 i = 2，‘r’ 后面的第 3 个字符是 ‘a’。
对于 i = 3，‘t’ 后面的第 3 个字符是 ‘r’。
解题思路
遍历字符串，每个下标都进行一次判断是否加上k会大于字符串的长度，如果大于等于字符串的长度，则对下标进行+k%len的操作，并把对应下标的值赋过去
class Solution {
public String getEncryptedString(String s, int k) {
char[]sa=s.toCharArray();
int len=sa.length;
for(int i=0;i<len;i++){
sa[i]=s.charAt((i+k)%len);
}
return new String(sa);
}
}
生成不含相邻零的二进制字符串
给你一个正整数 n。
如果一个二进制字符串 x 的所有长度为 2 的
子字符串
中包含 至少 一个 “1”，则称 x 是一个 有效 字符串。
返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。
示例 1：
输入： n = 3
输出： [“010”,“011”,“101”,“110”,“111”]
解释：
长度为 3 的有效字符串有：“010”、“011”、“101”、“110” 和 “111”。
解题思路
我们可以把 i 取反（保留低 n 位），记作 x。问题变成：判断 x 中是否有相邻的 1。
这可以用 x & (x >> 1) 来判断，如果这个值等于 0，则说明 x 中没有相邻的 1。
class Solution {
public List<String> validStrings(int n) {
List<String> ans = new ArrayList<>();
int mask = (1 << n) - 1;
for (int i = 0; i < (1 << n); i++) {
int x = mask ^ i;
if (((x >> 1) & x) == 0) {
ans.add(Integer.toBinaryString((1 << n) | i).substring(1));
}
}
return ans;
}
}
统计 X 和 Y 频数相等的子矩阵数量
给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 ‘X’、‘Y’ 或 ‘.’，返回满足以下条件的
子矩阵
数量：
包含 grid[0][0]
‘X’ 和 ‘Y’ 的频数相等。
至少包含一个 ‘X’。
示例 1：
输入： grid = [[“X”,“Y”,“.”],[“Y”,“.”,“.”]]
输出： 3
解释：
解题思路
二位前缀和
class Solution {
public int numberOfSubmatrices(char[][] grid) {
int ans = 0;
int m = grid.length;
int n = grid[0].length;
int[][][] sum = new int[m + 1][n + 1][2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum[i + 1][j + 1][0] = sum[i + 1][j][0] + sum[i][j + 1][0] - sum[i][j][0];
sum[i + 1][j + 1][1] = sum[i + 1][j][1] + sum[i][j + 1][1] - sum[i][j][1];
if (grid[i][j] != '.') {
sum[i + 1][j + 1][grid[i][j] & 1]++;
}
if (sum[i + 1][j + 1][0] > 0 && sum[i + 1][j + 1][0] == sum[i + 1][j + 1][1]) {
ans++;
}
}
}
return ans;
}
}
最小代价构造字符串
给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs，这两个数组长度相同。
设想一个空字符串 s。
你可以执行以下操作任意次数（包括零次）：
选择一个在范围 [0, words.length - 1] 的索引 i。
将 words[i] 追加到 s。
该操作的成本是 costs[i]。
返回使 s 等于 target 的 最小 成本。如果不可能，返回 -1。
示例 1：
输入： target = “abcdef”, words = [“abdef”,“abc”,“d”,“def”,“ef”], costs = [100,1,1,10,5]
输出： 7
解释：
选择索引 1 并以成本 1 将 “abc” 追加到 s，得到 s = “abc”。
选择索引 2 并以成本 1 将 “d” 追加到 s，得到 s = “abcd”。
选择索引 4 并以成本 5 将 “ef” 追加到 s，得到 s = “abcdef”。
解题思路
字符串哈希可以O(1) 的判断 子字符串 target[l…r] 是否在 words 中
class Solution {
static int INF = (int) 1e9;
static int B = 37;// 哈希的基数
static long[] A = new long[50001];// A[i] = B ^ i
static {
A[0] = 1;
for (int i = 1; i <= 50000; i++) {
A[i] = A[i - 1] * B;
}
}
long[] hash;
public int minimumCost(String target, String[] words, int[] costs) {
char[] str = target.toCharArray();
int n = str.length;
hash = new long[n + 1];
for (int i = 1; i <= n; i++) {
hash[i] = hash[i - 1] * B + str[i - 1];
}
HashMap<Long, Integer> cost = new HashMap<>();// words 中不同 hash 值的 cost
HashSet<Integer> tmp = new HashSet<>();
for (int i = 0; i < costs.length; i++) {
long v = 0;
for (char c : words[i].toCharArray()) {
v = v * B + c;
}
tmp.add(words[i].length());
cost.merge(v, costs[i], Integer::min);
}
int[] len = new int[tmp.size()];// words 中字符串长度种类数
int j = 0;
for (int v : tmp) {
len[j++] = v;
}
Arrays.sort(len);
int[] dp = new int[n + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int k : len) {
if (i < k) {
break;
}
// 判断 target[(i-k)..(i-1)] 是否在 words 中，如果在就转移
dp[i] = Math.min(dp[i], cost.getOrDefault(query(i - k, i - 1), INF) + dp[i - k]);
}
}
return dp[n] >= INF ? -1 : dp[n];
}
// 查询 target[l..r] 的哈希值
long query(int l, int r) {
return hash[r + 1] - hash[l] * A[r - l + 1];
}
}
来源
LeetCode
