牛顿法-LeetCode 319、322、324、331、332、389
- 2019 年 12 月 24 日
- 笔记
作者：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
