少年游

欲买桂花同载酒，终不似，少年游。

0%

LeetCode算法题

发表于 更新于 分类于
一天一道算法题，持之以恒！up! up! up!

Day9.Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

1
2
Example:
Given num = 16, return true. Given num = 5, return false.

Solution:O(n)

1
2
3
4
5
6
7
8
9
10
bool isPowerOfFour(int num) {
    if(!(num & (num-1))){
        double res = log(num) * 1.0/log(4);

        if(fabs(res - round(res)) < 0.0000001){
            return true;
        }
    }
    return false;
}

Day8.Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

1
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Solution:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
int integerBreak(int n) {
    if(n < 4)return n - 1;
    int res = 1;
    while(n > 2){
        res *= 3;
        n -= 3;
    }
    if(n == 0)return res;
    if(n == 1)return res / 3 * 4;
    if(n == 2)return res * 2;
    return res;
}

Day7.Reverse String

Write a function that takes a string as input and returns the string reversed.

1
2
Example:
Given s = "hello", return "olleh".

My solution:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
char* reverseString(char* s) {
    if(s == NULL)return NULL;
    int size = strlen(s);
    char* start,*end;
    start = s;
    end = s + size - 1;
    while(start < end){
        char temp = *start;
        *start = *end;
        *end = temp;
        start ++;
        end --;
    }
    return s;
}

Day6.Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

1
2
3
4
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".

My solution:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int isVowels(char c){
    //大写转小写
    if(c >= 'A' && c <= 'Z') {
        c += 32;
    }

    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
        return 1;
    }

    return 0;
}
char* reverseVowels(char* s) {
    if(s == NULL)return NULL;
    int len = strlen(s);
    char *pre,*end;
    pre = s;
    end = s + len - 1;
    while(pre < end){
        while(pre < end && !isVowels(*pre))pre ++;
        while(pre < end && !isVowels(*end))end --;
        if(isVowels(*pre) && isVowels(*end)) {
            char temp = *pre;
            *pre = *end;
            *end = temp;
        }
        pre++;
        end--;
    }
    return s;
}

Day5.Power of Three

Given an integer, write a function to determine if it is a power of three.
Follow up:
Could you do it without using any loop / recursion?

Solution:O(1)

1
2
3
4
5
6
7
8
9
10
//误差限制,另外本来应该用round，但是发现ceil所有测试实例都通过了，也就是所有情况res < ceil(res)
bool isPowerOfThree(int n) {
    double exp = 10e-15;
    if(n <=0)return false;
    double res = log(n)/log(3);

    if(fabs(res - ceil(res)) < exp)return true;

    return false;
}

Day4.Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

My Solution1:O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    //？这里有个想法，建两个个小根堆，大小为index - 1(n) ，index，直接夹出来那个一个或n个中间元素
    int size = nums1Size + nums2Size;
    double result;
    //全为空
    if(size == 0)return -1;

    //不全为空
    int flag = size % 2;
    int midIndex = (size - 1) / 2;

    //一个为空
    if(nums1Size == 0){
        if(flag == 1)result = *(nums2 + midIndex);
        else
            result = (*(nums2 + midIndex) + *(nums2 + midIndex +1))/2.0;
        return  result;
    }

    if(nums2Size == 0){
        if(flag == 1)result = *(nums1 + midIndex);
        else
            result = (*(nums1 + midIndex) + *(nums1 + midIndex +1))/2.0;
        return result;
    }
    //两个均不为空
    int i = 0,j = 0;
    while(i + j < midIndex){
        //防止数组越界
        if(i < nums1Size && *(nums1 + i) <= *(nums2 + j))i ++;
        else if(j < nums1Size && *(nums1 + i) > *(nums2 + j))j ++;
    }
    if(flag == 0){
            result = (*(nums1 + i) + *(nums2 + j))/2.0;
    }
    else result = *(nums1 + i) < *(nums2 + j)?*(nums1 + i):*(nums2 + j);
    return result;
}

My Solution2:O(n)

Day3.Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

1
2
3
4
5
Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

My Solution:O(N):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//
// Created by Paul on 2016/4/14.
//
#include "iostream"
#include "string.h"
/**
 * 最长不重复子串
 */
using namespace std;
int lengthOfLongestSubstring(char* s);

int main(){
    char* s;
    printf("请输入字符串\n");
    scanf("%s", s);
    int length = lengthOfLongestSubstring(s);
    printf("\n子串长度为 %d", length);

}

int lengthOfLongestSubstring(char* s) {
    //记录字符串位置
    int hashTable[256];
    int length = 0;
    int maxLength = 0;
    //初始化
    memset(hashTable, -1, sizeof(hashTable));

    char *slow, *fast;
    fast = slow = s;
    //缓存一次历史数据
    int history_fast = 0;
    int history_slow = 0;
    int i = 0;
    int flag = 0;
    while (*fast != '\0') {
        //大于或等于碰撞点进入数据更改，初始碰撞点为0
        if (hashTable[*fast] >= history_fast && hashTable[*fast] > -1) {
            flag = 1;
            //未更新的fast位置
            history_fast = hashTable[*fast];
            //未更新slow的位置
            history_slow = hashTable[*slow];
            slow = s + history_fast + 1;
        }
        //更新碰撞位置
        hashTable[*fast] = i++;

        if (flag == 1) {
            length = hashTable[*fast] - history_slow;
            flag = 0;
        }else{
            length = hashTable[*fast] - hashTable[*slow] + 1;
        }

        if (maxLength < length)maxLength = length;
        //O(n)的指针不回退
        fast++;
    }
    //打印出该字符串
    int x = maxLength;
    while(x -- > 0){
        printf("%c",*slow);
        slow ++;
    }
    return maxLength;
}

Day2.add-two-numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

My Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    //分配头结点内存
    struct ListNode* la;
    struct ListNode* p = (struct ListNode *)malloc(sizeof(struct ListNode));
    la = p;
    if(l1 == NULL){
        return l2;
    }
    if(l2 == NULL){
        return l1;
    }

    int carrier = 0;
    int sum;
    while(l1->next != NULL && l2->next != NULL){

        sum = l1->val + l2->val + carrier;

        carrier = sum / 10;
        sum = sum % 10;

        struct ListNode* node = (struct ListNode *)malloc(sizeof(struct ListNode));
        node->val = sum;
        node->next = NULL;
        p->next = node;
        p = node;

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

    }
    int flag = 0;
    //必定有一个到达链表末端
    //l2到达末端
    sum = l1->val + l2->val + carrier;
    while(l1->next != NULL){
        if(flag == 0)flag = 1;
        struct ListNode* node = (struct ListNode *)malloc(sizeof(struct ListNode));
        carrier = sum / 10;
        sum = sum % 10;
        node->val = sum;
        l1 = l1->next;
        p->next = node;
        p = node;
        sum = l1->val + carrier;
    }
    //l1 到达末端
    while(l2->next != NULL){
        if(flag == 0)flag = 2;
        struct ListNode* node = (struct ListNode *)malloc(sizeof(struct ListNode));
        carrier = sum / 10;
        sum = sum % 10;
        node->val = sum;
        l2 = l2->next;
        p->next = node;
        p = node;
        sum = l2->val + carrier;
    }

    struct ListNode* node = (struct ListNode *)malloc(sizeof(struct ListNode));
    if(flag == 0){
        sum = carrier + l1->val + l2->val;
    }
    if(flag == 1){
        sum = carrier + l1->val;
    }
    if(flag == 2){
        sum = carrier +l2->val;
    }
    carrier = sum / 10;
    sum = sum % 10;
    node->val = sum;
    node->next = NULL;
    p->next = node;
    p = node;

    if(carrier != 0){
        node = (struct ListNode *)malloc(sizeof(struct ListNode));
        node->val = carrier;
        node->next = NULL;
        p->next = node;
    }

    return la->next;
}

Day1.two-sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int result[2];
int* twoSum(int* nums, int numsSize, int target) {
    int* p = nums;

    if(numsSize < 2){
        return NULL;
    }
    int i,j;
    for(i = 0;i < numsSize;i ++){
        for(j = i + 1;j < numsSize;j ++){
            if(*(p + i) + *(p + j) == target){
                result[0] = i;
                result[1] = j;
                return q;
            }
        }
    }
    if(i == numsSize && j == numsSize){
        return NULL;
    }

}

如果数组有序,可以用二分法查找
Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int* twoSum(int* nums, int numsSize, int target);
int bSearch(int* nums,int numsSize,int target);

int main(){
    int nums[4] = {2,7,11,15};
    int* p = twoSum(nums,4,13);
    if(p != NULL){
        printf("%d %d",*p,*(p + 1));
    }else{
        printf("未找到");
    }

}
int result[2];
int* twoSum(int* nums, int numsSize, int target) {
    int* p = nums;
    if(numsSize < 2){
       return NULL;
    }

    for(int i = 0;i < numsSize;i ++){
        int bTarget = target - *(p + i);
        int* pS = p + i + 1;
        int bSize = numsSize - i - 1;
        int index;
        if(bSize > 0) {
            index = bSearch(pS, bSize, bTarget);
            if(index != -1 && *(p + i) + *(p + index + i + 1) == target){
                result[1] = index + i + 1;
                result[0] = i;
                return result;
            }
        }
    }

    return NULL;
}
int bSearch(int* nums,int numsSize,int target){
    int low = 0,high = numsSize - 1;
    int mid;
    if(target < *nums){
        return -1;
    }
    if(target > *(nums + numsSize - 1)){
        return -1;
    }
    while(low <= high) {
        mid = (low + high)/2;
        if (*(nums + mid) == target) {
            return mid;
        } else if (*(nums + mid) > target){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;
}