有趣的算法题2

一：二叉搜索树和双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

1.要用一个lastNode指针指着最右的节点。

/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
TreeNode lastNode = null;
lastNode = ConvertNode(pRootOfTree, lastNode);
while(lastNode != null && lastNode.left != null){
lastNode = lastNode.left;
}
return lastNode;

}
public TreeNode ConvertNode(TreeNode root, TreeNode lastNode){
if(root == null)
return null;
if(root.left != null)
lastNode = ConvertNode(root.left, lastNode);
root.left = lastNode;
if(lastNode != null)
lastNode.right = root;
lastNode = root;
if(root.right != null){
lastNode = ConvertNode(root.right, lastNode);
}
return lastNode;
}
}

二：字符串排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

import java.util.ArrayList;
import java.util.*;
public class Solution {
public ArrayList Permutation(String str) {
ArrayList list = new ArrayList();
int index = 0;
Permutation(list, index, str.toCharArray());
Collections.sort(list);
return list;

}
public void Permutation(ArrayList list, int index, char[] str){
if(index == str.length - 1)
list.add(new String(str));
else{
for(int i = index; i if(i == index || str[i] != str[index])
{
swap(str, i, index);
Permutation(list, index+1, str);
swap(str, index, i);
}
}
}
}
public void swap(char[] str, int i, int j){
if(str.length <2)
return;
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}

三：数组中出现次数超过一半的元素

1.先拿第一个数作为标准num，后面元素相同count+1，不同count-1;当count==0时，num指向新的数，令count=1，再继续这样下去，知道后面。

2.用最后得到的num再遍历一次，看看出现次数是否真的大于array.length/2;

四：最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

1.先对前K个数建最大堆。

2.K后面的数依次和堆顶元素比较，小于堆顶的删除堆顶元素，使该元素进队，一直维持这个堆为K个元素。

3.最后那个堆里的K个数即为所求元素。

import java.util.*;
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList list = new ArrayList();
if(input == null || input.length return list;
for(int i = k/2 - 1; i >= 0; i--){
adjustMaxHeap(input, i, k-1);
}
for(int i = k; i if(input[i] {
int temp = input[i];
input[i] = input[0];
input[0] = temp;
adjustMaxHeap(input, 0, k-1);
}
}
for(int i = 0; i list.add(input[i]);
}
return list;
}
public void adjustMaxHeap(int[] input, int pos, int length){
int child = 0;
int temp;
for(temp = input[pos]; 2*pos+1 <= length; pos = child)
{
child = 2*pos+1;
if(child {
child++;
}
if(input[child] > temp){
input[pos] = input[child];
}
else{
break;
}
}
input[pos] = temp;
}
}

五：把数组排成最小数

1.定义一个Collections的函数使它把list里的所有组合按组合的大小排序。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
ArrayList list = new ArrayList();
int n = numbers.length;
String s = "";
for(int i = 0; i {
list.add(numbers[i]);
}
Collections.sort(list, new Comparator(){
public int compare(Integer s1, Integer s2)
{
String str1 = s1 + "" + s2;
String str2 = s2 + "" + s1;
return str1.compareTo(str2);
}
});
for(int data : list)
{
s += data;
}
return s;
}
}

六：查找第N个丑数（只能被2,3,5整除）

1.建造一个N长度的数组，和p2,p3,p5三个指针。

2.三个指针分别乘上对应的数，比较找到最小的添加在数组的下一个数，这是只有选中的指针后退，其他的不变。

public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index <= 0)
return 0;
int[] pUgly = new int[index];
pUgly[0] = 1;
int nextUgly = 1;
int p2 = 0;
int p3 = 0;
int p5 = 0;
while(nextUgly {
int min = Min(2*pUgly[p2], 3*pUgly[p3], 5*pUgly[p5]);
pUgly[nextUgly] = min;
if(2*pUgly[p2] <= pUgly[nextUgly])
p2++;
if(3*pUgly[p3] <= pUgly[nextUgly])
p3++;
if(5*pUgly[p5] <= pUgly[nextUgly])
p5++;
nextUgly++;
}
return pUgly[nextUgly-1];


}
public int Min(int p1, int p2, int p3)
{
return p1 >= p2 ? (p2 > p3 ? p3 : p2) : (p1 > p3 ? p3 : p1);
}
}

七：第一个出现一次的字符

import java.util.*;
public class Solution {
public int FirstNotRepeatingChar(String str) {
Map map = new HashMap();
char[] ch = str.toCharArray();
for(int i = 0; i {
if(map.containsKey(ch[i]))
{
map.put(ch[i], map.get(ch[i])+1);
}
else{
map.put(ch[i], 1);
}
}
for(int i = 0; i {
if(map.get(ch[i]) == 1)
return i;
}
return -1;
}
}

八：数组中的逆序对

1.要用归并排序解决

public class Solution {
public int InversePairs(int [] array) {
if(array.length <= 1 || array == null)
return 0;
int[] copy = new int[array.length];
for(int i = 0; i copy[i] = array[i];
int count = 0;
count = InverseCorePairs(array, copy, 0, array.length-1)%1000000007;
return count % 1000000007;
}
public int InverseCorePairs(int[] array, int[] copy, int start, int end)
{
if(start == end)
{
return 0;
}
int mid = (start+end)>>1;
int left = InverseCorePairs(array, copy, start, mid)%1000000007;
int right = InverseCorePairs(array, copy, mid+1, end)%1000000007;
int i = mid;
int j = end;
int copyIndex = end;
int count = 0;
while(i >= start && j >= mid+1)
{
if(array[i] > array[j])
{
copy[copyIndex--] = array[i--];
count += j - mid;
if(count >= 1000000007)
count = count % 1000000007;
}
else{
copy[copyIndex--] = array[j--];
}
}
for(;i >= start; i--)
{
copy[copyIndex--] = array[i];
}
for(; j >= mid+1; j--)
{
copy[copyIndex--] = array[j];
}
for(int ii = start; ii <= end; ii++)
array[ii] = copy[ii];
return (left + count + right)%1000000007;
}
}


九：数组中只出现一次的数字

1.将数组中所有的数异或得到结果mayor(相同的全部相消了，剩下的是两个不同的数)。

2.找到mayor中最后一个为1的数。

3.根据次数将数组分为两组，两个不同的数分别落在两组，最后用异或求出最后的数。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int mayor = 0;
for(int i = 0; i {
mayor ^= array[i];
}
int flag = 1;
while((flag & mayor) == 0)
flag <<= 1;
for(int i = 0; i {
if((array[i] & flag) == 0)
num1[0] ^= array[i];
else
num2[0] ^= array[i];
}

}
}

十：和为S的连续整数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

1）由于我们要找的是和为S的连续正数序列，因此这个序列是个公差为1的等差数列，而这个序列的中间值代表了平均值的大小。假设序列长度为n，那么这个序列的中间值可以通过（S / n）得到，知道序列的中间值和长度，也就不难求出这段序列了。

2）满足条件的n分两种情况：

n为奇数时，序列中间的数正好是序列的平均值，所以条件为：(n & 1) == 1 && sum % n == 0；

n为偶数时，序列中间两个数的平均值是序列的平均值，而这个平均值的小数部分为0.5，所以条件为：(sum % n) * 2 == n.

3）由题可知n >= 2，那么n的最大值是多少呢？我们完全可以将n从2到S全部遍历一次，但是大部分遍历是不必要的。为了让n尽可能大，我们让序列从1开始，

根据等差数列的求和公式：S = (1 + n) * n / 2，得到.

最后举一个例子，假设输入sum = 100，我们只需遍历n = 13~2的情况（按题意应从大到小遍历），n = 8时，得到序列[9, 10, 11, 12, 13, 14, 15, 16]；n  = 5时，得到序列[18, 19, 20, 21, 22]。

完整代码：时间复杂度为

import java.util.ArrayList;
public class Solution {
public ArrayList > FindContinuousSequence(int sum) {
ArrayList> list = new ArrayList>();
for(int n = (int)Math.sqrt(2*sum); n>=2; n--)
{
if(((n&1)==1 && sum%n == 0) || ((sum%n)*2 == n))
{
ArrayList l = new ArrayList();
for(int j = 0, k = sum/n - (n-1)/2; j {
l.add(k++);
}
list.add(l);
}
}
return list;
}
}

十一：孩子们的游戏（圆圈中最后一个数字）

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

1.用一个数组arr[]从1到n记录，若蹲下了记为0；

2.index记录走过的人数，dunNumbers记录走过的但是却是蹲下的人数，duns记录蹲下的人数。

public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n <1 || m <1)
return -1;
int[] arr = new int[n];
for(int i = 0; i arr[i] = i+1;
int index = 0;
int duns = 0;
int dunNumbers = 0;
while(duns != n-1)
{
if(arr[index%n] == 0)
{
dunNumbers++;
index++;
}
else{
if((index+1-dunNumbers)%m==0)
{
arr[index%n] = 0;
index++;
duns++;
}
else{
index++;
}
}
}
for(int i = 0; i if(arr[i] != 0)
return arr[i]-1;
return -1;

}
}