Leetcode刷题记录

递归方法和循环方法的对比
递归方法代码实现比较简洁，但是性能不如循环方法，还有可能出现栈溢出的问题。一般情况下优先考虑递归方法来实现！
搜索路径的题目：一般使用回溯法，回溯法很适合使用递归方法的代码来实现！当要求不能使用递归实现的时候，考虑使用栈模拟递归的过程
求某个问题的最优解时，并且该问题可以拆分为多个子问题时：可以尝试使用动态规划的方法！在使用自上而下的递归思路去分析动态规划问题时，会发现子问题之间存在重叠
的更小的子问题。为了避免不必要的重复计算，使用自下而上的循环代码来实现，即把子问题的最优解先计算出来并用数组保存下来，然后基于子问题的解计算大问题的解。
特殊情况：在分解子问题的时候存在某个特殊的选择，采用这个特殊的选择将一定那个得到最优解，则此题目可能适用于贪心算法！
典型题目的解题思路：在一个已经排好序的数组中查找一个数字或者统计某个数字出现的次数，可以尝试使用二分查找算法！
Q1:给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。

自己写的：暴力解决，时间复杂度太大

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        result = []
        temp = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                for k in range(j + 1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        result.append([nums[i], nums[j], nums[k]])
        for i in range(len(result)):
            if result[i] not in temp:
                temp.append(result[i])
            else:
                continue
        return temp


if __name__ == "__main__":
    s = Solution()
    result = s.threeSum([-1, 0, 1, 2, -1, -4, 3, -5, -2, -3])
    print(result)

网上大神的解法：

class Solution:
    def threeSum(self, nums):
    # 存储结果列表
        result = []
        # 对nums列表进行排序，无返回值，排序直接改变nums顺序
        nums.sort()
        for i in range(len(nums)):
            # 因为是升序排列，如果排序后第一个数都大于0，则跳出循环，不可能有为0的三数之和
            if nums[i] > 0:
                break
            # 排序后相邻两数如果相等，则跳出当前循环继续下一次循环，相同的数只需要计算一次
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 记录i的下一个位置
            j = i + 1
            # 最后一个元素的位置
            k = len(nums) - 1
            while j < k:
                # 判断三数之和是否为0
                if nums[j] + nums[k] == -nums[i]:
                    # 把结果加入数组中
                    result.append([nums[i], nums[j], nums[k]])
                    # 判断j相邻元素是否相等，有的话跳过这个
                    while j < k and nums[j] == nums[j+1]: j += 1
                    # 判断后面k的相邻元素是否相等，是的话跳过
                    while j < k and nums[k] == nums[k-1]: k -= 1
                    # 没有相等则j+1，k-1，缩小范围
                    j += 1
                    k -= 1
                # 小于-nums[i]的话还能往后取
                elif nums[j] + nums[k] < -nums[i]:
                    j += 1
                else:
                    k -= 1
        return result

Q2:见下图

A2：

class Solution:
def romanToInt(self, s: str) -> int:
    d = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
    result = 0
    s_len = len(s)
    for i in range(s_len-1):
        if d[s[i]] < d[s[i+1]]:
            result -= d[s[i]]
        else:
            result += d[s[i]]
    result += d[s[-1]]
    return result

Q3:编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀，返回空字符串 “”。

A3：仅仅比较最长与最短的字符串，如果存在相同的前缀就返回；不存在就返回一个空字符串。重要的是如何从两个字符串中取相同位置的字符进行比较。

def longest_str(strs):
    s1 = min(strs)  # 最短字符串
    s2 = max(strs) # 最长字符串
    for i, v in enumerate(s1):
        if v != s2[i]:
            return s2[:i]   # 当第一个字符就不相等时,返回s2[:0]=[],执行下面的if语句
    if not strs:
        return ""
if  __name__ == "__main__":
    strs = ["dog", "racecar", "car"]
    strs1 = ["flower", "flow", "flight"]
    result = longest_str(strs)
    result1 = longest_str(strs1)
    print(result)
    print(result1)

Q4:给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合;左括号必须以正确的顺序闭合;注意空字符串可被认为是有效字符串
A4:只有完整出现[],{},()的情况才会返回true,同时空字符串也被任何是有效字符串,所以,用空格进行替换[],{},()，然后比较替换后的结果是否是空字符串，不是的话说明不是有效字符串。
1
2
3
4
5
6
def is_Valid(s):
while("{}" in s or "()" in s or "[]" in s):
s = s.replace("{}", "")
s = s.replace("()", "")
s = s.replace("[]", "")
return s == ""
Q5:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。例如，输入：1->2->4, 1->3->4；输出：1->1->2->3->4->4

A5:

struct ListNode{
    int val;
    struct ListNode *next;
};
    // 借助归并排序的思路，递归方法实现
struct ListNode* mergeTwoLists(struct ListNode *l1, struct ListNode *l2){
    struct ListNode *p;
    if (!l1)
        retutn l2;
    if (!l2)
        return l1;
    if(l1->val < l2->val){   // 将两个链表中小的元素放在新的链表中，用指针p指向它
        p = l1;
        p->next = mergeTwoLists(l1->next, l2);
    }else{
        p = l2;
        p->next = mergeTwoLists(l2->next,l1);
    }
    return p;
}

Q6:给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

A6:

int removeDuplicates(int *nums, int numsSize){
    if (numsSize < 2)
        return numsSize;
    int i, j=0;
    for (i=1;i<numsSize;i++){
        if(nums[j] != nums[i])
                nums[++j]=nums[i];
    }
    return j+1;
}

Q7:给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

A7:

int removeElement(int* nums, int numsSize, int val){
    int i,j=0;
    for (i=0;i < numsSize;i++){
        if(nums[i] != val)
            nums[j++] = nums[i];
    }
    return j;
}

Q8:统计小于非负整数n的质数的个数。例如。n=10,则输出小于10的质数个数是4个，具体是2, 3, 5, 7。

A8:使用厄拉多塞筛法：首先从数字2开始，依次删除2的倍数；接着从3开始，依次删除3的倍数，然后从5开始(因为4是2的倍数，已经被删除了)，依次删除5的倍数。一直循环上面的步骤的n-1即可，然后统计最后剩余的数的个数，即质数的个数。

class Solution:

   def countPrimes(self, n: int) -> int:
       if n<=2:
           return 0
       isPrime = [1] * n  # 生成一个全为1的列表
       isPrime[0], isPrime[1] = 0, 0
       for i in range(2, int(n**0.5)+1):   # 质数：除1和本身外，没有其他的因数。如果有其他因数p,则p*p = n,即p = n**0.5
           if isPrime[i] == 1:  # 如果i是质数
               isPrime[2*i:n:i] = [0] * len(isPrime[i*2:n:i])  # 将i的倍数置为0
             #  print(i, isPrime)
       return sum(isPrime)

Q9：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

A9：思路是如果最后一位不是9，而是0到8，就执行普通的最后一位的加1操作；如果最后一位是9，就要考虑向前面一位产生进位标志1，这是此题的关键！

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        flag = False
        for i in range(len(digits)-1, -1, -1):  # 反向遍历list(起点，终点,步长)
            if digits[i] is 9:
                flag = True
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
        if flag:   # 防止出现list=[9]的情况
            digits.insert(0, 1)
            return digits

Q10:删除链表中等于给定值 val 的所有节点。示例:输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5

A10:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 空链表的情况
        if(!head){
            return nullptr;
        }
        // 删除的节点是头节点
        while(head->val == val){
            head = head->next;
            if(!head){
                return nullptr;
            }
        }
        ListNode* pNode = head;
        ListNode* pCur = head->next;
        // 删除的是中间的某个节点
        while(pCur){
            if(pCur->val == val){
                pNode->next = pCur->next;
                pCur = pCur->next;
            }else{
                pNode = pCur;
                pCur = pCur->next;
            }
        }
        return head;
    }
};

Q11：编写一个算法来判断一个数是不是“快乐数”。一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

A11:

class Solution{
public:
    bool isHappy(int n){
        int sum = 0;
        // 1到9中只有1和7符合快乐数的定义！
        if(n == 1 || n==7){
            return true;
        }
         // 其余不符合的情况，都不是快乐数!
        if(n<10){
            return false;
        }
        sum = isHappyCore(n);
        return isHappy(sum);  // 递归判断
    }
private:
    int isHappyCore(int n){
        // 下面的代码是取一个整数的各个位置上的数，具有一般性，记忆！
        int sum = 0
        while(n > 0){
            int mod = n % 10;
            sum += mod * nod;
            n /= 10;
        }
        return sum;
    }
}

Q12:给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

A12：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || head->next == nullptr){
            return head;
        }
        ListNode* pNode = head;  // 慢指针
        ListNode* pCur = head->next;  // 快指针
        while(pNode->next != nullptr){
            if(pNode->val == pCur->val){  // 找到重复元素
                if(pCur->next == nullptr){  // 快指针后面若没有元素直接剔除
                    pNode->next = nullptr;
                }else{  // 快指针后有元素
                    pNode->next = pCur->next;
                    pCur = pCur->next;
                }

            }else{  //元素不相等
                pNode = pNode->next;
                pCur = pCur->next;
            }
        }
        return head;
    }
};

Q13：给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

A13：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr && q==nullptr){
            return true;
        }

        if(p != nullptr && q != nullptr && p->val == q->val){
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);  // 在左右子树上递归实现！
        }else{
            return false;
        }

    }
};

Q14：给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

A14：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// 如果是对称二叉树，则从左子树开始遍历与从右子树开始遍历时，遍历的结果都相同！
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
       return isMirror(root,root);  // 递归实现
    }

    bool isMirror(TreeNode* root1, TreeNode* root2){
        if(root1 == nullptr && root2 == nullptr){
            return true;
        }
        if(root1 == nullptr || root2 == nullptr){
            return false;
        }
        return (root1->val == root2->val) && isMirror(root1->left, root2->right) && isMirror(root1->right, root2->left);
    }
};

A15：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

Q15：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # nums.sort()
        # nums_len = len(nums)
        # return nums[nums_len // 2]   # 返回中间的数
        candidate = None   # 摩尔投票法
        count = 0
        for num in nums:
            if num == candidate:  # 如果数组中的下一个元素num与candidate相同，就不会碰撞，此时count加1
                count += 1
            elif count > 0:  # 如果数组中的下一个元素num与candidate不同，就会发生碰撞，此时count减1，candidate维持上一次的数据
                count -= 1
            else:
                candidate, count = num, 1  # 第一次进入循环，candidate是第一个元素，count加1
        return candidate

A16：实现一个函数，将字符串中的每个空格替换成%20。例如，输入“hello world.”，则输出”hello%20world.”

Q16：解题思路：观察出空格替换后原始字符串变长的关系。在原始字符串的基础上进行修改，利用观察出的关系，使用两个指针从后向前移动将字符串从原始字符串复制到新的字符串中。

#include <iostream>
#include <string>

using namespace std;


// 解题思路：在原始字符串的基础上进行修改，注意原始字符串有足够的空间。使用两个指针，发现空格数量与原始字符串增加的长度关系！
class Solution{
public:
   void ReplaceSPace(char* str, int len){
       if(str == nullptr || len <= 0){
           return;
       }

       int original_len = 0;
       int number_blank = 0;
       int i=0;
       // 遍历原始字符串，统计空格的数目
       while(str[i] != '\0'){
           ++original_len;
           if(str[i] == ' '){
               ++number_blank;
           }
           ++i;
       }

       int new_len = original_len + 2 * number_blank;
       if(new_len > len){
           return;
       }

       int original_index = original_len;
       int new_index = new_len;

       while(original_index >= 0 && new_index > original_index){
           if(str[original_index] == ' '){
               str[new_index--] = '0';
               str[new_index--] = '2';
               str[new_index--] = '%';
           }else{
               str[new_index--] = str[original_index];
           }
           original_index--;
       }

   }
};

Q17：单向链表的基础操作：在单向链表的末尾插入一个节点和找到第一个值为value的节点并将其删除

A17：注意不要忘记释放在堆空间上申请的动态内存

#include <iostream>

using namespace std;

struct ListNode{
    ListNode* m_pNext;
    int m_pVal;
};



// 在链表的末尾插入一个节点
void AddNodeToTail(ListNode** pHead, int value){
    // 为新插入的节点分配空间
    ListNode* pNew = new ListNode();
    pNew->m_pNext = nullptr;
    pNew->m_pVal = value;

    if(pHead == nullptr){  // 空链表
        *pHead = pNew;
    }
    else{
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != nullptr){
            pNode = pNode->m_pNext;
        }
        pNode->m_pNext = pNew;
    }
}


// 找到第一个含某值value的节点并删除此节点
void RemoveNode(ListNode** pHead, int value){
    if(pHead == nullptr || *pHead == nullptr){
        return;
    }

    ListNode* pToDeleted = nullptr;
    if((*pHead)->m_pVal == value){  // 头节点就是要删除的那个节点
        pToDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }else{                               // 头节点不是要删除的那个节点
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != nullptr && pNode->m_pNext->m_pVal != value){   // 头节点不是要删除的那个节点，后面的节点也没有出现value，则一直向后查找
            pNode = pNode->m_pNext;
        }

        if(pNode->m_pNext != nullptr && pNode->m_pNext->m_pVal == value){   //  头节点不是要删除的那个节点,后面的节点找到了value，则执行删除操作
            pToDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
    }

    if(pToDeleted != nullptr){
        delete pToDeleted;
        pToDeleted = nullptr;
    }
}

Q18：从尾到头反向打印出单向链表

A18：因为单向链表方向不能反过来，如果将指针反过来来实现改变单向链表的方向。但是，这会改变单向链表的数据结构，故在不改变数据结构的基础上，使用栈来实现！


#include <iostream>
#include <vector>
#include <stack>


using namespace std;


struct ListNode{
    ListNode* m_pNext;
    int m_pVal;
};

// 利用栈这个数据结构，后进先出！因为单向链表方向不能反过来，如果将指针反过来，从而实现改变链表的方向，但是这会改变链表的数据结构，故在不改变数据结构的基础上，使用栈来实现

class Solution{
public:
    vector<int> printListFromTailToHead(ListNode* pHead){
        stack<int> nodes;
        vector<int> result;
        ListNode* pNode = pHead;
        while(pNode != nullptr){
            nodes.push(pNode->m_pVal);
            pNode = pNode->m_pNext;
        }

        while(!nodes.empty()){
            result.push_back(nodes.top());
            nodes.pop();
        }

        return result;
    }
};