Leetcode初级算法——数组

#pragma once
#include#include#includeusing std::vector;

class Solution {
public:
    
    vectorintersect(vector& nums1, vector& nums2) {
        
        /*by myself(排序，双指针)
        int len1 = nums1.size();
        int len2 = nums2.size(); 
        int index_1 = 0;                      //每个数组设置一个起始指针，指向数组第一个元素
        int index_2 = 0;
        vectorvec;

        std::sort(nums1.begin(), nums1.end());     //先将俩个数组进行排序
        std::sort(nums2.begin(), nums2.end());

        while (index_1 < len1 && index_2 < len2) { //其中一个指针遍历完所在数组时，查找结束 if (nums1[index_1] == nums2[index_2]) { //向后移动俩个指针的过程中，如果所指元素相同则说明找到满足条件元素，将其加入数组vec中，同时俩个指针同时向后移动一个位置 vec.push_back(nums1[index_1]); ++index_1; ++index_2; } else if (nums1[index_1] != nums2[index_2] && nums1[index_1] > nums2[index_2]) {     //如果所指元素不相同，则将所指元素值更小的指针向后移动
                ++index_2;
                }
                else{
                    ++index_1;
                }
        }

        return vec;
        */


        //哈希表
        std::vectorvec;
        std::unordered_map<int>u_map;
        /*
        if (nums1.size() > nums2.size()) {    //优化，将数组元素较小的数组记录在哈希表中
            return intersect(nums2, nums1);
        }
        */

                                      //对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
        for (int num : nums1) {       //首先遍历第一个数组，并在哈希表中记录第一个数组中每个数字以及其出现的次数
            ++u_map[num];
        }

        for (int num : nums2) {         //遍历第二个数组，查找哈希表找对应元素值，找到则说明该元素满足条件，将其加入到vec数组中，同时将对应哈希表中该元素的出现次数减1
            if (u_map.count(num)) {      //count是一个查找函数，找到返回1，没找到返回0
                vec.push_back(num);
                --u_map[num];

                if (u_map[num] == 0) {   //如果该元素在哈希表中出现次数为0，则删除该元素
                    u_map.erase(num);
                }
            }
        }

        return vec;
    }
};</int>

加一

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

#pragma once
#include#includeusing std::vector;

class Solution {
public:
    vectortwoSum(vector& nums, int target) {

        std::unordered_map<int>hash_table;   
        int len = nums.size();

        for (int i = 0; i < len; ++i) { //遍历整个数组元素 int t = target - nums[i]; //t表示与nums[i]对应满足条件的那个值 std::unordered_map<int>::iterator itr = hash_table.find(nums[i]);    //查找在hash_table中是否存对应键t与该元素值sums[i]相同
            if (itr == hash_table.end()) {
                hash_table[t] = i;                //itr == hash_table.end()表示没找到，则将t和对应下标i插入hash_table中
            }
            else {
                return { itr->second,i };         //否则说明在hash_table中找到对应键t==sums[i],找到满足条件的两个元素(t+sums[i]=target),返回俩个元素的下标
            }
        }
       
        return {};
    }
};
</int></int>

有效的数独

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'

#pragma once
#include#include#includeusing std::vector;

class Solution {
public:
    bool isValidSudoku(vector& board) {

        /*by myself(暴力解法)
        for (int i = 0; i < 9; ++i) { std::unordered_setset;              //为每一行创建一个哈希表，接下来遍历每一行
            for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') { //首先跳过非数字 continue; } if (set.count(board[i][j]) == 0) { //如果该数字不在哈希表中则插入该数字，否则表示该行出现重复数字，所以返回false set.insert(board[i][j]); } else { return false; } } } for (int i = 0; i < 9; ++i) { std::unordered_setset;              //为每一列创建一个哈希表，接下来遍历每一列
            for (int j = 0; j < 9; ++j) { if (board[j][i] == '.') { //首先跳过非数字 continue; } if (set.count(board[j][i]) == 0) { //如果该数字不在哈希表中则插入该数字，否则表示该行出现重复数字，所以返回false set.insert(board[j][i]); } else { return false; } } } for (int i = 0; i < 9; i+=3) { for (int j = 0; j < 9; j+=3) { //按每三行三列为一个单元格进行遍历 std::unordered_setset;                  //为每一个单元格创建一个哈希表，接下来遍历每一个单元格
                for (int n = i; n < i + 3; ++n) { for (int m = j; m < j + 3; ++m) { if (board[n][m] == '.') { //首先跳过非数组 continue; } if (set.count(board[n][m]) == 0) { //如果该数字不在哈希表中则插入该数字，否则表示该单元格出现重复数字，所以返回false set.insert(board[n][m]); } else { return false; } } } } } return true; */ /*by myself(稍加优化，依旧暴力) for (int i = 0; i < 9; ++i) { std::unordered_setset_h;            //为每一行创建一个哈希表，接下来遍历每一行
            std::unordered_setset_l;            //为每一列创建一个哈希表，接下来遍历每一列

            for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') { //首先跳过非数字 continue; } if (set_h.count(board[i][j]) == 0) { //如果该数字不在哈希表中则插入该数字，否则表示该行出现重复数字，所以返回false set_h.insert(board[i][j]); } else { return false; } } for (int j = 0; j < 9; ++j) { if (board[j][i] == '.') { //首先跳过非数字 continue; } if (set_l.count(board[j][i]) == 0) { //如果该数字不在哈希表中则插入该数字，否则表示该行出现重复数字，所以返回false set_l.insert(board[j][i]); } else { return false; } } if ((i + 3) % 3 == 0) { //三列三列的检验单元格(竖着) for (int h = 0; h < 9; h += 3) { //每三列有九行，分成三个单元格 std::unordered_setset_d;                  //为每一个单元格创建一个哈希表，接下来遍历每一个单元格

                    for (int H = h; H < h + 3; ++H) { //按每三行三列为一个单元格进行遍历 for (int L = i; L < i + 3; ++L) { if (board[H][L] == '.') { //首先跳过非数组 continue; } if (set_d.count(board[H][L]) == 0) { //如果该数字不在哈希表中则插入该数字，否则表示该单元格出现重复数字，所以返回false set_d.insert(boa `rd[H][L]); } else { return false; } } } } } } return true; */ //数组法(用数组代替哈希表建立三个查找表) int row[9][10] = { 0 }; //为9行的每一行定义一个数组，下标1-9用来标记该行的数字是否出现过（下标为0不用），数组初始化为0，每当该行数字出现时，将对应下标位置元素置1(下标值=数字值) int column[9][10] = { 0 }; //为9列的每一列定义一个数组，下标1-9用来标记该列的数字是否出现过（下标为0不用），数组初始化为0，每当该列数字出现时，将对应下标位置元素置1(下标值=数字值) int block[9][10] = { 0 }; //为9块的每一块定义一个数组，下标1-9用来标记该块的数字是否出现过（下标为0不用），数组初始化为0，每当该块数字出现时，将对应下标位置元素置1(下标值=数字值) for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { //遍历整个board if (board[i][j] == '.') { //首先跳过非数字 continue; } int cur_number = board[i][j] - '0'; //得到该元素对应数值cur_number（从char到int），且将作为对应行列块中的下标 if (row[i][cur_number]) { //如果查找表row中的 第i行第cur_number列 对应值不为0，表示 第i行 中出现过值为cur_number的元素(所以重复出现)。则返回false return false; } if (column[j][cur_number]) { //如果查找表column中的 第j行第cur_number列 对应值不为0，表示 第j列 中出现过值为cur_number的元素。则返回false return false; } if (block[i / 3 * 3 + j / 3][cur_number]) { //如果查找表block中的 第i/3*3+j/3行 第cur_number列 对应值不为0，表示 第i/3*3+j/3块 中出现过值为cur_number的元素。则返回false return false; } row[i][cur_number] = 1; //经过上面三个条件判断可知，在对应 行列块 中之前都没有出现过，现在出现，所以将查找表中相应位置置1 column[j][cur_number] = 1; block[i / 3 * 3 + j / 3][cur_number] = 1; } } return true; } };

旋转图像

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

#pragma once
#includeusing std::vector;

class Solution {
public:

    
    void rotate(vector& matrix) {

        /*by myself(暴力解法)
        std::vectorvec;          //定义一个数组大小为n*n(n为块长度)
        for (auto i = matrix.begin(); i != matrix.end(); ++i) {   //先把块按从上到小、从左到右装入数组
            for (auto j = (*i).begin(); j != (*i).end(); ++j) {
                vec.push_back(*j);
            }
        }
        
        int n = 0;
        for (int i = matrix.size() - 1; i >= 0; --i) {      //再把数组中的元素从头到尾部，对应块按从右到左、从上到下的顺序填入
            for (int j = 0; j < matrix[i].size(); ++j) { matrix[j][i] = vec[n++]; } } */ /* 俩次折叠(分析规律法) int n = matrix.size(); for (int i = 0; i < n -1; ++i) { //先沿 右上-左下 的对角线翻转 for (int j = 0; j < n - 1 - i; ++j) { int t = matrix[i][j]; matrix[i][j] = matrix[n - 1 - j][n - 1 - i]; matrix[n - 1 - j][n - 1 - i] = t; } } for (int i = 0; i < n / 2; ++i) { //再沿 水平中线 上下翻转,最终得到顺时针90°的效果 for (int j = 0; j < n; ++j) { int t = matrix[i][j]; matrix[i][j] = matrix[n - 1 - i][j]; matrix[n - 1 - i][j] = t; } } */ //自外向内顺时针旋转 int n = matrix.size(); for (int i = 0; i < n / 2; ++i) { //设n为图像块的边长，则一共有从外向内 n/2层 需要旋转90°,i为层数起始为0，所以i<n for="">  </n>