2020-04-27

最接近的三数之和

题目描述

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法一

暴力法三次循环，时间复杂度是O(N^3)，如何降低复杂度？我们知道，在数组无序的情况下，只能采用这种遍历的方法，没有启发式搜索的信息。所以先排序，之后每个元素i，都依次遍历其[i+1,n]范围内的和，保存最接近target的和，遍历结束后输出即可。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        if(n <= 2) return -1;
        sort(nums.begin(), nums.end());
        int min_diff = INT_MAX;
        int closest_sum;
        for(int i = 0; i < n; i++) {
            int left = i+1;
            int right = n-1;
            while(left < right) {
                // calc diff
                int sum = nums[i] + nums[left] + nums[right];
                int diff = abs(target-sum);
                if(diff < min_diff) {
                    min_diff = diff;
                    closest_sum = sum;
                }
                if(sum == target) {
                    // 必然是最小的 直接返回则节省时间
                    return sum;
                } else if (sum > target) {
                    --right;
                } else {
                    ++left;
                }
            } // end while
        }
        return closest_sum;
    }
};

2020-04-26

最接近的两数之和

题目描述

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的两个整数，使得它们的和与 target 最接近。返回这两个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的两个数的和为 1. (-1 + 2 = 1).

解法一

暴力破解，需要O(N^2)的时间复杂度，能不能降低？我们知道在乱序情况下，只能做到两个循环去遍历，如果排序，则可能可以利用头尾指针去智能化地遍历（和大于target则右指针左移，小于target则左指针右移），这样只需要O(N)的复杂度，加上排序复杂度O(NlogN)，最后复杂度是O(NlogN)
头尾双指针算法的正确性如何证明？我们要找最接近的两数之和，如此移动，如果能证明不会错失最优解即可。

class Solution {
public:
    // 返回最接近的两数之和
    int twoSumClosest(vector<int> nums, int target) {
        int n = nums.size();
        if(n <= 1) return 0;
        sort(nums.begin(), nums.end());
        int left = 0;
        int right = n - 1;
        int min_diff = INT_MAX;
        int closest_sum;
        while(left < right) {
            int sum = nums[left] + nums[right];
            int diff = abs(sum - target);
            if(diff < min_diff) {
                min_diff = diff;
                closest_sum = sum;
            }
            // 移动指针
            if(sum > target) {
                --right;
            } else {
                ++left;
            }
        } // end while
        return closest_sum;
    }
};

2020-04-26

最长递增子序列的个数

问题描述

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

来源：LeetCode

解法一

计算LIS的个数，LIS的解法在这里。因为最长递推子序列的个数是不同的，分两种情况：1.LIS[i]是最大的LIS，但以i结尾的LIS个数有多个，在遍历的过程中，逐渐把刚好等于最大长度-1的，都加和起来，作为LIS[i]的序列个数；2.不同结尾的LIS可能都是最大值，则需要把这些也加和，作为最终的结果。

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) return n;
        vector<int> dp(n, 1);    // 以j结尾的最大递增子序列的长度
        vector<int> count(n, 1); // 以j结尾的最大递增子序列的个数
        int max_len = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                // 找到相同最大长度的加和起来
                // 这里如何判断最大长度？有更大的值赋值替换即可
                if(nums[j] < nums[i]) {
                    if(dp[j] >= dp[i]) { // 赋值更新 长度采用j的长度
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if(dp[j] + 1 == dp[i]) { // 当前长度下刚好相等
                        count[i] += count[j];
                    }
                }
            }
            max_len = max(max_len, dp[i]);
        }
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(max_len == dp[i]) {
                cnt += count[i];
            }
        }
        return cnt;
    }
};

2020-04-26

最长递增子序列

题目描述

给定一个序列X=(X1,X2,…,Xm)，求X的最长递增子序列。（子序列可以是不连续的，比如{5,6,7,1,2,8}的LIS是5,6,7,8）

说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(nlogn) 吗?

来源：LeetCode

解法一

因为是数组，求数组的最优解，问题太大了，我们能不能划分一下，分成多个子问题？这里子问题是需要跟问题对应的，即与递增子序列对应，我们把子问题划分为(X1…Xi)，LIS[i]是以Xi为结尾的最长递增子序列，最优子结构利用了递增的性质，即比较当前结尾元素和所有子问题结尾元素的大小，如果大，则在子问题解的基础上加1。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> dp(n, 1);
        int max_len = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_len = max(max_len, dp[i]);
        }
        return max_len;
    }
};

2020-04-26

两个链表的第一个公共节点

题目描述

输入两个链表，找出它们的第一个公共节点。

注意：
如果两个链表没有交点，返回null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
公共节点

来源：LeetCode

解法一

用hashset可以很快解决问题，即先把链表1的所有节点指针放入set，遍历链表2时，如果找到有相等的指针，则说明这就是第一个公共节点，遍历结束还没找找到，说明没有相交节点。但这种方法的空间复杂度是O(n)，如何找到O(1)的方法呢？这里O(1)必然是使用双指针，分别遍历两个链表，但因为两个链表长度的问题，一次遍历肯定不行，第二次遍历如何继续？
因为相交必须是严格的数学推导出的，我们把节点a1…a2的长度记为a，把b1…b3的长度记为b，把公共c1…c3的长度记为c，要判断是否相交，则通过a+c+b=b+c+a这个等式判断，即在链表1第一次遍历结束后，马上从链表2的开始位置继续遍历，链表2同理。在遍历的过程中比较指针是否相等。如果两个链表没有相交，第二次遍历时，会同时指向最后的null，返回null即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode * p1 = headA;
        ListNode * p2 = headB;
        while(p1 != p2) {
            p1 = p1 != NULL ? p1->next : headB;
            p2 = p2 != NULL ? p2->next : headA;
        }
        return p1;
    }
};

2020-04-25

最长公共子串（Longest Common Substring）

题目描述

给定两个序列X=(X1,X2,…,Xm)和Y=(Y1,Y2,…,Yn)，求X和Y的最长公共子串。
例如：输入两个字符串acbac和acaccbabb，则最大连续子串为cba, 则返回长度3。

解法一

参考之前关于最长公共子序列LCS的解法，我们发现LCS是一种通用的公共子序列，而子串是一种连续的子序列，所以需要修改递推公式。此处动态规划表格存放的内容有所不同，LCS是比较子串，当前问题是为了使用连续子串这一条件，所以考虑设数组dp[i,j]表示以Xi和Yj结尾的最大公共连续子串的长度，如果Xi=Yj，则dp[i,j]=dp[i-1,j-1]+1，只需要再考虑dp[i-1,j-1]这个子问题，如果不相等，则dp[i,j]=0，如果i=0或j=0，说明有一个字符串已经结束了，则dp[i,j]=0。需要注意的是，dp的含义决定了最后的输出结果不是dp[m,n]，而必须在计算dp的过程中寻找最大值。

递归+memo：

class Solution {
public:
    int longestCommonSubstring(string text1, string text2) {
        int size1 = text1.size();
        int size2 = text2.size();
        int memo[1001][1001];
        memset(memo, 0, 1001*1001*sizeof(int));
        int max_len = 0;
        int end_index;
        lcs(text1, text2, memo, size1-1, size2-1, max_len, end_index);
        cout<<text1.substr(end_index-max_len+1, max_len);
        return max_len;
    }

    int lcs(string & a, string & b, int memo[][1001], int i, int j, int & max_len, int & end_index) {
        if(i == -1 || j == -1) return 0; // 有一个字符串已经结束
        if(memo[i][j] != -1) return memo[i][j];
        if(a[i] == b[j]) {
            memo[i][j] = lcs(a, b, memo, i-1, j-1, max_len, end_index) + 1;
        } else {
            memo[i][j] = 0;
            // 此处这么做为了使lcs继续推进 不然遇到零就停下来了
            lcs(a, b, memo, i, j-1, max_len, end_index);
            lcs(a, b, memo, i-1, j, max_len, end_index);
        }
        if(memo[i][j] > max_len) {
            max_len = memo[i][j];
            end_index = i;
        }
        return memo[i][j];
    }
};

解法二

自底向上的解法

class Solution {
public:
    int longestCommonSubstring(string text1, string text2) {
        int dp[1001][1001];
        // memset更高效 memset针对cpu指令集做了优化
        memset(dp, 0, 1001*1001*sizeof(int));
        int size1 = text1.size();
        int size2 = text2.size();
        int max_len = 0;
        int end_index;
        // 从1开始 是为了把c[0,j]和c[i,0]留给空字符串用
        for(int i = 1; i <= size1; i++) {
            for(int j = 1; j <= size2; j++) {
                if(text1[i-1] == text2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                // 保存最大长度
                if(dp[i][j] > max_len) {
                    max_len = dp[i][j];
                    end_index = i-1;
                }
            }
        }
        cout<<text1.substr(end_index-max_len+1, max_len);
        return max_len;
    }
};

2020-04-25

翻转二叉树

题目描述

翻转一棵二叉树。

示例：

输入：

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

输出：

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

来源：LeetCode

解法一

从根节点的左右子树开始，互换两个节点的指针，完成根节点的翻转，再递归地翻转左右子树节点的左右节点。递归出口是到达树的底部。

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        TreeNode * temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->right);
        invertTree(root->left);
        return root;
    }
};

解法二

二叉树BFS，对遍历到的每一个节点，都对其左右节点进行翻转。
注意：此时push到队列的元素都非空，因为只有非空才会有对子节点翻转的必要。

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode * node = q.front();
            q.pop();
            TreeNode * temp = node->left;
            node->left = node->right;
            node->right = temp;
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        return root;
    }
};

2020-04-25

最长公共子序列

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

示例 1:
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3

提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。

来源：LeetCode

解法一

动态规划思想的本质是动态表格(dynamic table)，使用动态规划必须满足两个条件：1.重复子问题，2.最优子结构，表格的思想是以空间换时间，把求解的所有子问题的解都保存下来，不用重复计算，最优子结构则保证了，原问题的解由子问题的组合构成，就可以写成递推公式，在较短的时间复杂度内求解。
针对LCS问题，把字符串a表示为(X1,X2,…,Xm)，字符串b表示为(Y1,Y2,…,Yn)，我们先看看能不能划分子问题：求a和b的LCS，可以定义为LCS[i,j]，其中i表示从X1到Xi的子串，j表示从Y1到Yj的子串，这里固定了字符串的起始索引1。为什么这么划分子问题？因为如果起始索引和结束索引都动态的话，那就更难解决了，更重要的是，我们求最长公共子序列，起始索引动态是没有意义的，因为起始索引大于1的子问题，其结果总会小于等于索引为1的子问题结果。
问题形式化之后，我们发现，如果Xi=Yj，则LCS[i,j]=LCS[i-1,j-1]+1，只需要再考虑LCS[i-1,j-1]这个子问题，如果不相等，则有两个子问题需要解决，LCS[i,j]=max(LCS[i,j-1], LCS[i-1,j])，如果i=0或j=0，说明有一个字符串已经结束了，则LCS[i,j]=0

解决递推公式问题，有两种方法，一种是自底向上，从求解小问题开始，逐渐求解整个问题，另一种是递归的方式，因为中途有很多重复子问题（如LCS[i-1,j-1]可能是LCS[i,j]的子问题，也可能LCS[i,j-1]的子问题），所以使用memo数组记录下这些子问题的解。

以下是递归+memo的解法：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int size1 = text1.size();
        int size2 = text2.size();
        int memo[1001][1001];
        for(int i = 0; i < 1001; i++) {
            for(int j = 0; j < 1001; j++) {
                memo[i][j] = -1;
            }
        }
        return lcs(text1, text2, memo, size1-1, size2-1);
    }
    int lcs(string & a, string & b, int memo[][1001], int i, int j) {
        if(i == -1 || j == -1) return 0; // 有一个字符串已经结束
        if(memo[i][j] != -1) return memo[i][j];
        if(a[i] == b[j]) {
            memo[i][j] = lcs(a, b, memo, i-1, j-1) + 1;
            return memo[i][j];
        } else {
            memo[i][j] = max(lcs(a, b, memo, i-1, j), lcs(a, b, memo, i, j-1));
            return memo[i][j];
        }
    }
};

解法二

自底向上的解法

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int dp[1001][1001];
        // 对于dp数组的初始化
        // memset更高效 memset针对cpu指令集做了优化
        memset(dp, 0, 1001*1001*sizeof(int));
        int size1 = text1.size();
        int size2 = text2.size();
        for(int i = 1; i <= size1; i++) {
            for(int j = 1; j <= size2; j++) {
                if(text1[i-1] == text2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[size1][size2];
    }
};

2020-04-25

对称二叉树

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

来源：LeetCode

解法一

给定一个根节点，如何判断左右子树对称，设计一个递归函数，传递左右子树的根节点到递归函数，返回值是这两颗子树是否相等。在函数里，每次只比较两个子树的根节点是否相等，剩下的交给函数递归求解。

/**
 * 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) {
        if(!root) return true;
        return helper(root->left, root->right);
    }

    bool helper(TreeNode * left, TreeNode * right) {
        if(!left && !right) return true;
        if(!left || !right) return false;
        if(left->val != right->val) return false;
        return helper(left->left, right->right) && helper(left->right, right->left);
    }
};

解法二

既然对称的树，每一层都是符合对称的规则，那么能不能按照逐层判断的方式，层次遍历，每一层判断过程中，如果检测到不对称，则立即返回，如果最后遍历完，仍然没有不对称的，则说明树是对称的。
注意：此处push到队列的后续节点，可以是null，null是参与比较是否对称的。而一般的二叉树层次遍历只输出非null的节点。

/**
 * 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) {
        if(!root) return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty()) {
            // 每次取对称位置的两个节点判断
            TreeNode *node1 = q.front();
            q.pop();
            TreeNode *node2 = q.front();
            q.pop();
            // 继续判断别的对称位置的节点
            if(!node1 && !node2) continue;
            if(!node1 || !node2) return false;
            if(node1->val != node2->val) return false;
            q.push(node1->left);
            q.push(node2->right);
            q.push(node1->right);
            q.push(node2->left);
        }
        return true;
    }
};

2020-04-20

反转链表

题目描述

反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：LeetCode

解法一

从前往后，每次反转后一个节点，维持两个指针prev和last，分别指向第一个和第二个节点，依次后移，直到链表结束同时因为last反转后，下一个节点的连接丢失，所以必须维持一个临时指针，保存last的下一个节点。结束时，置head节点为NULL。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode * prev = head;
        ListNode * last = head->next;
        while(last) {
            ListNode * temp = last->next;
            last->next = prev;
            prev = last;
            last = temp;
        }
        head->next = nullptr;
        return prev;
    }
};

解法二

反转链表有点像栈，最简单的思路是节点指针存放在栈中，出栈时依次指向下一个在栈顶中的元素。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return head;
        stack<ListNode*> s;
        while(head) {
            s.push(head);
            head = head->next;
        }
        ListNode * cur; // 工作指针
        ListNode * newhead = s.top(); // 最开始的位置
        while(!s.empty()) {
            cur = s.top();
            s.pop();
            cur->next = nullptr;
            if(!s.empty()) {
                cur->next = s.top();
            }
        }
        return newhead;
    }
};

解法三

与栈的解法类似，可以用递归的方式模拟栈。递归首先要找出能递归的子问题，子问题的结构在递归时需要保持一致，每次递归都完成一点工作，最后递归过程结束时，就得到了问题的解。
反转链表中，首先依次递归到底部，找到结尾节点作为返回值，之后因为从倒数第二个节点开始，用p->next->next=p的方式完成后一个节点到当前节点的反转，递归结束退回到head。注意每次递归下一个节点返回，都把它的next置位nullptr，这是为了最后不用单独置head->next=nullptr，保持递归的结构。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode * newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

Spark Era Coming...

分享技术记录生活

最接近的三数之和

题目描述

解法一

最接近的两数之和

题目描述

解法一

最长递增子序列的个数

问题描述

解法一

最长递增子序列

题目描述

解法一

两个链表的第一个公共节点

题目描述

解法一

最长公共子串（Longest Common Substring）

题目描述

解法一

解法二

翻转二叉树

题目描述

解法一

解法二

最长公共子序列

题目描述

解法一

解法二

对称二叉树

题目描述

解法一

解法二

反转链表

题目描述

解法一

解法二

解法三