public class _机器人走方格 {
public static void main(String[] args) {
System.out.println(solve(6, 6));
System.out.println(solve1(6, 6));
}
public static int solve(int x, int y) {
if (x == 1 || y == 1) return 1;
return solve(x - 1, y) + solve(x, y - 1);
}
public static int solve1(int m, int n) {
int[][] state = new int[m + 1][n + 1];
for (int i = 1; i <= n; i++) {
state[1][i] = 1;
}
for (int i = 1; i <= m; i++) {
state[i][1] = 1;
}
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
state[i][j] = state[i][j - 1] + state[i - 1][j];
}
}
return state[m][n];
}
}
public class _全排列1 {
public static void main(String[] args) {
ArrayList res = new _全排列1().getPermutation0("abcd");
System.out.println(res.size());
System.out.println(res);
}
public ArrayList getPermutation0(String A) {
int n = A.length();
ArrayList res = new ArrayList<>();
res.add(A.charAt(0) + "");//初始化,包含第一个字符
for (int i = 1; i < n; i++) {//第二个字符插入到前面生成集合的每个元素里面
ArrayList res_new = new ArrayList<>();
char c = A.charAt(i);//新字符
for (String str : res) {//访问上一趟集合中的每个字符串
// 插入到每个位置,形成一个新串
String newStr = c + str;//加在前面
res_new.add(newStr);
newStr = str + c;//加在后面
res_new.add(newStr);
//加在中间
for (int j = 1; j < str.length(); j++) {
newStr = str.substring(0, j) + c + str.substring(j);
res_new.add(newStr);
}
}
res = res_new;//更新
}
return res;
}
}
public class _全排列2 {
public static void main(String[] args) {
ArrayList res = new _全排列2().getPermutation("12345");
System.out.println(res.size());
System.out.println(res);
}
ArrayList res = new ArrayList<>();
public ArrayList getPermutation(String A) {
char[] arr = A.toCharArray();
Arrays.sort(arr);//abc
getPermutationCore(arr, 0);
return res;
}
private void getPermutationCore(char[] arr, int k) {
if (k == arr.length) {//排好了一种情况,递归的支路走到底了
res.add(new String(arr));
}
//从k位开始的每个字符,都尝试放在新排列的k这个位置
for (int i = k; i < arr.length; i++) {
swap(arr, k, i);//把后面每个字符换到k位
getPermutationCore(arr, k + 1);
swap(arr, k, i);//回溯
}
}
//交换位置
static void swap(char[] arr, int i, int j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
public class _全排列3第K个排列 {
public static void main(String[] args) {
String s = "123";
permutation("", s.toCharArray());
}
final static int k = 3;
static int count = 0;
private static void permutation(String prefix, char[] arr) {
if (prefix.length() == arr.length) {//前缀的长度==字符集的长度,一个排列就完成了
// System.out.println(prefix);
count++;
if (count == k) {
System.out.println("-------:" + prefix);
System.exit(0);
}
}
//每次都从头扫描,只要该字符可用,我们就附加到前缀后面,前缀变长了
for (int i = 0; i < arr.length; i++) {
char ch = arr[i];
//这个字符可用:在pre中出现次数<在字符集中的出现次数
if (count(prefix, ch) < count(arr, ch)) {
permutation(prefix + ch, arr);
}
}
}
private static int count(char[] arr, char ch) {
int cnt = 0;
for (char c : arr
) {
if (c == ch) cnt++;
}
return cnt;
}
private static int count(String str, char ch) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ch) cnt++;
}
return cnt;
}
}
public class _硬币表示某个数值 {
public static void main(String[] args) {
_硬币表示某个数值 obj = new _硬币表示某个数值();
for (int i = 1; i < 101; i++) {
int ways = obj.countWays(i);
System.out.println(i + "---" + ways);
ways = obj.countWays2(i);
System.out.println(i + "---" + ways);
}
}
int[][] state;
public int countWays1(int n) {
int[] coins = {1, 5, 10, 25};
int[][] dp = new int[4][n + 1];//前i种面值,组合出面值j
for (int i = 0; i < 4; i++) {
dp[i][0] = 1;//凑出面值0,只有一种可能,第一列初始化为1
}
for (int j = 0; j < n + 1; j++) {
dp[0][j] = 1;//用1来凑任何面值都只有一种凑法,第一行初始化为1
}
for (int i = 1; i < 4; i++) {
for (int j = 1; j < n + 1; j++) {
for (int k = 0; k <= j / coins[i]; ++k) {
dp[i][j] += dp[i - 1][j - k * coins[i]];
}
}
}
return dp[3][n];
}
public int countWays2(int n) {
int[] coins = {1, 5, 10, 25};
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 0; i < 4; i++) {
for (int j = coins[i]; j < n + 1; j++) {
dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007;
}
}
return dp[n];
}
public int countWays(int n) {
if (n <= 0) return 0;
return countWaysCore(n, new int[]{1, 5, 10, 25}, 3);
}
private int countWaysCore(int n, int[] coins, int cur) {
if (cur == 0) return 1;
int res = 0;
//不选coins[cur]
//要一个
//要两个......
for (int i = 0; i * coins[cur] <= n; i++) {
int shengyu = n - i * coins[cur];
res += countWaysCore(shengyu, coins, cur - 1);
}
return res;
}
}
public class _走楼梯 {
static final int mod = 1000000007;
public static void main(String[] args) {
System.out.println(recursion2(7));
System.out.println(recursion1(7));
System.out.println(recursion3(7));
}
public static long recursion1(int n) {
if (n < 0) return 0;
if (n == 0 || n == 1) return 1;
if (n == 2) return 2;
return recursion1(n - 1) % mod + recursion1(n - 2) % mod + recursion1(n - 3) % mod;
}
// 1 2 4 7 13 24 44
public static int recursion2(int n) {
if (n < 0) return 0;
if (n == 0 || n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
int x1 = 1;
int x2 = 2;
int x3 = 4;
for (int i = 4; i <= n; i++) {
int x_1 = x1;
x1 = x2 % mod;
x2 = x3 % mod;
x3 = ((x1 + x2) % mod + x_1) % mod;//注意此处
}
return x3;
}
public static int recursion3(int n) {
long[][] base = {
{0, 0, 1},
{1, 0, 1},
{0, 1, 1}};
long[][] f1f2f3 = {{1, 2, 4}};
return (int) matrixMultiply(f1f2f3, matrixPower(base, n - 1))[0][0];
}
public static long[][] matrixPower(long[][] matrix, long p) {
//初始化结果为单位矩阵，对角线为1
long[][] result = new long[matrix.length][matrix[0].length];
//单位矩阵，相当于整数的1
for (int i = 0; i < result.length; i++) {
result[i][i] = 1;
}
//平方数
long[][] pingFang = matrix; // 一次方
while (p != 0) {
if ((p & 1) != 0) { // 当前二进制位最低位为1，将当前平方数乘到结果中
result = matrixMultiply(result, pingFang);//
}
//平方数继续上翻
pingFang = matrixMultiply(pingFang, pingFang);
p >>= 1;
}
return result;
}
public static long[][] matrixMultiply(long[][] m1, long[][] m2) {
final int n = m1.length;
final int m = m1[0].length;
if (m != m2.length) throw new IllegalArgumentException();
final int p = m2[0].length;
long[][] result = new long[n][p];// 新矩阵的行数为m1的行数，列数为m2的列数
for (int i = 0; i < n; i++) {//m1的每一行
for (int j = 0; j < p; j++) {//m2的每一列
for (int k = 0; k < m; k++) {
result[i][j] += m1[i][k] * m2[k][j];
}
}
}
return result;
}
public static String arrayToString(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int e : arr) {
sb.append(e);
}
return sb.toString();
}
}
