Cisco

— / 33已做

01FizzBuzz Variant

When given a number N, for each integer i in the range from 1 to N inclusive, print one value per line as follows:

If i is a multiple of both 3 and 5, print FizzBuzz.
If i is a multiple of 3 but not 5, print Fizz.
If i is a multiple of 5 but not 3, print Buzz.
Otherwise, print the value of i.

Constraints

0 < N ≤ 2 × 10⁶.

解法

线性扫描，用 by3 / by5 两个布尔标记。输出用 StringBuilder 或预分配字符串缓冲，避免大 N 下的二次拼接。复杂度 O(N)。

import sys

def fizz_buzz(n: int) -> str:
    out = []
    for i in range(1, n + 1):
        by3, by5 = i % 3 == 0, i % 5 == 0
        if by3 and by5: out.append("FizzBuzz")
        elif by3:       out.append("Fizz")
        elif by5:       out.append("Buzz")
        else:           out.append(str(i))
    return '\n'.join(out)

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    sys.stdout.write(fizz_buzz(n))

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            boolean by3 = i % 3 == 0, by5 = i % 5 == 0;
            if (by3 && by5)      sb.append("FizzBuzz");
            else if (by3)        sb.append("Fizz");
            else if (by5)        sb.append("Buzz");
            else                 sb.append(i);
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
 ios::sync_with_stdio(false);
 int n; cin >> n;
 string out;
 out.reserve(n * 4);
 for (int i = 1; i <= n; i++) {
 bool by3 = i % 3 == 0, by5 = i % 5 == 0;
 if (by3 && by5) out += "FizzBuzz";
 else if (by3) out += "Fizz";
 else if (by5) out += "Buzz";
 else out += to_string(i);
 out += '\n';
 }
 cout << out;
}

There is a set of N jars containing chocolates. Some of them may be empty. Determine the maximum number of chocolates Andrew can pick from the jars given that he cannot pick from jars next to each other.

Input: first line N, second line N space-separated integers (chocolates per jar). Output: max chocolates pickable. Constraints

1 ≤ N ≤ 1000.

解法

经典打家劫舍 DP：dp[i] = max(dp[i-1], dp[i-2] + jars[i])。滚动两个变量即可。时间 O(N)，空间 O(1)。

def tallest_chocolate(jars: list[int]) -> int:
    prev2 = prev1 = 0
    for x in jars:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int prev2 = 0, prev1 = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        System.out.println(prev1);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
 int n; cin >> n;
 int prev2 = 0, prev1 = 0;
 for (int i = 0; i < n; i++) {
 int x; cin >> x;
 int cur = max(prev1, prev2 + x);
 prev2 = prev1;
 prev1 = cur;
 }
 cout << prev1;
}

03Saddle Point in Matrix

Find the element which is largest in its row and smallest in its column in a matrix. If no such element exists, print -1.

Input: N M then N rows of M non-negative integers. Constraints

1 ≤ N, M ≤ 1000.

解法

预处理 rowMax[i](第 i 行最大值所在列)和 colMin[j](第 j 列最小值所在行)。(i, j) 是鞍点当且仅当 j == rowMax[i] 且 i == colMin[j]。复杂度 O(N · M)。

def saddle_point(a: list[list[int]]) -> int:
    n, m = len(a), len(a[0])
    row_max_col = [max(range(m), key=lambda j: a[i][j]) for i in range(n)]
    col_min_row = [min(range(n), key=lambda i: a[i][j]) for j in range(m)]
    for i in range(n):
        j = row_max_col[i]
        if col_min_row[j] == i:
            return a[i][j]
    return -1

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) a[i][j] = sc.nextInt();
        int[] rowMaxCol = new int[n], colMinRow = new int[m];
        for (int i = 0; i < n; i++) {
            int idx = 0;
            for (int j = 1; j < m; j++) if (a[i][j] > a[i][idx]) idx = j;
            rowMaxCol[i] = idx;
        }
        for (int j = 0; j < m; j++) {
            int idx = 0;
            for (int i = 1; i < n; i++) if (a[i][j] < a[idx][j]) idx = i;
            colMinRow[j] = idx;
        }
        for (int i = 0; i < n; i++) {
            int j = rowMaxCol[i];
            if (colMinRow[j] == i) { System.out.println(a[i][j]); return; }
        }
        System.out.println(-1);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
 int n, m; cin >> n >> m;
 vector<vector<int>> a(n, vector<int>(m));
 for (int i = 0; i < n; i++)
 for (int j = 0; j < m; j++) cin >> a[i][j];
 vector<int> rowMaxCol(n), colMinRow(m);
 for (int i = 0; i < n; i++) {
 int idx = 0;
 for (int j = 1; j < m; j++) if (a[i][j] > a[i][idx]) idx = j;
 rowMaxCol[i] = idx;
 }
 for (int j = 0; j < m; j++) {
 int idx = 0;
 for (int i = 1; i < n; i++) if (a[i][j] < a[idx][j]) idx = i;
 colMinRow[j] = idx;
 }
 for (int i = 0; i < n; i++) {
 int j = rowMaxCol[i];
 if (colMinRow[j] == i) { cout << a[i][j]; return 0; }
 }
 cout << -1;
}

04Binary Linked List to Decimal

A binary number is represented as a series of 0s and 1s in the form of a single-linked list. Given a reference of the head, convert the binary number to a decimal number (head = MSB).

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

05Minimum Password Update Operations

A company's IT department is faced with a dilemma that users keep using simple passwords such as "password", "abc123" etc. Write an algorithm to identify the total minimum number of changes (insertions and deletions) of characters to convert these simple passwords to their more difficult versions.

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

06Count Days with Odd Number of Birthdays

In a hostel, there are birthday celebrations every month. Find the number of days where there are an odd number of birthday celebrations.

Input: N then N date numbers. Output: number of dates that appear an odd number of times.

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

07Prime vs Composite

Given a list of integers, find out if the elements are prime or composite. Print Prime or Composite, one per line.

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

08Add Numbers

Write an algorithm to add the numbers and print them as a list. Input The first line of input consists of an integer- list1_size, representing the size of the first list (N). The second line consists of N space-separated integers representing the elements in the first list. The third line of input consists of an integer- list2_size, representing the size of the second list (M). The last line consists of M space-separated integers representing the elements in the second list. Output Print K space-separated integers representing the digits in reverse order which are the sum of both the numbers.

01FizzBuzz Variant

02Tallest Chocolate Stack

03Saddle Point in Matrix

04Binary Linked List to Decimal

05Minimum Password Update Operations

06Count Days with Odd Number of Birthdays

07Prime vs Composite

08Add Numbers

09Calculate Mean and Mode

10Check Alphabetical Order

11Collect Coins

12Compact the List

13Convert Simple Password to Complex

14Count Numbers with Digit Sum

15Create New Version

16Expand Given String

17Process Queries to Find Critical Nodes

18Find Elements Largest in Row Smallest in Column

19Find Largest Sum Contiguous Subarray

20Find Last Cell

21Find Longest Palindromic Substring

22Find Maximum Difference

23Find Maximum Number Drop Points Connected

24Find Minimum Cost to Shift Machines

25Find Number in Matrix

26Find Words in Grid

27Get Minimum Servers

28Identify the Non-Twin Person

29Longest Palindromic Substring

30Maximum Chocolates from Jars (LeetCode 198)

31Delete Nodes Greater Than X

32Rotate Matrix

33Minimum Steps to Achieve Target State

解锁全部 30 道题的解法