2026年計(jì)算機(jī)軟件工程師面試寶典及答案解析一、編程語言與數(shù)據(jù)結(jié)構(gòu)（10題，每題10分，共100分）1.題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)字符串是否為有效的括號(hào)組合（例如，輸入`"(())"`返回`true`，輸入`"(()"`返回`false`）。答案解析：可以使用棧來處理括號(hào)匹配問題。遍歷字符串，遇到左括號(hào)`'('`或`'{'`或`'['`時(shí)入棧，遇到右括號(hào)`')'`或`'}'`或`']'`時(shí)，檢查棧是否為空，若為空則返回`false`；否則出棧并與當(dāng)前右括號(hào)匹配，若不匹配則返回`false`。遍歷結(jié)束后，棧應(yīng)為空，否則返回`false`。javapublicbooleanisValid(Strings){Stack<Character>stack=newStack<>();for(charc:s.toCharArray()){if(c=='('||c=='{'||c=='['){stack.push(c);}elseif(c==')'){if(stack.isEmpty()||stack.pop()!='(')returnfalse;}elseif(c=='}'){if(stack.isEmpty()||stack.pop()!='{')returnfalse;}elseif(c==']'){if(stack.isEmpty()||stack.pop()!='[')returnfalse;}}returnstack.isEmpty();}2.題目：給定一個(gè)整數(shù)數(shù)組，返回其中三個(gè)數(shù)相加等于零的個(gè)數(shù)（例如，輸入`[-1,0,1,2]`返回`2`，因?yàn)閌-1+0+1=0`和`-1+2+1=0`）。答案解析：先對(duì)數(shù)組排序，然后固定一個(gè)數(shù)，使用雙指針法查找另外兩個(gè)數(shù)。具體步驟如下：1.排序數(shù)組；2.遍歷數(shù)組，對(duì)于每個(gè)`nums[i]`，設(shè)置`left=i+1`和`right=n-1`；3.若`nums[i]+nums[left]+nums[right]==0`，則計(jì)數(shù)并移動(dòng)`left`和`right`；若和小于零，移動(dòng)`left`；若和大于零，移動(dòng)`right`；重復(fù)直到`left==right`。javapublicintthreeSum(int[]nums){Arrays.sort(nums);intcount=0;intn=nums.length;for(inti=0;i<n-2;i++){if(i>0&&nums[i]==nums[i-1])continue;//去重intleft=i+1,right=n-1;while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum==0){count++;while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;left++;right--;}elseif(sum<0)left++;elseright--;}}returncount;}3.題目：實(shí)現(xiàn)一個(gè)`LruCache`類，支持最近最少使用（LRU）緩存，支持`get`和`put`操作（例如，容量為2的緩存，`put(1,1)`后`put(2,2)`，`get(1)`返回`1`，`put(3,3)`會(huì)刪除鍵`2`）。答案解析：使用雙向鏈表和哈希表實(shí)現(xiàn)。哈希表存儲(chǔ)鍵到鏈表節(jié)點(diǎn)的映射，鏈表頭部為最常用節(jié)點(diǎn)，尾部為最久未使用節(jié)點(diǎn)。`get`操作通過哈希表找到節(jié)點(diǎn)，移動(dòng)到鏈表頭部；`put`操作若鍵已存在則更新值并移動(dòng)到頭部，否則新建節(jié)點(diǎn)并加入頭部，若超出容量則刪除鏈表尾部節(jié)點(diǎn)并刪除哈希表映射。javaclassNode{intkey,val;Nodeprev,next;Node(intk,intv){key=k;val=v;}}classLruCache{Map<Integer,Node>map;Nodehead,tail;intcapacity;publicLruCache(intcap){capacity=cap;map=newHashMap<>();head=newNode(0,0);tail=newNode(0,0);head.next=tail;tail.prev=head;}publicintget(intkey){if(map.containsKey(key)){Nodenode=map.get(key);moveToHead(node);returnnode.val;}return-1;}publicvoidput(intkey,intvalue){if(map.containsKey(key)){Nodenode=map.get(key);node.val=value;moveToHead(node);}else{if(map.size()==capacity){NodetoRemove=tail.prev;map.remove(toRemove.key);removeNode(toRemove);}NodenewNode=newNode(key,value);map.put(key,newNode);addToHead(newNode);}}privatevoidmoveToHead(Nodenode){removeNode(node);addToHead(node);}privatevoidaddToHead(Nodenode){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}privatevoidremoveNode(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}}4.題目：設(shè)計(jì)一個(gè)算法，找出數(shù)組中重復(fù)次數(shù)超過一半的數(shù)（例如，輸入`[2,2,1,1,1,2,2]`返回`2`）。答案解析：可以使用摩爾投票算法，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。維護(hù)一個(gè)候選數(shù)和計(jì)數(shù)器，遍歷數(shù)組：若計(jì)數(shù)器為0，設(shè)當(dāng)前數(shù)為候選數(shù)并計(jì)數(shù)1；若當(dāng)前數(shù)等于候選數(shù)，計(jì)數(shù)器加1；否則計(jì)數(shù)器減1。最后驗(yàn)證候選數(shù)是否滿足條件。javapublicintmajorityElement(int[]nums){intcandidate=0,count=0;for(intnum:nums){if(count==0)candidate=num;count+=(num==candidate)?1:-1;}//驗(yàn)證候選數(shù)count=0;for(intnum:nums)if(num==candidate)count++;returncount>nums.length/2?candidate:-1;}5.題目：實(shí)現(xiàn)一個(gè)函數(shù)，將字符串中的每個(gè)空格替換為`%20`（例如，輸入`"Wearehappy."`返回`"We%20are%20happy."`）。答案解析：方法一：先統(tǒng)計(jì)空格數(shù)量，再從后往前替換，避免覆蓋。方法二：使用`StringBuilder`，遍歷字符串并替換。javapublicStringreplaceSpace(Strings){StringBuildersb=newStringBuilder();for(charc:s.toCharArray()){if(c=='')sb.append("%20");elsesb.append(c);}returnsb.toString();}6.題目：給定一個(gè)非空二叉樹，返回其最大深度（例如，輸入`[3,9,20,null,null,15,7]`對(duì)應(yīng)的樹，返回`3`）。答案解析：使用遞歸或迭代方法計(jì)算深度。遞歸方法：最大深度為左右子樹深度的最大值加1。javapublicintmaxDepth(TreeNoderoot){if(root==null)return0;return1+Math.max(maxDepth(root.left),maxDepth(root.right));}7.題目：實(shí)現(xiàn)一個(gè)函數(shù)，檢查一個(gè)字符串是否是回文串（例如，輸入`"121"`返回`true`，輸入`"13a31"`返回`false`）。答案解析：雙指針法：左指針從頭部開始，右指針從尾部開始，比較字符是否相同，若不同則返回`false`；若相同則移動(dòng)指針。忽略非字母數(shù)字字符。javapublicbooleanisPalindrome(Strings){intleft=0,right=s.length()-1;while(left<right){while(left<right&&!Character.isLetterOrDigit(s.charAt(left)))left++;while(left<right&&!Character.isLetterOrDigit(s.charAt(right)))right--;if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right)))returnfalse;left++;right--;}returntrue;}8.題目：實(shí)現(xiàn)一個(gè)`MinStack`類，支持`push`、`pop`、`top`和`getMin`操作（例如，`push(5)`,`push(2)`,`push(5)`,`getMin()`返回`2`）。答案解析：使用兩個(gè)棧：一個(gè)存儲(chǔ)所有元素，另一個(gè)存儲(chǔ)當(dāng)前最小值。`push`時(shí)，若當(dāng)前棧為空或棧頂大于等于新值，則將新值壓入最小值棧；`pop`時(shí)，若彈出的值等于最小值棧頂，則最小值棧也彈出；`getMin`返回最小值棧頂。javaclassMinStack{Stack<Integer>stack;Stack<Integer>minStack;publicMinStack(){stack=newStack<>();minStack=newStack<>();}publicvoidpush(intval){stack.push(val);if(minStack.isEmpty()||val<=minStack.peek())minStack.push(val);}publicvoidpop(){intval=stack.pop();if(val==minStack.peek())minStack.pop();}publicinttop(){returnstack.peek();}publicintgetMin(){returnminStack.peek();}}9.題目：實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)整數(shù)是否是回文數(shù)（例如，輸入`121`返回`true`，輸入`-121`返回`false`）。答案解析：將整數(shù)反轉(zhuǎn)，若與原數(shù)相同則為回文數(shù)。注意負(fù)數(shù)和末尾為0的情況。javapublicbooleanisPalindrome(intx){if(x<0||(x%10==0&&x!=0))returnfalse;intreversed=0;while(x>reversed){reversed=reversed10+x%10;x/=10;}returnx==reversed||x==reversed/10;}10.題目：實(shí)現(xiàn)一個(gè)函數(shù)，找出數(shù)組中缺失的第一個(gè)正數(shù)（例如，輸入`[3,4,-1,1]`返回`2`）。答案解析：將正數(shù)按順序填入原數(shù)組對(duì)應(yīng)位置（例如，`nums[0]=1`），然后遍歷數(shù)組，第一個(gè)不滿足`nums[i]==i+1`的索引即為缺失的數(shù)字。若全部滿足，返回`n+1`。javapublicintfirstMissingPositive(int[]nums){intn=nums.length;for(inti=0;i<n;i++){while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i])swap(nums,nums[i]-1,i);}for(inti=0;i<n;i++)if(nums[i]!=i+1)returni+1;returnn+1;}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}二、算法與設(shè)計(jì)（5題，每題20分，共100分）1.題目：設(shè)計(jì)一個(gè)算法，找出數(shù)組中重復(fù)的數(shù)字，但不能修改數(shù)組，且空間復(fù)雜度O(1)。答案解析：使用Floyd判圈算法（龜兔賽跑）。將數(shù)字作為數(shù)組索引，若`nums[i]`與`nums[nums[i]]`相同，則存在重復(fù)；否則交換`nums[i]`和`nums[nums[i]]`，直到找到重復(fù)數(shù)字。javapublicintfindDuplicate(int[]nums){intslow=nums[0],fast=nums[0];do{slow=nums[slow];fast=nums[nums[fast]];}while(slow!=fast);slow=nums[0];while(slow!=fast){slow=nums[slow];fast=nums[fast];}returnslow;}2.題目：設(shè)計(jì)一個(gè)算法，找出數(shù)組中所有三個(gè)數(shù)的組合，使得這三個(gè)數(shù)的和為零（例如，輸入`[0,1,1]`返回`[[0,0,0]]`）。答案解析：先排序，然后固定一個(gè)數(shù)，使用雙指針法查找另外兩個(gè)數(shù)。若`nums[i]+nums[left]+nums[right]==0`，則記錄組合并移動(dòng)指針；若和小于零，移動(dòng)`left`；若和大于零，移動(dòng)`right`。去重時(shí)跳過相同值。javapublicList<List<Integer>>threeSum(int[]nums){Arrays.sort(nums);List<List<Integer>>res=newArrayList<>();intn=nums.length;for(inti=0;i<n-2;i++){if(i>0&&nums[i]==nums[i-1])continue;intleft=i+1,right=n-1;while(left<right){intsum=nums[i]+nums[left]+nums[right];if(sum==0){res.add(Arrays.asList(nums[i],nums[left],nums[right]));while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;left++;right--;}elseif(sum<0)left++;elseright--;}}returnres;}3.題目：設(shè)計(jì)一個(gè)算法，找出字符串中最長無重復(fù)字符的子串長度（例如，輸入`"abcabcbb"`返回`3`，對(duì)應(yīng)`"abc"`）。答案解析：使用滑動(dòng)窗口法。維護(hù)一個(gè)哈希表記錄字符上一次出現(xiàn)的位置，左指針指向窗口左側(cè)，右指針遍歷字符串。若當(dāng)前字符在哈希表中且位置大于等于左指針，則移動(dòng)左指針；更新哈希表并記錄最大長度。javapublicintlengthOfLongestSubstring(Strings){intleft=0,maxLen=0;Map<Character,Integer>map=newHashMap<>();for(intright=0;right<s.length();right++){charc=s.charAt(right);if(map.containsKey(c)&&map.get(c)>=left)left=map.get(c)+1;map.put(c,right);maxLen=Math.max(maxLen,right-left+1);}returnmaxLen;}4.題目：設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)LRU緩存的高效實(shí)現(xiàn)（使用雙向鏈表和哈希表）。答案解析：參考第一題`LruCache`類的實(shí)現(xiàn)。雙向鏈表頭部為最近使用節(jié)點(diǎn)，尾部為最久未使用節(jié)點(diǎn)；哈希表存儲(chǔ)鍵到鏈表節(jié)點(diǎn)的映射。`get`操作移動(dòng)節(jié)點(diǎn)到頭部，`put`操作插入節(jié)點(diǎn)到頭部，若超出容量則刪除尾部節(jié)點(diǎn)。5.題目：設(shè)計(jì)一個(gè)算法，判斷一個(gè)數(shù)是否是素?cái)?shù)（例如，輸入`11`返回`true`，輸入`10`返回`false`）。答案解析：若`n`小于等于1，返回`false`；若`n`小于等于3，返回`true`；若`n`能被2或3整除，返回`false`；否則從5開始，以6為步長檢查`n%i==0`或`n%(i+2)==0`，直到`ii>n`。javapublicbooleanisPrime(intn){if(n<=1)returnfalse;if(n<=3)returntrue;if(n%2==0||n%3==0)returnfalse;for(int