題目：有序數(shù)組的平方

• 給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序。

題解

• 數(shù)組其實(shí)是有序的， 只不過負(fù)數(shù)平方之后可能成為最大數(shù)了。那么數(shù)組平方的最大值就在數(shù)組的兩端，不是最左邊就是最右邊，不可能是中間?？梢允褂脙蓚€(gè)指針分別指向位置 0 和 n?1，每次比較兩個(gè)指針對(duì)應(yīng)的數(shù)，選擇較大的那個(gè)逆序放入答案并移動(dòng)指針。時(shí)間復(fù)雜度：O(n)，其中 n 是數(shù)組 nums 的長(zhǎng)度?？臻g復(fù)雜度：O(1)。除了存儲(chǔ)答案的數(shù)組以外，我們只需要維護(hù)常量空間。

• 如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

• class Solution {
  public:
      vector<int> sortedSquares(vector<int>& nums) {
          int left=0,right=nums.size()-1;
          int ptr_index = nums.size()-1;
          vector<int> res(ptr_index+1);
          while(left<=right){
              if(nums[left]*nums[left] < nums[right]*nums[right]){
                  res[ptr_index] = nums[right]*nums[right];
                  --right;
              }else{
                  res[ptr_index] = nums[left]*nums[left];
                  ++left;
              }
              --ptr_index;
          }
          return res;
      }
  };
  

• 此時(shí)的時(shí)間復(fù)雜度為O(n)，相對(duì)于暴力排序的解法O(n + nlog n)還是提升不少的。

題目：長(zhǎng)度最小的子數(shù)組

• 給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。找出該數(shù)組中滿足其和 ≥ target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長(zhǎng)度。如果不存在符合條件的子數(shù)組，返回 0 。

題解

• 這道題目暴力解法當(dāng)然是 兩個(gè)for循環(huán)，然后不斷的尋找符合條件的子序列，時(shí)間復(fù)雜度很明顯是 $O(n^2)$。接下來就開始介紹數(shù)組操作中另一個(gè)重要的方法：滑動(dòng)窗口。代碼隨想錄 (programmercarl.com)

• 所謂滑動(dòng)窗口，就是不斷的調(diào)節(jié)子序列的起始位置和終止位置，從而得出我們要想的結(jié)果。在暴力解法中，是一個(gè)for循環(huán)滑動(dòng)窗口的起始位置，一個(gè)for循環(huán)為滑動(dòng)窗口的終止位置，用兩個(gè)for循環(huán) 完成了一個(gè)不斷搜索區(qū)間的過程。 那么滑動(dòng)窗口如何用一個(gè)for循環(huán)來完成這個(gè)操作呢？如果只用一個(gè)for循環(huán)來表示 滑動(dòng)窗口的起始位置，那么如何遍歷剩下的終止位置？

• 只用一個(gè)for循環(huán)，那么這個(gè)循環(huán)的索引，一定是表示 滑動(dòng)窗口的終止位置。

  • 

• 在本題中實(shí)現(xiàn)滑動(dòng)窗口，主要確定如下三點(diǎn)：

  • 窗口內(nèi)是什么？（窗口就是 滿足其和 ≥ s 的長(zhǎng)度最小的 連續(xù) 子數(shù)組）

  • 如何移動(dòng)窗口的起始位置？(如果當(dāng)前窗口的值大于s了，窗口就要向前移動(dòng)了)

  • 如何移動(dòng)窗口的結(jié)束位置？(窗口的結(jié)束位置就是遍歷數(shù)組的指針，也就是for循環(huán)里的索引)

• 可以發(fā)現(xiàn)滑動(dòng)窗口的精妙之處在于根據(jù)當(dāng)前子序列和大小的情況，不斷調(diào)節(jié)子序列的起始位置。從而將 $O(n^2)$ 暴力解法降為O(n)。

• 不要以為for里放一個(gè)while就以為是 $O(n^2)$ 啊， 主要是看每一個(gè)元素被操作的次數(shù)，每個(gè)元素在滑動(dòng)窗后進(jìn)來操作一次，出去操作一次，每個(gè)元素都是被操作兩次，所以時(shí)間復(fù)雜度是 2 × n 也就是O(n)。

• class Solution {
  public:
      int minSubArrayLen(int target, vector<int>& nums) {
          int len_nums = nums.size();
          int sum = 0;
          int start_index = 0,sub_len=len_nums+3;
          for(int i = 0;i<len_nums;i++){
              sum += nums[i];
              while(sum>=target){
                  sub_len = min(sub_len,i-start_index+1);
                  sum -= nums[start_index];
                  start_index++;
              }
          }
          return sub_len>len_nums?0:sub_len;
      }
  };
  

題目：螺旋矩陣 II

• 給你一個(gè)正整數(shù) n ，生成一個(gè)包含 1 到 n2 所有元素，且元素按順時(shí)針順序螺旋排列的 n x n 正方形矩陣 matrix 。

題解

• 本題并不涉及到什么算法，就是模擬過程，但卻十分考察對(duì)代碼的掌控能力。模擬矩陣的生成。按照要求，初始位置設(shè)為矩陣的左上角，初始方向設(shè)為向右。若下一步的位置超出矩陣邊界，或者是之前訪問過的位置，則順時(shí)針旋轉(zhuǎn)，進(jìn)入下一個(gè)方向。如此反復(fù)直至填入 $n^2$ 個(gè)元素。求解本題要堅(jiān)持循環(huán)不變量原則。模擬順時(shí)針畫矩陣的過程:

  • 填充上行從左到右

  • 填充右列從上到下

  • 填充下行從右到左

  • 填充左列從下到上

• 由外向內(nèi)一圈一圈這么畫下去。這里一圈下來，我們要畫每四條邊，這四條邊怎么畫，每畫一條邊都要堅(jiān)持一致的左閉右開，或者左開右閉的原則，這樣這一圈才能按照統(tǒng)一的規(guī)則畫下來。

• class Solution {
  public:
      vector<vector<int>> generateMatrix(int n) {
          vector<vector<int>> res(n,vector<int>(n,0));
          int startx=0,starty=0;
          int cirle = n/2;
          int offset=1;
          int count=1;
          int i,j;
          while(cirle--){
              i=startx;
              j=starty;
              for(j=starty;j<n-offset;j++){
                  res[startx][j] = count++;
              }
              for(i=startx;i<n-offset;i++){
                  res[i][j]=count++;
              }
              for(;j>starty;j--){
                  res[i][j]=count++;
              }
              for(;i>startx;i--){
                  res[i][j]=count++;
              }
              startx++;
              starty++;
              offset++;
          }
          if(n%2){
              res[startx][starty]=count++;
          }
          return res;
      }
  };
  

C++ STL 四種智能指針

• C++ 標(biāo)準(zhǔn)模板庫 STL（Standard Template Library） 一共給我們提供了四種智能指針：auto_ptr、unique_ptr、shared_ptr 和 weak_ptr，其中 auto_ptr 是 C++98 提出的，C++11 已將其摒棄，并提出了 unique_ptr 替代 auto_ptr。雖然 auto_ptr 已被摒棄，但在實(shí)際項(xiàng)目中仍可使用，但建議使用更加安全的 unique_ptr。shared_ptr 和 weak_ptr 則是 C++11 從準(zhǔn)標(biāo)準(zhǔn)庫 Boost 中引入的兩種智能指針。此外，Boost 庫還提出了 boost::scoped_ptr、boost::scoped_array、boost::intrusive_ptr 等智能指針，雖然尚未得到 C++ 標(biāo)準(zhǔn)采納，但是在開發(fā)實(shí)踐中可以使用C++ STL 四種智能指針_c++智能指針_戀喵大鯉魚的博客-CSDN博客。

• C++ 智能指針底層是采用引用計(jì)數(shù)的方式實(shí)現(xiàn)的。智能指針在申請(qǐng)堆內(nèi)存空間的同時(shí)，會(huì)為其配備一個(gè)整形值（初始值為 1），每當(dāng)有新對(duì)象使用此堆內(nèi)存時(shí)，該整形值 +1；反之，每當(dāng)使用此堆內(nèi)存的對(duì)象被釋放時(shí)，該整形值減 1。當(dāng)堆空間對(duì)應(yīng)的整形值為 0 時(shí)，即表明不再有對(duì)象使用它，該堆空間就會(huì)被釋放掉。

• 每種智能指針都是以類模板的方式實(shí)現(xiàn)的，shared_ptr 也不例外。shared_ptr（其中 T 表示指針指向的具體數(shù)據(jù)類型）的定義位于<memory>頭文件，并位于 std 命名空間中，因此在使用該類型指針時(shí)，程序中應(yīng)包含如下 2 行代碼：

  • #include <memory>
    using namespace std;
    

unique_ptr

• 作為智能指針的一種，unique_ptr 指針自然也具備“在適當(dāng)時(shí)機(jī)自動(dòng)釋放堆內(nèi)存空間”的能力。和 shared_ptr 指針最大的不同之處在于，unique_ptr 指針指向的堆內(nèi)存無法同其它 unique_ptr 共享，也就是說，每個(gè) unique_ptr 指針都獨(dú)自擁有對(duì)其所指堆內(nèi)存空間的所有權(quán)。

• 這也就意味著，每個(gè) unique_ptr 指針指向的堆內(nèi)存空間的引用計(jì)數(shù)，都只能為 1，一旦該 unique_ptr 指針放棄對(duì)所指堆內(nèi)存空間的所有權(quán)，則該空間會(huì)被立即釋放回收。

• 創(chuàng)建空的 unique_ptr 指針

  • std::unique_ptr<int> p1();
    std::unique_ptr<int> p2(nullptr);
    

• 構(gòu)建 unique_ptr 智能指針并初始化確定數(shù)據(jù)

  • std::unique_ptr<int> p3(new int);
    

• 基于 unique_ptr 類型指針不共享各自擁有的堆內(nèi)存，因此 C++11 標(biāo)準(zhǔn)中的 unique_ptr 模板類沒有提供拷貝構(gòu)造函數(shù)，只提供了移動(dòng)構(gòu)造函數(shù)。例如：

  • std::unique_ptr<int> p4(new int);
    std::unique_ptr<int> p5(p4);//錯(cuò)誤，堆內(nèi)存不共享
    std::unique_ptr<int> p5(std::move(p4));//正確，調(diào)用移動(dòng)構(gòu)造 函 數(shù) 
    //值得一提的是，對(duì)于調(diào)用移動(dòng)構(gòu)造函數(shù)的 p4 和 p5 來說，
    //p5 將獲取 p4 所指堆空間的所有權(quán)，而 p4 將變成空指針（nullptr）。
    

• 默認(rèn)情況下，unique_ptr 指針采用 std::default_delete 方法釋放堆內(nèi)存。也可自定義釋放規(guī)則。和 shared_ptr 指針不同， unique_ptr 自定義釋放規(guī)則只能采用函數(shù)對(duì)象的方式。

shared_ptr

• 值得一提的是，和 unique_ptr、weak_ptr 不同之處在于，多個(gè) shared_ptr 智能指針可以共同使用同一塊堆內(nèi)存。并且，由于該類型智能指針在實(shí)現(xiàn)上采用的是引用計(jì)數(shù)機(jī)制，即便有一個(gè) shared_ptr 指針放棄了堆內(nèi)存的“使用權(quán)”（引用計(jì)數(shù)減 1），也不會(huì)影響其他指向同一堆內(nèi)存的 shared_ptr 指針（只有引用計(jì)數(shù)為 0 時(shí)，堆內(nèi)存才會(huì)被自動(dòng)釋放）。

• 構(gòu)造 shared_ptr 類型的空智能指針

  • std::shared_ptr<int> p1; //不傳入任何實(shí)
    std::shared_ptr<int> p2(nullptr); //傳入空指針 nullptr
    

• 構(gòu)建 shared_ptr 智能指針并初始化確定數(shù)據(jù)

  • std::shared_ptr<int> p3(new int(10));
    std::shared_ptr<int> p3 = std::make_shared<int>(10);
    //調(diào)用拷貝構(gòu)造函數(shù)
    std::shared_ptr<int> p4(p3);//或者 std::shared_ptr<int> p4 = p3;
     //調(diào)用移動(dòng)構(gòu)造函數(shù)
    std::shared_ptr<int> p5(std::move(p4)); //或者 
     std::shared_ptr<int> p5 = std::move(p4);
    

• 如上所示，p3 和 p4 都是 shared_ptr 類型的智能指針，因此可以用 p3 來初始化 p4，由于 p3 是左值，因此會(huì)調(diào)用拷貝構(gòu)造函數(shù)。需要注意的是，如果 p3 為空智能指針，則 p4 也為空智能指針，其引用計(jì)數(shù)初始值為 0；反之，則表明 p4 和 p3 指向同一塊堆內(nèi)存，同時(shí)該堆空間的引用計(jì)數(shù)會(huì)加 1。而對(duì)于 std::move(p4) 來說，該函數(shù)會(huì)強(qiáng)制將 p4 轉(zhuǎn)換成對(duì)應(yīng)的右值，因此初始化 p5 調(diào)用的是移動(dòng)構(gòu)造函數(shù)。另外和調(diào)用拷貝構(gòu)造函數(shù)不同，用 std::move(p4) 初始化 p5，會(huì)使得 p5 擁有了 p4 的堆內(nèi)存，而 p4 則變成了空智能指針。

• 注意：一普通指針不能同時(shí)為多個(gè) shared_ptr 對(duì)象賦值，否則會(huì)導(dǎo)致程序發(fā)生異常。例如：

  • int* ptr = new int;
    std::shared_ptr<int> p1(ptr);
    std::shared_ptr<int> p2(ptr);//錯(cuò)誤
    

• 初始化 shared_ptr 智能指針時(shí)，可自定義堆內(nèi)存的釋放規(guī)則，當(dāng)堆內(nèi)存的引用計(jì)數(shù)為 0 時(shí)，會(huì)優(yōu)先調(diào)用自定義的釋放規(guī)則。

  • //指定 default_delete 作為釋放規(guī)則
    std::shared_ptr<int> p6(new int[10], std::default_delete<int[]>());
    //自定義釋放規(guī)則
    void deleteInt(int*p) {
     delete []p;
    }
    //初始化智能指針，并自定義釋放規(guī)則
    std::shared_ptr<int> p7(new int[10], deleteInt);
    

weak_ptr

• C++11標(biāo)準(zhǔn)雖然將 weak_ptr 定位為智能指針的一種，但該類型指針通常不單獨(dú)使用（沒有實(shí)際用處），只能和 shared_ptr 類型指針搭配使用。甚至于，我們可以將 weak_ptr 類型指針視為 shared_ptr 指針的一種輔助工具，借助 weak_ptr 類型指針， 我們可以獲取 shared_ptr 指針的一些狀態(tài)信息，比如有多少指向相同的 shared_ptr 指針、shared_ptr 指針指向的堆內(nèi)存是否已經(jīng)被釋放等等。

• 需要注意的是，當(dāng) weak_ptr 類型指針的指向和某一 shared_ptr 指針相同時(shí)，weak_ptr 指針并不會(huì)使所指堆內(nèi)存的引用計(jì)數(shù)加 1；同樣，當(dāng) weak_ptr 指針被釋放時(shí)，之前所指堆內(nèi)存的引用計(jì)數(shù)也不會(huì)因此而減 1。也就是說，weak_ptr 類型指針并不會(huì)影響所指堆內(nèi)存空間的引用計(jì)數(shù)。

std::unique_ptr：內(nèi)存的所有者或者說管理者必須是唯一的。如果進(jìn)入不同的模塊或者調(diào)用者，那么執(zhí)行所有權(quán)轉(zhuǎn)移。

std::shared_ptr: 內(nèi)存由多個(gè)指針變量共同使用，共同擁有內(nèi)存的所有權(quán)。但是必須杜絕循環(huán)拷貝！

std::weak_ptr: 對(duì)內(nèi)存的使用僅僅是訪問而已，不涉及其生命周期的管理。
1。也就是說，weak_ptr 類型指針并不會(huì)影響所指堆內(nèi)存空間的引用計(jì)數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-670415.html

到了這里，關(guān)于【C++代碼】有序數(shù)組的平方，長(zhǎng)度最小的子數(shù)組，螺旋矩陣 II--代碼隨想錄的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！