牛顿法-LeetCode 319、322、324、331、332、389
牛顿法-LeetCode 319、322、324、331、332、389
作者：TeddyZhang，公众号：算法工程师之路
牛顿法：
LeetCode # 319 322 324 331 332 389
1
编程题
【LeetCode #319】灯泡开关
初始时有 n 个灯泡关闭。第 1 轮，你打开所有的灯泡。第 2 轮，每两个灯泡你关闭一次。第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。对于第 n 轮，你只切换最后一个灯泡的开关。找出 n 轮后有多少个亮着的灯泡。
示例: 输入: 3 输出: 1
解题思路：求平方数，使用牛顿法
class Solution {
public:
int bulbSwitch(int n) {
if (n < ) return ;
long r = n;
while(r * r > n) {
r = (r + n/r) / ;
}
return (int) r;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/bulb-switcher
【LeetCode #322】零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1
解题思路：
核心递推式：dp[j] = min(dp[j], dp[j-coins[i]]+1); 表示总金额j所需的硬币数，以及减掉一个coins，即dp[j-coins[i]]所需的硬币数再加1。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int INF = amount + ;
vector<int> dp(amount+, INF+);
dp[] = ;
for(int i = ; i < coins.size(); i++) {
for(int j = coins[i]; j < amount+; j++){
dp[j] = min(dp[j], dp[j - coins[i]] + );
}
}
return dp[amount] < INF ? dp[amount] : -1;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-change
【LeetCode #324】摆动排序 II
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
示例 1: 输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
解题思路：
首先对nums进行排序，然后从中间开始分开，进行穿插，注意中间点位置的计算，要考虑size为奇数或者偶数，得到统一的公式，mid = (size+1) / 2 - 1.
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int size = nums.size();
vector<int> tmp(nums);
int end = size-1, mid = (size+) / - ;
sort(tmp.begin(), tmp.end());
for(int i = ; i < size; i++) {
nums[i] = (i % == ) ? tmp[mid--] : tmp[end--];
}
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/wiggle-sort-ii
【LeetCode #331】验证二叉树的前序序列化
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。 示例 1: 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true
解题思路：
这道题目可以通过二叉树的性质来解，对于一棵二叉树，其叶子节点的数量是非叶子节点数量 + 1。因此我们初始化degree = 1，每次遇到叶子结点就减1，遇到其他非叶子节点就加1，判断degree最后是否为零即可。
class Solution {
public:
bool isValidSerialization(string preorder) {
int degree = ;
int n = preorder.length();
for(int i = ; i < n; i++) {
if (degree == ) return false;
if (preorder[i] == ',') continue;
if (preorder[i] == '#') degree -= ;
else {
while(i < n && preorder[i] != ',') i++;
degree += ;
}
}
return degree == ;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
【LeetCode #332】重新安排行程
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。
示例 1: 输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] 输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
解题思路：
使用回溯法，需要注意数据结构使用map，这是由于题中的说明，但行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前，需要有序性。
class Solution {
public:
int n = ;
map<string, map<string, int>> mp;
vector<string> res, tmp;
vector<string> findItinerary(vector<vector<string>>& tickets) {
n = tickets.size();
for(auto& ticket: tickets) {
++mp[ticket[]][ticket[]];
}
tmp.emplace_back("JFK");
dfs();
return res;
}
void dfs() {
if (res.size() == n + ) return;
if (tmp.size() == n + ) {
res = tmp; return;
}
for(auto& tt: mp[tmp.back()]) {
if (tt.second == ) continue;
--tt.second;
tmp.emplace_back(tt.first);
dfs();
tmp.pop_back();
++tt.second;
}
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reconstruct-itinerary
【LeetCode #389】找不同
给定两个字符串 s 和 t，它们只包含小写字母。 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。 请找出在 t 中被添加的字母。
示例: 输入： s = "abcd" t = "abcde" 输出： e
解题思路：由于t是s的重排再添加一个字母，然后我们直接求和，然后相减即可！
class Solution {
public:
char findTheDifference(string s, string t) {
long sum = ;
for (auto i: t) sum += i;
for (auto i: s) sum -=i;
return static_cast<char>(sum);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-the-difference