Array

Summary Ranges

vector<string> summaryRanges(vector<int>& nums) {
    vector<string> res;
    if (nums.empty()){
        return res;
    }

    int nLength = nums.size() ,tail = 0;//use head & tail
    for(int tail = 0; tail < nLength; ){
        int head = nums[tail];//head can be set to nums[i] directly
        while (tail + 1 != nLength && nums[tail + 1] == nums[tail] + 1) 
            tail += 1;

        if(nums[tail] > head)
            res.push_back(to_string(head) + "->" + to_string(nums[tail]));
        else
            res.push_back(to_string(head));

        tail ++;
    }
    return res;
}

Rotate Array

翻转算法：28ms

void rotate(int nums[], int n, int k) {
    k %= n;
    reverse (nums,nums+n-k);
    reverse (nums+n-k,nums+n);
    reverse (nums,nums+n);
}

块交换算法：24ms ，improve 14%

inline void swap(vector<int>& nums,int head1, int head2, int moves){
    int temp ;
    while (moves--){
        temp = nums[head1];
        nums[head1++] = nums[head2];
        nums[head2++] =temp;
    }
}
void rotate(vector<int>& nums, int k) {
    k %= nums.size();
    if (nums.size() < 2 || k == 0 )
        return ;
    //0--left~~k~~right--end,move part is dicided by min(left,right)
    //and the start of right need to be caculated
    //p for the rotate point, be the last one in left
    int left = nums.size() - k, right = k, p = left - 1;
    while(left != right){
        if (left < right){
            swap(nums,p-left+1, p+right - left+1, left);
            right -= left;
        }else{//left > right
            swap(nums,p-left+1, p+1, right);
            left -= right;
        }
    }
    //left == right
    swap(nums, p-left+1, p+1, left);
}

RemoveElements

不能使用swap（如果111112移除1）

int removeElement(vector<int>& nums, int val) {
    int m = 0, nNums = nums.size();
    for (int i = 0; i < nNums;i++){
        if(nums[i] != val)
            nums[m++] = nums[i];
    }
    return m;
}

RemoveDeplicatesFromSortedArray

32ms

int removeDuplicates(vector<int>& nums) {
    if (nums.size() < 2) return nums.size();
    //nums[m] records the begaining of duplicates
    int m = 1;
    for (int i = 1;i < nums.size();i++){
        if (nums[i] != nums[i-1])
            nums[m++] = nums[i];
    }
    return m;
}

PlusOne

vector<int> plusOne(vector<int>& digits) {
    for (auto r = digits.rbegin(); r != digits.rend(); r++){
        if(*r <9){
            *r += 1;
            return digits;
        }//esle
        *r = 0;
    }
    //this means digits is 9...99
    digits[0] = 1;
    digits.push_back(0);
    return digits;
}

Pascal'sTriangle： Ⅰ & Ⅱ

vector<vector<int>> generate(int numRows) {
    vector<vector<int> > res;
    for (int i = 0; i < numRows; i++){
        vector<int> oneLine{1};
        for (int j = 1; j < i; j++){//i>=2, numRows >=3
            oneLine.push_back(res[i-1][j-1] + res[i-1][j]);
        }
        if (i != 0)
            oneLine.push_back(1);
        res.push_back(oneLine);
    }
    return res;
}

vector<int> getRow(int rowIndex) {
    vector<int> res(rowIndex +1);
    res[0] = 1;

    for (int i = 1; i <= rowIndex; i++){
        int mid = i >>1;
        for (int j = mid; j >= 1; j--){
            //mid-(mid-j)=i-j
            res[i-j] = res[j]= res[j]+res[j-1];
        }
        res[i] = 1;//j>0
    }
    return res;
}

MoveZeroes

20ms

void moveZeroes(vector<int>& nums) {
    int nNums = nums.size();
    int index;
    for (int i = 0; i < nNums; i++){
        if(nums[i] != 0){
            swap(nums[index],nums[i]);
            index++;
        }
    }
}

MergeSortedArray

从nums1逆向merge。若m、n中有一个为0，对应数组已耗尽。若耗尽的是nums1，将nums2装到nums1中；若是nums1，则可略过

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    m--;n--;
    for (int i = m+n+1; i >= 0 ; i--){
        if (m >=0 && n >=0){
            if(nums1[m] > nums2[n])
                nums1[i] = nums1[m--];
            else
                nums1[i] = nums2[n--];
        }
        else if (n >= 0){//m<0
            while(n>=0) nums1[i--] = nums2[n--];
            return;
        }
        else 
            return;
    }
}

MajorityElement

将nNums替换nums.size()后，从20提升到了16ms。20%

int majorityElement(vector<int>& nums) {
    int major = nums[0],nNums = nums.size();
    short count = 1;
    for (int i = 1; i < nNums;i++){
        if (nums[i] == major)
            count++;
        else{
            if(count >1)
                count--;
            else//count == 1,and count-- == 0
                major = nums[i];
        }
    }
    return major;
}

ContainsDuplicate Ⅰ & Ⅱ

36ms。如果不用unordered_map，使用int[]，可以达到20ms，但是要数组长度无法设置。另外一种低效但简单地方法是set之后比较长度是否有缩短。

inline void hashSet(unordered_map<int,int>& map, int i ){ 
    map[i>>5] |= 1<<(i&0x1f);
}
inline bool isInHash(unordered_map<int,int>& map, int i){
    return map[i>>5] & (1<<(i&0x1f));
}
bool containsDuplicate(vector<int>& nums) {
    auto nNums = nums.size();
    unordered_map<int,int> map;
    for(int i = 0; i < nNums; i++){
        if(!isInHash(map,nums[i])){
            hashSet(map,nums[i]);
        }
        else
            return true;
    }
    return false;
}

尝试过使用queue，失败；int[]，超时

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    int nNums = nums.size();
    unordered_set<int> pipe;

    for(int i = 0;i < nNums; i++){
        if (i > k) pipe.erase(nums[i-k-1]);
        if (!pipe.insert(nums[i]).second)
            return true;//find
    }
    return false;
}

WordSearch

public:
bool exist(vector<vector<char>>& board, string word) {
    if(board.size() == 0) return false;

    I = board.size(), J = board[0].size();
    for (int i = 0; i < I; i++){
        for (int j = 0; j < J; j++){
            if (isValid(board,word,i,j,0)) return true;
        }
    }
    return false;
}
private:
int I,J;
bool isValid(vector<vector<char>>& board, string &word,int i, int j,int matchLen){
    if (word.size() == matchLen)
        return true;
    if (i < 0 || j < 0 || i == I || j == J)
        return false;
    if (board[i][j] != word[matchLen++])
        return false;
    //matche a letter,forward    
    board[i][j] ^= 0xff;//no letter's ASCII would begin with 1
    bool isvalid = isValid(board,word,i-1,j,matchLen) 
                    ||isValid(board,word,i+1,j,matchLen)
                    ||isValid(board,word,i,j-1,matchLen)
                    ||isValid(board,word,i,j+1,matchLen);
    board[i][j] ^= 0xff;//recover
    return isvalid;
}

UniquePaths Ⅰ & Ⅱ

int uniquePaths(int m, int n) {    
    int dp[n+1] {0};    dp[1] = 1;
    for (int i = 1; i <= m; i++)//i starts at 1
        for (int j = 1; j <= n; j++)
            dp[j] += dp[j-1];//[i,j] = [i-1,j]+[i,j-1]
    return dp[n];
}

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if (obstacleGrid.empty()) return 0;
    //dp 添加了1个辅助行和列，元素比obstacle的下标有偏移1
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    int dp[n+1] {0};    dp[1] = !obstacleGrid[0][0];
    for (int i = 0; i < m; i++)//i,j是obstacle的下标，不是dp的
        for (int j = 0; j < n; j++){
            if (obstacleGrid[i][j])
                dp[j+1] = 0;
            else dp[j+1] += dp[j];
        }
    return dp[n];
}

TwoSum

vector<int> twoSum(vector<int>& nums, int target) {
    auto sortNums = nums;
    int nNums = nums.size();
    sort(sortNums.begin(),sortNums.end());

    //这里不用for循环二分搜索，采用两段相向查询
    int left = 0, right = nums.size()-1;
    while (true){//一定有答案，所以略去判断
        int sum = sortNums[left] + sortNums[right];
        if (sum == target) break;
        if (sum < target) left++;
        else right--; 
    }

    for (int i = 0; i < nNums; i++){
        if (nums[i] == sortNums[left]){
            left = i;
            break;
        }
    }//逆向搜索，以免nums有重复值
    for (int i = nNums-1; i >=0; i--){
        if (nums[i] == sortNums[right]){
            right =i;
            break;
        }
    }

    //left >right 时，swap(left,right)
    if (left > right) { left^= right; right^= left;  left^= right;}
    return vector<int> {left+1,right+1};
}

Triangle

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<int> dp(triangle[n-1]);

    for (int i = n-2; i >= 0; i--){
        for (int j = 0; j <= i; j++)
            dp[j] = triangle[i][j] + min(dp[j],dp[j+1]) ;
    }
    return dp[0];
}

Subsets Ⅰ &Ⅱ

外循环为nums时更简洁。外循环为逐条子集的时候，似乎会更快，但是OJ的时间没有变化，故略去。8ms

vector<vector<int>> subsets(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    int nNums = nums.size();
    int nRes = (1<<nNums);
    vector<vector<int> > res(nRes);

    int tempI ;
    for (int i = 0; i < nNums; i++){
        for (int j = 0;j <nRes; j++){
            if ((j>>i)&1)
                res[j].push_back(nums[i]);
        }
    }
    return res;
}

Ⅱ不能使用Ⅰ中的办法。12ms

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    int nNums = nums.size();
    vector<vector<int>> subsets{{}};//不能省略，见nSub
    vector<int> oneSub;


    for (int i = 0;i < nNums; ){
        int count = 1;
        while (i+count < nNums && nums[i+count] == nums[i] )
            count ++;
        int nSub = subsets.size();
        for (int j = 0; j < nSub; j++){
            oneSub = subsets[j];
            for (int k = 0; k < count; k++){
                oneSub.push_back(nums[i]);
                subsets.push_back(oneSub);
            }
        }
        i += count;
    }
    return subsets;
}

SpiralMatrix Ⅰ & Ⅱ

CleanCode 第35题

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (!matrix.size() || !matrix[0].size()) return result;
    int nrow = matrix.size(), ncol = matrix[0].size();

    int row = 0,col = -1;//每一个循环假定从左方驶入
    while (true){
        int i ;
        for (i = 0; i < ncol; i++)
            result.push_back(matrix[row][++col]);
        if (--nrow == 0) break;

        for (i = 0; i < nrow; i++)
            result.push_back(matrix[++row][col]);
        if (--ncol == 0) break;

        for (i = 0; i < ncol; i++)
            result.push_back(matrix[row][--col]);
        if (--nrow == 0) break;

        for (i = 0; i < nrow; i++)
            result.push_back(matrix[--row][col]);
        if (--ncol == 0) break;
    }
}

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int> > result(n,vector<int>(n));
    if (n == 0) return result;
    int row = 0, col = -1;
    int walker = 1;

    while (true){
        for (int i = 0; i < n; i++)
            result[row][++col] = walker++;
        if (--n == 0) break;
        for (int i = 0; i< n; i ++)
            result[++row][col] = walker++;

        for (int i = 0; i < n; i++)
            result[row][--col] = walker++;
        if (--n == 0) break;
        for (int i = 0; i < n; i++)
            result[--row][col] = walker++;
    }
    return result;
}

SortColors

注意，异或的swap不能作用于相同的数

void sortColors(vector<int>& nums) {
    int left = 0, right = nums.size()-1;

    for (int i = 0; i <= right; ){
        switch (nums[i]){
            case 0: {// if(nums[i] == 0) {//swap
                swap(nums[i++],nums[left++]);
                break;
            }
            case 2:{//else if ( nums[i] == 2)
                swap(nums[i],nums[right--]);//右边没检查过，不能i++跳过
                break;
            }
            default: i++;
        }
    }
}

SetMatrixZeroes

第二个for循环想调优一下，然并卵

    if (!matrix.size() ||!matrix[0].size()) return ;
    int nrow = matrix.size(), ncol = matrix[0].size();
    bool setColOne = false;//第一列是否置0要排除来自行的干扰

    for (int i = 0; i < nrow; i++){
        if (!setColOne && !matrix[i][0]) setColOne = true;
        for (int j = 1; j < ncol;j++){
            if (!matrix[i][j]){
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    //逆序，因为信息在首行/列
    for (int i = nrow-1; i >=0 ; i--){
        bool tempRow0 = matrix[i][0] == 0;//for speed up
        for (int j = ncol - 1; j >=1 ;j--){
            if (tempRow0 || !matrix[0][j])//!matrix[i][0]
                matrix[i][j] = 0;
        }
        if (setColOne) matrix[i][0] = 0;
    }
}

SearchInsertPosition

最简单是用lower_bound。自己写一个二分搜索也一样。都是8ms

int searchInsert(vector<int>& nums, int target) {
    return lower_bound(nums.begin(),nums.end(),target)- nums.begin();
}

int searchInsert(vector<int>& nums, int target) {
    int nNums = nums.size();
    if (!nNums) return 0;
    if (nums[nNums-1] < target) return nNums;

    int left = 0, right = nNums -1;
    while (left < right){
        int middle = left+right>>1;//(left>>1)+(right-left>>1) 
        if (nums[middle] < target)
            left = middle+1;
        else 
            right = middle;
    }
    //if target > nums[nNums-1], it has already been returned
    return right;
}

SearchForARange

不想写二分搜索，直接用std

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> result{-1,-1};
    if (nums.size() && binary_search(nums.begin(),nums.end(),target)) {
        result[0] = lower_bound(nums.begin(),nums.end(),target) - nums.begin();
        result[1] = upper_bound(nums.begin(),nums.end(),target) - nums.begin()-1;

    }
    return result;
}