面试经典算法

1.全排列

• 1 字典序法………………………………………………………………………..

  字典序法主要用来求下一个方便。如果要完全遍历 字典序法并不是比较好的选择。时间还是比较复杂的,需要比较n!次
  字典序法的主要步骤为：

  • 1. 对于序列A 从右至左 找出第一个左边小于右边的数字。并记下其位置i.
  • 2. 继续对该序列 从右至左 找出第一个比A[i] 大的数字 记下其位置j(要保证j>i). 由于A[i]右侧的数字是递增的。在A[i]的右边的数字中，找出所有比A[i]大的数中最小的数字A[j]，即 j=max{i|pj>pi}（右边的数从右至左是递增的，因此j是所有大于A[i]的数字中序号最大者）
  • 3. 交换 A序列 i j 位置的值即A[i] 和 A[j]的值.
  • 4. 反转序列 A[i+1]A[i+2]…A[j]
  • 5. 反转之后的序列即为当前排列的下一排列。
       那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后我们再从后往前找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字转置一下即可，步骤如下：

1　　2　　7　　4　　3　　1

1　　2　　7　　4　　3　　1

1　　3　　7　　4　　2　　1

1　　3　　1　　2　　4　　7

• 2. 递归求解。主要思想是动态规划：即当前任务的完成是在上一个任务的基础上的。对已N个数 每个数轮流做开头 我们只需对剩余N-1个数的全排列即可，把第N个数放在N-1个数的全排列的开头就构成了N个数的全排列。这个明显的缺点就是有重复问题。
  • 1. 解决重复问题的方法：避免重复的数字做开头就好啦。递归操作时也是如此。保证的重复元素避免多次排列。

2.组合.

对于数组[1,2,3,4,5,6],求任意3个数的组合。

• 1. 同样可以使用递归的思路。对于没有重复元素的数组 对于第一个数选择要或者不要。如果要就从剩余的数中选择出2个数(递归问题)。如果不要 就从剩余的数中选出3个数(递归问题)。
• 2. 关于去重：去重的话只要判断在第i个位置是否已经出现过某数字 有的话 跳过.比如对 1 2 2 选两个数字进行排列.已经有了 [1 2] 时 第二个 [1] + [2]就直接跳过。

  相关问题汇总于C++版排列组合问题全解