首页 > 编程语言 > 详细

算法 day1

时间:2020-09-30 11:55:55      阅读:40      评论:0      收藏:0      [点我收藏+]

2020结束之前,再怎么忙也要写满30天吧。

 

【leetcode 】two sum1

hashmap

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hashmap;
        vector<int> res;
        vector<int>::iterator it;
        int index = 0;
        for(it = nums.begin();it != nums.end();it++)
        {
            if(hashmap.find(target - (*it))!=hashmap.end())
            {
                res.push_back(hashmap[target - (*it)]);
                res.push_back(index);
                return res;
            }
            hashmap[(*it)] = index;
            index++;
            printf("%d %d\n",(*it),hashmap[(*it)]);
        }
        return res;

    }
};

 

【leetcode】two sum2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* old = new ListNode(0);
        ListNode* head = old;

        while(l1!=NULL&&l2!=NULL)
        {
            int tmpres = carry + l1->val + l2->val;
            carry = tmpres/10;

            head->next =new  ListNode(tmpres%10);
            head = head->next;

            l1 = l1->next;
            l2 = l2->next;
        }

        while(l1!=NULL)
        {
            head->next = new ListNode((l1->val + carry)%10);
            head = head->next;
            carry = (l1->val + carry)/10;

            l1 = l1->next;
        }

        while(l2!=NULL)
        {
            head->next =new  ListNode((l2->val + carry)%10);
            head = head->next;
            carry = (l2->val + carry)/10;

            l2 = l2->next;
        }

        if(carry == 1)
        head->next =new  ListNode(1);

        return old->next;
    }
};

 

【leetcode】判定字符是否唯一

class Solution {
public:
    bool isUnique(string astr) {
        int a[257];
        memset(a,0,sizeof(a));

        int len = astr.length();
        for(int i=0;i<len;i++)
        {
            printf("%d\n",int(astr[i]));
            if(a[int(astr[i])] != 0)
                return false;
            a[int(astr[i])]++;
        }
        return true;
    }
};

 

【leetcode】学生出勤记录1

class Solution {
public:
    bool checkRecord(string s) {
        int len = s.length();
        int ccounta = 0;
        int prel = 0;

        for(int i=0;i<len;i++)
        {
            if(s[i] == A)
            {
                ccounta ++;
            }
            else if(s[i] == L)
            {
                prel++;
            }

            if(s[i]!=L)
            {
                prel = 0;
            }

            if(prel > 2 || ccounta > 1)
                return false;
            
        }

        return true;
    }
};

 

【leetcode】学生出勤记录2

 动态规划

class Solution {
public:
    int checkRecord(int n) {
        int mod = 1000000007;
        long long dp[n+1][2][3];
        memset(dp,0,sizeof(dp));
        dp[1][0][1] = 1; //L
        dp[1][1][0] = 1; //A
        dp[1][0][0] = 1; //p
        for(int i=2;i<=n;i++)
        {
            //无A 末尾没有L
            dp[i][0][0] = (dp[i-1][0][0]%mod + dp[i-1][0][1]%mod + dp[i-1][0][2]%mod)%mod;
            //无A 末尾有1个L
            dp[i][0][1] = dp[i-1][0][0]%mod;
            //无A 末尾有2个L
            dp[i][0][2] = dp[i-1][0][1]%mod;
            //有A 末尾没有L
            dp[i][1][0] = (dp[i-1][0][0]%mod + dp[i-1][0][1]%mod + dp[i-1][0][2] %mod
                            +dp[i-1][1][0]%mod + dp[i-1][1][1]%mod + dp[i-1][1][2]%mod)%mod;
            
            //有A 末尾1个L
            dp[i][1][1] = dp[i-1][1][0]%mod;

            //有A 末尾2个L
            dp[i][1][2] = dp[i-1][1][1]%mod;
        }
        long long res = (dp[n][0][0]%mod + dp[n][0][1]%mod + dp[n][0][2]%mod + 
                    dp[n][1][0]%mod + dp[n][1][1]%mod + dp[n][1][2]%mod)%mod;
        return (int)res;
    }
};

 

 

【PAT1078】字符串压缩与解压

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
    char c;
    c = getchar();
    getchar();

    if(c == C)
    {
        c = getchar();
        int ccount = 0;
        while(c!=\n)
        {
            char preletter;
            preletter = c;
            ccount = 0;
            while(preletter == c)
            {
                ccount++;
                c = getchar();
            }

            if(ccount>1)
            {
                printf("%d%c",ccount,preletter);
            }
            else
            {
                printf("%c",preletter);
            }

        }
    }
    else if(c==D)
    {
        c = getchar();
        while(c!=\n)
        {
            int num = 0;
            while(c>=0 && c<=9)
            {
                num*=10;
                num+=(c-0);
                c = getchar();
            }
            if(num == 0 || num == 1)
            {
                printf("%c",c);
            }
            else
            {
                for(int i=0;i<num;i++)
                    printf("%c",c);
            }
            c = getchar();
        }
    }

}

 

【PAT 1007】 素数对猜想

 

#include<stdio.h>
#include<iostream>
using namespace std;
int isp[100005];
int p[100005];
int ccount = 0;
void genp()
{
    for(int i=0;i<100005;i++)
    {
        isp[i] = 1;
    }

    for(int j=2;j<100005;j++)
        if(isp[j] == 1)
        {
            p[ccount++] = j;
            for(int i = j+j;i<=100005;i = i+j)
            {
                isp[i] = 0;
            }
        }

}
int main()
{
    genp();

    int n;
    scanf("%d",&n);

    int paircount = 0;
    for(int i=2;i<=n-2;i++)
    {
        if(isp[i] == 1 && isp[i+2] == 1)
            paircount++;
    }
    printf("%d\n",paircount);
}

 

算法 day1

原文:https://www.cnblogs.com/yoyoyayababy/p/13753463.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!