13 July 2019
MySQL----complementary knowledge
by Jerry Zhang
LeetCode Day 8: P108. ConvertSorted Array to Binary Search Tree (Easy)
题目
一个升序的数组，转化为一个平衡二叉搜索树
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
复习：
平衡二叉树。。。当时就没学好，只学了AVL tree，而且全忘得差不多了。。。又要复习了。。。
平衡二叉树非常适合实现sorted map
Algorithm TreeSearch(p, k):
if p is external then
return p // unsuccessful search
else if k == key(p) then
return p // successful search
else if k < key(p) then
return TreeSearch(left(p), k) // recur on left subtree
else // we know that k > key(p)
return TreeSearch(right(p), k) // recur on right subtree
平衡二叉树的插入算法：
put(k, v)，首先搜索键值k, 如果找到了，就重新赋值，如果没找到，就插入进去。
Algorithm TreeInsert(k, v):
Input: A search key k to be associated with value v
p = TreeSearch(root( ), k)
if k == key(p) then
Change p’s value to (v)
else
expandExternal(p, (k,v))
复习了半天，发现其实对这道题没什么帮助。。。
我的思路：
通过二分法，每次都取中间的数，然后用左右两边的子数组去生成左右子树。可能用递归。
第一步：为了取中间的index, 顺手做了个小实验：
public class E_108_ConvertSortedArrayToBST {
public static void main(String[] args) {
for (int i = 1; i < 11; i++) {
System.out.println("mid index of array with length " + i + ": " + i / 2);
}
}
}
mid index of array with length 1: 0
mid index of array with length 2: 1
mid index of array with length 3: 1
mid index of array with length 4: 2
mid index of array with length 5: 2
mid index of array with length 6: 3
mid index of array with length 7: 3
mid index of array with length 8: 4
mid index of array with length 9: 4
mid index of array with length 10: 5
从这个实验我们发现，如果用数组的长度除以二，得到的index分二种情况，如果数组长度为奇数，那么就是正中间那个数；如果数组长度为偶数， 是中间偏右的那个数。
第二步：我想拿到除了中间那个数，左右两边子数组。
想用Arrays.copyOfRange, 基础太差了，又得做实验-.-
public class E_108_ConvertSortedArrayToBST {
public static void main(String[] args) {
String[] arr = {"A", "B", "C"};
String[] strings = Arrays.copyOfRange(arr, 1, 2);
System.out.println(Arrays.toString(strings));
}
}
[B]
所以第一个参数是原数组，第二个参数是from包含，第三个参数是to不包含。
int midIndex = nums.length / 2;
int[] left = Arrays.copyOfRange(nums, 0, midIndex - 1);
int[] right = Arrays.copyOfRange(nums, midIndex + 1, nums.length);
这里需要讨论数组越界的问题。只有在数组长度为0、1、2时，midIndex加减1后可能超过左右界，所以我干脆把这三种情况直接解决掉。
if (nums.length == 0) {
return null;
}
if (nums.length == 1) {
node = new TreeNode(nums[0]);
return node;
}
if (nums.length == 2) {
node = new TreeNode(nums[1]);
node.left = new TreeNode(nums[0]);
return node;
}
做过这里，发现总是有空指针异常。突然想到，这个其实就是一个树的中序遍历，那我能否先把树构建起来，然后往里面填写内容呢？
最后把辅助函数删掉了，也不传入节点了，问题就解决了。
我的算法：
检查数组长度为1、2、3的情况。
取中间的index，节点的值就是它。
用左右子数组生成两个子树，分别赋到左右子节点中。
我的代码：
public class E_108_ConvertSortedArrayToBST {
public static TreeNode sortedArrayToBST(int[] nums) {
if (nums.length == 0) {
return null;
}
if (nums.length == 1) {
return new TreeNode(nums[0]);
}
if (nums.length == 2) {
TreeNode node = new TreeNode(nums[1]);
node.left = new TreeNode(nums[0]);
return node;
}
int midIndex = nums.length / 2;
TreeNode node = new TreeNode(nums[midIndex]);
int[] left = Arrays.copyOfRange(nums, 0, midIndex);
node.left = sortedArrayToBST(left);
int[] right = Arrays.copyOfRange(nums, midIndex + 1, nums.length);
node.right = sortedArrayToBST(right);
return node;
}
public static void main(String[] args) {
int[] arr = {-10,-3,0,5,9};
sortedArrayToBST(arr);
}
}
坑：
求左边子数组时，midIndex不应该减1。因为copy array时右边是不包含的。
最优解法：
class Solution {
public static TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
return helper(nums, 0, nums.length - 1);
}
public static TreeNode helper(int[] nums, int start, int end) {
if (start > end) return null;
int middle = start + (end - start) / 2;
TreeNode root = new TreeNode(nums[middle]);
root.left = helper(nums, start, middle - 1);
root.right = helper(nums, middle + 1, end);
return root;
}
}
反思：
- 大体思路跟我差不多，但代码比我简洁很多。没用copy array, 而是通过两个index，start，end来记录。
- 取中间值时， 用int middle = start + (end - start) / 2; 比我的效果好。
- 数组里不需要搞子数组，用index就最方便了。
- 取中间值的问题以后应该整理一下，形成一个固定的思路。
MySQL
Where is the configuration file of MySQL?
On the desktop, right click the computer, manage, then check the servers. MySQL should be a server running there. In
my case, MySQL80 is running.
Right click, select property, then we can see the path to executable. Here we can find the path of the configuration
file, my.ini.
DO NOT FOLLOW THE STEPS BELOW!
In this file, we can see the datadir, where the data is saved. We can also change the character set.
default-character-set=utf8
character-set-server=utf8
Restart MySQL
Because we changed the configuration file, we need to restart MySQL service.
坑：修改了my.ini后，无法重新启动MySQL80服务了。折腾了一晚上，最后还是把MySQL彻底删除了，重新安装了最新版本8.0.17。
错误提示：
The mysql80 service on local computer started and then stopped.