leetcode weekly contest 记录

leetcode第194场周赛

1486. XOR Operation in an Array

python 实现，时间和空间复杂度都是 $O(n)$, $n$ 是数组的长度

1
2
3
4
5
6
7
8
9

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        arr =[]
        for i in range(n):
            arr.append(start + 2*i)
        res =0
        for num in arr:
            res ^= num
        return res

python 实现，时间复杂度是 $O(n)$， 空间复杂度是 $O(1)$。

1
2
3
4
5
6
7

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        res =0
        for i in range(n):
            t = start + 2*i
            res ^= t
        return res

c++ 实现，时间复杂度是 $O(n)$ 空间复杂度是$O(1)$

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int xorOperation(int n, int start) {
        int res =0;
        for(int i =0; i<n; i++)
            res ^=  start+ i*2;
        return res;   
    }
};

1487. Making File Names Unique

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    // 思路：暴力求解。每次判断一下当前的已经新建的文件名，如果有那么进行某种操作，否则直接新建
    // 这种操作 k+=1
    vector<string> getFolderNames(vector<string>& names) {
        
        unordered_set<string> hash;
        vector<string> res;
        
        for(auto name :names)
        {
            int k =0;
            string suf;
            
            while(hash.count(name+suf))
            {
                k ++;
                suf ="(" +to_string(k) +")";
            }
            hash.insert(name+ suf);
            res.push_back(name+suf);
                
        }
        return res;
    }
};

优化的版本：如果之前已经枚举过，那么就不必重新枚举。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    // 时间复杂度主要在for while 循环，那么减少while循环次数，如果之前已经枚举过，那么直接枚举下一个
    // cnt map中存储的是当前已经枚举到的最大的值
    vector<string> getFolderNames(vector<string>& names) {
        unordered_map<string, int> cnt;
        unordered_set<string> hash;
        vector<string> res;
        
        for(auto name :names)
        {
            int k =0;
            string suf;
            
            if(cnt[name]) k =cnt[name];
            
            while(hash.count(name+suf))
            {
                k ++;
                suf ="(" +to_string(k) +")";
            }
            cnt[name] =k;
            hash.insert(name+ suf);
            res.push_back(name+suf);
                
        }
        return res;
    }
};

leetcode第28场双周赛

1475. Final Prices With a Special Discount in a Shop

c++ 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    // 通过查看数据范围，那么是可以通过暴力的方式求解的， n^2 的时间复杂度
    //  找到最近一个比他小的数字，可以使用单调栈的思路解题，这个是一个模板题， 时间复杂 O(n)
    // 单调栈，栈顶元素是比后面的元素要大，建立的过程是从后往前遍历的
    vector<int> finalPrices(vector<int>& prices) {
        
        vector<int> res;
        stack<int> stk;
        
        for(int i =prices.size() -1; i >=0; i--)
        {
            int t =prices[i];
            
            while(stk.size() && stk.top() > t) stk.pop();
            
            if(stk.size() ) res.push_back(t - stk.top());
            else res.push_back(t);
            while(stk.size() && stk.top() ==t) stk.pop();
            stk.push(t);
        }
        return vector<int>{res.rbegin(), res.rend()};
    }
};

python 解法： 比较完全还原上面 c++ 的算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):
    def finalPrices(self, prices):
        """
        :type prices: List[int]
        :rtype: List[int]
        """
        # reverse for easier processing
        
        prices = prices[::-1]
        stk =[]
        res =[0] *len(prices)
        for (index, p) in enumerate(prices):
            while stk and stk[-1] > p: stk.pop()
            if stk:
                res[index] = p- stk[-1]
            else:
                res[index] =p
            
            stk.append(p)
        return res[::-1]

1476. 子矩形查询

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class SubrectangleQueries {
    
    // 一定要从解决当前问题的角度出发，当前的数据范围 500 100 100 这样是500 w，那么暴力解法是可以接受的
public:
    vector<vector<int>> q;
    
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        q =rectangle;   
    }
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        
        // 做事情一定要想想最笨的方法
        for(int i = row1; i <= row2; i++)
            for(int j =col1; j <= col2; j++)
                q[i][j]  =newValue;
    }
    int getValue(int row, int col) {
        return q[row][col];
    }
};

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
 * obj->updateSubrectangle(row1,col1,row2,col2,newValue);
 * int param_2 = obj->getValue(row,col);
 */

思路二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class SubrectangleQueries {
public:
    // 还有一种思路：维护修改记录
    // 这个表示的是二维数组
    vector<vector<int>> q;
    vector<vector<int>> updates;
    
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        q =rectangle;
    }
    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        // 给出的是 某个范围的 newValue
        // 这个是无脑的加入，最后会使 updates 越来越大。
        updates.push_back({row1, col1, row2, col2, newValue});
    }
    
    int getValue(int row, int col) {
        // 记录表 越往后面越是新的数据, 所以从后往前进行遍历
        for(int i =updates.size() -1; i >=0 ; i--)
        {
            if (row >= updates[i][0] && row <= updates[i][2] && col >= updates[i][1] && col<= updates[i][3])
                return updates[i][4];
        }
        return q[row][col];
    }
};

/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * SubrectangleQueries* obj = new SubrectangleQueries(rectangle);
 * obj->updateSubrectangle(row1,col1,row2,col2,newValue);
 * int param_2 = obj->getValue(row,col);
 */

python 实现的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class SubrectangleQueries:
    def __init__(self, rectangle: List[List[int]]):
        self.q =rectangle
        self.updates =[]

    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        self.updates.append([row1, col1, row2, col2, newValue])
        
    def getValue(self, row: int, col: int) -> int:

        size =len(self.updates)  if self.updates else 0
        
        for i in range(size -1, -1, -1):
            if row>= self.updates[i][0] and row <= self.updates[i][2] and col >= self.updates[i][1] and col <=self.updates[i][3]:
                return self.updates[i][4] 
        return self.q[row][col]

# Your SubrectangleQueries object will be instantiated and called as such:
# obj = SubrectangleQueries(rectangle)
# obj.updateSubrectangle(row1,col1,row2,col2,newValue)
# param_2 = obj.getValue(row,col)

leetcode第195场周赛

1496. Path Crossing

主要的问题：没有思路

c++ 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:

    // 使用hash 表存储走过的路径，如果发现当前遍历的点在 hash表中，那么就return false。
    bool isPathCrossing(string path) {
        unordered_set<string> hash;
        hash.insert("0.0");
        int row =0, col =0;
        for (char ch : path)
        {
            if (ch =='N') row +=1;
            else if (ch =='E') col +=1;
            else if(ch =='S') row -=1;
            else if (ch =='W') col -=1;
            string t =to_string(row) +"."+to_string(col);
            if(hash.find(t) != hash.end()) return true;
            hash.insert(t);
            
        }
        return false;
    }
};

python 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    def isPathCrossing(self, path):
        """
        :type path: str
        :rtype: bool
        """
        points =[]
        points.append("00")
        row, col =0, 0
        for ch in path:
            if ch =='N':
                row +=1
            elif ch =='E': col +=1
            elif ch =='S': row -=1
            elif ch =='W': col -=1
            
            t =str(row)+ str(col)
            if t in points:
                return True
            points.append(t)
        return False

上述算法时间复杂度 $O(n)$，空间复杂度$O(n)$

1497. 检查数组对是否可以被 k 整除

自己的想法：首先需要枚举各种组合的数组对，然后判断各个数组对是否能被 k整除。

更好的想法： 整除转换为余数，如果余数为0，那么就可以被整除。

题意： 判断一个数组中的数组对是否可以被 k 整除。可以任意组成一个数组对。

思路： 整除问题转换成余数问题，如果余数为0，那么可以被整除。如果两个数字组成的和可以被整除，那么这两个数的余数是$i$ 和$k-i$，其中$k$ 是这数字.

Note: the elements in arr can be negative, therefore in Java the remainder may be negative too; In order to get positive remainder for any element a, use (a % k + k) % k; 如果一个数组中可能含有负数，那么使用 (a%k +k )%k 是可以得到余数的结果

c++ 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> r(k, 0);
        
        for(int a: arr)
            r[ (a%k +k) %k] +=1;
        
        if(r[0] %2 != 0) return false; // 这个是偶数个直接能被整除，不是说非要等于0
        
        for(int i =1, j =k -1; i<j; i++, j--)
            if(i ==j)
            {
                if(r[i] %2 != 0) return false;
            }
        else{
            if(r[i] != r[j]) return false;
        }
        return true;
    }
};

python 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution(object):
    def canArrange(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: bool
        """
        r = [0] *k
        for num in arr:
            r[ (num %k +k)%k] +=1
        return r[0] %2 ==0 and all(r [i] ==r[k -i] for i in range(1, k))

python 可以使用更加简洁的语句，all 中所有的判断，如果全部符合条件，那么return True，只有有一个False 那么return False

LeetCode 1498. 满足条件的子序列数目

分析：自己能够想到的是先排序，然后就没有思路了。忘记了不去重的进行排列组合的数学公式，hhh。

比如这里例子中：

1
2
3
4

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

解题思路：

  • 排序
  • 双指针算法找出 两个满足 target 的两个元素，根据index 计算结果

编程 tips： 对于去余，那么凡是相加的情况下都是要取余。

c++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    // 
    int numSubseq(vector<int>& nums, int target) {
        const int mod =1000000007;
        
        int n =nums.size();
        sort(nums.begin(), nums.end());
        
        vector<int> power(n);
        power[0] =1;
        
        for(int i =1; i< n; i++)
            power[i] = power[i -1] * 2 %mod;
        
        int l =0, r =n-1;
        int ans =0;
        
        while(l <=r)
        {
            if( nums[l] +nums[r] <= target)
            {
                ans = (ans + power[r-l]) %mod;
                l +=1;
            }
            else
                r -=1;   
        }
        return ans;
        
    }
};

python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution(object):
    def numSubseq(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        mod = 1000000007
        nums.sort()
        n =len(nums)
        power =[1] * n
        for i in range(1,n):
            power[i] =power[i-1] * 2 % mod;
        
        l, r =0, n-1
        res =0
        while l<=r:
            if nums[l] +nums[r] <= target:
                res = (res +power[r -l]) %mod
                l +=1
            else:
                r -=1
        return res

7月第四周（完成了两道）

leetcode第29场双周赛

1491. Average Salary Excluding the Minimum and Maximum Salary

python 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution(object):
    def average(self, salary):
        """
        :type salary: List[int]
        :rtype: float
        """
        # python 中初始化最大和最小值
        #min_s, max_s, sum_s = max(salary), min(salary), 0
        min_s, max_s, sum_s =float('inf'), -float('inf'), 0
        
        for item in salary:
            if item < min_s: min_s =item
            if item > max_s: max_s =item
            sum_s += item
        return (sum_s -min_s- max_s)*1.0/(len(salary) -2)

无论是在python2 还是在python3 中，都是可以使用 float('inf') 进行初始化最值的。

c++ 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    double average(vector<int>& salary) {
        int max_s =INT_MIN, min_s =INT_MAX, sum =0;
        for(auto s: salary)
        {
            if(s > max_s) max_s =s;
            if( s< min_s) min_s =s;
            sum += s;
        }
        return (sum -max_s -min_s)*1.0 /( salary.size() -2);
    }
};

1492. The kth Factor of n

难点：

求解数字的因数（这个应该是基本功），然后排序，找到第 k 个。

c++ 解法一： 时间复杂度大概是 $nlog(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    // 计算因数的时间复杂度是 O(sqrt(n)) ，这个是常识
    int kthFactor(int n, int k) {
        vector<int> res;
        for(int i =1; i*i <=n; i++)
            if( n %i ==0)
            {
                res.push_back(i) ;// 这个是符合因数的定义的
                if( i *i != n) res.push_back(n /i); //一对因数中相对比较大的数字
            }
        sort(res.begin(), res.end());
        if(k <= res.size()) return res[k-1];
        return -1;
        
    }
};

c++ 解法二： 时间复杂度是 $O(\sqrt(n))$。注意 beg 和 end 的数字 push_back 和获取的方式还是很精妙的，好好体会。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int kthFactor(int n, int k) {
        vector<int> beg, end;
        for(int i =1; i*i <= n; i++)
            if( n %i ==0)
            {
                beg.push_back(i);
                if (i *i != n) end.push_back(n/i);
            }
        if(k <= beg.size()) return beg[k -1];
        if(k <= beg.size() + end.size()) return end[ beg.size() + end.size() -k];
        return -1;      
    }
};

python 解法 (基本上就是按照 c++ 解法二进行的复写)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        
        beg, end =[], []
        i =1
        while i*i <= n:
            if n%i ==0:
                beg.append(i)
                if (i *i != n):
                    end.append(n //i)
            i +=1
        
        if k <= len(beg): return beg[k -1];
        if k <= len(beg) +len(end): return end[len(beg) +len(end) -k];
        return -1

八月第一周 (完成三道)

leetcode第29场双周赛

1493. Longest Subarray of 1’s After Deleting One Element

没有思路，知道和最长子序列有关。最长子序列一般和双指针有关。

给定的是二进制数组 binary array

思路： 可以使用双指针求解，也可以使用动态规划求解（需要两个函数 $f$ 和$g$），相对来说双指针算法比较难想，比较好写。问题可以转换成最多包含一个0的最长的1的序列 。每个数字最多被访问两次，所以时间复杂度是 $O(n)$

滑动窗口是一种特殊的双指针算法

难点： 将问题转换成双指针算法。 c++ 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        
        int res =0;
        int zeros =0;
        for(int i =0, j =0; j < nums.size(); j++)
        {
            if(nums[j] ==0) zeros ++;
            // [i,j] 闭区间中 0 的个数最多1
            while( zeros >1 && i<= j)
            {
                if(nums[i] ==0) zeros -=1;
                i ++;
            }
            res =max(res, j -i +1 -1);   
        }
        return res;
    }
};

python 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        # 双指针算法，[i,j] 闭区间0的个数最多为1
        res =0
        n =len(nums)
        i =0
        zeros =0
        for j in range(n):
            if nums[j] ==0: zeros +=1
            while i<=j and zeros >1:
                if nums[i] ==0: zeros -=1
                i +=1
            res =max(res, j -i)
        return res

leetcode第196场周赛

1502. Can Make Arithmetic Progression From Sequence

（看题目的时候，可以看看数据范围，根据数据范围，也能大概猜出使用什么算法是ok的） python 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        # 从数据范围可以知道，时间复杂度是$O(n^2)$或者 $O(nlogn)$ 做法
        # 所以可以使用先排序，然后再判断
        arr.sort()
        diff =arr[0] -arr[1]
        for i in range(1, len(arr)-1):
            if diff != arr[i] -arr[i+1]:
                return False
        return True

c++ 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int diff =arr[0] -arr[1];
        for(int i =1; i< arr.size()-1; i++)
            if (diff !=arr[i] -arr[i+1])
                return false;
        return true;
    }
};

1492. The kth Factor of n

leetcode第29场双周赛 （复习）

以 $n *n $作为中点，能够被整除的数字是左右各有一个的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    
    # sqrt(n) 的时间复杂度在于，左右两个值是比较对称的
    # 使用 beg 和end 两个就不用重新排序，因为是有序的
    def kthFactor(self, n: int, k: int) -> int:
        
        i =1
        beg, end =[], []
        while i * i <=n:
            if n%i ==0: 
                beg.append(i)
                if i*i !=n:
                    end.append( n//i)
            i +=1
        
        if k<=len(beg):
            return beg[k-1]
        if k <= len(beg) +len(end):
            return end[len(beg)+len(end) -k] # 在end中数字越大，但index 越小
        return -1

1503. Last Moment Before All Ants Fall Out of a Plank

leetcode第196场周赛

模拟题。时间复杂度是 $O(n)$

c++解题思路。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    // 场景很丰富，是一道模拟题
    // 两个方向相反的蚂蚁相遇之后，方向转变，不会花销时间，如果不考虑编号实际上是没有交换（求解max 时间也是不用考虑编号的）
    // 向左做的时间是 index，向右走的时间是 len -index
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int res =0;
        for(auto num : left)
            res =max(res, num);
        for(auto num :right)
            res =max(res, n-num);
        return res;
    }
};

python 解题思路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution(object):
    def getLastMoment(self, n, left, right):
        """
        :type n: int
        :type left: List[int]
        :type right: List[int]
        :rtype: int
        """
        res =0
        for num in left:
            res =max(res, num)
        for num in right:
            res =max(res, n-num)
        return res

八月第二周（完成三道）

1504. Count Submatrices With All Ones

从数据范围，可以看出 是$O(n^3)$ 做法

属于技术性问题（枚举），一定要保证不重复。

枚举的顺序：以当前的格子作为右下角进行枚举，先往左枚举宽度，同时向上枚举高度，所以是三重循环。

每个格子往上数 1 的个数，需要进行预处理得到，是$O(n^2)$ 的过程。

找到左边第一个比他小的数字：单调栈类型的模板

c++ 实现

还是看不懂呀，这个是需要多看几遍视频才能弄懂。

1

统计全 1 子矩形 视频教程

leetcode第30场双周赛

c++ 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n =mat.size(), m =mat[0].size();
        vector<vector<int>> f(n, vector<int>(m) );
        
        
        // 预处理，f(i,j) 表示该点上面有几个连续的1
        for(int i =0; i<n; i++)
            for(int j =0; j< m; j++)
                if(mat[i][j])
                {
                    f[i][j] =1;
                    if(i ) f[i][j] += f[i-1][j];
                }
        int res =0;
        
        for(int i =0; i<n; i++)
        {
            // 单调栈, 找到左边第一个比当前数小的数字，这个是模板题目
            stack<pair<int, int>> stk; // 不仅存储index 还要存储总和
            
            for(int j =0; j< m; j++)
            {
                // 如果发现栈顶元素比较大，那么就弹出
                while( stk.size() && f[i][stk.top().first] >= f[i][j]) stk.pop();
                
                // 找到了第一个比当前元素小的元素
                int s =0;
                if(stk.size())
                {
                    s += stk.top().second;
                    s += (j -stk.top().first) * f[i][j];
                }
                else
                    s += (j +1) * f[i][j];
                
                stk.push({j, s});
                res += s;
            }
            
        }
        return res;
    }
};

python 实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    def numSubmat(self, dp):
        """
        :type mat: List[List[int]]
        :rtype: int
        """
        sums, n, m = 0, len(dp), len(dp[0])
        cnt = [[0]*m for _ in range(n)]
        sts = [[] for _ in range(m)]
        for i in range(n):
            for j in range(m):
                dp[i][j] += dp[i][j-1]*dp[i][j] if j > 0 else 0
                while sts[j] and dp[sts[j][-1]][j] >= dp[i][j]:
                    sts[j].pop() 
                pre, precnt = -1, 0
                if sts[j]:
                    pre, precnt = sts[j][-1], cnt[sts[j][-1]][j]
                cnt[i][j] += precnt + (i-pre)*dp[i][j]
                sums += cnt[i][j]
                sts[j].append(i)
                
        return sums

1507. 转变日期格式

字符串类的问题，使用Python 处理比 c++ 更容易一些。

python 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def reformatDate(self, date: str) -> str:
        date =date.split()
        
        months =["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
        
        day =int(date[0][:-2])
        month =months.index(date[1]) +1
        year =int(date[2])
        return '{:04d}-{:02d}-{:02d}'.format(year, month, day)

还需要学习一下 format 的使用。（注意需要写的 int类型）

c++ 处理字符串感觉有点复杂，暂时没有写。

1508. Range Sum of Sorted Subarray Sums

c++实现。暴力枚举的方式。时间复杂度是$O(n^2 logn)$

共有 $n^2$ 个区间，所以排序的时间复杂度是 $n^2 log n^2$ ，即 $n^2 logn$ 的时间复杂度。 这种算法会超时。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    // 先写个基本的解法，即暴力搜索
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        const int mod =1000000007;
        
        vector<int> sums ;
        
        for(int i  =0; i< nums.size() ; i ++)
        {
            int s =0;
            for(int j =i ; j< nums.size() ; j++)
            {
                s += nums[j];
                sums.push_back(s);
            }   
        }
        sort(sums.begin(), sums.end());
        int res =0;
        
        for(int i =left-1 ; i< right; i++)
            res += sums[i];
        
        return res%mod;
    }
};

c++ 解法 时间复杂度是 $O(nlog M)$ 其中 $M$ 是一个很大的数字，但是这个时间复杂度大概还是 $nlogn$ 的。主要的思路就是 二分+ 前缀和。

将[a, b] 区间和转换成求解 [1, b] 和[1, a] 区间和的差值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

typedef long long LL;
typedef pair<int, LL> PIL;

const int MOD =1e9+7;

class Solution {
public:
    vector<LL> s, ss;
    int n ;
    PIL get(LL mid)
    {
        int cnt =0; 
        LL sum =0;
        
        for(int i =1, j =0; i<=n ; i++)
        {
            
            while(s[i] - s[j] > mid) j ++;
            if( j< i)
            {
                cnt += i -j;
                sum += s[i] * (i -j) -ss[i-1];
                if(j) sum += ss[j-1];
            }
        }
        return {cnt, sum};
        
    }
    
    LL f(int m)
    {
        LL l =0, r =ss.back();
        
        while(l <r)
        {
            LL mid = l +r >> 1;
            auto t  =get(mid);
            if(t.first >=m) r =mid;
            else l =mid +1;

        }
        auto t =get(r);
        return t.second - (t.first -m) * r;
        
    }
    int rangeSum(vector<int>& nums, int _n, int left, int right) {
        n =_n ;
        s.resize(n +1), ss.resize(n +1);
        
        for(int i =1; i<=n; i++)
        {
            s[i] =s[i-1] + nums[i-1];
            ss[i] =ss[i-1] +s[i];
        }
        return (f(right) -f(left -1))% MOD;
        
    }
};

八月第三周（完成两道）

leetcode第30场双周赛

1509. Minimum Difference Between Largest and Smallest Value in Three Moves

c++ 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    // 这道题是非常具有技巧性的：通过移动三次，寻找最大和最小数字之间的差值。 最大的三个数字和最小的三个数字相互差值的最小值。
    //数据范围是 10^5 那麼使用sort 函數，nlogn 的時間複雜度就是可以接受的
    
    // 貪心的做法：從直觀上講，我們會修改最大的若干數字或者最小的若干數字
    // 當修改三個數字時候，有四種選擇：最小的三个；最小的两个+最大的一个； 最小的一个+最大的两个；最大的三个
    int minDifference(vector<int>& nums) {
        
        int n =nums.size();
        if(n<4) return 0;
        sort(nums.begin(), nums.end() );
        return  min(min(nums[n-1]-nums[3], nums[n-2] -nums[2]), min(nums[n-3]-nums[1], nums[n-4]-nums[0]));
    }
};

python 解法

1
2
3
4
5
6
7

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        if len(nums) <4: return 0
        n =len(nums)
        nums.sort()
        return min( nums[n-1] -nums[3], nums[n-2]-nums[2], nums[n-3]-nums[1], nums[n-4] -nums[0])

1510. Stone Game IV

python 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    # 两个人都采取最优策略：这个是不太能理解的。
    # 解法：如果一方拿走stone 之后，剩下的个使得对方没有办法走下去，那么这个就是最优的策略。使用动态规划的思想 f[i] 表示剩下 i个元素 是否可以达成最优策略
    # 转移方程  j =1 开始枚举， j^2<= i, 如果 f[j] ==false，那么f[i] =True
    # 时间复杂度 n\sqrt(n)
    def winnerSquareGame(self, n: int) -> bool:
        f =[False] *(n+1)
        for i in range(1, n+1):
            j =1
            while j*j <=i:
                
                if f[i-j*j] ==False: 
                    f[i] = True
                    break
                j +=1        
        return f[n]

c++ 解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool winnerSquareGame(int n) {
        
        vector<bool> f(n+1);
        f[0] =false;
        
        for(int i =1; i<n+1; i++)
        {
            f[i] =false; //在这里进行初始化，非常nice
            for(int j =1; j *j<= i; j++)
            {
                if(!f[i-j *j])
                {
                    f[i] =true;
                    break;
                }
            }
        }
        return f[n];
    }
};

八月第四周（完成两道）

LeetCode第197场周赛

1512. Number of Good Pairs

题解： 从数据范围中可以知道，使用 $n^2$ 的算法是没有问题的，所以可以直接暴力求解。

c++ 解法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int  n =nums.size();
        int cnt =0;
        for(int i =0; i<n; i++)
            for(int j =i +1 ; j< n; j++)
                if (nums[i] ==nums[j])
                    cnt +=1;
        return cnt;
        
    }
};

但还有更优的做法，可以实现 $O(n)$ 的算法复杂度。 思路：使用字典维护数字出现的频率，每次重复出现一次就在之前的基础上 +1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> dict ;
        int cnt =0;
        for(auto num : nums)
        {
            cnt += dict[num];
            dict[num] +=1;
        }
        return cnt;
        
    }
};

python 解法, 使用第二种思路，时间复杂度是$O(n)$ 空间复杂度是$O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        dic ={}
        cnt =0
        for num in nums:
            if num in dic:
                cnt += dic[num]
                dic[num] +=1
            else:
                dic[num] =1
        return cnt

LeetCode 1513. Number of Substrings With Only 1s

除了使用count 函数之外，没有其他的想法。从数据范围上看，应该是 $nlogn$ 或者 $n^2$ 的时间复杂度。

正确的思路是这样的： [i, j] 表示区间是连续的1，那么所有字符为 1 的子字符串的书目录是 (c =j-i +1)

1
2

c +c -1 + ... +1 = c (c+1)/2

所以先找出连续的字符串，然后使用上述的公式计算。找出连续的子串可以使用双指针算法。

c++ 解法。使用双指针找出连续的字符串是很常见的解题思路。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int numSub(string s) {
        int MOD  =1000000000 +7;
        cout << MOD << endl;
        int res =0;
        
        for(int i =0; i< s.size() ; i++)
        {
            if(s[i] =='1')
            {
                int j =i +1;
                while(s[j] =='1' && j < s.size()) 
                {
                    j ++;
                }
                int c =j -i ;
                res = (res + c *(c+1ll)/2 ) %MOD;
                i =j -1;
            }
        }
        return res;
    }
};

python 解法

下面的解法是错误的，在python 中 range() 函数中的i 会一直从 1, 2, 3 这样进行遍历。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def numSub(self, s: str) -> int:
        res =0
        for i in range(len(s)):
            
            if (s[i] =='1'):
                j =i
                while j < len(s) and s[j] =='1':
                    j +=1
                c =j -i +1
                print(c)
                res = (res + c *(c+1)) %  1000000007
                i =j -1
        return res

正确的 python代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def numSub(self, s: str) -> int:
    
        res =0
        len_ =len(s)
        i =0
        while i < len_ :
            if s[i] =='1':
                j =i +1
                while j < len_ and s[j] =='1':
                    j +=1
                c =j -i 
                #print(c)
                res += (c *(c+1)/2) % (1000000007)
                i =j +1
            else:
                i +=1
        return int(res)