题目1：两数之和
位运算是计算机科学中的一个基础概念，涉及对整数在内存中的二进制表示进行操作。位运算算法利用位运算来解决问题，可以提高程序的执行效率，尤其是在处理大量数据时。下面是一些基本的位运算类型和应用的知识点。
基本位运算
与（AND）：两个位都为1时，结果为1（a & b）。或（OR）：两个位中有一个为1时，结果为1（a | b）。异或（XOR）：两个位相异时，结果为1（a ^ b）。这个操作用于切换位的状态。非（NOT）：位为0时，结果为1，反之亦然（~a）。左移：将二进制位向左移动指定的位数（a << b），右边空出的位用0填充。右移：将二进制位向右移动指定的位数（a >> b），左边空出的位用0或符号位填充，这取决于使用的是逻辑右移还是算术右移。
应用示例
判断奇偶性：x & 1。如果结果为0，x是偶数；否则是奇数。交换两个数：通过x ^= y; y ^= x; x ^= y;不使用临时变量交换两个数。移除最后一个1：x = x & (x - 1)。这个操作可以用来计算二进制中1的个数或者进行某些特殊计算。获取最后一个1的位置：x & -x。设置某一位为1：x |= (1 << n)。检查某一位是否为1：(x & (1 << n)) != 0。翻转特定位：x ^= (1 << n)。清零最低位的1：x & (x - 1)。提取最低位的1：x & (-x)。
技巧和优化
利用位运算进行快速乘除法：例如，x << 1为x乘以2，x >> 1为x除以2。使用异或操作进行值交换，无需额外空间。位掩码（Bit Masking）：使用位操作来同时检查和设置多个布尔变量。
位运算在解决某些算法问题时能提供优雅且效率高的解决方案，特别是那些涉及到整数的低级操作。掌握位运算不仅能帮助你在编程中找到更简洁、更高效的方法，也是面试中常考的技能之一。 题目描述：给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解法：
def two_sum(nums, target):
hash_table = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_table:
return [hash_table[complement], i]
hash_table[num] = i
return []
# 示例
print(two_sum([2, 7, 11, 15], 9))
题目2：反转链表
题目描述：反转一个单链表。
示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
链表定义：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
解法：
def reverse_list(head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
题目3：有效的括号
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例：
输入: "()[]{}"
输出: true
解法：
def is_valid(s):
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
# 示例
print(is_valid("()[]{}"))
这些题目和解法涵盖了数组、链表和栈的基本操作，是面试中常见的问题类型。务必在真正的面试前熟练掌握这些基础知识和编程技巧。
推荐阅读
发表评论