微信紅包、連結清單習題

1.若棧采用順序存儲方式存儲，現兩棧共享空間V[1…m]，top[i]代表第i個棧( i =1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（B）。

A top[1]+top[2]=m

B top[1]+1=top[2]

C top[2]-top[1]|=0

D top[1]=top[2]

2.某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ B）

A 不存在這樣的二叉樹

B 200

C 198

D 199

解析：

根據二叉樹的基本性質，對任何一棵二叉樹，度為0的結點（即葉子結點）總是比度為 2 的結點多一個。題目中度為 2 的結點為 199 個，則葉子結點為 199+1=200 。故本題答案為 B 選項。

3.以下哪種排序算法對(1,3,2,4,5,6,7,8,9)進行的排序最快？A

A 冒泡

B 快排

C 歸并

D 堆排

解析：

若記錄的初始狀态已經按關鍵碼基本有序，則選用直接插入排序或冒泡排序發為宜

4.設無向圖的頂點個數為n，則該圖最多有多少條邊？C

A n-1

B n（n+1）/2

C n（n-1）/2

D n

E 不同于以上答案

解析：

無向圖的頂點個數為n,則該圖最多有n(n-1)/2 條邊；

有相圖的頂點個數為n，則該圖最多有n(n-1)條邊。

5.标題：微信紅包

【微信紅包】 春節期間小明使用微信收到很多個紅包，非常開心。在檢視領取紅包記錄時發現，某個紅包金額出現的次數超過了紅包總數的一半。請幫小明找到該紅包金額。寫出 具體算法思路和代碼實作，要求算法盡可能高效。 給定一個紅包的金額數組gifts及它的大小n，請傳回所求紅包的金額。 若沒有金額超過總數的一半，傳回0。

測試樣例：[1,2,3,2,2],5 傳回：2

import java.util.*;
public class Gift {
    public int getValue(int[] gifts, int n) {
        // write code here
        int result = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        int a = 0;
        if(n%2==0){
            a = n/2;
        }else{
            a = (n/2)+1;
        }
        for(int i = 0;i<gifts.length;i++){
            int count = map.getOrDefault(gifts[i],0);
            map.put(gifts[i],count+1);
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            int num = entry.getKey();
            int c = entry.getValue();
            if(c>=a){
                result = num;
            }
        }
        return result;
    }
}
//方法二：
import java.util.*;
public class Gift {
    public int getValue(int[] gifts, int n) {
        if (gifts.length < n) return 0;
        if (gifts.length == 0) return 0;
        int count = 0, temp = 0;
        for (int i = 0; i < n; i++) {
            if (count == 0) {
                temp = gifts[i];
                count = 1;
            } else {
                if (temp == gifts[i]) 
                    count++;
                else
                    count--;
            }
        }
        int size = 0;
        for (int i = 0; i < n; i++) {
            if (temp == gifts[i]) size++;
        }
        return (size > n / 2) ? temp : 0;
    }
}
           

6.編寫代碼，以給定值x為基準将連結清單分割成兩部分，所有小于x的結點排在大于或等于x的結點之前給定一個連結清單的頭指針 ListNode* pHead，請傳回重新排列後的連結清單的頭指針。注意：分割以後保持原來的資料順序不變。

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode result = null;
        ListNode node = pHead;
        ListNode b = null;
        ListNode last1 = null;
        ListNode last2 = null;
        ListNode back = null;
        while (node != null) {
            if (node.val < x) {
                ListNode n = new ListNode(node.val);
                if (result == null) {
                    result = n;
                    back = n;
                } else {
                    last1 = result;
                    while (last1.next!=null){
                        last1 = last1.next;
                    }
                    last1.next = n;
                    back = n;
                }
            } else {
                ListNode n = new ListNode(node.val);
                if (b == null) {
                    b = n;
                } else {
                    last2 = b;
                    while (last2.next!=null){
                        last2 = last2.next;
                    }
                    last2.next = n;
                }
            }
            node = node.next;
        }
        if(back!=null){
            back.next = b;
            return result;
        }else {
            return b;
        }
    }
}
//方法二：
import java.util.*; 
/*public class ListNode { 
        int val;
        ListNode next = null;
        ListNode(int val) {
         this.val = val;
        } 
  }*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {

        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode cur = pHead;
        //定義2個連結清單，此處Shead Bhead兩個頭指針 
        ListNode Shead = new ListNode(-1);
        ListNode Bhead = new ListNode(-1);
        ListNode Stmp = Shead;
        ListNode Btmp = Bhead;
        while (cur != null) {
            if (cur.val < x) {
                //值小于x的節點 
                Stmp.next = new ListNode(cur.val);
                Stmp = Stmp.next;
            } else {
                //值大于等于x的節點 
                Btmp.next = new ListNode(cur.val);
                Btmp = Btmp.next;
            }
            cur = cur.next;
        }//第1個連結清單的頭
        cur = Shead;
        //循環周遊找到第1個連結清單的尾 
        while (cur.next != null && cur.next.val != -1) {
            cur = cur.next;
        }
        //cur的next指向第2個節點的next(非頭節點) 
        // 相當于将第1個連結清單和第2個連結清單連接配接 
        cur.next = Bhead.next;
        return Shead.next;
        //傳回第1個節點next(不含頭節點) 
    }
}