-
题目:输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
先对这个序列从小到大排序,然后输出前面的最小的k个数即可。如果选择快速排序法来进行排序,则时间复杂度:O(n*logn)
function findMin(arr,k){
var arr1 = [];
for(var i = 0; i<arr.length; i++){
for(var j = 0; j<arr.length-1-i;j++){
if(arr[j] > arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(var h = 0;h<k;h++ ){
arr1.push(arr[h]);
}
return arr1;
}
var arr=[2,8,7,9,6,5,1,10,3,4];
console.log(findMin(arr, 4));
var N = 90;
function multiplyNum(N){
var arr = [];
var temp = []; //一个新的临时数组
for(var n = N; n > 0; n--){
if(N%n == 0 ){
for (var m = N;m>0;m--){
if (m*n == N){
var arr1 = arr.push(m,n);
for(var i = 0; i < arr.length; i++){
if(temp.indexOf(arr[i]) == -1){
temp.push(arr[i]);
}
}
}
}
}
}
var newArr = temp.map((e, i) => i % 2 ? null : [temp[i], temp[i + 1]]).filter(Boolean);
return newArr;
}
console.log(multiplyNum(N))
-
题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点,输出这两个结点在树中最低的共同父结点。
有两种思路,
一种是通过中序遍历和后序遍历。由于中序遍历是先左子树中的结点,再访问根,再访问右子树中结点,因此这两个结点的公共父结点一定处于这两个结点之间。
如:中序遍历:8, 4, 9, 2, 5, 1, 6, 3, 7 结点2处于结点8 和 结点5 之间,也就是说:结点8 和 结点5 的最低公共父结点在 [8~5]之间的候选结点,
这里为{4,9,2}中取后序遍历是先访问左右子树中的结点,最后再访问根。故这两个结点的最低公共父结点一定处于 结点8 和 结点5 之后的结点,且是第一个出现在{4,9,2}中的那个结点。
后序遍历:8, 9, 4, 5, 2, 6, 7, 3, 1 8->9->4->5 这之后的结点,才可能是 结点8 和 结点5 的父结点。
另一种方法则是:递归,首先从树根开始考虑:
①结点A 和 结点B 要么都在树根的左子树中;②要么都在树根的右子树中;③要么一个在左子树中,一个在右子树中。
这是一个分治算法,对于情况①和②,可以继续递归分解。对于情况③属于代码第10行判断,复杂度为O(1)。
递归表达式可表示为:T(N)=2T(N/2)+O(1),解得T(N)=O(N)
对于③,最低公共父结点为树根。
对于①,可以进一步判断,从树根的左孩子结点考虑:
1)结点A 和 结点B 要么都在树根的左子孩子 的 左子树中;2)要么都在树根的左孩子 的 右子树中;3) 要么一个在树根的左孩子的 左子树中,一个在树根的左孩子 的 右子树中。
对于②,可以进一步判断,从树根的右孩子的结点考虑:
1)结点A 和 结点B 要么都在树根的右子孩子 的 左子树中;2)要么都在树根的右孩子 的 右子树中;3) 要么一个在树根的右孩子的 左子树中,一个在树根的右孩子 的 右子树中。
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;
struct TreeNode
{
int m_nValue;
TreeNode *m_pLeft;
TreeNode *m_pRight;
};
//假定所创建的二叉树如下图所示
/*
/
1
/ / /
2 3
/ / / /
4 5 6 7
/ /
8 9
/
*/
void CreateBitree(TreeNode *&pNode, fstream &fin, TreeNode *&pNodeOne, TreeNode *&PNodeTwo)
{
int dat;
fin>>dat;
if(dat == 0)
{
pNode = NULL;
}
else
{
pNode = new TreeNode();
pNode->m_nValue = dat;
if (NULL == pNodeOne && !(rand() % 3))
{
pNodeOne = pNode;
}
if (NULL == PNodeTwo && !(rand() % 5))
{
PNodeTwo = pNode;
}
CreateBitree(pNode->m_pLeft, fin, pNodeOne, PNodeTwo);
CreateBitree(pNode->m_pRight, fin, pNodeOne, PNodeTwo);
}
}
//寻找二叉树两个结点的最低共同父节点
TreeNode *FindFirstCommonParentNode(TreeNode *pRoot, TreeNode *pNodeOne, TreeNode *pNodeTwo)
{
if (NULL == pRoot)
{
return NULL;
}
if (pRoot == pNodeOne || pRoot == pNodeTwo)
{
return pRoot;
}
TreeNode *pLeft = FindFirstCommonParentNode(pRoot->m_pLeft, pNodeOne, pNodeTwo);
TreeNode *pRight = FindFirstCommonParentNode(pRoot->m_pRight, pNodeOne, pNodeTwo);
if (NULL == pLeft) //1、左子树没有找到任何一个结点,则第一个公共父节点必定在右子树,而且找到第一个结点就是最低共同父节点
{
return pRight;
}
else if (NULL == pRight) //2、右子树没有找到任何一个结点,则第一个公共父节点必定在左子树,而且找到第一个结点就是最低共同父节点
{
return pLeft;
}
else //3、分别在结点的左右子树找到,则此节点必为第一个公共父节点
{
return pRoot;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
srand((unsigned)time(NULL));
fstream fin("tree.txt");
TreeNode *pRoot = NULL;
TreeNode *pNodeOne = NULL;
TreeNode *pNodeTwo = NULL;
TreeNode *pParent = NULL;
CreateBitree(pRoot, fin, pNodeOne, pNodeTwo);
pParent = FindFirstCommonParentNode(pRoot, pNodeOne, pNodeTwo);
cout<<"第一个结点为:"<<pNodeOne->m_nValue<<endl;
cout<<"第二个结点为:"<<pNodeTwo->m_nValue<<endl;
cout<<"首个父结点为:"<<pParent->m_nValue<<endl;
cout<<endl;
return 0;
}
-
给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
#include <iostream>
#include <iomanip>
#include <limits>
using namespace std;
void copystr(char pachar[], char pbchar[], int sza, int szb, char* &result);
int main()
{
char pachar[] = "woaimai";
char pbchar[] = "maio";
int sza = sizeof(pachar);
int szb = sizeof(pbchar);
int sz = sza + szb - 1;
char* result = new char[sz];
copystr(pachar, pbchar, sza, szb, result);
cout << result << endl;
return 0;
}
void copystr(char pachar[], char pbchar[], int sza, int szb, char* &result)
{
int posa = 0;
int posb = 0;
int pos = 0;
int sa = 0;
int sz = sza + szb - 1;
while(pos < sz && posa < sza - 1 && posb < szb - 1){ // 字符串索引为 [0 ~ size -1], 最后一个字符为结束字符‘