2020.10

2020.10.16

题目：剑指 Offer 58 - II. 左旋转字符串
难度：E
用时：10分钟

剑指 Offer 58 - II. 左旋转字符串

# C

char* reverseLeftWords(char* s, int n){
    //异常检查
    if(*s == '\0'|| n<= 0) return NULL;
    //统计字符个数
    int size = 0;
    char* t = s;
    while(*t != '\0')
    {
        size ++;
        t++;
    }
    //移动：新建操作
    char* rt = (char*)malloc((size+1)*sizeof(char));
    rt[size] = '\0';
    for(int i = 0; i< size;i++)
    {
        if(i < n)
        {
            rt[size-n+i] = s[i];
        }
        else
        {
            rt[i-n] = s[i];
        }
    }
    return rt;
    
}

时间：58%
内存：5%

char* reverseLeftWords(char* s, int n){
    int len = strlen(s),i = 0;;
    char *ans = malloc(sizeof(char) * (len + 1));
    while(i < len){
        *(ans++) = s[(n + i++)%len];
    }
    *ans= '\0';
    return ans - len;
}

时间：58%
内存：5%

作者：ning-junzhi
链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/solution/cjian-dan-yi-dong-de-jie-fa-by-ning-junzhi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2020.10.15

开始使用c刷题

题目：1480. 一维数组的动态和
难度：E
用时：10分钟

1480. 一维数组的动态和

# C

int* runningSum(int* nums, int numsSize, int* returnSize){
    if (nums == NULL || numsSize <= 0) {
        *returnSize = 0;
        return NULL;
    }

    int *sum = (int *)malloc(numsSize * sizeof(int));

    int k = 0;
    for (int i = 0; i < numsSize; ++i) {
        k += nums[i];
        sum[i] = k;
    }

    *returnSize = numsSize;
    return sum;

}

特别容易越界，leetcode对于指针越界管得严格

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* runningSum(int* nums, int numsSize, int* returnSize){
    int k = 0;
    int* cur = nums;
    int * rt = (int*)malloc(numsSize*sizeof(int));
    int * r=rt;
    *returnSize = numsSize;
    int size = numsSize-1;
    while (size--) {
        k += *cur;
        *r = k;

        r++;
        cur++;
    }
    k += *cur;
    *r = k;
    
    return rt;

}

2020.09

2020.09.18

题目：剑指 Offer 05. 替换空格
用时：20分钟
状态：不错

剑指 Offer 05. 替换空格

# C++

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int old_size = s.size();
        //统计有几个空格
        for (int i = 0; i < old_size; i++)
        {
            if (s[i] == ' ')    count++;
        }
        int new_size = old_size + count * 2;
        s.resize(new_size);
        //附加的空间在原string s的后面
        for (int i = old_size - 1,  j = new_size - 1; j > i; i--, j-- )
        {
            if(s[i] != ' ')
                s[j] = s[i];        
            else
            {
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j-=2;
            }

        }
        return s;

    }
};

时间：100%
内存：46%

class Solution {
public:
    
};

2020.09.17

题目：剑指 Offer 03. 数组中重复的数字
用时：8分钟
状态：不错

剑指 Offer 03. 数组中重复的数字

C++的知识忘了，不如复习一下：C++复习贴

# C++

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int size = nums.size();
        sort(nums.begin(), nums.end()); // 对nums进行升序排序
        for(int i=0; i<size; ++i)
        {
            // 排好序之后找重复元素就很容易了
            if(nums[i] == nums[i+1]) return nums[i]; 
        }
        return -1;
    }
};

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        bool flags[n];
        memset(flags, false, sizeof(flags));
        for( int i = 0; i < n; i++ )
        {
            if(flags[nums[i]]==true)
            {
                return nums[i];
            }
            else
            {
                flags[nums[i]] = true;
            }
        }
        return -1;
    }
};

时间：92%
内存：60%

就是遍历nums数组，把nums数组里的每个数为索引的flags数组（初始全都是0）里面的值改为1，若发现已经被改了，那就是重复了，返回。

在这个过程中需要建立一个大小为n的flags数组，内存消耗在此

题目：剑指 Offer 04. 二维数组中的查找
用时：20分钟
状态：不错

剑指 Offer 04. 二维数组中的查找

# C++

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {
                if (matrix[i][j] == target)
                    return true;
                if (matrix[i][j] > target)
                    break;
            }
        }
        return false;

    }
}; 


class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()||matrix[0].empty()) return false;
        int i = 0;
        int j = matrix[0].size()-1;
        while(i < matrix.size() && j >= 0)
        {
            if(target == matrix[i][j])  return true;
            else if (target < matrix[i][j])  j--;
            else i++;
        }
        return false;
    }
};

2020.09.16

题目：226. 翻转二叉树
用时：8分钟
状态：不错

226. 翻转二叉树

从今天起刷题使用C++

# C++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return nullptr;
        TreeNode* temp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = temp;
        return root;
    }
};

2020.09.15

题目：6. Z 字形变换
用时：1小时
状态：及格

6. Z 字形变换

# python3

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        strep = ''
        index = 0
        if (numRows == 1): return s
        else:
            for i in range(0, numRows):
                index = 0
                while index < len(s):
                    rf = index % (2*numRows - 2)
                    maxindex = numRows-1
                    if rf == i and ((rf // maxindex)%2)==0 :
                        strep += s[index]
                    elif (maxindex-(rf % maxindex)) == i and ((rf // maxindex)%2)==1:
                        strep += s[index]
                    index+=1
            return strep

最后修改：2020 年 11 月 11 日 08 : 06 PM
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏