亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

為什么我會超過時間限制?

為什么我會超過時間限制?

慕神8447489 2023-03-23 15:30:08
我收到超過時間限制?類似 Char 問題描述 Tahir 和 Mamta 正在 TCS 中的一個項目中工作。Tahir 是一個問題解決者,他為他的朋友 Mamta 想出了一個有趣的問題。問題由一個長度為 N 的字符串組成,并且只包含小寫字母。接下來是 Q 個查詢,其中每個查詢將包含一個整數 P (1<=P<=N),表示字符串中的一個位置。Mamta 的任務是找到該位置出現的字母表,并確定給定位置 P 之前相同字母表的出現次數。Mamta 正忙于她的辦公室工作。因此,她請求你幫助她。約束 1 <= N <= 500000S 由小寫字母組成1 <= Q <= 100001 <= P <= N輸入格式 第一行有一個整數N,表示字符串的長度。第二行包含字符串 S 本身僅包含小寫字母 ('a' - 'z')。第三行包含一個整數 Q,表示將被詢問的查詢數。接下來的 Q 行包含一個整數 P (1 <= P <= N),您需要為此查找 P 之前第 P 個位置出現的字符的出現次數。輸出 對于每個查詢,在單行上打印一個表示答案的整數。測試用例說明例1輸入9算盤293輸出31解釋這里 Q = 2對于 P=9,第 9 個位置的字符是 'a'。P 之前'a' 的出現次數,即9 是3。類似地,對于 P=3,第 3 個字符是 'a'。P 之前'a' 的出現次數。即3 是一次。import java.io.*;public class simchar{    public static void main(String gg[]) throws Exception    {        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));        int n=Integer.parseInt(reader.readLine());        String s=reader.readLine();        if(s.length()!=n) return;        int q=Integer.parseInt(reader.readLine());        int qq;        int []count=new int[q];        char someChar;        for(int j=0;j<q;j++)        {            qq=Integer.parseInt(reader.readLine());            someChar=s.charAt(qq-1);            for(int k=0;k<s.substring(0,qq-1).length();k++){                if((s.substring(0,(qq-1)).charAt(k)==someChar)) count[j]++;            }            System.out.println(count[j]);        }        reader.close();    }}
查看完整描述

2 回答

?
揚帆大魚

TA貢獻1799條經驗 獲得超9個贊

除了奧萊的回答,你還需要考慮一些“微”優化:

我懷疑大部分時間都會花在執行這個循環上:

for(int k=0;k<s.substring(0,qq-1).length();k++){
  if((s.substring(0,(qq-1)).charAt(k)==someChar)) count[j]++;
}

讓我們看幾個方面:

  • k<s.substring(0,qq-1).length()創建一個子字符串,以便它可以計算出它的長度。但是我們知道那個長度是多少: qqqq因此,您無緣無故地創建了一個新字符串并復制了字符。效率低下。無意義。

  • s.substring(0,(qq-1)).charAt(k)==someChar創建另一個字符串,然后獲取它的k第 th 個字符。但是k子字符串的第 th 個字符也是k原始字符串的第 th 個字符s。(想想看?。┧?,再一次創建子串是沒有意義的。

  • 那些不必要的計算都重復了qq多次。這是相同的(不必要的)計算完成2 x qq時間。

注意:此分析不考慮您的代碼是否正確或算法是否最優。這純粹是關于微觀效率。你所做的是將O(N^2)算法變成O(N^3)算法......由于不必要的子字符串創建。


查看完整回答
反對 回復 2023-03-23
?
達令說

TA貢獻1821條經驗 獲得超6個贊

對于長字符串(最多 500000 個字母)和許多查詢(最多 10000 個)的有效解決方案,您需要以某種方式預處理字符串數據,以便之后您可以快速處理每個查詢。我建議對于 26 個可能的小寫字母(問題明確表示“a”-“z”)中的每一個,找到第 1、2、3 次出現的位置等,并將它們填充到數組或列表中。然后對于每個查詢,在數組中進行二進制搜索以查找您作為輸入獲得的位置。然后找到的數組索引會告訴你答案。這會將您的時間復雜度從O(s^2 * q)降低到O(s + q * log(s))。

如果您不知道二進制搜索,請查找它。或者使用 aMap<Integer, Integer>而不是數組或列表。

更高效的是,構建一個與字符串長度相同的數組,并在每個索引中存儲關于該索引的查詢的答案。我相信這可以用復雜度O(s + q)來實現。


查看完整回答
反對 回復 2023-03-23
  • 2 回答
  • 0 關注
  • 145 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號