leetcode 编程能力入门（学习计划）

目录

1 在区间范围内统计奇数数目

2 去掉最低工资和最高工资后的工资平均值

3 位1的个数

4 整数的各位积和之差

5 三角形的最大周长

6 找到最近的有相同 X 或 Y 坐标的点

7 数组元素积的符号

8 判断能否形成等差数列

10 仅执行一次字符串交换能否使两个字符串相等

11 N 叉树的前序遍历

12 下一个更大元素 I

13 缀点成线

14 所有奇数长度子数组的和

15 移动零

16 最富有客户的资产总量

17 矩阵对角线元素的和

18 重塑矩阵

19 交替合并字符串

20 设计 Goal 解析器

21 找不同

22 转换成小写字母

23 解码字母到整数映射

25 二进制链表转整数

26 链表的中间结点

27 二叉树的最大深度

29 根据数字二进制下 1 的数目排序

30 用栈实现队列

31 有效的字母异位词

32 区域和检索 - 数组不可变

---

1 在区间范围内统计奇数数目

解题思路是将low与high分为奇-奇、奇-偶、偶-偶、偶-奇四种类型，除了偶-偶num=(high-low)//2以外，其余都是num = (high-low)//2 +1

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        num = (high - low)//2
        if not ((high % 2 == 0) and (low % 2 == 0)):
            num += 1
        return num

class Solution {
public:
    int countOdds(int low, int high) {
        int num = (high - low) / 2;
        if (!((high % 2 == 0) && (low % 2 == 0)))
        {
            num++;
        }
        return num;
    }
};

c++的与&&或 ||非!

2 去掉最低工资和最高工资后的工资平均值

class Solution:
    def average(self, salary: List[int]) -> float:
        max_salary = max(salary)
        min_salary = min(salary)
        average_salary = (sum(salary) - max_salary - min_salary) / (len(salary) - 2)
        return average_salary

class Solution:
    def average(self, salary: List[int]) -> float:
        sum_salary = max_salary = 0
        min_salary = 1000001
        for i in salary:
            if max_salary < i:
                max_salary = i
            if min_salary > i:
                min_salary = i
            sum_salary += i
        average_salary = (sum_salary - min_salary - max_salary) / (len(salary) - 2)
        return average_salary

class Solution {
public:
    double average(vector<int>& salary) {
        double sum_salary = 0;
        int max_salary = 0;
        int min_salary = 1000001;
        for (int i=0; i<salary.size(); ++i)
        {
            if(max_salary < salary[i]) max_salary = salary[i];
            if(min_salary > salary[i]) min_salary = salary[i];
            sum_salary += salary[i];
        }
        double average_salary = (sum_salary - min_salary -max_salary) / (salary.size() - 2);
        return average_salary;
    }
};

class Solution {
public:
    double average(vector<int>& salary) {
        double maxValue = *max_element(salary.begin(), salary.end());
        double minValue = *min_element(salary.begin(), salary.end());
        double sum = accumulate(salary.begin(), salary.end(), - maxValue - minValue);
        return sum / int(salary.size() - 2);
    }
};

设置两个flag分别标志最大值和最小值，最后求和的时候减去这两个值，题目给出了工资范围，要注意最大值的初始值要比最小值小，最小值的初始值要比最大值大。直接调用函数就能通过

accumulate用法：accumulate(arr.begin(), arr.end(), int val);其中val是初始值

3 位1的个数

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            if n&1:
                count += 1
            n = n >> 1
        return count

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n)
        {
            if (n&1) count++;
            n >>= 1;
        }
        return count;
    }
};

python和c++的按位与&、或|、异或^、取反~、左移<<、右移>>。

x&1==0是偶数；x&1==1是奇数。如果位数不一致则右对齐

4 整数的各位积和之差

class Solution:
    def subtractProductAndSum(self, n: int) -> int:
        mul_ = 1
        sum_ = 0
        while(n > 0):
            tmp = n % 10
            mul_ *= tmp
            sum_ += tmp
            n = n // 10
        return mul_ - sum_

class Solution {
public:
    int subtractProductAndSum(int n) {
        int mul_ = 1; 
        int sum_ = 0;
        while (n > 0)
        {
            int tmp = n % 10;
            mul_ *= tmp;
            sum_ += tmp;
            n = int(n / 10);
        }
        return (mul_ - sum_);
    }
};

取余 再相加相乘 再除以10

5 三角形的最大周长

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums = sorted(nums, reverse=True)
        for i in range(len(nums) - 2):
            if nums[i] < nums[i+1] + nums[i+2]:
                return nums[i] + nums[i+1] + nums[i+2]
        return 0

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        reverse(nums.begin(), nums.end());
        for(int i=0; i<nums.size()-2; ++i)
        {
            if (nums[i] < nums[i+1] + nums[i+2])
                return (nums[i] + nums[i+1] + nums[i+2]);
        }
        return 0;
    }
};

三角形成立条件为任意两边之和大于第三边，于是先将数组按照从大到小排序，最大值大于右边两个小值相加即可

C++排序sort()方法在#include <algorihm>下面

6 找到最近的有相同 X 或 Y 坐标的点

class Solution:
    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
        min_length = 100000
        point = -1
        for i in range(len(points)):
            if points[i][0] == x or points[i][1] == y:
                tmp = abs(points[i][1] - y) + abs(points[i][0] - x)
                if min_length > tmp:
                    min_length = tmp
                    point = i
        return point

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int min_length =100000;
        int point = -1;
        for (int i=0; i<points.size(); ++i)
        {
            if (points[i][0] == x || points[i][1] == y)
            {
                int tmp = abs(points[i][0] - x) + abs(points[i][1] - y);
                if (min_length > tmp)
                {
                    point = i;
                    min_length = tmp;
                }
            }
        }
        return point;
    }
};

本题的案例应该是没有加入多个有效点的判断。。不判断也能过

7 数组元素积的符号

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        x = 1
        for num in nums:
            if num == 0:
                return 0
            if num < 0:
                x *= -1      
        return x
           

class Solution {
public:
    int arraySign(vector<int>& nums) {
        int x = 1;
        for(auto it = nums.begin(); it!=nums.end(); it++)
        {
            if(*it == 0) return 0;
            if(*it < 0) x = -x;
        }
        return x;
    }
};

不必真的计算具体数值，只计算负数= -x，正数也不用管，遇到0直接返回0

8 判断能否形成等差数列

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr = sorted(arr)
        flag = True
        diff = arr[0] - arr[1]
        for i in range(1, len(arr)-1):
            if (arr[i] - arr[i+1]) != diff:
                flag = False
        return flag

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

先排序，再看差值是否相等。估计面试的时候要自己手写排序算法？

10 仅执行一次字符串交换能否使两个字符串相等

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        flag = True
        tmp1 = tmp2 = ''
        count = 0
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                count += 1
                if tmp1 == '':
                    tmp1 = s1[i]
                    tmp2 = s2[i]
                else:
                    if tmp1 != s2[i] or tmp2 != s1[i]:
                        flag = False
                        break
        if (count != 0 and count != 2):
            flag = False
        return flag

class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        int count = 0;
        char a,b;
        for (int i=0; i<s1.length(); ++i)
        {
            if(s1[i] != s2[i])
            {
                count++;
                if (count == 1)
                {
                    a = s1[i];
                    b = s2[i];
                }
                if (count == 2)
                {
                    if (s1[i] != b || s2[i] != a) return false;
                }
            }
        }
        if (count !=0 && count != 2) return false;
        return true;
    }
};

字面意思，如果能一次交换成功，必然是只有0处或两处不同，然后再判断这两处不同的字符是否能互换

11 N 叉树的前序遍历

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        pre_list = []
        self.mypre(root, pre_list)
        return pre_list
    def mypre(self, root, pre_list):
        if not root:
            return
        pre_list.append(root.val)
        if root.children:
            for c in root.children:
                self.mypre(c, pre_list)

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> pre_list;
        mypre(pre_list, root);
        return pre_list;
    }
    void mypre(vector<int>& pre_list,Node* root){
        if (! root){ return;}
        pre_list.push_back(root->val);
        for (auto c:root->children)
        {
            mypre(pre_list, c);
        }
    }
};

还是递归香啊

12 下一个更大元素 I

暴力解法

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        for num in nums1:
            flag2 = True
            flag = False
            for i in range(len(nums2)):
                if num == nums2[i]:
                    flag = True
                if flag:
                    if nums2[i] > num:
                        result.append(nums2[i])
                        flag2 = False
                        break
            if flag2:
                result.append(-1)
        return result

看题解中可以使用单调栈解，后续了解后再补充

13 缀点成线

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
            if coordinates[0][0] == coordinates[1][0]:
                for i in range(1, len(coordinates) - 1):
                    if coordinates[i][0] != coordinates[i + 1][0]:
                        return False
            elif coordinates[0][1] == coordinates[1][1]:
                for i in range(1, len(coordinates) - 1):
                    if coordinates[i][1] != coordinates[i+1][1]:
                        return False
            else:
                gradient = (coordinates[0][0] - coordinates[1][0]) / (coordinates[0][1] - coordinates[1][1])
                for i in range(1, len(coordinates) - 1):
                    if (coordinates[i][0] - coordinates[i + 1][0]) / (coordinates[i][1] - coordinates[i+1][1]) != gradient:
                        return False
            return True

能成线，必然斜率一致，只是还要考虑斜率为0的情况（横线和竖线）

看到题解在讨论时认为最好不要用除法，一来除法开销比乘法大，而来除法可能涉及精度不对的问题，二来还需要考虑0的情况。只需要稍微变换一下，由除法变成乘法：a/b = c/d 即 ad = bc

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        for (int i=1; i<coordinates.size()-1; ++i)
        {
            int res1 = (coordinates[i][0] - coordinates[i - 1][0]) * (coordinates[i + 1][1] - coordinates[i][1]);
            int res2 = (coordinates[i + 1][0] - coordinates[i][0]) * (coordinates[i][1] - coordinates[i - 1][1]);
            if(res1 != res2){
                return false;
            }
        }
        return true;
    }
};

14 所有奇数长度子数组的和

万能递归，假设[1,4,5,2,3]，则第一次先计算以1开头的奇数子序列的和：[1]，[1,4,2]，[1,4,2,5,3]；再考虑以4开头的和[4]，[4,5,2]...如此下去。终止条件为数组长度小于等于1.

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        arr_sum = 0
        arr_sum += self.count_sum(arr)
        return arr_sum

    def count_sum(self, next_arr):
        if len(next_arr) <= 1:
            return next_arr[0]
        else:
            tmp = 0
            for i in range(1, len(next_arr)+1, 2):
                tmp += sum(next_arr[:i])
            next_arr_2 = next_arr[1:]
            return tmp + self.count_sum(next_arr_2)

c++版本考虑一下数学解法：力扣

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {

        int res = 0;
        for(int i = 0; i < arr.size(); i ++){
            int left = i + 1, right = arr.size() - i,
                left_even = (left + 1) / 2, right_even = (right + 1) / 2,
                left_odd = left / 2, right_odd = right / 2;
            res += (left_even * right_even + left_odd * right_odd) * arr[i];
        }
        return res;
    }
};

15 移动零

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        first = second = 0
        while(first < len(nums)):
            nums[second] = nums[first]
            if nums[second] != 0:
                second += 1
            first += 1
        for i in range(second, len(nums)):
            nums[i] = 0

定义两个变量，first一直指向下一个数字，而second表示当前不为0才会指向下一个数字，每次循环开始前都需要让nums[first]赋值给nums[second]。循环完毕时后面补0

看题解的意思是要正经的双指针交换0，而不是覆盖再补0的答案，好处是0比较多的时候操作次数少

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0,right = 0;
        int n = nums.size();
        while(right < n)
        {
            if(nums[right])
            {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

c++交换可以用swap函数

16 最富有客户的资产总量

按照字面意思的答案，求出每一行的和然后算最大值

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        max_accounts = 0
        for acc in accounts:
            tmp = sum(acc)
            if tmp > max_accounts:
                max_accounts = tmp
        return max_accounts

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int max_account = 0;
        for (auto &acc:accounts)
        {
            max_account = max(max_account, accumulate(acc.begin(), acc.end(), 0));
        }
        return max_account;
    }
};

17 矩阵对角线元素的和

对角线元素相加，如果长度为奇数则减去中间部分

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        dia_sum = 0
        n = len(mat)
        for i in range(len(mat)):
            dia_sum += mat[i][i]
            dia_sum += mat[i][n-i-1]
        if n%2 != 0:
            dia_sum -= mat[n//2][n//2]
        return dia_sum

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size();
        int dia_sum = 0;
        for(int i=0; i<n; ++i)
        {
            dia_sum += mat[i][i] + mat[i][n-i-1];
        }
        if (n%2 != 0) dia_sum -= mat[n/2][n/2];
        return dia_sum;
    }
};

18 重塑矩阵

完全按照题目描述

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
            if len(mat) * len(mat[0]) != r * c:
                return mat
            new_list = []
            h = 0
            tmp = []
            for i in range(len(mat)):
                for j in range(len(mat[0])):
                    if h <= c:
                        tmp.append(mat[i][j])
                        h += 1
                    if h == c:
                        new_list.append(tmp)
                        h = 0
                        tmp = []
            return new_list

                

题解给出的答案时间复杂度为O(rc)。。不是很懂在成功的情况下O(rc)和O(mn)有什么区别

19 交替合并字符串

挨个插入，最后多的那一部分再放到新字符串尾部

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        new_str = ""
        i = 0
        while(i < len(word1) and i < len(word2)):
            new_str += word1[i]
            new_str += word2[i]
            i += 1
        if len(word1) > len(word2):
            new_str += word1[i:len(word1)]
        else:
            new_str += word2[i:len(word2)]
        return new_str

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string new_str;
        int i = 0; 
        while(i < word1.size()  && i < word2.size())
        {
            new_str = new_str + word1[i] + word2[i];
            ++i;
        }
        if(word1.size() > word2.size())
        {
            new_str += word1.substr(i);
        }
        else
        {
            new_str += word2.substr(i);
        }
        return new_str;
    }
};

substr使用方法：

假设：string s = "0123456789";

string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789"

string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = "567"

20 设计 Goal 解析器

先来个Python直接调用函数s.replace

class Solution:
    def interpret(self, command: str) -> str:
        command = command.replace('()', 'o')
        command = command.replace('(al)', 'al')
        return command

c++就按照题目暴力解，新建一个空字符串，遇到匹配的字符就往里加

class Solution {
public:
    string interpret(string command) {
        string goal;
        int index = 0;
        while(index < command.size())
        {
            if(command[index] == 'G')
            {
                goal += 'G';
                ++index;
                continue;
            }
            if(command[index] == '(')
            {
                if(command[index+1] == ')')
                {
                    goal += 'o';
                    index += 2;
                    continue;
                }
                if(command[index+1] == 'a')
                {
                    goal += "al";
                    index += 4;
                }
            }
        }
        return goal;
    }
};

21 找不同

继续使用python的replace函数，不过需要主要的是字符可能会重复出现，所以只替换一次

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        for i in range(len(s)):
            t = t.replace(s[i], "", 1)
        return t

c++官方有一个很棒的解法，就是求两个字符串的ASCII码的和，然后相减就是剩下的那个字符

class Solution {
public:
    char findTheDifference(string s, string t) {
        int as = 0, at = 0;
        for(auto c : s)
        {
            as += c;
        }
        for(auto c : t)
        {
            at += c;
        }
        return (at - as);
    }
};

22 转换成小写字母

是的python就是最棒的，直接调函数

class Solution:
    def toLowerCase(self, s: str) -> str:
        return s.lower()

c++ 将大写字母转换为小写字母只需要+32。因此如果字符在A-Z之间，即ascii码在65-90之间，加上32就可以了。

class Solution {
public:
    string toLowerCase(string s) {
        for(auto &c : s)
        {
            if(c <= 90 && c >= 65) c += 32;
        }
        return s;
    }
};

官方在c++解法的基础上，提出了不要使用加法而是使用按位或的操作c|=32

23 解码字母到整数映射

python使用查表方法

class Solution:
    def freqAlphabets(self, s: str) -> str:
        s_new = ""
        i = 0
        dictory = {'1':'a', '2':'b', '3':'c', '4':'d', '5':'e', '6':'f', '7':'g', '8':'h',
                   '9':'i', '10#':'j', '11#':'k','12#':'l','13#':'m','14#':'n', '15#':'o',
                   '16#':'p', '17#':'q', '18#':'r', '19#':'s', '20#':'t', '21#':'u', '22#':'v',
                   '23#':'w', '24#':'x', '25#':'y', '26#':'z'}
        while(i < len(s)):
            if i+2 < len(s) and s[i+2] == '#':
                s_new += dictory[s[i:i+3]]
                i += 3
            else:
                s_new += dictory[s[i]]
                i += 1
        return s_new

python 中将ascii转换为字符的函数为chr()

class Solution {
public:
    string freqAlphabets(string s) {
        int i = 0;
        string s_new = "";
        while(i < s.size())
        {
            if(i+2 < s.size() && s[i+2] == '#')
            {
                s_new += char((s[i]-'0')*10 + (s[i+1]-'0') + 96);
                i+=3;
            }
            else
            {
                s_new += char(s[i]-'0'+96);
                i++;
            }
        }
        return s_new;
    }
};

c++则是之间转换，ch-'0'是转换成数字，因为对应是从1开始，所以数字再变为a-z的时候加（97-1）

25 二进制链表转整数

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        s = []
        sum_ = 0
        while(head):
            s.append(head.val)
            head = head.next
        s = s[::-1]
        for i in range(len(s)):
            sum_ += s[i] * pow(2, i)
        return sum_

自身想的是得先知道长度，然后才能乘以2的次方，实际上解法不需要。当读到下一个节点值的时候，需要将已经读到的结果乘以 2，再将新读到的节点值当作当前二进制数的最低位。相当于把十进制转二进制的做法倒过来。

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int sum_ = 0;
        while(head)
        {
            sum_ <<= 1;
            sum_ += head->val;
            head = head->next;
        }
        return sum_;
    }
};

26 链表的中间结点

是的，快慢指针，python:

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        first = head
        second = head
        while(second and second.next):
            first = first.next
            second = second.next.next
        return first

c++：

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* first = head;
        ListNode* second = head;
        while(second && second->next)
        {
            first = first->next;
            second = second->next->next;
        }
        return first;
    }
};

27 二叉树的最大深度

二叉树最深是1+max(左子树深度，右子树深度），所以用递归合适

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

29 根据数字二进制下 1 的数目排序

python 直接调用函数，其中lamba的含义是第一次按照count1的个数排序，第二次按照x的大小排序。

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x:(bin(x).count('1'),x))

c++则是自行构建两个函数，第一个函数是计算位1的个数，在之前的题目中出现过，第二个函数是通过sort函数自行构建比较方式，cmp函数的意思是如果位1的个数相等则从小到大排序。注意要使用static

class Solution {
public:
    static int count_1(int n){
        int count = 0;
        while(n)
        {
            if (n&1) count++;
            n >>= 1;
        }
        return count;
    }
    static bool cmp(int x, int y){
        int m = count_1(x);
        int n = count_1(y);
        if(m == n) return x < y;
        else return m < n;
    }
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

30 用栈实现队列

大概意思就是两个栈变成一个队列，先从一个栈进再从一个栈出。但所有操作一个要把pushstack清空才能操作，不然会错误

class MyQueue {
private:
    stack<int> pushstack;
    stack<int> popstack;
public:
    MyQueue() {}
    
    void push(int x) {
        while(!popstack.empty())
        {
            int temp=popstack.top();
            popstack.pop();
            pushstack.push(temp);
        }
        pushstack.push(x);
    }
    
    int pop() {
        while(!pushstack.empty())
        {
            popstack.push(pushstack.top());
            pushstack.pop();
        }
        int tmp = popstack.top();
        popstack.pop();
        return tmp;
    }
    
    int peek() {
        while(!pushstack.empty())
        {
            popstack.push(pushstack.top());
            pushstack.pop();
        }
        return popstack.top();
    }
    
    bool empty() {
        return (popstack.empty() && pushstack.empty());
    }
};

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.pushStack = []
        self.popStack = []
    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.pushStack.append(x)
    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        l = len(self.pushStack)
        if self.popStack == []:
            for i in range(l):
                self.popStack.append(self.pushStack.pop())
        return self.popStack.pop()
    def peek(self) -> int:
        """
        Get the front element.
        """
        l = len(self.pushStack)
        if self.popStack == []:
            for i in range(l):
                self.popStack.append(self.pushStack.pop())
        return self.popStack[-1]
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return self.pushStack == [] and self.popStack == []

另外c++的stack.pop()返回值是空，必须使用stack.top()才能取到最上面的值

31 有效的字母异位词

题目意思就是找字符相等且数目相等的

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int>tmp = {};
        if(s.size() != t.size()) {return false;}
        for(char c : s)
        {
            if (tmp.find(c) == tmp.end()) tmp[c] = 1;
            else tmp[c] += 1;
        }
        for(auto i : t)
        {
            if (tmp.find(i) == tmp.end()) return false;
            else tmp[i] -= 1;
            if(tmp[i] < 0) return false;
        }
        return true;
    }
};

c++用的是哈希表，判断字母是否在哈希表中可以用tmp.find()==endl()。不过其实直接定义长度为26的数组然后tmp[c-'a']更快速。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s = sorted(s)
        t = sorted(t)
        if s == t:
            return True
        else:
            return False

python就直接排序然后判断两个字符串是否相等

32 区域和检索 - 数组不可变

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left:right+1])

python用的是一般的思想，直接进行相加

c++使用前缀和的思想，将nums的前n项和都存到sums数组中，这样每次调用的时候只需要计算一次减法就行

class NumArray {
public:
    vector<int> sums;

    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n + 1);
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
};

最后

以上就是舒心野狼为你收集整理的leetcode 编程能力入门（学习计划）的全部内容，希望文章能够帮你解决leetcode 编程能力入门（学习计划）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。