HRT OA 面试经验分享：高效解题策略 | 面试代面, OA代做, 面试辅导

HRT OA 面试经验分享：高效解题策略 | 面试代面, OA代做, 面试辅导

在这次HRT的在线测试中，面试官给出了两个挑战性的算法题，分别涉及数字的特殊表示和棋盘游戏策略的实现。这些题目不仅考察了考生的算法和编程能力，还要求考生在高压环境下快速解决问题。如果你希望在这样的面试中表现出色，我们的代面服务能够帮助你提前准备，掌握各种高效的解题技巧，助你成功拿下理想的offer。

想要了解更多或获取我们的服务，欢迎添加微信 leetcode-king。

---

题目1：Fancy Positive Integers

Problem Description:

A positive integer is "fancy" if its representation in base 4 only includes 0s and 1s. For example:

• 17 is fancy: its base-4 representation, 101, only includes 0s and 1s.
• 18 is not fancy: its base-4 representation, 102, includes a 2.

Given a positive integer n, find the number of fancy positive integers less than n.

Note that n may be as large as a billion! Your algorithm should be faster than iterating over values less than n and checking if each one is fancy.

Example:

• For n = 1, the output should be 0; there are no positive integers less than 1.
• For n = 10, the output should be 3 since [1, 4, 5] are all fancy.

Code:

def count_helper(input_str, e, i):
    if i == len(input_str):
        return 1
    if e:
        if input_str[i] > '1':
            return 2 * count_helper(input_str, False, i + 1)
        elif input_str[i] == '1':
            return count_helper(input_str, True, i + 1) + count_helper(input_str, False, i + 1)
        else:
            return count_helper(input_str, True, i + 1)
    else:
        return 2 * count_helper(input_str, False, i + 1)

def is_fancy(num):
    for c in num:
        if c > '1':
            return False
    return True

def fancy_solution(n):
    num = ""
    while n > 0:
        num += chr(n % 4 + ord('0'))
        n //= 4
    num = num[::-1]
    return count_helper(num, True, 0) - (1 if is_fancy(num) else 0)

题目2：Reversi (Othello) Game

Problem Description:

Reversi (or Othello) is a 2-player game played on an N x N board. Player 1 plays the black pieces and Player 2 plays the white pieces.

On each turn, players take turns placing pieces on the board. Once a player places down a piece, the following process occurs: any sequence of opponent disks that are in a straight line (vertical, horizontal, or diagonal) and bounded by the player’s just-played disk and another disk of the same color are turned into the moving player’s color.

Given an N x N board and the moves of the players, implement the game logic to reflect the board state after each move.

Example:

Here's an example on a 4 x 4 board, where it's currently White's turn to play:

0 1 2 3
0 B . B .
1 W B B .
2 . . . .
3 . . . .

White plays at (3, 1). Now, the two Black pieces at (1, 1) and (2, 1) are reversed, since they are in a straight line and bounded by the just-played piece at (3, 1) and the previous piece at (0, 1):

0 1 2 3
0 B . B .
1 W W W .
2 . . . .
3 . . . .

Now, Black plays at (2, 2), and flips the two White pieces at (1, 1) and (2, 1), as they are bounded by the new piece at (2, 2) and the Black pieces at (0, 0) and (2, 0) respectively:

0 1 2 3
0 B . B .
1 W W W .
2 . . B .
3 . . . .

Code:

def apply_move(board, player, x, y):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    board[x][y] = player
    opponent = 'B' if player == 'W' else 'W'
    
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        pieces_to_flip = []
        while 0 <= nx < len(board) and 0 <= ny < len(board) and board[nx][ny] == opponent:
            pieces_to_flip.append((nx, ny))
            nx += dx
            ny += dy
        if 0 <= nx < len(board) and 0 <= ny < len(board) and board[nx][ny] == player:
            for flip_x, flip_y in pieces_to_flip:
                board[flip_x][flip_y] = player

def print_board(board):
    for row in board:
        print(' '.join(row))

board = [['.' for _ in range(4)] for _ in range(4)]
board[0][0] = 'B'
board[0][2] = 'B'
board[1][0] = 'W'
board[1][1] = 'B'
board[1][2] = 'B'
print("Initial board:")
print_board(board)
print("\nWhite plays at (3, 1):")
apply_move(board, 'W', 3, 1)
print_board(board)
print("\nBlack plays at (2, 2):")
apply_move(board, 'B', 2, 2)
print_board(board)