Comprehensive Collection of Algorithm Interview Problems and Solutions (剑指 Offer)

This document presents a curated list of algorithmic interview problems originally from the "剑指 Offer" series, offering problem descriptions, solution ideas, and reference implementations in JavaScript/TypeScript style code.

1. Search in a 2D Array

Given a matrix where each row is sorted left‑to‑right and each column top‑to‑bottom, determine whether a target integer exists.

题目：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的二维数组和一个整数，判断数组中是否含有该整数。

Two approaches: brute‑force O(n²) scanning, or start from the top‑right corner and move left/down achieving O(n) time.

2. Replace Spaces

Replace every space in a string with "%20".

题目：
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为 We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy
思路：
使用正则表达式，结合字符串的 replace 方法将空格替换为 "%20"
str.replace(/\s/g,"%20")

3. Print Linked List from Tail to Head

Print the values of a singly linked list in reverse order using a stack.

题目：
输入一个链表，从尾到头打印链表每个节点的值。
思路：
利用栈来实现，首先遍历链表将节点压入栈中，遍历完成后弹出栈中元素并打印。

4. Rebuild Binary Tree

Given preorder and inorder traversal arrays (no duplicate values), reconstruct the original binary tree.

题目：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的遍历序列中都不含重复的数字。

Use recursion: the first element of preorder is the root; locate it in inorder to split left/right subtrees. Time O(n), space O(log n).

5. Implement Queue with Two Stacks

Use two stacks to simulate a queue supporting push and pop operations.

题目：
用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

Push elements onto stack1; for pop, transfer elements to stack2 if empty, then pop from stack2. The maximum queue length equals twice the shorter stack's capacity.

6. Minimum Element in Rotated Sorted Array

Find the smallest number in a rotated non‑decreasing sorted array.

题目：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

Linear scan to detect the break point or binary search for O(log n) solution.

7. Fibonacci Number

Compute the n‑th Fibonacci number (n ≤ 39) using an iterative O(n) algorithm.

题目：
大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项。

8. Jump Stairs

Count the number of ways a frog can reach the n‑th stair when it can jump 1 or 2 steps at a time (dynamic programming).

题目：
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

9. Super Jump Stairs

Generalize the previous problem: the frog may jump any number of steps from 1 to n.

题目：
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

10. Rectangle Tiling

Count ways to tile a 2×n rectangle with 2×1 tiles (another Fibonacci‑type problem).

题目：
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？

11. Number of 1s in Binary Representation

Count set bits of an integer using the trick of repeatedly clearing the lowest set bit.

题目：
输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。

12. Power Function

Compute base^exponent handling positive, negative, and zero exponents via recursion.

题目：
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。

13. Rearrange Array: Odds Before Evens

Stable partition an array so that odd numbers appear before even numbers.

题目：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

14. Find Kth Node from End in Linked List

Two‑pointer technique to locate the k‑th node from the tail.

题目：
输入一个链表，输出该链表中倒数第 k 个结点。

15. Reverse Linked List

Iteratively reverse a singly linked list using three pointers.

题目：
输入一个链表，反转链表后，输出链表的所有元素。

16. Merge Two Sorted Linked Lists

Recursively merge two increasing linked lists into one sorted list.

题目：
输入两个单调递增的链表，输出两个链表合成后的链表，要求保持单调不减。

17. Substructure of a Tree

Determine whether tree B is a substructure of tree A using recursion.

题目：
输入两棵二叉树 A、B，判断 B 是不是 A 的子结构。

18. Mirror Image of Binary Tree

Swap left and right children of every node recursively.

题目：
操作给定的二叉树，将其变换为源二叉树的镜像。

19. Print Matrix Clockwise

Print matrix elements in clockwise order layer by layer.

题目：
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

20. Stack with Min Function

Maintain an auxiliary stack that tracks the minimum element.

题目：
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的 min 函数。

21. Validate Stack Push‑Pop Sequence

Simulate push and pop using an auxiliary stack to verify a given pop order.

题目：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

22. Level‑Order Traversal of Binary Tree

Breadth‑first traversal using a queue.

题目：
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

23. Verify Postorder Sequence of BST

Recursively check whether an array can be the postorder traversal of a binary search tree.

题目：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

24. Paths with Given Sum in Binary Tree

Depth‑first search accumulating path sums to match a target value.

题目：
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

25. Copy Complex Linked List

Three methods: O(n²) with nested loops, O(n) time & O(n) space using a hash map, and O(n) time & O(1) space by interleaving copied nodes.

题目：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回复制后复杂链表的 head。

26. BST to Sorted Doubly Linked List

In‑order traversal to rewire pointers, producing a sorted doubly linked list without creating new nodes.

题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

27. String Permutations

Recursively generate all permutations of a string (length ≤ 9) in lexicographic order.

题目：
输入一个字符串，按字典序打印出该字符串中字符的所有排列。

28. Number Appearing More Than Half

Three solutions: sort and take median, quick‑select partition, or Boyer‑Moore voting algorithm (O(n) time, O(1) space).

题目：
数组中有一个数字出现的次数超过数组长度的一半。请找出这个数字。

29. Smallest K Numbers

Approaches: full sort, quick‑select partition, or max‑heap of size k.

题目：
输入 n 个整数，找出其中最小的 K 个数。

30. Maximum Subarray Sum

Kadane’s algorithm (O(n)) and brute‑force O(n²) are described.

题目：
计算连续子向量的最大和。

31. Count of Digit 1 in Range

Two methods: naive iteration and positional analysis achieving O(log n).

题目：
求出 1~13 的整数中 1 出现的次数，并算出 100~300 的整数中 1 出现的次数。

32. Arrange Array to Form Minimum Number

Custom comparator that compares concatenations to sort numbers for the smallest possible combined value.

题目：
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

33. Ugly Numbers

Generate numbers whose only prime factors are 2, 3, 5 using dynamic programming.

题目：
把只包含质因子 2、3 和 5 的数称作丑数。求按从小到大的顺序的第 N 个丑数。

34. First Non‑Repeating Character in String

Two‑pass method using a map to count occurrences.

题目：
在一个字符串中找到第一个只出现一次的字符，并返回它的位置。

35. Inverse Pairs in Array

Count inversions using merge sort (O(n log n)).

题目：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

36. First Common Node of Two Linked Lists

Three techniques: brute‑force, stack comparison, and length‑difference two‑pointer method.

题目：
输入两个链表，找出它们的第一个公共结点。

37. Count of a Number in Sorted Array

Linear scan O(n) or binary search to find first and last occurrence (O(log n)).

题目：
统计一个数字在排序数组中出现的次数。

38. Depth of Binary Tree

Recursive depth = max(leftDepth, rightDepth) + 1.

题目：
输入一棵二叉树，求该树的深度。

39. Balanced Binary Tree

Check balance while computing height; return -1 immediately when unbalanced.

题目：
输入一棵二叉树，判断该二叉树是否是平衡二叉树。

40. Two Numbers Appearing Once

Use XOR to isolate differing bits and partition the array to find the two unique numbers.

题目：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

41. Consecutive Positive Sequences Summing to S

Sliding window with two pointers to maintain a running sum.

题目：
求所有和为 S 的连续正数序列。

42. Two Numbers with Sum S (Minimum Product)

Two‑pointer technique on a sorted array to find the first pair whose sum equals S, which yields the minimal product.

题目：
输入一个递增排序的数组和一个数字 S，在数组中查找两个数，使得它们的和正好是 S，若有多对则输出乘积最小的一对。

43. Left Rotate String

Slice the string at position K and concatenate the two parts.

题目：
把字符串循环左移 K 位后的序列输出。

44. Reverse Word Order in Sentence

Split by spaces, reverse the array, and join back.

题目：
将句子中单词的顺序翻转，使其恢复正确的阅读顺序。

45. Poker Straight

Treat jokers as 0, sort the hand, count zeros, and ensure no duplicate non‑zero cards; the total gaps must not exceed the number of zeros.

题目：
判断抽出的 5 张牌是否可以组成顺子，大小王可以视为任意数字。

46. Josephus Problem (Last Remaining Number)

Mathematical recurrence or simulation with a circular linked list.

题目：
0, 1, … , n‑1 排成一个圈，从数字 0 开始每次删除第 m 个数字，求最后剩下的数字。

47. Sum 1+2+…+n Without Loops or Conditionals

Recursive solution leveraging short‑circuit evaluation of the && operator.

题目：
求 1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句。

48. Add Two Integers Without Arithmetic Operators

Use bitwise operations (carry and sum) recursively.

题目：
写一个函数，求两个整数之和，要求在函数体内不得使用 +、-、×、÷ 四则运算符号。

49. String to Integer (atoi)

Parse optional sign, validate digits, and accumulate value manually.

题目：
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。

50. Find Any Duplicate in Array

Three strategies: sort and scan, hash map counting, or in‑place swapping based on indices.

题目：
在一个长度为 n 的数组里，所有数字都在 0 到 n‑1 范围内，找出任意一个重复的数字。

51. Construct Product Array

Compute prefix products C[i] and suffix products D[i]; then B[i] = C[i] * D[i].

题目：
给定一个数组 A，构建数组 B，使得 B[i] 等于除 A[i] 之外所有元素的乘积，且不能使用除法。

52. Regular Expression Matching

Implement a matcher supporting '.' (any character) and '_' (Kleene star for the preceding character).

题目：
实现一个函数用来匹配包括 '.' 和 '_' 的正则表达式。

53. Validate Numeric String

Use a comprehensive regular expression to test integer, decimal, and scientific notation formats.

题目：
实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

54. First Non‑Repeating Character in a Stream

Same approach as problem 34, maintaining counts as characters arrive.

题目：
请实现一个函数用来找出字符流中第一个只出现一次的字符。

55. Entry Node of Loop in Linked List

Detect loop with fast/slow pointers, compute loop length, then advance one pointer by that length to locate the entry.

题目：
一个链表中包含环，如何找出环的入口结点？

56. Delete Duplicated Nodes in Sorted List

Traverse with a dummy head, skip all nodes that have duplicates, linking only distinct nodes.

题目：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

57. Next Node in In‑order Traversal

Three cases: node has right subtree, node is left child of its parent, or climb up until finding a node that is a left child.

题目：
给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？

58. Symmetric Binary Tree

Compare left‑right mirrored preorder traversals or recursively check mirrored subtrees.

题目：
请实现一个函数来判断一棵二叉树是不是对称的。

59. Zigzag Level Order Traversal

Use two stacks to alternate left‑to‑right and right‑to‑left order per level.

题目：
请实现一个函数按照之字形顺序打印二叉树。

60. Level Order Print (One Line per Level)

Queue with counters for current and next level node counts.

题目：
从上到下按层打印二叉树，同一层的结点从左至右输出，每一层输出一行。

61. Serialize and Deserialize Binary Tree

Use array (or string) representation with placeholders for null nodes.

题目：
请实现两个函数，分别用来序列化和反序列化二叉树。

62. Kth Smallest Node in BST

In‑order traversal with a counter; stop when the counter reaches k.

题目：
给定一颗二叉搜索树，请找出其中的第 k 小的结点。

63. Median of Data Stream

Maintain two heaps (max‑heap for lower half, min‑heap for upper half) to retrieve median in O(log n).

64. Sliding Window Maximum

Use a deque to keep indices of useful elements in decreasing order.

65. Word Search in Matrix

Depth‑first search with backtracking, marking visited cells.

66. Robot Movement Range

DFS/BFS constrained by the sum of digits of coordinates not exceeding k.

Additional references and acknowledgments are listed at the end of the original article.