有序數(shù)組的平方
題目鏈接：有序數(shù)組的平方
思路：雙指針法产场，數(shù)組平方的最大值就在數(shù)組的兩端鹅髓，i指向起始位置，j指向終止位置京景，定義一個新數(shù)組result窿冯，和A數(shù)組一樣的大小，讓k指向result數(shù)組終止位置确徙。
class?Solution?{
public:
????vector<int>?sortedSquares(vector<int>&?A)?{
????????int?k?=?A.size()?-?1;
????????vector<int>?result(A.size(),0);
????????for(int?i?=?0,j?=?A.size()?-?1;?i?<=?j;){
????????????if(A[i]?*?A[i]?<?A[j]?*?A[j]){
????????????????result[k--]?=?A[j]?*?A[j];
????????????????j--;
????????????}
????????????else{
????????????????result[k--]?=?A[i]?*?A[i];
????????????????i++;
????????????}
????????}
????????return?result;
????}
};
209.長度最小的子數(shù)組
題目鏈接：長度最小的數(shù)組
思路：滑動窗口醒串，主要確定如下三點(diǎn)：
窗口內(nèi)是什么？如何移動窗口的起始位置鄙皇？如何移動窗口的結(jié)束位置芜赌？
窗口就是 滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組。
窗口的起始位置如何移動：如果當(dāng)前窗口的值大于s了伴逸，窗口就要向前移動了（也就是該縮小了）缠沈。
窗口的結(jié)束位置如何移動：窗口的結(jié)束位置就是遍歷數(shù)組的指針佳晶，也就是for循環(huán)里的索引择份。
解題的關(guān)鍵在于 窗口的起始位置如何移動候址。
class?Solution?{
public:
????int?minSubArrayLen(int?target,?vector<int>&?nums)?{
????????int?result?=?INT32_MAX;//設(shè)置窗口最大值
????????int?sum?=?0;?//窗口數(shù)值之和
????????int?i?=?0;//起始位置
????????int?subLength?=?0;//窗口長度
????????for(int?j?=?0;?j?<?nums.size();?j++){
????????????sum?+=?nums[j];
????????????while(sum?>=?target){
????????????????subLength?=?(j?-?i?+?1);
????????????????result?=?result?<?subLength???result?:?subLength;
????????????????sum?-=?nums[i++];//不斷變更子序列起始位置
????????????}
????????}
????????return?result?==??INT32_MAX???0?:?result;
????}
};
59.螺旋矩陣II
題目鏈接：螺旋矩陣Ⅱ
思路：模擬順時針畫矩陣的過程:
填充上行從左到右
填充右列從上到下
填充下行從右到左
填充左列從下到上
由外向內(nèi)一圈一圈這么畫下去偿渡。(注意是左閉右開）
class?Solution?{
public:
????vector<vector<int>>?generateMatrix(int?n)?{
????????vector<vector<int>>?res(n,?vector<int>(n,0));
????????int?startx?=?0,?starty?=?0;//每循環(huán)一個圈的起始位置
????????int?loop?=?n?/?2;//循環(huán)幾次圈
????????int?mid?=?n?/?2;//矩陣中間位置
????????int?count?=?1;//每個空格賦值
????????int?offset?=?1;//控制每一條邊遍歷長度，每次循環(huán)右邊界收縮一位
????????int?i,?j;
????????while(loop?--){
????????????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?+=?1;
????????}
????????if(n?%?2){
????????????res[mid][mid]?=?count;
????????}
????????return?res;
????}
};
總結(jié)：1械姻、對于排序斑响，數(shù)組的兩端最大枉侧，考慮用雙指針
2官紫、滑動窗口的精髓在于窗口起始位置在變化
3肛宋、螺旋矩陣應(yīng)考慮圈數(shù)、填元素的順序束世，以及考慮中間位置元素是否存在的問題
4悼吱、因?yàn)閿?shù)組的在內(nèi)存空間的地址是連續(xù)的，所以我們在刪除或者增添元素的時候良狈，就難免要移動其他元素的地址。要注意vector 和 array的區(qū)別笨枯，vector的底層實(shí)現(xiàn)是array薪丁，嚴(yán)格來講vector是容器遇西，不是數(shù)組。數(shù)組的元素是不能刪的严嗜，只能覆蓋粱檀。
