Haiyang Yu's Blog

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

1
2
3
4
5
6
7
8
9

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:

      0
     / \
   -3   9
   /   /
 -10  5

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

1
2
3
4
5
6
7
8
9
10
11

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Constraints:

• The length of the given array is positive and will not exceed 20.
• The sum of elements in the given array will not exceed 1000.
• Your output answer is guaranteed to be fitted in a 32-bit integer.

WSL2(Ubuntu 18.04)安装MySQL

前言

因为在windows下面mysql安装很简单, 所以没把安装MySQL当成一个很难的事情. 结果踩了一晚上的坑.

安装

首先是按照网上的各种教程按部就班的安装. (这里我还没有意识到WSL的Ubuntu18.04和普通的Ubuntu18.04有什么不同)

这里我是跟着https://zhuanlan.zhihu.com/p/64080934上面的步骤来做的. 要注意以下两点

• Ubuntu18.04是不兼容MySQL5.7的. 安装MySQL5.7可能导致有些功能不正常使用.
• 在安装的过程中, 输入两次默认root密码之后, 会让你选择验证插件default authentication plugin , 这时候一定要选择下面那个”Use Legacy Authentication Method (Retain MySQL 5.x Compatibility)”. 否则也可能出现兼容问题。

入坑

这时候看着安装教程的你以为安装完了? NO!

当你兴高采烈的使用mysql -u root -p想开启mysql时, 会发现他出了这么一个错

ERROR 2002 (HY000): Can’t connect to local MySQL server through socket ‘/var/run/mysqld/mysqld.sock’ (2)

这时, 你原本以为复制一下错误信息Google一下怎么解决就完事了.

但是会发现网上几乎所有的解决方案都是建立一个软连接, 并且人家都是有mysqld.sock这个文件, 只不过不在/var/run/mysqld/目录下面. 这时人家建立一个软连接ln -s /storage/db/mysql/mysql.sock /var/lib/mysql/mysql.sock就能解决问题了.

而你呢, 找了半天都找不到mysqld.sock这个文件在哪里!!!

之后, 你再Google解决方案, 会发现, 别人的解决办法对你根本不适用.

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

1
2
3
4
5
6

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

• S will have length in range [1, 500].
• S will consist of lowercase English letters ('a' to 'z') only.

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

1
2
3

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

1. The input string length won’t exceed 1000.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

• Methods pop, top and getMin operations will always be called on non-empty stacks.

Given a singly linked list, determine if it is a palindrome.

Example 1:

1
2

Input: 1->2
Output: false

Example 2:

1
2

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

1
2
3

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

1
2
3

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

1
2
3
4

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Each value on each linked list is in the range [1, 10^9].
• Your code should preferably run in O(n) time and use only O(1) memory.

Invert a binary tree.

Example:

Input:

1
2
3
4
5

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

1
2
3
4
5

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1
2
3
4
5

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6