Leetcode 202.快乐数

发表于 2019-05-18 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

编写一个算法来判断一个数是不是“快乐数”。

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

示例:

1 2	输入: 19 输出: true

解释:

$1^2 + 9^2 = 82$
$8^2 + 2^2 = 68$
$6^2 + 8^2 = 100$
$1^2 + 0^2 + 0^2 = 1$

题目分析

就求呗…
把每次的结果存在哈希堆里来查重

源码

int toNextInt(int x) {
    int digits = log10(x)+1;
    int res = 0;
    while(x != 0) {
        res += (x%10) * (x%10);
        x /= 10;
    }
    return res;
}

class Solution {
public:
    unordered_set<int> nums;
    bool isHappy(int n) {
        int res = n;
        while(res != 1) {
            if(nums.find(res) == nums.end()) {
                nums.insert(res);
                res = toNextInt(res);
            }else {
                return false;
            }
        }
        return true;
    }
};

Leetcode 24.两两交换链表中的节点

发表于 2019-05-18 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

1	给定 1->2->3->4, 你应该返回 2->1->4->3.

题目分析

源码

/* Defination of ListNode
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
*/
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 如果是空表返回NULL, 如果是单节点返回head
        if(head == NULL || head->next == NULL) return head;
        ListNode* slow = head;
        ListNode* fast = slow->next;
        slow->next = fast->next;
        fast->next = slow;
        swap(slow, fast);
        ListNode* res = slow;
        while(fast->next != NULL && fast->next->next != NULL) {
            slow = fast->next;
            fast->next = slow->next;
            fast = slow->next;
            slow->next = fast->next;
            fast->next = slow;
            swap(slow, fast);
        }
        return res;
    }
};

Leetcode 19.删除链表的倒数第N个节点

发表于 2019-05-18 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

1
2
3

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

题目分析

既然没有给链表的长度, 一个指针是没法用一边扫描实现的. 所以用两个指针, 一开始两个指针slow和fast都指向头结点, 让fast指针先走n步, 之后两个指针一起走, 在fast到NULL时候,

源码

#include<bits/stdc++.h>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// @lc code=start
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == NULL) return NULL;
        if(head->next == NULL) return n == 1 ? NULL : head;
        ListNode* slow = head;
        ListNode* fast = slow;
        for(int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        if(fast == NULL) return head->next;
        while(fast->next != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};
// @lc code=end

Leetcode 66.加一

发表于 2019-05-05 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

1
2
3

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

1
2
3

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

题目分析

从后向前遍历数组, 如果某一位是9则设为0, 如果非9则加一, 并返回.
如果全部为9则将全部位设为0并在数组开头插入1.

源码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i=digits.size()-1; i>=0; --i) { // 从后向前遍历
            if(digits[i] != 9) { // 如果某一位不为9则这位加1后返回
                ++digits[i];
                return digits;
            }else {
                digits[i] = 0; // 为9的则设为0
            }
        }
        // 到达这里说明原数组所有位均为9
        digits.insert(digits.begin(), 1, 0);
        return digits;
    }
};

Leetcode 28.实现str-str

发表于 2019-05-05 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。

如果不存在，则返回 -1。

示例 1:

1 2	输入: haystack = "hello", needle = "ll" 输出: 2

示例 2:

1 2	输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

题目分析

在haystack字符串中寻找needle的首字符, 取needle长度的子串并和needle对比, 如果相同返回位置, 否则将haystack字符串的那一位改为0.

源码

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle == "") return 0; // needle为空字符时返回0
        while(haystack.find(needle[0]) != -1) {
            int pos = haystack.find(needle[0]);
            // pos为haystack中找到needle首字符的位置
            if(haystack.substr(pos, needle.size()) == needle) {
                // 子串和needle相同
                return pos;
            }else {
                haystack[pos] = 0;
            }
        }
        return -1;
    }
};

Leetcode 26.删除排序数组中的重复项

发表于 2019-05-05 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以引用方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

题目分析

迭代整个数组, 如果某一个元素和其上一个元素相等则删除此元素.

源码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        vector<int>::iterator it = nums.begin()+1;
        while(it != nums.end()) {
            if(*it == *(it-1)) {
                nums.erase(it);
            }else {
                it++;
            }
        }
        return nums.size();
    }
};

Leetcode 23.合并K个排序链表

发表于 2019-05-04 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

题目分析

同 Leetcode 21.合并两个有序链表, 将所有节点放入优先队列后建新表.

源码

struct comp{ // 自定义排序函数
    bool operator()(ListNode* &a, ListNode* &b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    priority_queue<ListNode*, vector<ListNode*>, comp> q; // 用优先队列储存节点

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return NULL; // 如果数组为空则返回NULL
        ListNode* it;
        for(int i=0; i<lists.size(); ++i) { // 遍历所有表并将每个表中所有节点存入优先队列
            it = lists[i];
            while(it != NULL) {
                q.push(it);
                it = it->next;
            }
        }
        if(q.size() == 0) return NULL; // 如果数组中只有空节点则返回NULL
        ListNode* res = q.top();
        q.pop();
        it = res;
        while(q.size() != 0) {
            it->next = q.top();
            it = it->next;
            q.pop();
        }
        it->next = NULL; // ***将最后一个节点的next设为NULL***
        return res;
    }
};

Leetcode 21.合并两个有序链表

发表于 2019-05-04 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

1 2	输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

题目分析

通过自定义排序函数来使用优先队列来push所有节点后重新建立新链表返回, 这个方法可以用在多链表的题型中: Leetcode 23.合并K个排序链表.
一定要将最后的节点的next设为NULL!!!

源码

struct comp{ // 自定义比较函数
    bool operator()(ListNode* &a, ListNode* &b) { // 重载()运算符
        return a->val > b->val;
    }
};

class Solution {
public:
    priority_queue<ListNode*, vector<ListNode*>, comp> q; // 用优先队列储存节点

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL && l2 == NULL) return NULL; // 两个表都为空是返回空表
        ListNode* it = l1;
        while(it != NULL) { // 遍历l1链表将所有节点存到优先队列中
            q.push(it);
            it = it->next;
        }
        it = l2;
        while(it != NULL) { // 遍历l2链表将所有节点存到优先队列中
            q.push(it);
            it = it->next;
        }
        ListNode* res = q.top(); // 返回的头节点
        q.pop();
        it = res;
        while(q.size() != 0) {
            it->next = q.top();
            it = it->next;
            // cout<<"poped"<<endl;
            q.pop();
        }
        it->next = NULL; // ***将最后一个节点的next设为NULL***
        return res;
    }
};

Leetcode 897.递增顺序查找树

发表于 2019-04-29 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

示例:

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

      5
      / \
    3    6
  / \    \
  2   4    8
/        / \
1        7   9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1
  \
  2
    \
    3
      \
      4
        \
        5
          \
          6
            \
            7
              \
              8
                \
                9

题目分析

使用递归中序储存节点至vector中, 后重新构建树.

源码

class Solution {
public:
    vector<TreeNode*> nodes;
    void iterate(TreeNode* root) {
        if(root == NULL) { // 如果节点为空则返回
            return;
        }else { // 节点不为空
            iterate(root->left); // 中序遍历左子树储存节点
            nodes.push_back(root); // 储存本节点
            iterate(root->right); // 中序遍历右子树储存节点
            return;
        }
    }

    TreeNode* increasingBST(TreeNode* root) {
        iterate(root); // 
        TreeNode* res = nodes[0];
        res->left = NULL;
        TreeNode* it = res;
        for(int i=1; i<nodes.size(); ++i) {
            it->right = nodes[i];
            it->left = NULL;
            it = it->right;
        }
        it->left = NULL;
        return res;
    }
};

Leetcode 896.单调数列

发表于 2019-04-29 | 更新于 2020-04-13 | 分类于 Leetcode

题目描述

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true，否则返回 false。

题目分析

将A的升序排序和降序排序后的数组与A相比较, 如果有一个和A相同则A是单调的.

源码

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        vector<int> B = A, C = A;
        sort(B.begin(), B.end(), greater<int>());
        sort(C.begin(), C.end(), less<int>());
        return B == A || C == A;
    }
};