Leetcode学习

回文数

反转一半数字
第一个想法是将数字转换为字符串，并检查字符串是否为回文。
但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。

第二个想法是将数字本身反转，然后将反转的数字与原始数字比较，如果它们是相同的，那么这个数字就是回文。
但是，如果反转后的数字大于int.MAX，我们将遇到整数溢出问题。

反转int数字的一半，如果该数字是回文，反转后半部分应与原始数字的前半部分相同。

例如，输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

首先，我们应该处理一些临界情况。所有负数都不可能是回文，例如：-123 不是回文，因为 - 不等于 3。所以我们可以对所有负数返回 false。除了 0 以外，所有个位是 0 的数字不可能是回文，因为最高位不等于 0。所以我们可以对所有大于 0 且个位是 0 的数字返回 false。

整个过程中，不断将原始数字除以10，然后给反转的数字乘上10，当原始数字小于或等于反转后的数字时，就意味着已经处理了一半位数的数字了。

最长公共前缀

显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。
用minLength表示字符串数组中的最短字符串的长度，则可以在[o, minLength]范围内通过二分查找得到最长公共前缀的长度。
每次查找返回的中间值mid，判断每个字符串的长度为mid的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于mid，如果不相同则小于mid。

移除链表元素

给一个链表的头节点head和一个整数val，请删除链表中所有满足Node.val==val的节点，并返回新的头节点。
递归
链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。

对于给定的链表，首先对除了头节点head以外的节点进行删除操作，然后判断。

递归的终止条件是head为空，此时直接返回head。
当head不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val并决定是否要删除 head。

同构字符串

哈希表
需要判断s和t每个位置上的字符是否都一一对应，即s的任意一个字符被t中唯一的字符对应，反之也成立，称为双射。

因此，维护两张哈希表，第一张哈希表以s中字符为键，t中字符为值。

爬楼梯

假设你正在爬楼梯，需要n阶才能到达楼顶
每次可以爬1或2个台阶，有多少种不同方法可以爬楼梯？

用f(x)表示爬到第x级台阶的方案数，最后一步可能跨了一级台阶，也可能跨了两级台阶，所以可以列出如下式子：

f(x) = f(x-1) + f(x-2)

买卖股票的最佳时机二

不能同时参与多笔交易，因此每天交易结束后只可能存在手里有一只股票或者没有股票的状态。

定义状态dp[i][0]表示第i天交易完后手里没有股票的最大利润，dp[i][1]表示第i天交易完后手里持有一支股票的最大利润（i从0开始）。

dp[i][0]的转移方程，如果这一天交易完后手里没有股票，那么可能前一天也没有，或者前一天的时候有

dp[i][0] = max{dp[i-1][0], dp[i-1][1]+prices[i]}

dp[i][1]，可能前一天就有这个股票，可能前一天没有然后买下了股票

dp[i][1] = max{dp[i-1][1], dp[i-1][0]-prices[i]}

对于初始状态，根据状态定义

dp[0][0] = 0;
dp[0][1] = -prices[0];

因此，只需要从前往后计算即可。
由于全部交易结束后，持有股票的收益一定低于不持有股票的收益
所以的最后答案一定为dp[n-1][0]

使用最小花费爬楼梯

给一个整数数组，cost[i]是从楼梯第i个台阶向上爬需要的费用，一旦支付此费用，可以向上爬一个或者两个台阶。

可以从下标0或1开始爬，求最低花费。

动态规划
假设数组cost的长度为n，则n个阶梯分别对应下标0到n-1，楼梯顶部对应下标n，问题等价于计算达到下标n的最小划分。

创建长度为n+1的数组dp，其中dp[i]表示达到下标i的最小花费。
dp[0] = dp[1] = 0;

dp[i] = min{dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]}

构造限制重复的字符串

给一个字符串s和一个整数repeatLimit，用s中的字符构造一个新字符，使任何字母连续出现的次数都不超过repeatLimit次。

每次选择当前剩余的字典序最大的字符添加到字符串末尾，如果字符串末尾的字符已经连续出现了repeatLimit次，则将字典序次大的字符添加到末尾，随后选择当前剩余字典序最大的字符添加到末尾，直到使用完。

用下标i指向当前未使用的字典序最大的字符，用下标j指向当前未使用的字典序的次大的字符（满足count[j]>0以及j<i），用m记录当前已经填入的末尾字符的连续次数。

拿出最少数目的魔法豆

给定一个正整数数组beans，其中每个整数表示一个袋子里装的魔法豆的数目。

在这里插入图片描述
可将问题转化为：寻找某一个数字x，当我们将豆子数量小于x的袋子清空，并将豆子数量大于x的袋中豆子数量变为x时，拿出的豆子数量最少。

那么，x一定等于某一个袋子的豆子数。

跳跃游戏

nums[i]表示从i向前跳转的最大长度，返回到达nums[n-1]的最小跳跃次数。

这道题典型是贪心算法，通过局部最优解得到全局最优解

反向查找出发位置
目标是到达最后一个位置，因此可以考虑跳跃最后一步之前所在的位置。

如果有多个位置都能通过跳跃到达最后一个位置，那么可以贪心地选择距离最后一个位置最远的位置。

正向查找可到达的最大位置
如果贪心地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少跳跃次数。

在具体实现中，我们维护能够到达的最大下标位置，称为边界。到达边界时，更新边界，并将跳跃次数增加1。

盛最多水的容器

双指针
在这里插入图片描述
在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为min(1,7)*8 = 8。

此时需要移动哪个指针呢？应该移动数字较小的那个指针，这是因为容纳的水量是由两个指针指向的较小值*指针之间的距离。

双指针代表的是可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界，因此还没有进行任何尝试。

在链表中插入最大公约数

给一个链表头head，每个结点包含一个整数值。

在相邻结点之间，插入一个新的结点，节点值为这两个相邻结点值的最大公约数。

class Solution{
public:
	ListNode* insertGreatestCommonDivisors(ListNode* head) {
		ListNode* node = head;
		while(node->next){
			node->next = new ListNode(__gcd(node->val,node->next->val), node->next);
			node = node->next->next;
		}
		return head;
	}
};

删除排序链表中的重复元素

给定一个已排序的链表的头head，删除所有重复元素，使每个元素只出现一次，返回已排序的链表。

删除排序链表中的重复元素二

我们只需要对链表进行一次遍历，就可以删除重复的元素。
由于链表的头节点可能会被删除，因此我们需要额外使用一个哑结点（dummy node）指向链表的头节点。

从指针cur指向链表的哑结点，然后遍历

故障键盘

笔记本键盘存在故障，当上面输入字符’i’时，会反转之前所写的字符。

使用双端队列进行模拟
比较直观的思路是维护答案字符串ans，当遇到非i字符时，就将其加入字符串的末尾，否则将字符串进行反转。

然而字符串翻转需要O(l)的时间，其中l是当前ans的长度，这样做的时间复杂度较高。

事实上，当字符串进行反转后，在末尾添加字符，相当于不对字符串进行反转，并且在开头添加字符，因此维护一个双端队列和一个布尔变量head来维护答案。

head初始值为假

当遇到非i字符时，head为假时，直接添加到末尾，head为真时，添加到队头。
遇到i时，head取反。

如果head为真，就将队列中的字符反序构造。

找出克隆二叉树中的相同节点

给两棵二叉树，原始树orginal和克隆树cloned，以及一个位于原始树的target节点，找到克隆树对应的节点。

深度优先搜索

/**
 * 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* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if(original == nullptr){
            return nullptr;
        }
        if(original == target){
            return cloned;
        }
        TreeNode* left = getTargetCopy(original->left, cloned->left, target);
        if(left != nullptr){
            return left;
        }
        return getTargetCopy(original->right, cloned->right, target);
    }
};

广度优先搜索
使用队列同时对二叉树original和cloned进行广度优先搜索，初始时分别将根节点original和clone压入队列q1和q2。
假设当前搜索的节点分别为node1和node2，将node1和node2分别弹出队列，如果node1节点的引用等于target，那么返回node2，否则分别将node1和node2的非空子节点压入队列q1和q2。

/**
 * 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* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        queue<TreeNode *> q1,q2;
        q1.push(original);
        q2.push(cloned);
        while(!q1.empty()){
            TreeNode *node1 = q1.front();
            TreeNode *node2 = q2.front();
            q1.pop();
            q2.pop();
            if(node1 == target){
                return node2;
            }
            if(node1->left != nullptr){
                q1.push(node1->left);
                q2.push(node2->left);
            }
            if(node1->right != nullptr){
                q1.push(node1->right);
                q2.push(node2->right);
            }
        }
        return nullptr;
    }
};

在带权树网络中统计可连接服务器对数目

给一颗无限带权树，树中总共有n个节点，表示n个服务器，服务器从0到n-1编号。

如果两个服务器a,b和c满足以下条件，那么我们称服务器a和b通过服务器c可连接：

a<b
c到a的距离是可以被整除
c到b的距离可以被整除
c到b的路径从c到a的路径没有公共边

count[i]表示通过服务器i可连接的服务器对的数目

丑数

class Solution{
public:
	bool isUgly(int n){
		if(n <= 0){
			return false;
		}
		vector<int> factors = {2, 3, 5};
		for(int factor:factors){
			while(n % factor == 0){
				n /= factor;
			}
		}
		return n == 1;
	}
}

丑数二

最小堆
初始化堆为空，首先将最小的丑数1加入堆。
每次取出堆顶元素，则x是堆中最小的丑数，由于2x，3x，5x也是丑数，因此将2x，3x，5x加入堆。

上述做法会导致堆中出现重复元素的情况。
为了避免，使用哈希集合去重。

在排除重复元素的情况下，第n次从最小堆中取出的元素就是第n个丑数。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> factors = {2, 3, 5};
        unordered_set<long> seen;
        priority_queue<long, vector<long>, greater<long>> heap;

        seen.insert(1L);
        heap.push(1L);

        int ugly = 0;
        for(int i=0; i<n; i++){
            long curr = heap.top();
            heap.pop();

            ugly = (int)curr;
            for(int factor: factors){
                long next = curr * factor;
                if(!seen.count(next)){
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return ugly;
    }
};