根据罗马数字的唯一表示法，为了表示一个给定的整数 num，我们寻找不超过 num 的最大符号值，将 num 减去该符号值，然后继续寻找不超过 num 的最大符号值，将该符号拼接在上一个找到的符号之后，循环直至 num 为 0。最后得到的字符串即为 num 的罗马数字表示。
编程时，可以建立一个数值-符号对的列表 valueSymbols，按数值从大到小排列。遍历 valueSymbols 中的每个数值-符号对，若当前数值 value 不超过 num，则从 num 中不断减去 value，直至 num 小于 value，然后遍历下一个数值-符号对。若遍历中 num 为 0 则跳出循环。
public String intToRoman(int num) { StringBuffer roman = new StringBuffer(); for (int i = 0; i < values.length; ++i) { int value = values[i]; String symbol = symbols[i]; while (num >= value) { num -= value; roman.append(symbol); } if (num == 0) { break; } } return roman.toString(); } }
MySQL报错：2002 - Can‘t connect to server on ‘localhost‘(10061)
今天上午，我在Navicat连接数据库的时候发现报错“2002 - Can‘t connect to server on ‘localhost‘(10061)”，一开始我照CSDN的方法在计算机管理的服务中找到MYSQL并点击启动，结果还是运行不了。同时我也发现即使我输入了正确的数据库登陆密码也会报错“Can‘t connect to server on ‘localhost‘(10061)”，所以就需要下面的方法来解决这个问题。
维修方法
以管理员身份运行cmd,并用cd命令切换到mysql的bin目录下；
输入命令mysql -u root -p,登录mysql,输入密码，会返回ERROR 2003 (HY000):Can't connect to MySQL server on localhost (10061);
//C++ class Solution { public: int trap(vector<int>& height) { int ans = 0; stack<int> stk; int n = height.size(); for (int i = 0; i < n; ++i) { while (!stk.empty() && height[i] > height[stk.top()]) { int top = stk.top(); stk.pop(); if (stk.empty()) { break; } int left = stk.top(); int currWidth = i - left - 1; int currHeight = min(height[left], height[i]) - height[top]; ans += currWidth * currHeight; } stk.push(i); } return ans; } };
//Java class Solution { public int trap(int[] height) { int ans = 0; Deque<Integer> stack = new LinkedList<Integer>(); int n = height.length; for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) { break; } int left = stack.peek(); int currWidth = i - left - 1; int currHeight = Math.min(height[left], height[i]) - height[top]; ans += currWidth * currHeight; } stack.push(i); } return ans; } }
复杂度分析
时间复杂度：O(n)，其中 n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。
空间复杂度：O(n)，其中 n 是数组 height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。
//C++ class Solution { public: int candy(vector<int>& ratings) { int n = ratings.size(); vector<int> left(n); for (int i = 0; i < n; i++) { if (i > 0 && ratings[i] > ratings[i - 1]) { left[i] = left[i - 1] + 1; } else { left[i] = 1; } } int right = 0, ret = 0; for (int i = n - 1; i >= 0; i--) { if (i < n - 1 && ratings[i] > ratings[i + 1]) { right++; } else { right = 1; } ret += max(left[i], right); } return ret; } };
//Java class Solution { public int candy(int[] ratings) { int n = ratings.length; int[] left = new int[n]; for (int i = 0; i < n; i++) { if (i > 0 && ratings[i] > ratings[i - 1]) { left[i] = left[i - 1] + 1; } else { left[i] = 1; } } int right = 0, ret = 0; for (int i = n - 1; i >= 0; i--) { if (i < n - 1 && ratings[i] > ratings[i + 1]) { right++; } else { right = 1; } ret += Math.max(left[i], right); } return ret; } }
复杂度分析
时间复杂度：O(n)，其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
//C++ class Solution { public: int candy(vector<int>& ratings) { int n = ratings.size(); int ret = 1; int inc = 1, dec = 0, pre = 1; for (int i = 1; i < n; i++) { if (ratings[i] >= ratings[i - 1]) { dec = 0; pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1; ret += pre; inc = pre; } else { dec++; if (dec == inc) { dec++; } ret += dec; pre = 1; } } return ret; } };
//Java class Solution { public int candy(int[] ratings) { int n = ratings.length; int ret = 1; int inc = 1, dec = 0, pre = 1; for (int i = 1; i < n; i++) { if (ratings[i] >= ratings[i - 1]) { dec = 0; pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1; ret += pre; inc = pre; } else { dec++; if (dec == inc) { dec++; } ret += dec; pre = 1; } } return ret; } }
复杂度分析
时间复杂度：O(n)，其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
直观的做法是暴力枚举将 N 个皇后放置在 N×N 的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。
显然，每个皇后必须位于不同行和不同列，因此将 N 个皇后放置在 N×N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。
回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当 N 个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。
由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 N 列可以选择，第二个皇后最多有 N−1 列可以选择，第三个皇后最多有 N−2 列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过 N! 种，遍历这些情况的时间复杂度是 O(N!)。
//Java class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int i = 0; while (i < n) { int sumOfGas = 0, sumOfCost = 0; int cnt = 0; while (cnt < n) { int j = (i + cnt) % n; sumOfGas += gas[j]; sumOfCost += cost[j]; if (sumOfCost > sumOfGas) { break; } cnt++; } if (cnt == n) { return i; } else { i = i + cnt + 1; } } return -1; } }
根据 H 指数的定义，如果当前 H 指数为 h 并且在遍历过程中找到当前值 citations[i]>h，则说明我们找到了一篇被引用了至少 h+1 次的论文，所以将现有的 h 值加 1。继续遍历直到 h 无法继续增大。最后返回 h 作为最终答案。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13
//C++ class Solution { public: int hIndex(vector<int>& citations) { sort(citations.begin(), citations.end()); int h = 0, i = citations.size() - 1; while (i >= 0 && citations[i] > h) { h++; i--; } return h; } };
1 2 3 4 5 6 7 8 9 10 11 12
//Java class Solution { public int hIndex(int[] citations) { Arrays.sort(citations); int h = 0, i = citations.length - 1; while (i >= 0 && citations[i] > h) { h++; i--; } return h; } }
复杂度分析
时间复杂度：O(nlogn)，其中 n 为数组 citations 的长度。即为排序的时间复杂度。
//C++ class Solution { public: int hIndex(vector<int>& citations) { int n = citations.size(), tot = 0; vector<int> counter(n + 1); for (int i = 0; i < n; i++) { if (citations[i] >= n) { counter[n]++; } else { counter[citations[i]]++; } } for (int i = n; i >= 0; i--) { tot += counter[i]; if (tot >= i) { return i; } } return 0; } };
//Java public class Solution { public int hIndex(int[] citations) { int n = citations.length, tot = 0; int[] counter = new int[n + 1]; for (int i = 0; i < n; i++) { if (citations[i] >= n) { counter[n]++; } else { counter[citations[i]]++; } } for (int i = n; i >= 0; i--) { tot += counter[i]; if (tot >= i) { return i; } } return 0; } }
空间复杂度：O(n)，其中 n 为数组 citations 的长度。需要创建长度为 n+1 的数组 counter。
（3）二分搜索
思路及算法
我们需要找到一个值 h，它是满足「有 h 篇论文的引用次数至少为 h」的最大值。小于等于h的所有值 x 都满足这个性质，而大于 h 的值都不满足这个性质。同时因为我们可以用较短时间（扫描一遍数组的时间复杂度为 O(n)，其中 n 为数组 citations 的长度）来判断 x 是否满足这个性质，所以这个问题可以用二分搜索来解决。
设查找范围的初始左边界 left 为 0，初始右边界 right 为 n。每次在查找范围内取中点 mid，同时扫描整个数组，判断是否至少有 mid 个数大于 mid。如果有，说明要寻找的 h 在搜索区间的右边，反之则在左边。
//Java class Solution { public int jump(int[] nums) { int position = nums.length - 1; int steps = 0; while (position > 0) { for (int i = 0; i < position; i++) { if (i + nums[i] >= position) { position = i; steps++; break; } } } return steps; } }
复杂度分析
时间复杂度：O(n^2^)，其中 n 是数组长度。有两层嵌套循环，在最坏的情况下，例如数组中的所有元素都是 1，position 需要遍历数组中的每个位置，对于 position 的每个值都有一次循环。
//C++ class Solution { public: int jump(vector<int>& nums) { int maxPos = 0, n = nums.size(), end = 0, step = 0; for (int i = 0; i < n - 1; ++i) { if (maxPos >= i) { maxPos = max(maxPos, i + nums[i]); if (i == end) { end = maxPos; ++step; } } } return step; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
//Java class Solution { public int jump(int[] nums) { int length = nums.length; int end = 0; int maxPosition = 0; int steps = 0; for (int i = 0; i < length - 1; i++) { maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) { end = maxPosition; steps++; } } return steps; } }
//C++ class Solution { public: bool canJump(vector<int>& nums) { int n = nums.size(); int rightmost = 0; for (int i = 0; i < n; ++i) { if (i <= rightmost) { rightmost = max(rightmost, i + nums[i]); if (rightmost >= n - 1) { return true; } } } return false; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
//Java public class Solution { public boolean canJump(int[] nums) { int n = nums.length; int rightmost = 0; for (int i = 0; i < n; ++i) { if (i <= rightmost) { rightmost = Math.max(rightmost, i + nums[i]); if (rightmost >= n - 1) { return true; } } } return false; } }
