經(jīng)典測(cè)試工程師面試題(一)
經(jīng)典測(cè)試工程師面試題(二)
背景
為了擴(kuò)展家里領(lǐng)導(dǎo)的測(cè)試知識(shí)水平和專業(yè)知識(shí)能力提升，以及為以后更好的面試做基礎(chǔ)，特意從眾多測(cè)試相關(guān)題型整理出來，其中的答案僅供參考。
給定一個(gè)已按照升序排列 的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2。
說明:
返回的下標(biāo)值（index1 和 index2）不是從零開始的。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。
示例:
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 。
## python
class Solution(object):
def twoSum(self, numbers, target):
l=0
r=len(numbers)-1
while(l<r):
if(numbers[l]+numbers[r]== target):
return [l+1,r+1]
if(numbers[l]+numbers[r] <target):
l += 1
else:
r -= 1
## 測(cè)試用例：
def test_towSum1(self):
assert towSum([0,1, 1, 2, 3, 6,8], 2) == [1, 4]
def test_towSum2(self):
assert towSum([1,2,5,6,12], 13) == [1, 5]
def test_towSum3(self):
assert towSum([2, 7, 11, 15], 9) == [1, 2]
## Java
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] == target) {
return new int[]{left + 1, right + 1};
}
if (numbers[left] + numbers[right] < target) {
left += 1;
} else {
right -= 1;
}
}
return null;
}
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
Python
## 不推薦 效率極低 ##
def setpMethod(num):
if(n == 1 or n == 2):
return n
else:
return self.setpMethod(num-1)+self.setpMethod(num-2)
## 推薦寫法 ##
def climbStairs(self, n):
if(n == 1 or n == 2):
return n
num1=1
num2=2
while(n >= 3):
result = num1 + num2
num1 = num2
num2 = result
n -=1
return result
## Java ##
public int setpMethod(int n){
if(n ==1 || n ==2){
return n;
}
int result = 0,n1 = 1,n2 = 2;
while (n>=3){
result = n1 + n2;
n1 = n2;
n2 = result;
n--;
}
return result;
}
給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個(gè)位置。
示例 1:
輸入: [2,3,1,1,4]
輸出: true
解釋: 從位置 0 到 1 跳 1 步, 然后跳 3 步到達(dá)最后一個(gè)位置。
示例 2:
輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣，你總會(huì)到達(dá)索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠(yuǎn)不可能到達(dá)最后一個(gè)位置。
## python ##
class Solution(object):
def canJump(self, nums):
need = 1
if(len(nums) ==1):
return True
if(nums[0] == 0):
return False
for i in range(len(nums)-2,-1,-1):
if(nums[i] == 0 or nums[i] < need):
need += 1
else:
need = 1
if(need == 1) :
return True
else:
return False
## java ##
public boolean canJump(int[] nums) {
int n = 1;
if(nums.length ==1){
return true;
}
if(nums[0] == 0){
return false;
}
for(int i=nums.length-2; i>=0; i--){
if(nums[i] >= n){
n=1;
}else{
n++;
}
}
if(n == 1){
return true;
}else{
return false;
}
}
以 Unix 風(fēng)格給出一個(gè)文件的絕對(duì)路徑，你需要簡(jiǎn)化它。或者換句話說，將其轉(zhuǎn)換為規(guī)范路徑。
在 Unix 風(fēng)格的文件系統(tǒng)中，一個(gè)點(diǎn)（.）表示當(dāng)前目錄本身；此外，兩個(gè)點(diǎn) （..） 表示將目錄切換到上一級(jí)（指向父目錄）；兩者都可以是復(fù)雜相對(duì)路徑的組成部分。更多信息請(qǐng)參閱：Linux / Unix中的絕對(duì)路徑 vs 相對(duì)路徑
請(qǐng)注意，返回的規(guī)范路徑必須始終以斜杠 / 開頭，并且兩個(gè)目錄名之間必須只有一個(gè)斜杠 /。最后一個(gè)目錄名（如果存在）不能以 / 結(jié)尾。此外，規(guī)范路徑必須是表示絕對(duì)路徑的最短字符串。
示例 1：
輸入："/home/"
輸出："/home"
解釋：注意，最后一個(gè)目錄名后面沒有斜杠。
示例 2：
輸入："/../"
輸出："/"
解釋：從根目錄向上一級(jí)是不可行的，因?yàn)楦悄憧梢缘竭_(dá)的最高級(jí)。
示例 3：
輸入："/home//foo/"
輸出："/home/foo"
解釋：在規(guī)范路徑中，多個(gè)連續(xù)斜杠需要用一個(gè)斜杠替換。
示例 4：
輸入："/a/./b/../../c/"
輸出："/c"
示例 5：
輸入："/a/../../b/../c//.//"
輸出："/c"
示例 6：
輸入："/a//b////c/d//././/.."
輸出："/a/b/c"
##python##
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
paths = path.split('/')
str = ''
pathlist = [i for i in paths if I]
result = []
for j in range(len(pathlist)):
print(j)
if(pathlist[j] == ".."):
if(result):
result.pop()
elif(pathlist[j] == "."):
continue
else :
result.append(pathlist[j])
if not result:
return '/'
for k in range(len(result)):
str = str + '/' + result[k]
return str
給定一個(gè)字符串 (s) 和一個(gè)字符模式 (p) ，實(shí)現(xiàn)一個(gè)支持 '?' 和 '' 的通配符匹配。'?' 可以匹配任何單個(gè)字符。'' 可以匹配任意字符串（包括空字符串）。兩個(gè)字符串完全匹配才算匹配成功。
說明:
s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 ? 和 *。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個(gè)字符串。
示例 2:
輸入:
s = "aa"
p = "*"
輸出: true
解釋: '*' 可以匹配任意字符串。
示例 3:
輸入:
s = "cb"
p = "?a"
輸出: false
解釋: '?' 可以匹配 'c', 但第二個(gè) 'a' 無法匹配 'b'。
示例 4:
輸入:
s = "adceb"
p = "*a*b"
輸出: true
解釋: 第一個(gè) '*' 可以匹配空字符串, 第二個(gè) '*' 可以匹配字符串 "dce".
示例 5:
輸入:
s = "acdcb"
p = "a*c?b"
輸入: false
##python##
def isMatch(self, s, p):
si, pi, pj, sj = 0, 0, -1, -1
while si < len(s):
if pi < len(p) and p[pi] == '*':
pi += 1
pj = pi
sj = si
elif pi < len(p) and (p[pi] == '?' or p[pi] == s[si]):
pi += 1
si += 1
elif pj != -1:
pi = pj
sj += 1
si = sj
else:
return False
while (pi < len(p) and p[pi] == '*'):
pi += 1
return pi == len(p)
執(zhí)行結(jié)果.png
給出兩個(gè) 非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。如果，我們將這兩個(gè)數(shù)相加起來，則會(huì)返回一個(gè)新的鏈表來表示它們的和。您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
## python ##
class Solution(object):
def addTwoNumbers(self, l1, l2):
n =l1.val + l2.val
l3 = ListNode(n%10)
l3.next = ListNode(n//10)
p1 = l1.next
p2 = l2.next
p3 = l3
while True:
if p1 and p2:
sum = p1.val+ p2.val + p3.next.val
p3.next.val = sum % 10
p3.next.next = ListNode(sum//10)
p1 = p1.next
p2 = p2.next
p3 = p3.next
elif p1 and not p2:
sum = p1.val + p3.next.val
p3.next.val = sum %10
p3.next.next = ListNode(sum // 10)
p1 = p1.next
p3 = p3.next
elif not p1 and p2:
sum = p2.val +p3.next.val
p3.next.val = sum % 10
p3.next.next = ListNode(sum // 10)
p2 = p2.next
p3 = p3.next
else :
if p3.next.val == 0:
p3.next = None
break
return l3
執(zhí)行結(jié)果.png
來源：
以上題目來源于leetcode-cn
