头像

Baymax0211




离线:3小时前


活动打卡代码 LeetCode 9. 回文数

bool isPalindrome(int x){

    int m[100] = {};
    int i = 0;
    int j = 0;
    if(x<0)
        {return false;}

    while(x){
        m[i] = x%10;
        x = x/10;
        i += 1;
    }
    while(j!=i/2){
        if(m[j]!=m[i-1-j])
            return false;
        j += 1;
    }
    return true;
}




int myAtoi(char* str) {
    long ret = 0;
    int flag = 1;//默认正数
    //去除空格及判断符号位
    for (; *str == 32; str++);
    switch (*str) {
    case 45:
        flag = -1;
    case 43:
        str++;
    }
    //排除非数字的情况
    if (*str < 48 || *str>57) return 0;

    while (*str >= 48 && *str <= 57) {
        ret = ret * 10 + (*str - 48);
        //判断溢出
        if ((int)ret != ret) {
            return (flag == 1) ? (INT_MAX) : (INT_MIN);
        }
        str++;
    }
    ret *= flag;
    return (int)ret;
}



活动打卡代码 LeetCode 7. 整数反转

int reverse(int x){
    long res = 0;
    while (x != 0) {
        res = res * 10 + x % 10;
        x = x / 10;
    }
    if (res > INT_MAX || res < INT_MIN) {
        res = 0;
    }
    return res;
}


活动打卡代码 LeetCode 6. Z 字形变换

char* convert(char* s, int numRows)
{
    int num=strlen(s),count = -1;char* ret= (char*)malloc((1+num)*sizeof(s[1]));
    if(numRows==1 || numRows>num)  return s;
    for (int cir = 0; cir < numRows; cir++)
    {
        int fir, sec; sec = 2 * cir; fir = (2 * numRows - 2) - sec;
        ret[++count] = s[cir];
        for (int c = cir; c < num;)
        {
            c = c + fir;
            if (c < num && cir != (numRows - 1))    ret[++count] = s[c];
            c = c + sec;
            if (c < num && cir != 0)    ret[++count] = s[c];
        }
    }
    ret[num] = '\0';
    return ret;
}



活动打卡代码 LeetCode 5. 最长回文子串

void help(char *s, int N, int left, int right, int *start, int *len) {
    while (left >= 0 && right < N && s[left] == s[right])
        left--, right++;
    if (right - left - 1 > * len) {  // 如果找到更长的子串,保存其信息
        *start = left + 1;
        *len = right - left - 1;
    }
}
char * longestPalindrome(char * s){
    int N = strlen(s), start = 0, len = 0;  // N 字符串长度, start 子串起始位置, len 子串长度
    for (int i = 0; i < N; i++)     // 奇数长度的回文子串
        help(s, N, i-1, i+1, &start, &len);
    for (int i = 0; i < N; i++)     // 偶数长度的回文子串
        help(s, N, i, i+1, &start, &len);
    s[start + len] = '\0';          // 原地修改返回
    return s + start;
}


活动打卡代码 LeetCode 1. 两数之和

int lengthOfLongestSubstring(char * s){
    int i, j = 0, count = 0, max = 0, index[128] = {0}, start = 0;
    for(i=0;s[i]!='\0';i++)     
    {
        if(index[s[i]]>start)   //index用来储存出现重复字符时
        {                       //子串起始下标应移动到的地方
            count = i-start;
            if(count>max)
            {
                max = count;
            }
            start = index[s[i]];
        }
        index[s[i]] = i+1;
    }
    count = i-start;
    return count>max?count:max;
}
。


活动打卡代码 LeetCode 1. 两数之和

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i, ret[1] = j;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}



活动打卡代码 LeetCode 2. 两数相加

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
        struct ListNode *res = malloc(sizeof(struct ListNode)); 
        res->val = -1;
        res->next = NULL;//这里要特别注意
        struct ListNode *cur = res;
        int carry = 0;  //表示进位
        while (l1 || l2) 
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur->next = malloc(sizeof(struct ListNode));
            cur->next->val = sum % 10;
            cur->next->next = NULL;
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }

        if (carry) {
            cur->next = malloc(sizeof(struct ListNode));
            cur->next->val = 1;
            cur->next->next = NULL;
        }
        return res->next;   //返回真正的头结点

}



Baymax0211
2019-09-01 02:39
class UnionFind{
public:
    vector<int>father;
    UnionFind(int num){//num表示元素的个数
        for(int i = 0; i < num; i++){
            father.push_back(i);//箭头指向自己
        }
    }
    int Find(int n){
        //递归
        if(father[n] == n)
            return n;
        father[n] = Find(father[n]);//路径压缩版本
        return father[n];
    }
    bool Union(int a, int b){//返回a和b是否本身在一个集合里
        int fa = Find(a);
        int fb = Find(b);
        bool res = fa==fb;
        father[fb] = fa;
        return res;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        UnionFind UF(N+1);
        vector<int>res(2, 0);
        for(int i = 0; i < edges.size(); i++){
            int u = edges[i][0];
            int v = edges[i][1];
            if(UF.Union(u, v)){//冗余
                res[0] = u;
                res[1] = v;
            }
        }
        return res;
    }
};



活动打卡代码 AcWing 547. Friend Circles

Baymax0211
2019-09-01 02:37
class UnionFind{
public:
    vector<int>father;
    UnionFind(int num){//num表示元素的个数
        for(int i = 0; i < num; i++){
            father.push_back(i);//箭头指向自己
        }
    }
    int Find(int n){
        //递归
        if(father[n] == n)
            return n;
        father[n] = Find(father[n]);//路径压缩版本
        return father[n];
    }
    void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        father[fb] = fa;
    }
};
class Solution {
public:  
    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        UnionFind UF(N);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(M[i][j]){
                    UF.Union(i, j);//两个人是朋友则合并朋友圈
                }
            }
        }
        int res = 0;
        for(int i = 0; i < N; i++){
            if(UF.Find(i) == i)//计算朋友圈的个数
                res++;
        }
        return res;
    }
};