JZ58 左旋转字符串
/* 模拟 */
public class JZ58_1
{
public static String LeftRotateString(String str, int n)
{
if (str.length() == 0) return "";
n %= str.length();
return str.substring(n) + str.substring(0, n);
}
}
/* 三次翻转 */
public class JZ58_2
{
public static String LeftRotateString(String str, int n)
{
char[] strArr = str.toCharArray();
int len = strArr.length;
if (len == 0) return str;
n = n % len;
reverseStr(strArr, 0, n - 1);
reverseStr(strArr, n, len - 1);
reverseStr(strArr, 0, len - 1);
return new String(strArr);
}
public static void reverseStr(char[] array, int begin, int end)
{
for (; begin < end; begin++, end--)
{
char c = array[begin];
array[begin] = array[end];
array[end] = c;
}
}
}
JZ62 孩子们的游戏(圆圈中最后剩下的数)
/* 约瑟夫环 */
public class JZ62_1
{
public static int LastRemaining_Solution(int n, int m)
{
if (n == 1) return 0;
else return (LastRemaining_Solution(n - 1, m) + m) % n;
}
}
JZ75 字符流中第一个不重复的字符
/* 队列 + hash */
public class JZ75_2
{
public static Queue<Character> queue = new LinkedList<>();
public static HashMap<Character, Integer> map = new HashMap<>();
public static void Insert(char ch)
{
if (!map.containsKey(ch))
queue.add(ch);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
public static char FirstAppearingOnce()
{
while (!queue.isEmpty())
{
if (map.get(queue.peek()) == 1)
return queue.peek();
else
queue.poll();
}
return '#';
}
}
/* 模拟 */
public class JZ75_1
{
public static int[] num = new int[256];
public static String str = "";
public static void Insert(char ch)
{
str += ch;
num[ch]++;
}
public static char FirstAppearingOnce()
{
for (char ch : str.toCharArray())
if (num[ch] == 1)
return ch;
return '#';
}
}
JZ14 剪绳子⭐
/* dfs + memo */
public class JZ14_1
{
public static int[] table = new int[100];
public static int cutRope(int n)
{
if (n == 0) return 1;
if (table[n] != 0) return table[n];
int res = -1;
for (int i = 1; i <= n; i++)
res = Math.max(res, i * cutRope(n - i));
table[n] = res;
return res;
}
}
/* dp */
public class JZ14_2
{
public static int cutRope(int n)
{
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for (int i = 4; i <= n; i++)
for (int j = 1; j < i; j++)
dp[i] = Math.max(dp[i], j * dp[i - j]);
return dp[n];
}
}
/*
* 当 n>4 时,
* 若将 n 分成 x 份,那么 (n/x)^(x) 最大时, x = e
* 因为 x 为整数，所以 x 取 3
* */
public class JZ14_3
{
public static int cutRope(int n)
{
int res = 1;
while (n > 4)
{
res *= 3;
n -= 3;
}
return res * n;
}
}
JZ81 调整数组顺序使奇数位于偶数前面(二)
/* 快排 */
public class JZ81_1
{
public static int[] reOrderArrayTwo(int[] array)
{
if (array.length == 0) return array;
int low = 0, high = array.length - 1;
int pivot = array[high];
while (low < high)
{
while (low < high && array[low] % 2 != 0) low++;
array[high] = array[low];
while (low < high && array[high] % 2 == 0) high--;
array[low] = array[high];
}
array[low] = pivot;
return array;
}
}
/* 双指针 */
public class JZ81_2
{
public static int[] reOrderArrayTwo(int[] array)
{
if (array.length == 0) return array;
int low = 0, high = array.length - 1;
while (low < high)
{
while (low < high && array[low] % 2 != 0) low++;
while (low < high && array[high] % 2 == 0) high--;
if (low < high)
{
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
}
return array;
}
}
JZ83 剪绳子（进阶版）
/* 与JZ14类似,使用快速幂 */
public class JZ83_1
{
public static long MOD = 998244353;
public static long cutRope(long number)
{
if (number == 2) return 1;
if (number == 3) return 2;
if (number == 4) return 4;
long pow = (number - 5) / 3 + 1;
System.out.println(pow);
return (quick(3, pow) * (number - 3 * pow)) % MOD;
}
public static long quick(long n, long m)
{
long ans = 1;
while (m != 0)
{
if (m % 2 != 0)
{
ans *= n;
ans %= MOD;
}
n *= n;
n %= MOD;
m >>= 1;
}
return ans;
}
}
JZ17 打印从1到最大的n位数
/* 模拟 */
public class JZ17_1
{
public static int[] printNumbers(int n)
{
int top = (int) Math.pow(10, n);
int[] res = new int[top - 1];
for (int i = 1; i < top; i++)
res[i - 1] = i;
return res;
}
}