杭州市网站建设_网站建设公司_HTML_seo优化

法在SDET面试中的重要性‌

软件测试工程师（SDET）不仅需验证功能，还需编写高效、可靠的代码。LeetCode算法题是面试常见环节，能评估候选人的问题解决能力和编码习惯。本文精选10道高频题，均来自真实SDET面试题库，涵盖基础数据结构与算法。每道题附Python和Java解法，强调可读性和效率（时间/空间复杂度）。练习时，建议从测试角度思考：输入边界、异常处理和性能优化，这将提升实际工作能力。

‌1. Two Sum（两数之和）‌

‌题目描述‌：给定整数数组nums和目标值target，返回数组中两数之和等于target的下标。假设每个输入有且仅有一个解，且同一元素不可重复使用。
‌解题思路‌：使用哈希表存储元素值到索引的映射。遍历数组，检查target - 当前值是否在哈希表中。若存在，返回对应下标；否则将当前值加入哈希表。时间复杂度O(n)，空间O(n)。
‌Python解法‌：

pythonCopy Code def two_sum(nums, target): num_map = {} for i, num in enumerate(nums): complement = target - num if complement in num_map: return [num_map[complement], i] num_map[num] = i return [] # 无解处理（题目保证有解，但测试需考虑边界）

‌Java解法‌：

javaCopy Code import java.util.HashMap; import java.util.Map; public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> numMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (numMap.containsKey(complement)) { return new int[]{numMap.get(complement), i}; } numMap.put(nums[i], i); } throw new IllegalArgumentException("No solution"); // 异常处理强化健壮性 }

‌2. Valid Parentheses（有效的括号）‌

‌题目描述‌：给定字符串s，包含括号(),[],{}，判断是否有效（开闭匹配且顺序正确）。
‌解题思路‌：使用栈处理。遍历字符串，遇开括号入栈，遇闭括号则检查栈顶是否匹配。若栈空或失配，则无效；遍历结束栈空则有效。时间复杂度O(n)。
‌Python解法‌：

pythonCopy Code def is_valid(s): stack = [] mapping = {')': '(', ']': '[', '}': '{'} for char in s: if char in mapping: # 闭括号 top = stack.pop() if stack else '#' if mapping[char] != top: return False else: # 开括号 stack.append(char) return not stack # 栈空则有效

‌Java解法‌：

javaCopy Code import java.util.Stack; public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); Map<Character, Character> mapping = new HashMap<>(); mapping.put(')', '('); mapping.put(']', '['); mapping.put('}', '{'); for (char c : s.toCharArray()) { if (mapping.containsKey(c)) { // 闭括号 char top = stack.isEmpty() ? '#' : stack.pop(); if (top != mapping.get(c)) return false; } else { // 开括号 stack.push(c); } } return stack.isEmpty(); }

‌3. Reverse Integer（整数反转）‌

‌题目描述‌：给定32位有符号整数x，返回其数字反转形式。若反转后溢出，返回0。
‌解题思路‌：循环取x的末位，构建新整数。关键点：处理溢出（32位范围: -2^31 到 2^31-1）。使用temp = rev * 10 + pop前检查是否超限。时间复杂度O(log n)。
‌Python解法‌：

pythonCopy Code def reverse(x): rev = 0 sign = -1 if x < 0 else 1 x = abs(x) while x: pop = x % 10 x //= 10 # 检查溢出 if rev > (2**31 - 1 - pop) // 10: return 0 rev = rev * 10 + pop return rev * sign

‌Java解法‌：

javaCopy Code public int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; // 正数溢出检查 if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE/10 && pop > 7)) return 0; // 负数溢出检查 if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE/10 && pop < -8)) return 0; rev = rev * 10 + pop; } return rev; }

‌4. Merge Two Sorted Lists（合并两个有序链表）‌

‌题目描述‌：合并两个升序链表，返回新链表。新链表需保持升序。
‌解题思路‌：迭代法。创建哑节点简化边界处理。比较两链表当前节点，将较小者链入新链表。时间复杂度O(n+m)。
‌Python解法‌：

pythonCopy Code class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def merge_two_lists(l1, l2): dummy = ListNode(-1) current = dummy while l1 and l2: if l1.val < l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next current.next = l1 if l1 else l2 # 剩余部分直接链入 return dummy.next

‌Java解法‌：

javaCopy Code public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode current = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } current.next = (l1 != null) ? l1 : l2; // 处理剩余节点 return dummy.next; }

‌5. Valid Anagram（有效的字母异位词）‌

‌题目描述‌：给定两个字符串s和t，判断t是否为s的字母异位词（字母相同但顺序不同）。
‌解题思路‌：统计字符频率。用数组或哈希表记录s的字符频次，遍历t减频次。若某字符频次为负或s/t长度不等，则无效。时间复杂度O(n)。
‌Python解法‌：

pythonCopy Code def is_anagram(s, t): if len(s) != len(t): return False freq = [0] * 26 # 假设仅小写字母 for char in s: freq[ord(char) - ord('a')] += 1 for char in t: index = ord(char) - ord('a') freq[index] -= 1 if freq[index] < 0: return False return True

‌Java解法‌：

javaCopy Code public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } for (char c : t.toCharArray()) { freq[c - 'a']--; if (freq[c - 'a'] < 0) return false; } return true; }

‌6. Best Time to Buy and Sell Stock（买卖股票的最佳时机）‌

‌题目描述‌：给定股价数组prices，选择一天买，后续一天卖，求最大利润。若无法盈利，返回0。
‌解题思路‌：贪心法。遍历数组，记录历史最低价，计算当前价与最低价的差值作为利润，并更新最大利润。时间复杂度O(n)。
‌Python解法‌：

pythonCopy Code def max_profit(prices): if not prices: return 0 min_price = prices[0] max_profit = 0 for price in prices: if price < min_price: min_price = price else: profit = price - min_price if profit > max_profit: max_profit = profit return max_profit

‌Java解法‌：

javaCopy Code public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int price : prices) { if (price < minPrice) { minPrice = price; } else if (price - minPrice > maxProfit) { maxProfit = price - minPrice; } } return maxProfit; }

‌7. Binary Tree Inorder Traversal（二叉树的中序遍历）‌

‌题目描述‌：给定二叉树根节点，返回中序遍历（左-根-右）结果。
‌解题思路‌：递归或迭代。迭代法用栈模拟：先压入所有左节点，再弹出访问，转至右子树。时间复杂度O(n)。
‌Python解法‌：

pythonCopy Code class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def inorder_traversal(root): stack, result = [], [] current = root while current or stack: while current: # 压入所有左节点 stack.append(current) current = current.left current = stack.pop() result.append(current.val) current = current.right # 转向右子树 return result

‌Java解法‌：

javaCopy Code public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; }

‌8. String to Integer (atoi)（字符串转换整数）‌

‌题目描述‌：实现atoi函数，将字符串转为整数。需处理前导空格、正负号、非数字字符和溢出。
‌解题思路‌：逐字符解析。跳过空格，检查符号，累积数字。溢出时返回边界值。时间复杂度O(n)。
‌Python解法‌：

pythonCopy Code def my_atoi(s): s = s.strip() if not s: return 0 sign = 1 if s[0] in ['+', '-']: if s[0] == '-': sign = -1 s = s[1:] num = 0 for char in s: if not char.isdigit(): break digit = int(char) # 检查溢出 if num > (2**31 - 1 - digit) // 10: return 2‌**31 - 1 if sign == 1 else -2**‌31 num = num * 10 + digit return sign * num

‌Java解法‌：

javaCopy Code public int myAtoi(String s) { s = s.trim(); if (s.isEmpty()) return 0; int sign = 1, i = 0; if (s.charAt(0) == '-' || s.charAt(0) == '+') { sign = (s.charAt(0) == '-') ? -1 : 1; i++; } long num = 0; // 用long防溢出 while (i < s.length() && Character.isDigit(s.charAt(i))) { int digit = s.charAt(i) - '0'; num = num * 10 + digit; if (num > Integer.MAX_VALUE) { return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE; } i++; } return (int) num * sign; }

‌9. Fibonacci Number（斐波那契数）‌

‌题目描述‌：计算第n个斐波那契数（F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)）。
‌解题思路‌：动态规划。用两个变量迭代存储前两值，避免递归重复计算。时间复杂度O(n)。
‌Python解法‌：

pythonCopy Code def fib(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b

‌Java解法‌：

javaCopy Code public int fib(int n) { if (n <= 1) return n; int a = 0, b = 1; for (int i = 2; i <= n; i++) { int next = a + b; a = b; b = next; } return b; }

‌10. Implement Queue using Stacks（用栈实现队列）‌

‌题目描述‌：仅用栈操作（push, pop, peek, empty）实现队列。
‌解题思路‌：双栈法。一个输入栈（in_stack）处理push，输出栈（out_stack）处理pop/peek。当out_stack空时，将in_stack元素倒入out_stack。时间复杂度：均摊O(1)。
‌Python解法‌：

pythonCopy Code class MyQueue: def __init__(self): self.in_stack = [] self.out_stack = [] def push(self, x): self.in_stack.append(x) def pop(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self): return not (self.in_stack or self.out_stack)

‌Java解法‌：

javaCopy Code import java.util.Stack; class MyQueue { private Stack<Integer> inStack; private Stack<Integer> outStack; public MyQueue() { inStack = new Stack<>(); outStack = new Stack<>(); } public void push(int x) { inStack.push(x); } public int pop() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); } }

‌总结与面试建议‌

以上10道题覆盖SDET面试高频考点：数组、字符串、链表、树、栈/队列和基础算法。练习时注意：

• ‌测试驱动思维‌：为每个解法添加边界测试（如空输入、极值）。
• ‌复杂度分析‌：在代码注释中注明时间/空间复杂度，展现优化意识。
• ‌语言选择‌：Python简洁适合快速实现，Java强调类型安全，面试中根据岗位要求调整。
  持续刷题并模拟面试

精选文章

边缘AI的测试验证挑战：从云到端的质量保障体系重构

编写高效Gherkin脚本的五大核心法则

10亿条数据统计指标验证策略：软件测试从业者的实战指南

数据对比测试（Data Diff）工具的原理与应用场景