Cプログラミング問題まとめ

43990 ワード

最大サブシーケンスと:
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
例:
入力:[−2,1,−3,4,−1,2,1,−5,4],出力:6解釈:連続サブ配列[4,−1,2,1]の和が最大で6であった.

int maxSubArray(int* nums, int numsSize){

int i = 0;
int sum=nums[0];
int summax = nums[0];
for(i = 1; i < numsSize;i++)
{
   if((nums[i]>sum)&&(sum<0)) {
       sum = nums[i];
   }
    else{
        sum+=nums[i];
    }
   // printf("sum=%d,nums[i]=%d
",sum,nums[i]);
    if(summax < sum){
        summax=sum;
    }
}

return summax;
}

レポートのシーケンス:
は整数のシーケンスで、その中の整数の順序でカウントして、次の数を得ます.最初の5つは次のとおりです.
1. 12. 113. 214. 12115.1112211は、「one 1」(「1つ1」)、すなわち11と読まれる.11は「two 1 s」(「2つ1つ」)、すなわち21.21は「one 2」、「one 1」(「1つ2つ」、「1つ1つ」)、すなわち1211と読まれる.
正の整数n(1≦n≦30)が与えられ、カウントシーケンスのn番目の項が出力される.
注:整数の順序は文字列として表示されます.
例1:
入力:1出力:1の例2:
入力:4出力:「1211」

#define Len 4500
char * countAndSay(int n){
    char *pre, *num;
    int i=1;
    int len=0;
    int m=0;
    char flag;
    int index=0;
    pre = (char *)malloc(sizeof(char) * Len);//       
    num = (char *)malloc(sizeof(char) * Len);//         
    if(n==1)
        return "1";
    else
    {
        num=countAndSay(n-1);//        
        len=strlen(num);//          
        flag=num[0];//          
        m=1;//         
        while(i//    
        {
            if(num[i]==flag)//             
                m+=1;//    
            else//              
            {
                pre[index++]=m+'0';//               
                pre[index++]=flag;
                m=1;//    
                flag=num[i];//           
            }
            i+=1;
       }
       pre[index++]=m+'0';//               
       pre[index++]=flag;
       pre[index]='\0';
       return pre;
    }
}

挿入位置の検索:
ソート配列とターゲット値を指定し、配列内にターゲット値を見つけ、インデックスを返します.ターゲット値が配列に存在しない場合は、順番に挿入される位置を返します.
配列に重複要素がないと仮定できます.
例1:
入力:[1,3,5,6],5出力:2例2:
入力:[1,3,5,6]、2出力:1

int searchInsert(int* nums, int numsSize, int target){
　　　int left=0;

　　 int right=numsSize-1;
    int mid;
    while(left<=right){//   
        mid=left+((right-left)>>1);
        if(nums[mid]==target) return mid;
        else if(nums[mid]>target) right=mid-1;//  +-1
        else if(nums[mid]1;
    }
    if(targetreturn mid;//  target  mid  
    else return mid+1;
}

strStr()関数の実装:
haystack文字列とneedle文字列を指定し、haystack文字列にneedle文字列が現れる最初の位置(0から)を見つけます.存在しない場合は、-1を返します.
例1:
入力:haystack=「hello」、needle=「ll」出力:2例2:
入力:haystack=「aaaa」、needle=「bba」出力:-1

int strStr(char * haystack, char * needle){
    int a=strlen(haystack);
    int b=strlen(needle);
    char *p=NULL;//       
    if(b==0) return 0;//     a,b       0   
    p=haystack;
    for(int i=0;i<=a-b;++i){//  a-b
        if(haystack[i]==needle[0]){
            if(!strncmp(p,needle,b)) return i;//  strcmp        ，       
        }
        ++p;
    }
    return -1;
}

2つの合計:
与えられたnums=[2,7,11,15],target=9
nums[0]+nums[1]=2+7=9なので[0,1]を返します

int* twoSum(int* nums, int numsSize, int target, int* returnSize){//  ：    ，      ，   ，      
    int* res=(int*)malloc(sizeof(int)*2);
    *returnSize=0;
    int i,j;
    for(i=0;i1;i++)
    {
        for(j=i+1;j
        {
            if(nums[i]+nums[j]==target)
            {
                res[0]=i;
                res[1]=j;
                *returnSize=2;
                return res;
            }
        }
    }
    return res;
}

重複する要素が存在します.
入力:[1,2,3,1]出力:true
入力:[1,2,3,4]出力:false

void swap(int *a, int *b)//        
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
void quickSort(int arr[] ,int start, int end)//        
{
    int arrBase, arrMiddle;

    int tempStart = start,
        tempEnd = end;

    //         ，               
    if(tempStart >= tempEnd)
        return;

    //                
    arrBase = arr[start];
    while(start < end)
    {
        while(start < end && arr[end] > arrBase)
            end--;
        if(start < end)
        {
            swap(&arr[start], &arr[end]);
            start++;
        }

        while(start < end && arr[start] < arrBase)
            start++;
        if(start < end)
        {
            swap(&arr[start], &arr[end]);
            end--;
        }
    }
    arr[start] = arrBase;
    arrMiddle = start;

    //        
    quickSort(arr,tempStart,arrMiddle-1);
    quickSort(arr,arrMiddle+1,tempEnd);
}
int comp(const void *a,const void *b){//        
    return (*(int*)a > *(int*)b);
}
bool containsDuplicate(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), comp);//       ，     
    for(int k=0;k1;k++){//  ，       ，   true。
        if(nums[k]==nums[k+1]){
            return true;
        }
    }
    return false;
}

2つの合計:
入力:(2->4->3)+(5->6->4)
出力:7->0->8
理由:342+465=807

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//    
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
    //     
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next =NULL;
    struct ListNode* tail;
    tail = head;
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;

    int carry = 0; //  
　　 if(p1==NULL) return p2;
　　 if(p2==NULL) return p1;

    //  ，        
    //                ，        ，          
    while (p1 != NULL && p2 != NULL)
    {
        //      ，      
        int sum = p1->val + p2->val + carry;
        //         10 
        if (sum >= 10)
        {
            sum -= 10;   //      -10，    
            carry = 1;     //  10，  1
        }
        else
        {
            carry = 0;
        }

        //     ,   ,                    ，        ，           (                     ，          )
        tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        tail = tail->next;
        tail->val = sum;
        

        p1 = p1->next;
        p2 = p2->next;
    }

    //          ，     NULL ，      ，    p1          ，    
    if (p1 == NULL)
    {
        p1 = p2;
    }
    else if (p2 = NULL)
    {
        p1 = p1;
    }

    //      
    while (p1 != NULL)
    {
        int sum = p1->val + carry; //           

        if (sum >= 10)
        {
            sum -= 10;
            carry = 1;
        }
        else
        {
            carry = 0;
        }
        //             
        tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        tail = tail->next;
        tail->val = sum;
        

        p1 = p1->next;

    }

    //          ，        1
    if (carry == 1)
    {
        tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        tail = tail->next;
        tail->val = 1;
        
    }
    
    tail->next = NULL; //     ，  

    //           ，          ，             
    struct ListNode* pTemp = head;
    head = head->next;
    free(pTemp);

    return head;
}

整数の反転:

  : 123
  : 321

  : -123
  : -321

  : 120
  : 21

int reverse(int x)
{
    int temp;
    int i;
    long c=0;//   long 
    for(i=0;i<10;++i){
        temp=x%10;//            
        x=x/10;
        c=c*10+temp;
        if(c>0x7fffffff||cint)0x80000000){//          
            return 0;
        }
        if(x==0) break;
    }
    return c;
}

ローマ数回転数:
文字値I 1 V 5 X 10 L 50 C 100 D 500 M 1000
特殊なルールは、次の6つの場合にのみ適用されます.
IはV(5)とX(10)の左側に置いて4と9を表すことができる.XはL(50)とC(100)の左側に置いて40と90を表すことができる.CはD(500)とM(1000)の左側に置いて400と900を表すことができる.

int romanToInt(char * s){
    int len=strlen(s);
    if(len==0) return 0;
    int num=0;
    for(int i=0;ii){
        switch(s[i]){//       
            case 'M':num+=1000;break;
            case 'D':num+=500;break;
            case 'C':num+=100;if(i1) if(s[i+1]=='D'||s[i+1]=='M') num-=200;break;//    ，    ，   if           
            case 'L':num+=50;break;
            case 'X':num+=10;if(i1) if(s[i+1]=='L'||s[i+1]=='C') num-=20;break;
            case 'V':num+=5;break;
            case 'I':num+=1;if(i1) if(s[i+1]=='V'||s[i+1]=='X') num-=2;break;
        }
    }
    return num;
}

文字列配列内の最長共通接頭辞の検索
共通の接頭辞が存在しない場合は、空の文字列「」を返します.
例1:
入力:[[flower]、[flow]、[flight]出力:[fl]例2:
入力:[「dog」、「racecar」、「car」出力:「」解釈:入力に共通接頭辞は存在しません.説明:
すべての入力には小文字a-zのみが含まれます.

char * longestCommonPrefix(char ** strs, int strsSize){
    if(strsSize==0){
        char *a=(char *)malloc(1);
        a[0]='\0';
        return a;
    }
    if(strsSize==1){
        return strs[0];
    }
　　//          
    int is = 1 , temp ;
    int i=0;
    for(;is;++i){
        temp = strs[0][i];
        for(int j=0;jj){
            if((!strs[j][i])||strs[j][i]!=temp){
                is = 0;
                break;
            }
        }
    }
    strs[0][i-1]='\0';
    return strs[0];
}

有効なかっこ:
注意空の文字列は有効な文字列とみなされます.
例1:
入力:「()」出力:true例2:
入力:「()[]{}」出力:true例3:
入力:「(」出力:false例4:
入力:「([)]出力:false例5:
入力:{[]}出力:true

bool isValid(char * s){
    if ( s == NULL || s[0] == '\0' ) return true;//      
    char *aus = (char *) malloc (strlen(s) + 1);
    int top = 0;
    for(int i=0;ii){
        if(s[i]=='('||s[i]=='{'||s[i]=='[') aus[top++]=s[i];//      
        else{
            if(--top<0) return false;//      
            if(s[i]==')'&&aus[top]!='(') return false;
            if(s[i]==']'&&aus[top]!='[') return false;
            if(s[i]=='}'&&aus[top]!='{') return false;
        }
    }
    return !top;//   0，     ，      ，     0。
}

回文数判断:
正の順序(左から右へ)と逆の順序(右から左へ)が同じ整数であることを意味します.
例1:
入力:121出力:true例2:
入力:-121出力:false解釈:左から右へ-121です.右から左に読むと121-.したがって、回文数ではありません.例3:
入力:10出力:false解釈:右から左へ、01です.したがって、回文数ではありません.

bool isPalindrome(int x){
    if(x<0) return false;
    if(x==0) return true;
    int a;
    long b=0,y=x;//   long 
    while(y>=1){
        a=y%10;
        y=y/10;
        b=b*10+a;
    }
    if(x==b) return true;
    return false;
}

2つの順序付きチェーンテーブルを結合するには、次の手順に従います.
2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.
例:
入力:1->2->4、1->3->4出力:1->1->2->3->4->4

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//    
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL) return l2;
    if(l2==NULL) return l1;//          
    struct ListNode* l;
    struct ListNode* j;
    if(l1->valval){
        l=l1;
        l1=l1->next;
    }
    else{
        l=l2;
        l2=l2->next;
    }//        
    j=l;
    while(l1&&l2){
        if(l1->valval){
            j->next=l1;//              
            l1=l1->next;
        }
        else{
            j->next=l2;
            l2=l2->next;
        }
        j=j->next;//      
    }
    if(l1){//     
        j->next=l1;
    }
    if(l2){
        j->next=l2;
    }
    return l;
}

並べ替え配列の重複を削除するには、次の手順に従います.
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例1:
与えられた配列nums=[1,1,2],
関数は新しい長さ2を返し、元の配列numsの最初の2つの要素は1,2に変更されます.
配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.

int removeDuplicates(int* nums, int numsSize){
    if(numsSize==0||numsSize==1) return numsSize;
    int len=0;
    for(int i=0;i1;++i){
        if(nums[i]!=nums[i+1]){//        
            nums[len++]=nums[i];
        }
    }
    nums[len++]=nums[numsSize-1];
    return len;
}

要素を除去するには
配列numsと値valを指定すると、valに等しいすべての数値の要素をその場で除去し、除去後の配列の新しい長さを返す必要があります.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
要素の順序は変更できます.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
例1:
与えられたnums=[3,2,2,3],val=3,
関数は新しい長さ2を返し、numsの最初の2つの要素は2です.
配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.

int removeElement(int* nums, int numsSize, int val){
    if(numsSize==0) return numsSize;//      
    int *left=nums;//       
    int *right=nums+numsSize-1;
    while(left<right){
        while(*left!=val&&left;//       val   
        while(*right==val&&left;//        val   
        *left=*right;//         
        right--;//     
    } 
    return left-nums+(*left!=val);//    
}

51 nod 1154(プッシュ)

IEでHTML5のvideoタグの動画が見られないときはURLACTION_ALLOW_AUDIO_VIDEOの値を確認