新浪微博 Java 筆試真題深度解析：二分查找、頻率統計與最長遞增子串

題目一：有序數組二分查找

問題

已排序整型數組，實現二分查找判斷目標值是否存在。

解法：遞歸版二分查找

public class SinaTest1 {
    public boolean findNum(int[] nums, int target) {
        if (nums == null) return false;
        return binarySearch(nums, target, 0, nums.length - 1);
    }

    private boolean binarySearch(int[] nums, int target, int left, int right) {
        if (left > right) return false; // 搜索區間為空
        
        int mid = left + (right - left) / 2; // 防止溢出
        if (nums[mid] == target) return true;
        else if (nums[mid] > target) 
            return binarySearch(nums, target, left, mid - 1);
        else 
            return binarySearch(nums, target, mid + 1, right);
    }

    // 迭代版（推薦，無棧溢出風險）
    public boolean findNumIterative(int[] nums, int target) {
        if (nums == null) return false;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) >>> 1; // 無符號右移等效除2
            if (nums[mid] == target) return true;
            else if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return false;
    }
}

複雜度

• 時間：O(log n)
• 空間：遞歸 O(log n)，迭代 O(1)

題目二：數組去重並按頻率/值排序

問題

統計數組中不同數字個數，按出現頻率升序，頻率相同按數值升序，輸出新數組。

解法：HashMap + 自定義排序

public class SinaTest2 {
    public int[] distinctNum(int[] nums) {
        if (nums == null) return new int[0];
        
        // 1. 統計頻率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int n : nums) freqMap.merge(n, 1, Integer::sum);
        
        // 2. 轉 Entry 列表排序
        List<Map.Entry<Integer, Integer>> entries = 
            new ArrayList<>(freqMap.entrySet());
        
        entries.sort((e1, e2) -> {
            int freqCmp = e1.getValue() - e2.getValue(); // 頻率升序
            return freqCmp != 0 ? freqCmp : e1.getKey() - e2.getKey(); // 值升序
        });
        
        // 3. 提取鍵
        int[] result = new int[entries.size()];
        for (int i = 0; i < result.length; i++) 
            result[i] = entries.get(i).getKey();
        return result;
    }
}

優化點

• 使用 Map.merge 簡化計數
• Java 8 List.sort + Lambda 替代 Collections.sort + 匿名類
• 可改用 TreeMap 但需自定義比較器，當前方案更直觀

題目三：字符串中最長遞增子串

問題

數字字符串（1-9），找最長嚴格遞增子串（相鄰字符差值為 1），長度相同取較大值。

解法：單次遍歷動態維護

public class SinaTest3 {
    public String findMaxIncreasing(String str) {
        if (str == null || str.isEmpty()) return "";
        
        String max = "";
        int start = 0; // 當前遞增段起始索引
        
        for (int i = 1; i < str.length(); i++) {
            // 判斷是否連續遞增：當前字符 - 前一字符 == 1
            if (str.charAt(i) - str.charAt(i - 1) == 1) {
                // 繼續遞增，檢查是否更新最大值
                int len = i - start + 1;
                if (len > max.length() || 
                    (len == max.length() && str.charAt(start) > max.charAt(0))) {
                    max = str.substring(start, i + 1);
                }
            } else {
                // 遞增中斷，重置起始點
                start = i;
            }
        }
        return max;
    }
}

關鍵邏輯解析

1. 連續性判斷：`charAt(i) - charAt(i-1) == 1` 利用字符編碼連續性
2. 滑動窗口：`start` 標記當前遞增段起點，無需額外空間
3. 即時更新：遍歷過程中直接比較長度和首字符值
4. 邊界處理：單字符自動處理（長度 1），空串返回空

測試用例

"28953456323"     → "3456" (長度4)
"12321"           → "123" (長度3)
"987654"          → "9" (無遞增，單字符)
"12345432123456"  → "123456" (長度6)
""                → ""
"5"               → "5"

面試加分點總結