Skip to content

Latest commit

 

History

History
581 lines (493 loc) · 20.4 KB

readme.md

File metadata and controls

581 lines (493 loc) · 20.4 KB

941. 有效的山脉数组

题目

给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

  • A.length >= 3
  • 在 0 < i < A.length - 1 条件下，存在 i 使得：
    • A[0] < A[1] < ... A[i-1] < A[i]
    • A[i] > A[i+1] > ... > A[A.length - 1]

 

示例 1：

输入：[2,1]
输出：false

示例 2：

输入：[3,5,5]
输出：false

示例 3：

输入：[0,3,2,1]
输出：true

 

提示：

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000 

 

 

## [Python](./941.%20有效的山脉数组.py) 
class Solution:
    def validMountainArray(self, A: [int]) -> bool:
        is_down = False
        left = None
        length = len(A)
        for index, num in enumerate(A):
            if left is None:
                left = num
            else:
                if is_down:
                    if left < num:
                        return False
                else:
                    if left > num:
                        if index < 2:
                            return False
                        is_down = True
                    if index == length - 1:
                        return False
        return True

C++

class Solution {
  public:
    bool validMountainArray(vector<int> &A) {
        if (A.size() < 3)
            return false;
        bool is_down = false;
        int left = A[0];
        for (int i = 1; i < A.size(); i++) {
            if (is_down) {
                if (left <= A[i]) {
                    return false;
                }
            } else {
                if (left > A[i]) {
                    if (i < 2) {
                        return false;
                    }
                    is_down = true;
                } else if (left == A[i]) {
                    return false;
                } else {
                    if (i == A.size() - 1) {
                        return false;
                    }
                }
            }
            left = A[i];
        }
        return true;
    }
};

977. 有序数组的平方

题目

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

 

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

 

提示：

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A 已按非递减顺序排序。

Python

正常思路

class Solution:
    def sortedSquares(self, A: [int]) -> [int]:
        for index, num in enumerate(A):
            A[index] = num * num
        A.sort()
        return A

Python特有一行法

class Solution:
    def sortedSquares(self, A: [int]) -> [int]:
        return sorted([num * num for num in A])

双指针法

class Solution:
    def sortedSquares(self, A: [int]) -> [int]:
        left = 0, A[0] ** 2
        right = len(A) - 1, A[len(A) - 1] ** 2
        B = [0 for _ in range(len(A))]
        index = right[0]
        while index >= 0:
            if left[1] < right[1]:
                B[index] = right[1]
                if right[0] != 0:
                    right = right[0] - 1, A[right[0] - 1] ** 2
            else:
                B[index] = left[1]
                if left[0] + 1 != len(A):
                    left = left[0] + 1, A[left[0] + 1] ** 2
            index -= 1
        return B

C++

双指针法

class Solution {
  public:
    vector<int> sortedSquares(vector<int> &A) {
        int left = 0, right = A.size() - 1;
        vector<int> B(A.size());
        for (int i = A.size() - 1; i >= 0; i--) {
            int leftValue = pow(A[left], 2), rightValue = pow(A[right], 2);
            if (leftValue < rightValue) {
                B[i] = rightValue;
                if (right != 0)
                    right -= 1;
            } else {
                B[i] = leftValue;
                if (left + 1 != A.size())
                    left += 1;
            }
        }
        return B;
    }
};

985. 查询后的偶数和

题目

给出一个整数数组 A 和一个查询数组 queries。

对于第 i 次查询，有 val = queries[i][0], index = queries[i][1]，我们会把 val 加到 A[index] 上。然后，第 i 次查询的答案是 A 中偶数值的和。

（此处给定的 index = queries[i][1] 是从 0 开始的索引，每次查询都会永久修改数组 A。）

返回所有查询的答案。你的答案应当以数组 answer 给出，answer[i] 为第 i 次查询的答案。

 

示例：

输入：A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
输出：[8,6,2,4]
解释：
开始时，数组为 [1,2,3,4]。
将 1 加到 A[0] 上之后，数组为 [2,2,3,4]，偶数值之和为 2 + 2 + 4 = 8。
将 -3 加到 A[1] 上之后，数组为 [2,-1,3,4]，偶数值之和为 2 + 4 = 6。
将 -4 加到 A[0] 上之后，数组为 [-2,-1,3,4]，偶数值之和为 -2 + 4 = 2。
将 2 加到 A[3] 上之后，数组为 [-2,-1,3,6]，偶数值之和为 -2 + 6 = 4。

 

提示：

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. 1 <= queries.length <= 10000
  4. -10000 <= queries[i][0] <= 10000
  5. 0 <= queries[i][1] < A.length

Python

class Solution:
    def sumEvenAfterQueries(self, A: [int], queries: [[int]]) -> [int]:
        sum_start = 0
        for num in A:
            if num % 2 == 0:
                sum_start += num
        result = []
        for val, index in queries:
            if A[index] % 2 == 0:
                sum_start -= A[index]
            A[index] += val
            if A[index] % 2 == 0:
                sum_start += A[index]
            result.append(sum_start)
        return result

C++

class Solution {
  public:
    vector<int> sumEvenAfterQueries(vector<int> &A,
                                    vector<vector<int>> &queries) {
        int sum = 0;
        for (auto num : A) {
            if (num % 2 == 0)
                sum += num;
        }
        vector<int> v;
        for (auto q : queries) {
            int val = q[0], index = q[1];
            if (A[index] % 2 == 0)
                sum -= A[index];
            A[index] += val;
            if (A[index] % 2 == 0)
                sum += A[index];
            v.push_back(sum);
        }
        return v;
    }
};

989. 数组形式的整数加法

题目

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

 

示例 1：

输入：A = [1,2,0,0], K = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

解释 2：

输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：

输入：A = [2,1,5], K = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

示例 4：

输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
输出：[1,0,0,0,0,0,0,0,0,0,0]
解释：9999999999 + 1 = 10000000000

 

提示：

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 9
  3. 0 <= K <= 10000
  4. 如果 A.length > 1，那么 A[0] != 0

Python

class Solution:
    def addToArrayForm(self, A: [int], K: int) -> [int]:
        return list(str(int("".join([str(num) for num in A])) + K))

C++

class Solution {
  public:
    vector<int> addToArrayForm(vector<int> &A, int K) {
        int carry = 0;
        for (int i = A.size() - 1; i >= 0; i--) {
            A[i] += K % 10 + carry;
            carry = 0;
            if (A[i] >= 10) {
                A[i] %= 10;
                carry = 1;
            }
            K /= 10;
        }
        while (K > 0) {
            A.insert(A.begin(), K % 10 + carry);
            carry = 0;
            if (A[0] >= 10) {
                A[0] %= 10;
                carry = 1;
            }
            K /= 10;
        }
        if (carry == 1)
            A.insert(A.begin(), 1);
        return A;
    }
};

999. 车的可用捕获量

题目

在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。

车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。

返回车能够在一次移动中捕获到的卒的数量。
 

示例 1：

输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释：
在本例中，车能够捕获所有的卒。

示例 2：

输入：[[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：0
解释：
象阻止了车捕获任何卒。

示例 3：

输入：[[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
输出：3
解释： 
车可以捕获位置 b5，d6 和 f5 的卒。

 

提示：

  1. board.length == board[i].length == 8
  2. board[i][j] 可以是 'R'，'.'，'B' 或 'p'
  3. 只有一个格子上存在 board[i][j] == 'R'

Python

class Solution:
    def numRookCaptures(self, board: [[str]]) -> int:
        # 首先找到 白色车的位置
        for i, line in enumerate(board):
            for j, item in enumerate(line):
                if item == "R":
                    R_index = (i, j)
        # 定义 4 个方向向量
        direction = ((1, 0), (-1, 0), (0, 1), (0, -1))
        count = 0
        for direc in direction:
            index = R_index
            while True:
                index = index[0] + direc[0], index[1] + direc[1]
                # 判断越界
                if index[0] < 0 or index[0] > 7 or index[1] < 0 or index[1] > 7:
                    break
                if board[index[0]][index[1]] == "B":
                    break
                if board[index[0]][index[1]] == "p":
                    count += 1
                    break
        return count

C++

class Solution {
  public:
    int numRookCaptures(vector<vector<char>> &board) {
        int x, y, count = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R')
                    x = i, y = j;
            }
        }
        vector<vector<int>> direction{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (auto v : direction) {
            int x1 = x, y1 = y;
            while (true) {
                x1 += v[0], y1 += v[1];
                if (x1 < 0 || x1 > 7 || y1 < 0 || y1 > 7)
                    break;
                if (board[x1][y1] == 'B')
                    break;
                if (board[x1][y1] == 'p') {
                    count += 1;
                    break;
                }
            }
        }
        return count;
    }
};

1002. 查找常用字符

题目

给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

 

示例 1：

输入：["bella","label","roller"]
输出：["e","l","l"]

示例 2：

输入：["cool","lock","cook"]
输出：["c","o"]

 

提示：

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100
  3. A[i][j] 是小写字母

Python

class Solution:
    def commonChars(self, A: [str]) -> [str]:
        # 统计法
        counts = []
        for string in A:
            counts.append({})
            for char in string:
                if char in counts[-1]:
                    counts[-1][char] += 1
                else:
                    counts[-1][char] = 1
        result = []
        # 统计完了 遍历第一个字典
        for key in counts[0]:
            number = counts[0][key]
            is_add = True
            for dic in counts[0:]:
                if key not in dic:
                    is_add = False
                    break
                else:
                    if dic[key] < number:
                        number = dic[key]
            if is_add:
                for _ in range(number):
                    result.append(key)
        return result

C++

class Solution {
  public:
    vector<string> commonChars(vector<string> &A) {
        vector<map<string, int>> counts;
        for (string &str : A) {
            map<string, int> m;
            for (char &c : str) {
                string s{c};
                m[s] += 1;
            }
            counts.push_back(m);
        }
        vector<string> result;
        // 遍历第一个字典
        for (auto &key : counts[0]) {
            int number = key.second;
            bool is_add = true;
            for (int i = 1; i < counts.size(); i++) {
                auto &value = counts[i];
                if (value.find(key.first) == value.end()) {
                    is_add = false;
                    break;
                } else {
                    if (value[key.first] < number) {
                        number = value[key.first];
                    }
                }
            }
            if (is_add) {
                for (int j = 0; j < number; j++) {
                    result.push_back(key.first);
                }
            }
        }
        return result;
    }
};

总结

C++ 超时，应该用空间换时间，map 的效率比较低。

用 vector 去存取所有的字母，然后遍历，效率比用 map 存取单个更高。