剑指offer(四)

<h2>剑指offer(四)</h2>

<h3>面试题四十：数组中只出现1次的数字</h3>

<blockquote>
题目：一个整形数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1);
</blockquote>

<pre><code class="java">package offer;

/**

• Created by KiSoo on 2017/2/7.
  */
  public class Offer40 {
  public static int[] findNumbersAppearanceOnce(int[] data) {
  int[] result = {0, 0};
  if (data == null || data.length < 2) {
  return result;
  }
  int xor = 0;
  for (int i : data) {
  xor ^= i;
  }
  int indexOf1 = findFirstBit1(xor);
  for (int i : data) {
  if (isBit1(i, indexOf1)) {
  result[0] ^= i;
  } else {
  result[1] ^= i;
  }
  }
  return result;
  }

  private static int findFirstBit1(int num) {
  int index = 0;
  while ((num & 1) == 0 && index < 32) {
  num = num >> 1;
  index++;
  }
  return index;
  }

  private static boolean isBit1(int num, int indexBit) {
  num = num >> indexBit;
  return (num & 1) == 1;
  }

  public static void main(String[] args) {
  int[] data1 = {2, 4, 3, 6, 3, 2, 5, 5};
  int[] result1 = findNumbersAppearanceOnce(data1);
  System.out.println(result1[0] + " " + result1[1]);
  int[] data2 = {4, 6};
  int[] result2 = findNumbersAppearanceOnce(data2);
  System.out.println(result2[0] + " " + result2[1]);
  int[] data3 = {4, 6, 1, 1, 1, 1};
  int[] result3 = findNumbersAppearanceOnce(data3);
  System.out.println(result3[0] + " " + result3[1]);
  }
  }

</code></pre>

<h4>思路</h4>

先将数组中的所有数字异或操作。然后，拿到得出的数值的最高位数字k，判断数字右移k后是否为0。如果为0，则为第一个数字，而将剩下的数字全部异或后就得出第二个不重复的数字啦。

<h3>面试题四十一：和为s的两个数字VS和为s的连续正数序列</h3>

<blockquote>
题目一：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s。输出任意一对即可。
</blockquote>

<pre><code class="java">package offer;

import java.util.Arrays;

/**

• Created by KiSoo on 2017/2/7.
  */
  public class offer41 {

  public static void main(String... args) {
  int[] a = {1, 2, 4, 7, 11, 15};
  Utils.syso(Arrays.toString(getResult(a, 15)));
  }

  public static int[] getResult(int[] data, int target) {
  int[] result = {0, 0};
  if (data == null) {
  return result;
  }
  int index1 = data.length - 1;
  int index2 = 0;
  while (index1 > index2) {
  int curr = data[index1] + data[index2];
  if (curr == target) {
  result[0] = data[index1];
  result[1] = data[index2];
  return result;
  } else if (curr > target) {
  index1--;
  } else index2++;
  }
  return result;
  }
  }

</code></pre>

<h4>思路</h4>

两个指针，分别指向首尾，然后逐个相加，大于的话，尾指针前移，小于则首指针后移。

<blockquote>
题目二：输入一个正数s，打印出所有和为s的连续正数序列。
</blockquote>

<pre><code class="java">public static void findArray(int num) {
if (num < 3)
return;
int small = 1;
int big = 2;
int middle = (1 + num) / 2;
int curSum = small + big;
while (small < middle) {
if (curSum == num)
System.out.println(small + "-->" + big);
while (curSum > num && small < middle) {
curSum -= small;
small++;
if (curSum == num)
System.out.println(small + "-->" + big);
}
big++;
curSum += big;
}
}
</code></pre>

<h4>思路</h4>

遍历(k+1)/2，不停地叠加终点，如果超过，就减去起点。起点++。直到起点大于半值。

<h3>面试题四十二：翻转单词顺序 VS 左旋旋转字符串</h3>

<blockquote>
题目一：输入一个英文句子，反转句子中单词的顺序，但单词内字符串的顺序不变。为简单起见，标点符号和普通字母一样处理。例如，输入字符串"I am a student."，则输出“student. a am I"。
</blockquote>

<h4>思路</h4>

1.先全部反转，再分单词反转。
2.使用栈，把单词全拷贝进入，然后再分单词读出。

<pre><code class="java">package offer;

import java.util.Stack;

/**

• Created by KiSoo on 2017/2/8.
  */
  public class Offer42 {
  public static void main(String... args) {
  String str = "I am a student.";
  String str1 = getReverse(str);
  Utils.syso(str1);
  }

  private static String getReverse2(String str) {
  StringBuilder temp = new StringBuilder();
  Stack<String> stack = new Stack<>();
  for (int i = 0; i < str.length(); i++) {
  char c = str.charAt(i);
  if (c != ' ') {
  temp.append(c);
  } else {
  stack.push(temp.toString());
  temp.delete(0, temp.length() - 1);
  }
  }
  stack.push(temp.toString());
  temp.delete(0, temp.length() - 1);
  for (String c : stack) {
  temp.append(c).append(" ");
  }
  temp.delete(temp.length() - 1, temp.length());
  return temp.toString();
  }

  private static String getReverse(String str) {
  char[] chars = str.toCharArray();
  reverse(chars, 0, chars.length - 1);
  reverseSentence(chars);
  return new String(chars);
  }

  public static void reverseSentence(char[] chars) {
  if (chars == null)
  return;
  int begin = 0, end = 0;
  while (begin < chars.length - 1) {
  if (chars[begin] == ' ') {
  begin++;
  end++;
  } else if (chars[end] == ' ' || end == chars.length - 1) {
  reverse(chars, begin, end - 1);
  begin = end;
  } else {
  end++;
  }
  }

  }

  private static char[] reverse(char[] chars, int index1, int index2) {
  while (index1 < index2) {
  char temp = chars[index1];
  chars[index1] = chars[index2];
  chars[index2] = temp;
  index1++;
  index2--;
  }
  return chars;
  }
  }

</code></pre>

<blockquote>
题目二：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部，请定义一个函数实现字符串左旋转操作的功能。比如输入字符串abcdefg和数字2，该函数将返回左旋转2位得到的结果“cdefgab”。
</blockquote>

<pre><code> public static void leftRotate(char[] data,int n){
reverse(data,0,n-1);
reverse(data,n,data.length-1);
reverse(data,0,data.length-1);
}
</code></pre>

<h3>面试题四十三：n个骰子的点数</h3>

<pre><code>package offer;

public class Offer43 {
/**
* 基于通归求解
*
* @param number 色子个数
* @param max 色子的最大值
/
public static void printProbability(int number, int max) {
if (number < 1 || max < 1) {
return;
}
int maxSum = number * max;
int[] probabilities = new int[maxSum - number + 1];
probability(number, probabilities, max);
double total = 1;
for (int i = 0; i < number; i++) {
total = max;
}
for (int i = number; i <= maxSum; i++) {
double ratio = probabilities[i - number] / total;
System.out.printf("%-8.4f", ratio);
}
System.out.println();
}
/
* @param number 色子个数
* @param probabilities 不同色子数出现次数的计数数组
* @param max 色子的最大值
/
private static void probability(int number, int[] probabilities, int max) {
for (int i = 1; i <= max; i++) {
probability(number, number, i, probabilities, max);
}
}
/*
* @param original 总的色子数
* @param current 当前处理的是第几个
* @param sum 已经前面的色子数和
* @param probabilities 不同色子数出现次数的计数数组
* @param max 色子的最大值
/
private static void probability(int original, int current, int sum, int[] probabilities, int max) {
if (current == 1) {
probabilities[sum - original]++;
} else {
for (int i = 1; i <= max; i++) {
probability(original, current - 1, i + sum, probabilities, max);
}
}
}
/*
* 基于循环求解
* @param number 色子个数
* @param max 色子的最大值
*/
public static void printProbability2(int number, int max) {
if (number < 1 || max < 1) {
return;
}
int[][] probabilities = new int[2][max * number + 1];
// 数据初始化
for (int i = 0; i < max * number + 1; i++) {
probabilities[0][i] = 0;
probabilities[1][i] = 0;
}
// 标记当前要使用的是第0个数组还是第1个数组
int flag = 0;
// 抛出一个骰子时出现的各种情况
for (int i = 1; i <= max; i++) {
probabilities[flag][i] = 1;
}
// 抛出其它骰子
for (int k = 2; k <= number; k++) {
// 如果抛出了k个骰子，那么和为[0, k-1]的出现次数为0
for (int i = 0; i < k; i++) {
probabilities[1 - flag][i] = 0;
}
// 抛出k个骰子，所有和的可能
for (int i = k; i <= max * k; i++) {
probabilities[1 - flag][i] = 0;
// 每个骰子的出现的所有可能的点数
for (int j = 1; j <= i && j <= max; j++) {
// 统计出和为i的点数出现的次数
probabilities[1 - flag][i] += probabilities[flag][i - j];
}
}
flag = 1 - flag;
}
double total = 1;
for (int i = 0; i < number; i++) {
total *= max;
}
int maxSum = number * max;
for (int i = number; i <= maxSum; i++) {
double ratio = probabilities[flag][i] / total;
System.out.printf("%-8.4f", ratio);
}
System.out.println();
}
public static void main(String[] args) {
test01();
test02();
}
private static void test01() {
printProbability(2, 4);
}
private static void test02() {
printProbability2(2, 4);
}
}
</code></pre>

<h3>面试题四十四：扑克牌的顺子</h3>

<blockquote>
题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这五张牌是不是连续的，2~10为数字本身，A为1，J为11，Q为12，K为13。大小王可以看成任意数字。
</blockquote>

<h4>思路</h4>

快速排序这组数组。

<pre><code>package offer;

import static offer.SortUtils.exchangeE;

/**

• Created by KiSoo on 2017/2/10.
  */
  public class Offer44 {
  public static void main(String... args) {
  int[] a = {7, 6, 4, 8, 2};
  Utils.syso(isContinous(a));
  }

  public static boolean isContinous(int[] numbers) {
  if (numbers == null || numbers.length < 5) {
  return false;
  }
  quickSort(numbers, 0, numbers.length - 1);
  int numOfZero = 0;
  int numOfGap = 0;
  for (int i = 0; i < numbers.length; i++) {
  if (numbers[i] == 0)
  numOfZero++;
  }
  int small = numOfZero;
  int big = small + 1;
  while (big < numbers.length) {
  if (numbers[small] == numbers[big]) {
  return false;
  }
  numOfGap += numbers[big] - numbers[small] - 1;
  small = big;
  big++;
  }
  return numOfZero >= numOfGap;
  }

  private static void quickSort(int[] numbers, int start, int end) {
  if (start > end)
  return;
  int i = sort(numbers, start, end);
  if (i == start) {
  quickSort(numbers, start + 1, end);
  } else if (i == end) {
  quickSort(numbers, start, end - 1);
  } else {
  quickSort(numbers, start, i - 1);
  quickSort(numbers, i + 1, end);
  }
  }

  private static int sort(int[] numbers, int left, int right) {
  int index = left;
  int target = numbers[right];
  for (int i = left; i < right; i++) {
  if (numbers[i] < target) {
  if (i != index) {
  exchangeE(numbers, index, i);
  }
  index++;
  }
  }
  exchangeE(numbers, index, right);
  return index;
  }
  }

</code></pre>

<h3>面试题四十五：圆圈中最后剩下的数字</h3>

<blockquote>
题目：从0,1,...,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字，求出这个圆圈里剩下的最后一个数字。
</blockquote>

<h4>思路</h4>

<ol>
<li>使用一个环形链表，模拟圆圈。</li>
<li>推倒出公式，利用递归或循环。</li>
</ol>

<pre><code class="java">package offer;

import java.util.ArrayList;

/**

• Created by KiSoo on 2017/2/10.
  */
  public class Offer45 {
  public static void main(String... args) {
  Utils.syso(lastRemaining(5, 3));
  }

  public static int lastRemaining(int n, int m) {
  ArrayList<Integer> array = new ArrayList<>();
  for (int i = 0; i < n; i++) {
  array.add(i);
  }
  int idx = 0;
  while (array.size() != 1) {
  idx = (idx + m - 1) % array.size();
  array.remove(idx);
  }
  return array.get(0);
  }

  public static int getM(int m, int size) {
  m = 3 + m;
  while (m > size) {
  m = m - size;
  }
  return m;
  }
  }

</code></pre>