A Caesar cipher encrypts a word by replacing each letter with another letter that is a fixed number of positions after it in the alphabet. For example, for a cipher that replaces a letter with one that is four letters after it in the alphabet, letter A is replaced by E, letter B is replaced by F, ..., letter Y is replaced by C and letter Z is replaced by D. In other words, each letter in the alphabet is rotated to the right by four positions. For example: PINEAPPLE is encrypted as TMRIETTPI. The table below shows the mapping of letters when using a Caesar cipher with a rotation of 4. Write a function: class Solution { public String encrypt(String text); } that, given a string text, returns the string encrypted using a Caesar cipher with a rotation of 4. Assume that:

• The length of string text is within the range [1..100];
• String text is made only of uppercase letters (A-Z). In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

解法

凯撒密码右移 4：对每个字符 c，输出 chr((c - 'A' + 4) % 26 + 'A')。复杂度 O(n)，空间 O(n)。

def encrypt(text: str) -> str:
 return "".join(chr((ord(c) - ord('A') + 4) % 26 + ord('A')) for c in text)

class Solution {
    public String encrypt(String text) {
        StringBuilder sb = new StringBuilder(text.length());
        for (char c : text.toCharArray()) sb.append((char) ((c - 'A' + 4) % 26 + 'A'));
        return sb.toString();
    }
}

class Solution {
public:
    string encrypt(string text) {
        string out;
        out.reserve(text.size());
        for (char c : text) out += char((c - 'A' + 4) % 26 + 'A');
        return out;
    }
};

Design and implement an in-memory key-value store that supports version checkpoints and rollback. Supported operations are:

• PUT <key> <value>
• GET <key>
• CHECKPOINT
• ROLLBACK <version> CHECKPOINT creates a new snapshot version. ROLLBACK version restores the store to the exact state at that checkpoint. Return the lines printed by the command sequence. Only GET outputs are required in the examples below. Function Description Complete the function runVersionedKvStore in the editor below. runVersionedKvStore has the following parameter:
• String[] operations: the operations to execute in order Returns String[]: the output lines produced by the batch.

Constraints

• Checkpoint ids are increasing integers.
• After a rollback,

Example 1

Input:

operations = ["PUT a 1", "CHECKPOINT", "PUT a 2", "GET a", "ROLLBACK 0", "GET a"]

Output:

["2", "1"]

Explanation: The first GET sees the updated value 2. After rolling back to the first checkpoint, a returns to 1.

Example 2

Input:

operations = ["PUT x 5", "CHECKPOINT", "PUT y 9", "CHECKPOINT", "PUT x 7", "ROLLBACK 1", "GET x", "GET y"]

Output:

["5", "9"]

Explanation: Rolling back to version 1 restores the snapshot created after y was added but before x was changed to 7.

解法

维护 store: Dict[str,str] 当前快照，checkpoints: List[Dict] 历史快照。CHECKPOINT 时拷贝当前 store 进 checkpoints。ROLLBACK v 用 checkpoints[v] 替换 store 并截断后续快照。复杂度每次 checkpoint O(n)，其余 O(1)。

from typing import List

def run_versioned_kv_store(operations: List[str]) -> List[str]:
    store = {}
    checkpoints = []
    out = []
    for op in operations:
        parts = op.split()
        cmd = parts[0]
        if cmd == "PUT":
            store[parts[1]] = parts[2]
        elif cmd == "GET":
            out.append(store.get(parts[1], ""))
        elif cmd == "CHECKPOINT":
            checkpoints.append(dict(store))
        elif cmd == "ROLLBACK":
            v = int(parts[1])
            store = dict(checkpoints[v])
            checkpoints = checkpoints[:v + 1]
    return out

import java.util.*;

class Solution {
    String[] runVersionedKvStore(String[] operations) {
        Map<String, String> store = new HashMap<>();
        List<Map<String, String>> checkpoints = new ArrayList<>();
        List<String> out = new ArrayList<>();
        for (String op : operations) {
            String[] parts = op.split(" ");
            switch (parts[0]) {
                case "PUT": store.put(parts[1], parts[2]); break;
                case "GET": out.add(store.getOrDefault(parts[1], "")); break;
                case "CHECKPOINT": checkpoints.add(new HashMap<>(store)); break;
                case "ROLLBACK":
                    int v = Integer.parseInt(parts[1]);
                    store = new HashMap<>(checkpoints.get(v));
                    checkpoints = new ArrayList<>(checkpoints.subList(0, v + 1));
                    break;
            }
        }
        return out.toArray(new String[0]);
    }
}

class Solution {
public:
    vector<string> runVersionedKvStore(vector<string>& operations) {
        unordered_map<string, string> store;
        vector<unordered_map<string, string>> checkpoints;
        vector<string> out;
        for (auto& op : operations) {
            vector<string> parts;
            string cur;
            for (char c : op) { if (c == ' ') { parts.push_back(cur); cur.clear(); } else cur += c; }
            if (!cur.empty()) parts.push_back(cur);
            if (parts[0] == "PUT") store[parts[1]] = parts[2];
            else if (parts[0] == "GET") {
                auto it = store.find(parts[1]);
                out.push_back(it == store.end() ? "" : it->second);
            } else if (parts[0] == "CHECKPOINT") checkpoints.push_back(store);
            else if (parts[0] == "ROLLBACK") {
                int v = stoi(parts[1]);
                store = checkpoints[v];
                checkpoints.resize(v + 1);
            }
        }
        return out;
    }
};

Ellen would like to assign this task to her subordinate workers. Each worker should get a distinct interval of adjacent shoes, such that the number of left shoes is equal to the number of right shoes. Each shoe must be assigned to exactly one worker. What is the maximum number of workers that Ellen can assign to this task? Write a function: class Solution { public int solution(String S); } that, given a string S of letters "L" and "R", denoting the types of shoes in line (left or right), returns the maximum number of intervals such that each interval contains an equal number of left and right shoes. Write an efficient algorithm for the following assumptions: N is an integer within the range [2..100,000]; String S is made only of the characters 'R' and/or 'L'; The number of letters "L" and "R" in string S is the same. Another problem from the same batch: