算法题积累 切面条

算法题积累 切面条

一、切面条

一根高筋拉面，中间切一刀，可以得到2根面条。
如果先对折1次，中间切一刀，可以得到3根面条。
如果连续对折2次，中间切一刀，可以得到5根面条。
那么，连续对折10次，中间切一刀，会得到多少面条呢？

/*** 思路一:算弯道* 不折    直线2   折点为0* 折一次  直线2   折点为1（2^0）* 折两次  直线2   折点为3（2^0+2^1）* 折三次  直线2   折点为7（2^0+2^1+2^2）* 折四次  直线2   折点为15（2^0+2^1+2^2+2^3）* ……* 折N次  直线2   折点为2^N-1（2^0+2^1+2^2+2^3+……+2^(N-1)）* * --------------------------* 一个折点代表一条线  总条数=直线+折点*/private double t1(int a) {double s = 2;if (a==0) return s;s = Math.pow(s,a-1) + t1(a-1);return s;}

/*** 思路二:每一次折至少有一个折点，这个折点在每次折的时候都不会翻倍，所以下一次折的条数是2*（上一次折的条数-1）+1(不会翻倍的折点)* 不折    2* 折一次  3 2*(2-1)+1* 折两次  5 2*(3-1)+1* 折三次  9 2*(5-1)+1* 折四次  17 2*(9-1)+1* ……* 折N次  2（N-1）+1** --------------------------* 一个折点代表一条线  总条数=直线+折点*/private double t2(int a) {int sum = 2;for (int i = 1; i <= a; i++) {sum = (sum-1)*2+1;// sum = sum*2-1}return sum;}

二、数字中有两个数出现奇数次，其余数出现偶数次，分别求出这两个值？

假设两个出现奇数次的数为a、b，现将所有数异或，结果必然为a^b，如果此时a^b!=0，则必定在二进制数字某个位置存在1，这表明a和b在该位上不相等，根据这个条件，将该位上为1和为0的分别取出与a^b与，结果便可算出。

public class Xor extends GetTwoValues{public void getTwoValuesByXor(int[] arr) {GetTwoValues getTwoValues = new GetTwoValues() {/*** 通过异或获取数组中出现奇数次的两个数** @param arr* @date 2022/5/30 11:00*/@Overridepublic void getTwoOddOccurrenceValuesFromAnArrayByXor(int[] arr) {int a = 0, b, eor = 0;// 获取a^bfor (int i : arr) {eor ^= i;}/** 获取a^b最右边为1的值* a         1100* b         1011* eor       0111* ~eor      1000* ~eor + 1  1001* rightOne  0001*/int rightOne = eor & (~eor + 1);for (int i : arr) {// 与rightOne &后为0，表示该位置为0（xxx0）if ((rightOne & i) == 0) {// 所有xxx0类型的值异或或，获得第一个值a ^= i;}}// b = a ^ b ^ a;b = eor ^ a;System.out.println("a = " + a + "; b = " + b);}};TwoOddOccurrenceValuesFromAnArrayByXor(arr);}
}