xv01

https://en.wikipedia.org/wiki/List_of_algorithms

https://sci-hub.ru/10.1007/978-3-030-54256-6

4.1. APPLICATIONS OF SORTING 111 Figure 4.1: The convex hull of a set of points (left), constructed by left-to-right insertion (right).

Cracking the Coding Interview

https://annas-archive.org/md5/67b672ec9fe9e34d8e9672e77fc51a08

https://github.com/careercup/CtCI-6th-Edition

1.1

# Determine if a string has all unique characters

u = 'abcd'

def is_unique(s):
    # If the string is longer than the number of unique characters, it cannot be unique
    # 26 letters in the alphabet
    # 10 digits
    # 0-9, a-z, A-Z
    if len(s) > len(u):
        return False
    # Create a set to store unique characters
    char_set = set()
    # Iterate through the string
    for char in s:
        # If the character is already in the set, return False
        if char in char_set:
            return False
        # Add the character to the set
        char_set.add(char)
    # If the program has reached this point, all characters are unique
    return True

# Test the function
print(is_unique('a'))  # True
print(is_unique('abcda'))  # False
print(is_unique('abcde'))  # **False**
print(is_unique('aabbcc'))  # False
print(is_unique(''))  # True

What if you cannot use additional data structures?

SOLUTION

Start off with asking your interviewer if the string is an ASCII string or a Unicode string. This is an important question, and asking it will show an eye for detail and a deep understanding of Computer Science.

We'll assume for simplicity that the character set is ASCII. If not, we would need to increase the storage size, but the rest of the logic would be the same.

Given this, one simple optimization we can make to this problem is to automatically return false if the length of the string is greater than the number of unique characters in the alphabet.

Our first solution is to create an array of boolean values, where the flag at index i indicates whether character i in the alphabet is contained in the string.

If you run across this character a second time, you can immediately return false.

Rust Practice

https://leetcode.com/problems/sqrtx

// Binary Search
pub fn my_sqrt1(x: i32) -> i32 {
    assert!(x >= 0);

    if x == 0 || x == 1 {
        return x;
    }

    let mut left: i32 = 0;
    let mut right: i32 = x;
    let mut ans: i32 = 0;

    while left <= right {
        let middle: i32 = left + (right - left) / 2;
        let square = middle.saturating_mul(middle);
        if square > x {
            //
            right = middle - 1;
        } else {
            ans = middle;
            //
            left = middle + 1;
        }
    }
    ans
}

421. 数组 中 两个数 的 最⼤ 异或值

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/

i = 0 1 2 [2, 3, 5]

>>> bin(2)
'0b10'
>>> bin(3)
'0b11'
>>> bin(4)
'0b100'
>>> bin(5)
'0b101'
>>> bin(6)
'0b110'
>>> bin(7)
'0b111'
>>> bin(8)
'0b1000'

异或 运算 每⼀位 单独 运算 ( 不 进位 加法 ) 所以 优先 找 ⼆进制 ⾼位 的 异或 结果 为 1 的 位置

尽量 让 每⼀位 的 异或 结果 为 1 , 这样才是 num[i] ^ num[j] 的 最⼤值

保存 前 i – 1 个 数 到 字典树中 , 然后 在 字典树中 查找 与 i 匹配 的 异或 结果 最⼤值 , 保留

遍历 数组 时 , 由于 先将 前⼀个数 存⼊ 字典树 中 , 然后 再找 当前 数字 在 字典树中 的 异或 最⼤值 , 所以 遍历完 所有 数字 之后 , 也就 找到了 最⼤的 异或值

在 字典树中 查找时 , 查找 数字的 每⼀位 在 字典树中 相反的值 , 0 找 1 , 1 找 0 , 这样 保证 找到 当前的 异或 最⼤值