2022年5月 – Pancake's Personal Website

29. 两数相除

迭代。eg: 65 / 8 = (65 – 8) / 8 + 1 = (57 – 16) / 8 + 2 + 1 = (41 – 32) / 8 + 4 + 2 + 1 = 9 / 8 + 7 = (9 – 8) / 8 + 1 + 7 = 1 / 8 + 8 = 8

因为有 INT_MAX 和 INT_MIN 的干扰，还得排除一下特殊情况

c++

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == INT_MIN) {
            if (dividend == INT_MIN)return 1;
            else return 0;
        }
        int flag = 1, fix = 0;
        if (dividend == INT_MIN) {
            if (divisor == 1)return INT_MIN;
            else if (divisor == -1)return INT_MAX;
            dividend = INT_MAX;
            divisor = -divisor;
            fix = 1;
        }
        if (dividend > 0 && divisor < 0) { 
            divisor = -divisor; 
            flag = -1;
        }
        else if (dividend < 0 && divisor > 0) { 
            dividend = -dividend; 
            flag = -1;
        }
        else if (dividend < 0 && divisor < 0) {
            dividend = -dividend;
            divisor = -divisor;
        }
        if (divisor > dividend)return 0;
        int result = 1 + iteration(dividend - divisor + fix, 1, divisor, divisor);
        return result * flag;
    }

    int iteration(int divide, int result, int now, int base) {
        if (divide < base) return 0;
        else if (now > divide) return iteration(divide, 1, base, base);
        else if (now <= divide) return result + iteration(divide - now, result << 1, now << 1, base);
        return 0;
    }
};

class Solution {

public:

int divide(int dividend, int divisor) {

if (divisor == INT_MIN) {

if (dividend == INT_MIN)return 1;

else return 0;

}

int flag = 1, fix = 0;

if (dividend == INT_MIN) {

if (divisor == 1)return INT_MIN;

else if (divisor == -1)return INT_MAX;

dividend = INT_MAX;

divisor = -divisor;

fix = 1;

}

if (dividend > 0 && divisor < 0) {

divisor = -divisor;

flag = -1;

}

else if (dividend < 0 && divisor > 0) {

dividend = -dividend;

flag = -1;

}

else if (dividend < 0 && divisor < 0) {

dividend = -dividend;

divisor = -divisor;

}

if (divisor > dividend)return 0;

int result = 1 + iteration(dividend - divisor + fix, 1, divisor, divisor);

return result * flag;

}

int iteration(int divide, int result, int now, int base) {

if (divide < base) return 0;

else if (now > divide) return iteration(divide, 1, base, base);

else if (now <= divide) return result + iteration(divide - now, result << 1, now << 1, base);

return 0;

}

};

28. 实现 strStr()

无算法遍历。高级算法：Knuth-Morris-Pratt 算法，前后缀法

c++ 遍历

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n1 = haystack.size(), now = 0, n2 = needle.size();
        while (1) {
            if (now + n2 > n1) return -1;
            int i = 0, begin = now;
            for (; i < n2; i++) {
                if (needle[i] == haystack[now++]) continue;
                else break;
            }
            if (i == n2)return now - i;
            now = begin + 1;
        }
        return -1;
    }
};

class Solution {

public:

int strStr(string haystack, string needle) {

int n1 = haystack.size(), now = 0, n2 = needle.size();

while (1) {

if (now + n2 > n1) return -1;

int i = 0, begin = now;

for (; i < n2; i++) {

if (needle[i] == haystack[now++]) continue;

else break;

}

if (i == n2)return now - i;

now = begin + 1;

}

return -1;

}

};

26/27. 删除有序数组中的项

更简单，刚开始我以为要把整个vector都变掉，结果只需要变前几个，返回长度就行，运行时间差的就很多。

c++ 26方法一

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        for(auto ptr = nums.begin() + 1; ptr != nums.end();){
            if(*ptr == *(ptr - 1)) {
                ptr = nums.erase(ptr);
                continue;
            }
            ptr++;
        }
        return nums.size();
    }
};

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

for(auto ptr = nums.begin() + 1; ptr != nums.end();){

if(*ptr == *(ptr - 1)) {

ptr = nums.erase(ptr);

continue;

}

ptr++;

}

return nums.size();

}

};

c++ 26方法二

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int now = 0;
        for(auto ptr = nums.begin() + 1; ptr != nums.end(); ptr++){
            if(*ptr == *(ptr - 1)) continue;
            else nums[++now] = *ptr;
        }
        return now + 1;
    }
};

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

int now = 0;

for(auto ptr = nums.begin() + 1; ptr != nums.end(); ptr++){

if(*ptr == *(ptr - 1)) continue;

else nums[++now] = *ptr;

}

return now + 1;

}

};

c++ 27

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int now = 0;    
        for(auto ptr = nums.begin(); ptr != nums.end(); ptr++){
            if(*ptr == val) continue;
            else nums[now++] = *ptr;
        }
        return now;
    }
};

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int now = 0;

for(auto ptr = nums.begin(); ptr != nums.end(); ptr++){

if(*ptr == val) continue;

else nums[now++] = *ptr;

}

return now;

}

};

22. 括号生成

迭代

python

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        self.result = []
        self.interation("", n, n)
        return self.result

    def interation(self, word, left, right):
        if left == 0 and right == 0:
            self.result.append(word)
            return 0
        if left == right:
            self.interation(word + '(', left - 1, right)
        else:
            if left != 0:
                self.interation(word + '(', left - 1, right)
            if right != 0:
                self.interation(word + ')', left, right - 1)

class Solution:

def generateParenthesis(self, n: int) -> list[str]:

self.result = []

self.interation("", n, n)

return self.result

def interation(self, word, left, right):

if left == 0 and right == 0:

self.result.append(word)

return 0

if left == right:

self.interation(word + '(', left - 1, right)

else:

if left != 0:

self.interation(word + '(', left - 1, right)

if right != 0:

self.interation(word + ')', left, right - 1)

21/23/24/25. 合并/交换有序链表

指针交换操作

c++ 21

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* temp;
        if(list1 == nullptr && list2 == nullptr)return nullptr;
        else if(list1 == nullptr) return list2;
        else if(list2 == nullptr) return list1;
        if(list1->val > list2->val){
            temp = list1;
            list1 = list2;
            list2 = temp;
        }
        ListNode* pre;
        ListNode* result = list1;
        while(1){
            if(list1->val <= list2->val) {
                pre = list1;
                list1 = list1->next;
            }
            else if(list1->val > list2->val){
                temp = list2->next;
                pre->next = list2;
                pre = list2;
                list2->next = list1;
                list2 = temp;
            }
            if(list1 == nullptr){
                pre->next = list2;
                return result;
            }
            else if(list2 == nullptr){
                return result;
            }
        }
        return result;
    }
};

class Solution {

public:

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

ListNode* temp;

if(list1 == nullptr && list2 == nullptr)return nullptr;

else if(list1 == nullptr) return list2;

else if(list2 == nullptr) return list1;

if(list1->val > list2->val){

temp = list1;

list1 = list2;

list2 = temp;

}

ListNode* pre;

ListNode* result = list1;

while(1){

if(list1->val <= list2->val) {

pre = list1;

list1 = list1->next;

}

else if(list1->val > list2->val){

temp = list2->next;

pre->next = list2;

pre = list2;

list2->next = list1;

list2 = temp;

}

if(list1 == nullptr){

pre->next = list2;

return result;

}

else if(list2 == nullptr){

return result;

}

return result;

}

};

c++ 23

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* result = nullptr;
        if(lists.empty()) return result;
        else if(lists.size() == 1)return lists[0];
        result = mergeTwoLists(lists[0], lists[1]);
        for(int i = 2;i < lists.size();i++){
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* temp;
        if(list1 == nullptr && list2 == nullptr)return nullptr;
        else if(list1 == nullptr) return list2;
        else if(list2 == nullptr) return list1;
        if(list1->val > list2->val){
            temp = list1;
            list1 = list2;
            list2 = temp;
        }
        ListNode* pre;
        ListNode* result = list1;
        while(1){
            if(list1->val <= list2->val) {
                pre = list1;
                list1 = list1->next;
            }
            else if(list1->val > list2->val){
                temp = list2->next;
                pre->next = list2;
                pre = list2;
                list2->next = list1;
                list2 = temp;
            }
            if(list1 == nullptr){
                pre->next = list2;
                return result;
            }
            else if(list2 == nullptr){
                return result;
            }
        }
        return result;
    }
};

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

ListNode* result = nullptr;

if(lists.empty()) return result;

else if(lists.size() == 1)return lists[0];

result = mergeTwoLists(lists[0], lists[1]);

for(int i = 2;i < lists.size();i++){

result = mergeTwoLists(result, lists[i]);

}

return result;

}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

ListNode* temp;

if(list1 == nullptr && list2 == nullptr)return nullptr;

else if(list1 == nullptr) return list2;

else if(list2 == nullptr) return list1;

if(list1->val > list2->val){

temp = list1;

list1 = list2;

list2 = temp;

}

ListNode* pre;

ListNode* result = list1;

while(1){

if(list1->val <= list2->val) {

pre = list1;

list1 = list1->next;

}

else if(list1->val > list2->val){

temp = list2->next;

pre->next = list2;

pre = list2;

list2->next = list1;

list2 = temp;

}

if(list1 == nullptr){

pre->next = list2;

return result;

}

else if(list2 == nullptr){

return result;

}

return result;

}

};

c++ 24

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* result = new ListNode(0, head);
        if(head == nullptr) return nullptr;
        ListNode* pre = result;
        ListNode* temp;
        while(1){
            if(head == nullptr || head->next == nullptr) return result->next;
            pre->next = head->next;
            temp = head->next->next;
            head->next->next = head;
            head->next = temp;
            pre = head;
            head = temp;
        }
        return result->next;
    }
};

class Solution {

public:

ListNode* swapPairs(ListNode* head) {

ListNode* result = new ListNode(0, head);

if(head == nullptr) return nullptr;

ListNode* pre = result;

ListNode* temp;

while(1){

if(head == nullptr || head->next == nullptr) return result->next;

pre->next = head->next;

temp = head->next->next;

head->next->next = head;

head->next = temp;

pre = head;

head = temp;

}

return result->next;

}

};

c++ 25

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* result = new ListNode(0, head);
        if (head == nullptr) return nullptr;
        ListNode* pre = result;
        ListNode* last;
        ListNode* temp;
        while (1) {
            temp = head;
            last = head;
            for (int i = 1; i < k + 1; i++) {
                if (temp == nullptr) return result->next;
                temp = temp->next;
            }
            ListNode* now_pre = pre;
            for (int i = 0; i < k - 1; i++) {
                head = now_pre->next;
                pre = now_pre;
                for (int j = 0; j < k - i - 1; j++) {
                    pre->next = head->next;
                    pre = pre->next;
                    temp = head->next->next;
                    head->next->next = head;
                    head->next = temp;
                }
            }
            pre = last;
            head = last->next;
        }
        return result->next;
    }
};

class Solution {

public:

ListNode* reverseKGroup(ListNode* head, int k) {

ListNode* result = new ListNode(0, head);

if (head == nullptr) return nullptr;

ListNode* pre = result;

ListNode* last;

ListNode* temp;

while (1) {

temp = head;

last = head;

for (int i = 1; i < k + 1; i++) {

if (temp == nullptr) return result->next;

temp = temp->next;

}

ListNode* now_pre = pre;

for (int i = 0; i < k - 1; i++) {

head = now_pre->next;

pre = now_pre;

for (int j = 0; j < k - i - 1; j++) {

pre->next = head->next;

pre = pre->next;

temp = head->next->next;

head->next->next = head;

head->next = temp;

}

pre = last;

head = last->next;

}

return result->next;

}

};