Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

Số ký tự tối đa khi sử dụng tổ hợp phím A, Ctrl+A, Ctrl+C và Ctrl+V

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 02:11:35 28 4
mua khóa gpt4 Nike

Đây là một câu hỏi phỏng vấn từ Google. Tôi không thể tự mình tìm ra nó. Ai đó có thể giải thích điều này?

Viết chương trình in một chuỗi các lần nhấn phím tạo ra số ký tự "A" tối đa. Bạn chỉ có thể sử dụng 4 phím:MỘT,Ctrl+MỘT,Ctrl+C Và Ctrl+V. Chỉ cho phép tổ hợp phím N. tất cả Ctrl+ các ký tự được coi là một lần nhấn phím, vì vậy Ctrl+MỘT Đó là một tổ hợp phím.

Ví dụ trình tựMỘT, Ctrl+MỘT, Ctrl+C, Ctrl+V Tạo hai chữ A trong 4 lần nhấn phím.

  • Ctrl+A chọn tất cả
  • Ctrl+C là sao chép
  • Ctrl+V là để dán

Tôi đã làm một số phép toán. Với N bất kỳ, sử dụng x A, a Ctrl+MỘT,một Ctrl+C và yCtrl+V, chúng ta có thể tạo ra mức tối đa ((N-1)/2)2An A. Đối với một số N > M, tốt hơn nên sử dụng càng nhiều Ctrl+MỘT,Ctrl+CVà Ctrl+V trình tự vì nó nhân đôi số lượng A.

sự liên tiếp Ctrl+MỘT, Ctrl+V, Ctrl+ C Các lựa chọn hiện tại sẽ không bị ghi đè. Nó nối thêm lựa chọn đã sao chép vào lựa chọn đã chọn.

câu trả lời hay nhất

Có một giải pháp lập trình động. Chúng ta biết rằng phím 0 có thể biến chúng ta thành 0 A. Sau đó chúng tôi đi ngang quaTôihầu hết n , thực hiện hai việc: nhấn A một lần và nhấn Select All + Copy rồi Paste jlần (thực tế như sau ji-1; lưu ý thủ thuật ở đây: nội dung vẫn còn trong clipboard nên chúng ta có thể dán nhiều lần thay vì sao chép mỗi lần). Chúng ta chỉ cần xét tối đa 4 lần dán liên tiếp, vì select,copy,paste x 5 tương đương với select,copy,paste,select,copy,paste, tốt hơn vì nó để lại nhiều nội dung hơn trong clipboard. một khi chúng tôi đến n , chúng tôi đã nhận được kết quả mong muốn.

Độ phức tạp có thể xuất hiện là O(N), nhưng vì các số tăng theo cấp số nhân nên thực tế nó là O(N) do độ phức tạp của việc nhân các số lớn2). Dưới đây là cách triển khai Python. Tính N=50.000 mất khoảng 0,5 giây.

định nghĩa max_chars(n):
  dp = [0] * (n+1)
  cho tôi trong xrange(n):
    dp[i+1] = max(dp[i+1], dp[i]+1) # nhấn a
    cho j trong xrange(i+3, min(i+7, n+1)):
      dp[j] = max(dp[j], dp[i]*(ji-1)) # nhấn chọn tất cả, sao chép, dán x (ji-1)
  trả về dp[n]

Trong mã,jBiểu thị tổng số phím được nhấn sau chuỗi phím mới của chúng tôi. chúng tôi đã có rồi Tôicác phím ở giai đoạn này, cũng như 2 phím mới để vào Select All và Copy. Vậy là chúng ta đang nhấn dán ji-2Hạng hai. Kể từ khi dán thêm vào dp[i] theo trình tự hiện cóMỘT, chúng ta cần thêm 1制作 ji-1 .điều này giải thích ji-1Ở hàng thứ hai đến cuối cùng.

Dưới đây là một số kết quả (n => số A):

  • 7 => 9
  • 8 => 12
  • 9 => 16
  • 10 => 20
  • 100 => 1391569403904
  • 1.000 => 326816000195374368378327270206631190344853389404948600842630 3248121757146615064636953144900245174442911064952028008546304
  • 50.000 => một con số rất lớn!

Tôi đồng ý với @SB rằng bạn phải luôn nêu giả thuyết của mình: Giả thuyết của tôi là bạn không cần dán hai lần để nhân đôi số ký tự. Câu này có 7 câu trả lời, vì vậy trừ khi giải pháp của tôi sai thì giả thuyết này phải đúng.

Nếu có ai thắc mắc tại sao tôi không kiểm tra Ctrl+MỘT, Ctrl+C , MỘT, Ctrl+V: Kết quả cuối cùng luôn là tổng củaMỘT, Ctrl+MỘT, Ctrl+C, Ctrl+V 我确实Đã cân nhắc nó.

Về thuật toán - số ký tự tối đa sử dụng tổ hợp phím A, Ctrl+A, Ctrl+C và Ctrl+V, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/4606984/

28 4 0
Bài viết khuyến nghị: Làm cách nào để kiểm tra ngay cấu trúc có giá trị bằng 0 mà không cần kiểm tra mọi phần tử?
Bài viết khuyến nghị: Cách hiệu quả nhất để nhận văn bản bằng boost asio?
Bài viết khuyến nghị: c++ - Triển khai bản đồ Trie
Bài viết khuyến nghị: Sắp xếp nhanh: chọn trục
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress