swap(list, k, i);
perm(list, k &＃43; 1);
swap(list, k, i);
}
}
}
private static void swap(int[] list, int pos1, int pos2) {
int temp &＃61; list[pos1];
list[pos1] &＃61; list[pos2];
list[pos2] &＃61; temp;
}
public static void main(String[] args) {
int[] x &＃61; {1, 2, 3, 4, 5};
perm(x);
}
}
5.对于一个有N个整数元素的一维数组&＃xff0c;找出它的子数组(数组中下标连续的元素组成的数组)之和的最大值。
下面给出几个例子(最大子数组用粗体表示)&＃xff1a;
数组&＃xff1a;{ 1, -2, 3,5, -3, 2 }&＃xff0c;结果是&＃xff1a;8
2) 数组&＃xff1a;{ 0, -2, 3, 5, -1, 2 }&＃xff0c;结果是&＃xff1a;9
3) 数组&＃xff1a;{ -9, -2,-3, -5, -3 }&＃xff0c;结果是&＃xff1a;-2
可以使用动态规划的思想求解&＃xff1a;public class MaxSum {
private static int max(int x, int y) {
return x > y? x: y;
}
public static int maxSum(int[] array) {
int n &＃61; array.length;
int[] start &＃61; new int[n];
int[] all &＃61; new int[n];
all[n - 1] &＃61; start[n - 1] &＃61; array[n - 1];
for(int i &＃61; n - 2; i >&＃61; 0;i--) {
start[i] &＃61; max(array[i], array[i] &＃43; start[i &＃43; 1]);
all[i] &＃61; max(start[i], all[i &＃43; 1]);
}
return all[0];
}
public static void main(String[] args) {
int[] x1 &＃61; { 1, -2, 3, 5,-3, 2 };
int[] x2 &＃61; { 0, -2, 3, 5,-1, 2 };
int[] x3 &＃61; { -9, -2, -3,-5, -3 };
System.out.println(maxSum(x1)); // 8
System.out.println(maxSum(x2)); // 9
System.out.println(maxSum(x3)); //-2
}
}
6.用递归实现字符串倒转public class StringReverse {
public static String reverse(String originStr) {
if(originStr &＃61;&＃61; null || originStr.length()&＃61;&＃61; 1) {
return originStr;
}
return reverse(originStr.substring(1))&＃43; originStr.charAt(0);
}
public static void main(String[] args) {
System.out.println(reverse("hello"));
}
}
7.输入一个正整数&＃xff0c;将其分解为素数的乘积。public class DecomposeInteger {
private static List list &＃61; new ArrayList();
public static void main(String[] args) {
System.out.print("请输入一个数: ");
Scanner sc &＃61; new Scanner(System.in);
int n &＃61; sc.nextInt();
decomposeNumber(n);
System.out.print(n &＃43; " &＃61; ");
for(int i &＃61; 0; i System.out.print(list.get(i) &＃43; " * ");
}
System.out.println(list.get(list.size() - 1));
}
public static void decomposeNumber(int n) {
if(isPrime(n)) {
list.add(n);
list.add(1);
}
else {
doIt(n, (int)Math.sqrt(n));
}
}
public static void doIt(int n, int div) {
if(isPrime(div) && n % div &＃61;&＃61; 0) {
list.add(div);
decomposeNumber(n / div);
}
else {
doIt(n, div - 1);
}
}
public static boolean isPrime(int n) {
for(int i &＃61; 2; i <&＃61; Math.sqrt(n);i&＃43;&＃43;) {
if(n % i &＃61;&＃61; 0) {
return false;
}
}
return true;
}
}
8、一个有n级的台阶&＃xff0c;一次可以走1级、2级或3级&＃xff0c;问走完n级台阶有多少种走法。public class GoSteps {
public static int countWays(int n) {
if(n <0) {
return 0;
}
else if(n &＃61;&＃61; 0) {
return 1;
}
else {
return countWays(n - 1) &＃43; countWays(n - 2) &＃43; countWays(n -3);
}
}
public static void main(String[] args) {
System.out.println(countWays(5)); // 13
}
}
9.写一个算法判断一个英文单词的所有字母是否全都不同(不区分大小写)public class AllNotTheSame {
public static boolean judge(String str) {
String temp &＃61; str.toLowerCase();
int[] letterCounter &＃61; new int[26];
for(int i &＃61; 0; i
int index &＃61; temp.charAt(i)- &＃39;a&＃39;;
letterCounter[index]&＃43;&＃43;;
if(letterCounter[index] > 1) {
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println(judge("hello"));
System.out.print(judge("smile"));
}
}
10.有一个已经排好序的整数数组&＃xff0c;其中存在重复元素&＃xff0c;请将重复元素删除掉&＃xff0c;例如&＃xff0c;A&＃61; [1, 1, 2, 2, 3]&＃xff0c;处理之后的数组应当为A&＃61; [1, 2, 3]。public class RemoveDuplication {
public static int[] removeDuplicates(int a[]) {
if(a.length <&＃61; 1) {
return a;
}
int index &＃61; 0;
for(int i &＃61; 1; i if(a[index] !&＃61; a[i]) {
a[&＃43;&＃43;index] &＃61; a[i];
}
}
int[] b &＃61; new int[index &＃43; 1];
System.arraycopy(a, 0, b, 0, b.length);
return b;
}
public static void main(String[] args) {
int[] a &＃61; {1, 1, 2, 2, 3};
a &＃61; removeDuplicates(a);
System.out.println(Arrays.toString(a));
}
}
11.给一个数组&＃xff0c;其中有一个重复元素占半数以上&＃xff0c;找出这个元素。public class FindMost {
public static T find(T[] x){
T temp &＃61; null;
for(int i &＃61; 0, nTimes &＃61; 0; iif(nTimes &＃61;&＃61; 0) {
temp&＃61; x[i];
nTimes&＃61; 1;
}
else {
if(x[i].equals(temp)) {
nTimes&＃43;&＃43;;
}
else {
nTimes--;
}
}
}
return temp;
}
public static void main(String[] args) {
String[]strs &＃61; {"hello","kiss","hello","hello","maybe"};
System.out.println(find(strs));
}
}
12.编写一个方法求一个字符串的字节长度?public int getWordCount(String s){
int length &＃61; 0;
for(int i &＃61; 0; i {
int ascii &＃61; Character.codePointAt(s, i);
if(ascii >&＃61; 0 && ascii <&＃61;255)
length&＃43;&＃43;;
else
length &＃43;&＃61; 2;
}
return length;
}
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号