亚信校招笔试题目

-*

1.BST

public class BSTMinLength {

public static void main(String[] args) {

TreeNode tNode11 = new TreeNode(10, null, null); TreeNode tNode12 = new TreeNode(50, null, null); TreeNode tNode13 = new TreeNode(5, null, null); TreeNode tNode14 = new TreeNode(30, null, null);

TreeNode tNode21 = new TreeNode(30, tNode11, tNode12); TreeNode tNode22 = new TreeNode(30, tNode13, tNode14); TreeNode tNodeRoot = new TreeNode(100, tNode21, tNode22); System.out.println(minlength(tNodeRoot)); }

private static int minlength(TreeNode tNode) {

if (tNode != null) { return getlength(tNode,0); } return -1; }

private static int getlength(TreeNode tNode,int curLength) { int minLeft=-1; int minRight=-1; if (tNode.leftNode!=null){

minLeft=getlength(tNode.leftNode, curLength+tNode.value); }

if (tNode.rightNode!=null) {

minRight=getlength(tNode.rightNode, curLength+tNode.value); }

if (tNode.leftNode==null && tNode.rightNode==null) { return curLength+tNode.value;

-*

}

if (tNode.leftNode==null) { return minRight; }

if (tNode.rightNode==null) { return minLeft; }

return minLeft>minRight? minRight:minLeft; } }

class TreeNode { int value;

TreeNode leftNode; TreeNode rightNode;

TreeNode(int value, TreeNode lefeNode, TreeNode rightNode) { this.value = value; this.leftNode = lefeNode; this.rightNode = rightNode; } } 2.lru

#include using namespace std;

int lruCountMiss(int max_cache_size, int *pages, int len) {

int count = 0; int i,j,k,n; bool flag = false;

int *a = new int[max_cache_size]; //初始化高速缓存数组

-*

for(i = 0; i < max_cache_size; i++) {

a[i] = -1; }

for(j= 0; j < len; j++) {

for(i = 0; i < max_cache_size; i++) {

if(pages[j] != a[i]) {

continue; } else { break; } }

if(i != max_cache_size) {

for(k = i; k < max_cache_size; k++) {

if(a[k] == -1) {

flag = true; break; } } if(!flag) {

for(n = i; n < max_cache_size - 1; n++)

-*

{

a[n] = a[n+1]; }

a[max_cache_size - 1] = pages[j]; } else {

flag = false;

for(n = i; n < k - 1; n++) {

a[n] = a[n+1]; }

a[k - 1] = pages[j]; } } else {

count ++;

for(i = 0; i < max_cache_size; i++) {

if(a[i] == -1) {

a[i] = pages[j]; flag = true; break; } } if(!flag) {

for(i = 0; i < max_cache_size-1; i++)

-*

{

a[i] = a[i+ 1]; }

a[max_cache_size - 1] = pages[j]; } else

flag = false; } }

return count; }

int main() {

int arr[] = {7, 0, 1, 2, 0, 3, 0, 4}; cout << lruCountMiss(3, arr, 8) << endl; return 0; } 3.反转链表

lnode *reverse(lnode *head){

if(head){

lnode *prev = NULL; lnode *curr = head; lnode *next = curr->next; curr->next = prev;

while(next != NULL){

prev = curr; curr = next; next = next->next; curr->next = prev;