Vector OJ 题

红太狼 2023-06-10 07:28 10阅读 0赞

1.只出现一次的数字

class Solution { 
    public:
     int singleNumber(vector<int>& nums) { 
      int value = 0;
      for (size_t i = 0; i <nums.size(); i++)
       value ^= nums[i];
      return value;
     }
    };

2.杨辉三角

//杨辉三角
    // 涉及resize / operator[] 
    class Solution { 
    public:
     // 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j] 
     vector<vector<int>> generate(int numRows) { 
      vector<vector<int>> vv;
      // 先开辟杨辉三角的空间 
      vv.resize(numRows);
      for (size_t i = 1; i <= numRows; ++i)
      { 
       vv[i - 1].resize(i, 0);
       // 每一行的第一个和最后一个都是1 
       vv[i - 1][0] = 1;
       vv[i - 1][i - 1] = 1;
      }
      for (size_t i = 0; i < vv.size(); ++i)
      { 
       for (size_t j = 0; j < vv[i].size(); ++j)
       { 
        if (vv[i][j] == 0)
        { 
         vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
        }
       }
      }
      return vv;
     }
    };

3.电话号码的字母组合

stringletterMap[10] = {  "", "", "abc", "def","ghi", \
    "jkl", "mno", "pqrs","tuv", "wxyz" };
    class Solution
    { 
    public:
         //思路：总计深度为digits.size()层的递归，
         //每层递归在字符串中一个字符进行组合
         void combineStr(const string& digits,size_t index, \
         const string& str, vector<string>& strs)
         { 
             if (index == digits.size())
             { 
                  strs.push_back(str);
                  return;
             }
             //获取数字对应的字符数组
             string letters =letterMap[digits[index] - '0'];
             for (size_t i = 0; i<letters.size();++i)
             { 
                  //获取当前按键的每个字符与下一个按键的字符进行组合
                  combineStr(digits, index + 1, str+ letters[i], strs);
             }
         }
         vector<string>letterCombinations(string digits) { 
             vector<string> strs;
             if (digits.empty())
                  return strs;
             size_t index = 0;
             //建立索引
             string str;
             //当前按键中存放的字符串
             //递归子问题组合字符串
             combineStr(digits, index, str, strs);
             return strs;
         }
    };

4.删除排序数组中的重复项

//双指针法
    class Solution { 
    public:
        int removeDuplicates(vector<int>& nums) { 
            int len =  nums.size();
            if (len <= 1) 
                return len;
            
            int k = 0;
            for (int i = 1; i < len; ++i) { 
                if (nums[k] != nums[i]) { 
                    nums[++k] = nums[i];
                }
            }
            return k + 1;
        }
    };

**总结**：通过上面的练习我们发现vector常用的接口更多的是插入和遍历，遍历更喜欢用数组operator\[ \]的形式访问，因为这样便捷。