本文主要是介绍面试算法十问(中英文),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.两数之和 (Two Sum)
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回它们的数组下标。
Given an array of integers nums and a target value target, find the two integers in the array that sum up to the target value and return their array indices.
解释:可以使用哈希表来存储已经遍历过的数字及其索引,这样可以在 O(1) 时间内查找 target - nums[i] 是否存在。
Explanation: You can use a hash table to store the numbers and their indices that have been traversed, so you can find if target - nums[i] exists in O(1) time.
伪代码:
hash_table = {}
for i = 0 to len(nums) - 1complement = target - nums[i]if complement in hash_tablereturn [hash_table[complement], i]hash_table[nums[i]] = i
return []
2.有效的括号 (Valid Parentheses)
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串,判断字符串是否有效。
Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
解释:使用栈来跟踪括号的匹配,左括号入栈,右括号时检查栈顶元素是否匹配。
Explanation: Use a stack to track the matching of parentheses. Push left parentheses onto the stack, and when encountering a right parenthesis, check if the top element of the stack matches.
伪代码:
stack = []
for each char in stringif char is left parenthesisstack.push(char)else if stack is not empty and top of stack matches charstack.pop()elsereturn false
return stack is empty
3.合并两个有序链表 (Merge Two Sorted Lists)
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
Merge two sorted linked lists into a new sorted linked list and return it. The new list is formed by splicing together the nodes of the given two lists.
解释:可以使用一个新的链表来逐个比较两个链表的节点,选择较小的节点添加到新链表中。
Explanation: You can use a new linked list to compare the nodes of the two lists one by one, and add the smaller node to the new list.
伪代码:
dummy = new Node(0)
current = dummy
while list1 is not null and list2 is not nullif list1.val < list2.valcurrent.next = list1list1 = list1.nextelsecurrent.next = list2list2 = list2.nextcurrent = current.next
if list1 is not nullcurrent.next = list1
elsecurrent.next = list2
return dummy.next
4.盛最多水的容器 (Container With Most Water)
给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). Draw n vertical lines such that the two endpoints of line i are at (i, ai) and (i, 0). Find two lines, which together with the x-axis form a container, such that the container contains the most water.
解释:使用两个指针分别指向数组的开始和结束,计算当前的容量,并逐步向中间移动较短的线,以寻找可能的更大容量。
Explanation: Use two pointers pointing to the start and end of the array, calculate the current capacity, and gradually move the shorter line towards the middle to find a potentially larger capacity.
伪代码:
left = 0
right = len(height) - 1
max_water = 0
while left < rightwidth = right - leftmax_water = max(max_water, min(height[left], height[right]) * width)if height[left] < height[right]left++elseright--
return max_water
5.无重复字符的最长子串 (Longest Substring Without Repeating Characters)
给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
Given a string, find the length of the longest substring without repeating characters.
解释:可以使用滑动窗口的方法,用一个哈希集合来记录窗口内的字符,当遇到重复字符时,移动窗口的开始位置。
Explanation: You can use the sliding window method and a hash set to record the characters within the window. When a repeated character is encountered, move the start position of the window.
伪代码:
start = 0
max_length = 0
char_set = set()
for i = 0 to len(string) - 1while string[i] in char_setchar_set.remove(string[start])start++char_set.add(string[i])max_length = max(max_length, i - start + 1)
return max_length
6.三数之和 (3Sum)
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0?请你找出所有满足条件且不重复的三元组。
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
解释:可以先对数组排序,然后使用一个固定的指针遍历数组,对于每个元素,使用两个指针在剩余部分进行搜索,找到满足条件的三元组。
Explanation: You can first sort the array and then use a fixed pointer to traverse the array. For each element, use two pointers to search in the remaining part to find triplets that meet the condition.
伪代码:
sort(nums)
result = []
for i = 0 to len(nums) - 3if i > 0 and nums[i] == nums[i - 1]continueleft = i + 1right = len(nums) - 1while left < rightsum = nums[i] + nums[left] + nums[right]if sum == 0result.add([nums[i], nums[left], nums[right]])while left < right and nums[left] == nums[left + 1]left++while left < right and nums[right] == nums[right - 1]right--left++right--else if sum < 0left++elseright--
return result
7.最接近的三数之和 (3Sum Closest)
给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。
Given an array nums of n integers and a target value target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers.
解释:和三数之和类似,先对数组排序,然后使用一个固定的指针遍历数组,对于每个元素,使用两个指针在剩余部分进行搜索,记录最接近的和。
Explanation: Similar to 3Sum, first sort the array, then use a fixed pointer to traverse the array. For each element, use two pointers to search in the remaining part and record the closest sum.
伪代码:
sort(nums)
closest_sum = inf
for i = 0 to len(nums) - 3if i > 0 and nums[i] == nums[i - 1]continueleft = i + 1right = len(nums) - 1while left < rightsum = nums[i] + nums[left] + nums[right]if abs(sum - target) < abs(closest_sum - target)closest_sum = sumif sum < targetleft++else if sum > targetright--elsereturn sum
return closest_sum
```
8.删除链表的倒数第N个节点 (Remove Nth Node From End of List)
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
Given a linked list, remove the nth node from the end of the list and return its head.
解释:可以使用两个指针,第一个指针先移动 n 步,然后两个指针同时移动直到第一个指针到达末尾,这时第二个指针指向的就是需要删除的节点的前一个节点。
Explanation: You can use two pointers, move the first pointer n steps first, then move both pointers at the same time until the first pointer reaches the end, at which point the second pointer points to the node before the one to be deleted.
伪代码:
dummy = new Node(0)
dummy.next = head
first = dummy
second = dummy
for i = 0 to nfirst = first.next
while first.next is not nullfirst = first.nextsecond = second.next
second.next = second.next.next
return dummy.next
9.回文数 (Palindrome Number)
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
解释:可以将整数转换为字符串,然后使用双指针法从两端向中间比较字符是否相同。
Explanation: You can convert the integer to a string and then use the two-pointer technique to compare characters from both ends towards the middle to see if they are the same.
伪代码:
str_num = str(num)
left = 0
right = len(str_num) - 1
while left < rightif str_num[left] != str_num[right]return falseleft++right--
return true
10.整数反转 (Reverse Integer)
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
Given a 32-bit signed integer, reverse digits of an integer.
解释:可以通过循环取出整数的最后一位数字,然后添加到新整数的末尾,注意处理整数溢出的情况。
Explanation: You can reverse the digits of an integer by repeatedly popping the last digit of the integer and appending it to the end of a new integer, being careful to handle integer overflow.
伪代码:
rev = 0
while num != 0pop = num % 10num /= 10if rev > INT_MAX/10 or (rev == INT_MAX / 10 and pop > 7)return 0if rev < INT_MIN/10 or (rev == INT_MIN / 10 and pop < -8)return 0rev = rev * 10 + pop
return rev
这篇关于面试算法十问(中英文)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!