摘要:題目鏈接思路從題目得知,我們是求字符串在字符串中出現的次數。也就是說,就可以獲得答案。當然可以利用數據結構進行優化。算法復雜度時間空間代碼用優化
題目鏈接:Jewels and Stones
思路:
從題目得知,我們是求字符串J在字符串S中出現的次數。也就是說,one-pass就可以brute force獲得答案。
當然可以利用set()數據結構進行優化。
算法復雜度:
時間:O(M*N) or O(M + N) where M is the length of J and N is the length of S 空間:O(1) or O(M) where M is the length of J
代碼:
class Solution(object): def numJewelsInStones(self, J, S): """ :type J: str :type S: str :rtype: int """ count = 0 for s in S: if s in J: count +=1 return count
用set()優化:
class Solution(object): def numJewelsInStones(self, J, S): """ :type J: str :type S: str :rtype: int """ setJ = set(J) return sum(s in setJ for s in S)
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/41969.html
摘要:由于是按難易度排序的,因此本題是第一題。先把問題簡化為中只有一個字符的情形,因為字符串可以看作是一個字符數組。這個函數的作用就是,根據閉包函數,過濾數組元素。要注意是字符串,需要先轉換成數組才行。 771. Jewels and Stones 由于是按難易度排序的,因此本題是第一題。 題目鏈接 771. Jewels and Stones 題目分析 從第二個參數S中找第一個參數J 中出...
摘要:字母區分大小寫,因此和是不同類型的石頭。輸入輸出暴力解法將寶石中的每個元素在石頭中的數量相加的時間復雜度為石頭中的每個元素此元素在寶石中則官方解法哈希表將搜索的時間復雜度變為 本文章基于Datewhale第30期組隊學習 2021.11.15 # 1 兩數之和# 給定一個整數數組 nums...
摘要:數據結構與算法簡介及攻略兩數之和數組串聯學到無返回值,是在原始數組進行的修改寶石與石頭官方題解我覺得我的方法應該進行簡化數組基礎加一尋找數組的中心下標左求和中間值數組所有旋轉數組旋轉圖像螺旋矩陣對角線遍歷 Task1:數據結構與算法簡介、LeetCode ??及攻略 0001.兩數之和 cl...
Problem A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a li...
摘要:石頭的位置用整數數組來表示。廣度優先遍歷可以從起點開始,對從該點出發的所有可能步數進行遍歷,并更新從該點可達的點的所有的可行步數。利用數據結構來記錄該結果,其中的為的數,它的對應的是從該出發的所有的上一步的步長。 題目要求 A frog is crossing a river. The river is divided into x units and at each unit the...
閱讀 3477·2021-09-22 15:02
閱讀 3524·2021-09-02 15:21
閱讀 2141·2019-08-30 15:55
閱讀 2789·2019-08-30 15:44
閱讀 789·2019-08-29 16:56
閱讀 2422·2019-08-23 18:22
閱讀 3349·2019-08-23 12:20
閱讀 3097·2019-08-23 11:28