# README.md

TECH OTAKUS SAVE THE WORLD

## Hi, I'm Alice! <img src="https://img.content.cc/a/2022/04/02/17-43-00-474-89c2bfd364dbf224f0d173b5ebeb0431-203477.gif" alt="" data-size="line">

*Independent Developer*

*Obsessed with JK Uniforms*

![](https://img.content.cc/a/2022/04/02/15-36-26-623-11ea7e2b8c91733899b8e355b99bc454-ddbb3b.gif)

#### A little more about me...<img src="https://img.content.cc/a/2022/04/03/09-44-05-005-ec1d824aabbb1974a0f02291caa441ba-751dbd.gif" alt="" data-size="line">

```javascript
const alice = {
  pronouns: "she" | "her",
  code: [Golang, Rust, Python, Typescript, Javascript, Java],
  tools: [K8s, Node, Vercel, PlanetScale, Upstash, Logflare],
  architecture: ["microservices", "event-driven", "design system pattern"],
  challenge: "I am doing the coding marathon focused on crypto."
}
```


# Crypto


# Solana


# Troubleshooting

Why do I always have so many questions?


# BPF SDK path does not exist

When I was in **step 9 of the tutorial named "**[**Solana 101**](https://github.com/figment-networks/learn-web3-dapp)**"**, I was trying to build my first smart contract. But when I use the command as the book says, I got an unexpected error:

```
$ yarn run solana:build:program                                                                                                       
yarn run v1.22.17
$ cargo build-bpf --manifest-path=contracts/solana/program/Cargo.toml --bpf-out-dir=dist/solana/program
BPF SDK: /Users/alice/.local/share/solana/install/releases/stable-a812f4410ee6195a3b78642f49e07dea69759240/solana-release/bin/sdk/bpf
cargo-build-bpf child: rustup toolchain list -v
cargo-build-bpf child: cargo +bpf build --target bpfel-unknown-unknown --release
    Finished release [optimized] target(s) in 0.28s
cargo-build-bpf child: /Users/alice/.local/share/solana/install/releases/stable-a812f4410ee6195a3b78642f49e07dea69759240/solana-release/bin/sdk/bpf/scripts/strip.sh /Users/alice/Codes/Private/learn-web3-dapp/contracts/solana/program/target/bpfel-unknown-unknown/release/helloworld.so /Users/alice/Codes/Private/learn-web3-dapp/dist/solana/program/helloworld.so
Failed to execute /Users/alice/.local/share/solana/install/releases/stable-a812f4410ee6195a3b78642f49e07dea69759240/solana-release/bin/sdk/bpf/scripts/strip.sh: No such file or directory (os error 2)
error Command failed with exit code 1.
info Visit https://yarnpkg.com/en/docs/cli/run for documentation about this command.
```

We all know this is not about `yarn` itself, so I google and google and google...

Most of the solutions are similar, the first solution is [cargo build-bpf fails](https://github.com/solana-labs/solana/issues/21053), after I tried the answer which has the most thumbs-ups, I got another error which means not work:

```shell-session
$ yarn run solana:build:program                                                                              
yarn run v1.22.17
$ cargo build-bpf --manifest-path=contracts/solana/program/Cargo.toml --bpf-out-dir=dist/solana/program
BPF SDK path does not exist: /Users/alice/.local/share/solana/install/active_release/bin/sdk/bpf: No such file or directory (os error 2)
error Command failed with exit code 1.
info Visit https://yarnpkg.com/en/docs/cli/run for documentation about this command.l
```

After careful comparison, I found my situation may differ from the above question. So I keep searching and I found another question on StackOverflow with the same keyword "[BPF SDK path does not exist](https://stackoverflow.com/questions/70929961/bpf-sdk-path-does-not-exist)". In the solution, it told me to up the version of Rust to date and check the version of  Solana CLI, so I tried the following:

```shell-session
$ rustup update stable                                                                                       
info: syncing channel updates for 'stable-aarch64-apple-darwin'
-- snip --
  stable-aarch64-apple-darwin updated - rustc 1.60.0 (7737e0b5c 2022-04-04) (from rustc 1.59.0 (9d1b2106e 2022-02-23))

info: checking for self-updates

$ sh -c "$(curl -sSfL https://release.solana.com/v1.10.6/install)"
downloading v1.10.6 installer
  ✨ 1.10.6 initialized
```

I updated the Rust and reinstall the Solana CLI with an exact version, and after that, I tried the build command again:

```shell-session
$ yarn run solana:build:program                                                                              
yarn run v1.22.17
$ cargo build-bpf --manifest-path=contracts/solana/program/Cargo.toml --bpf-out-dir=dist/solana/program
BPF SDK: /Users/alice/.local/share/solana/install/releases/1.10.6/solana-release/bin/sdk/bpf
cargo-build-bpf child: rustup toolchain list -v
cargo-build-bpf child: rustup toolchain uninstall bpf
info: uninstalling toolchain 'bpf'
info: toolchain 'bpf' uninstalled
cargo-build-bpf child: rustup toolchain link bpf /Users/alice/.local/share/solana/install/releases/1.10.6/solana-release/bin/sdk/bpf/dependencies/bpf-tools/rust
cargo-build-bpf child: cargo +bpf build --target bpfel-unknown-unknown --release
-- snip compile log --
+ rustup toolchain uninstall bpf
info: uninstalling toolchain 'bpf'
info: toolchain 'bpf' uninstalled
+ set -e
+ rustup toolchain link bpf bpf-tools/rust
+ exit 0
cargo-build-bpf child: /Users/alice/.local/share/solana/install/releases/1.10.6/solana-release/bin/sdk/bpf/dependencies/bpf-tools/llvm/bin/llvm-readelf --dyn-symbols /Users/alice/Codes/Private/learn-web3-dapp/dist/solana/program/helloworld.so

To deploy this program:
  $ solana program deploy /Users/alice/Codes/Private/learn-web3-dapp/dist/solana/program/helloworld.so
The program address will default to this keypair (override with --program-id):
  /Users/alice/Codes/Private/learn-web3-dapp/dist/solana/program/helloworld-keypair.json
✨  Done in 23.40s.
```

Wow! It works! I think maybe the previous version of Solana CLI I installed is somehow broken or not suitable for the Rust version. I'm relieved to finally be able to compile the program.


# Language


# Rust


# Reference


# Capturing the Environment with Closures

Mutable? Immutable?

## Problem Statement

After reading somthing about closure in "the book" of rust, I tried to create a counter with closure, the code is here, and **the build of the following code will fail**:

```rust
fn main() {
    let mut x = 0;
    let counter = || {
        x += 1; // IDE: cannot borrow `counter` as mutable, as it is not declared as mutable
        x
    };
    println!("{}", counter()); // IDE: cannot borrow as mutable
}
```

with an error:

```shell-session
$ cargo run
   Compiling counter v0.1.0 (file:///projects/counter)
error[E0596]: cannot borrow `counter` as mutable, as it is not declared as mutable
 --> src/main.rs:7:20
  |
3 |     let counter = || {
  |         ------- help: consider changing this to be mutable: `mut counter`
4 |         x += 1;
  |         - calling `counter` requires mutable binding due to mutable borrow of `x`
...
7 |     println!("{}", counter());
  |                    ^^^^^^^ cannot borrow as mutable

For more information about this error, try `rustc --explain E0596`.
error: could not compile `counter` due to previous error
```

## Resolution

When a variable in Rust is immutable, once a value is bound to a name, you can’t change that value. Since Rust’s closures are anonymous functions you can save in a variable or pass as arguments to other functions, it is still a variable, so maybe it should follow the rules of mutability.

OK, let me find some references.

As "[the book](https://doc.rust-lang.org/book/ch13-01-closures.html#capturing-the-environment-with-closures)" says:

> Closures can capture values from their environment in three ways, which directly map to the three ways a function can take a parameter: taking ownership, borrowing mutably, and borrowing immutably. These are encoded in the three `Fn` traits as follows:
>
> * `FnOnce` consumes the variables it captures from its enclosing scope, known as the closure’s *environment*. To consume the captured variables, the closure must take ownership of these variables and move them into the closure when it is defined. The `Once` part of the name represents the fact that the closure can’t take ownership of the same variables more than once, so it can be called only once.
> * `FnMut` can change the environment because it mutably borrows values.
> * `Fn` borrows values from the environment immutably.

So... In my code, the value `x` is borrowed, but by default, the closure is immutable. I should make the closure `FnMut` to change the environment.

Now, let's solve the problem!

I simply add a mut to the defination of counter, besides, some more lines call of counter is added for test:

```rust
fn main() {
    let mut x = 0;
    let mut counter = || {
        x += 1;
        x
    };
    println!("{}", counter());
    println!("{}", counter());
    println!("{}", counter());
    println!("{}", counter());
    println!("{}", counter());
}
```

and run it:

```shell-session
$ cargo run
   Compiling counter v0.1.0 (file:///projects/counter)
    Finished dev [unoptimized + debuginfo] target(s) in 0.12s
     Running `target/debug/counter`
1
2
3
4
5
```

Amazing! The program runs as wished, and the problem has been resolved.

## Conclusion

As a Rust newbie, the mutability may be confused for me.&#x20;

To take advantage of the safety and easy concurrency that Rust offers, maybe I should do more coding to be familiar with the feature provided by the Rust language.

## Reference

1. [Closures: Anonymous Functions that Can Capture Their environment](https://doc.rust-lang.org/book/ch13-01-closures.html#capturing-the-environment-with-closures)
2. [Variables and Mutability](https://doc.rust-lang.org/book/ch03-01-variables-and-mutability.html)


# Understanding \&mut \&mut Reference

\&mut? \&mut \&mut?? \&mut \&mut \&mut??? \&mut \&mut \&mut \&mut...

## Problem Statement

I followed [a Solana tutorial](https://github.com/figment-networks/learn-web3-dapp) and had some trouble understanding the following code:

```rust
greeting_account.serialize(&mut &mut account.data.borrow_mut()[..])?;
```

where `greeting_account` is a struct and `.serialize()` is a method derived from [BorshSerialize](https://docs.rs/borsh/latest/borsh/ser/trait.BorshSerialize.html).

One other thing to note is that `account` is an [AccountInfo](https://docs.rs/solana-program/1.8.1/solana_program/account_info/struct.AccountInfo.html) struct from the [solana\_program](https://docs.rs/solana-program/1.10.8/solana_program) crate and `data` has to type: `Rc<RefCell<&'a mut [u8]>>`

The magic with double `&mut` and `[..]` make me, a Rust newbie, really feel scared.&#x20;

This problem has troubled me for a long time, making me care neither for food nor drink, and now I want to beat fear and try to understand this sentence.

## Resolution

First of all, let me google it, and fortunately, I found the most relevant answer just on the top of the result: [Trouble understanding \&mut \&mut reference](https://stackoverflow.com/questions/69670357/trouble-understanding-mut-mut-reference).

Let me split the problem into the following:

1. Why should we add `[..]`?
2. Why double `&mut`?

The code in the tutorial is very long and deep, if you don't want to clone the code, the following code *(which has the same effect as the code in the tutorial I think...)* is simplified for you to understand:

```rust
use borsh::maybestd::io::Write; // Simply add 'borsh = "0.9.1"' to Cargo.toml
use std::cell::RefCell;
use std::rc::Rc;

struct Node<'a> {
    value: Rc<RefCell<&'a mut [u8]>>,
}

fn ref_mut<T: Write>(x: &mut T) -> &mut T {
    x
}

fn main() {
    let mut v: [u8; 3] = [1, 2, 3];
    let node = Node {
        value: Rc::new(RefCell::new(&mut v)),
    };
    println!("{:?}", ref_mut(&mut &mut node.value.borrow_mut()[..]));
}
```

where `value` in the struct `Node` has the same type as the `data` in `account`, and the function `ref_mut` has the same receiver as the function `serialize`.

### Why should we add `[..]`?

{% hint style="info" %}
Most of this part is referenced from the top answer in [Trouble understanding \&mut \&mut reference](https://stackoverflow.com/a/69674104).
{% endhint %}

If we want to know the secret of the double `&mut`, we may go through the `[..]` first.

When we look at the [documentation about certain cases of indexing](https://doc.rust-lang.org/std/ops/trait.IndexMut.html), we see, that

```rust
node.value.borrow_mut()[..]
```

is sugar for

```rust
*(node.value.borrow_mut().index_mut(..))
```

Why is that a valid expression?

`..` is a shorthand for [`RangeFull`](https://doc.rust-lang.org/std/ops/struct.RangeFull.html).

`RangeFull` has an implementation for [`SliceIndex<[u8]>`](https://doc.rust-lang.org/std/ops/struct.RangeFull.html#impl-SliceIndex%3C%5BT%5D%3E).

With this [blanket implementation](https://doc.rust-lang.org/std/ops/trait.IndexMut.html#impl-IndexMut%3CI%3E-1), we get a `IndexMut<RangeFull> for [u8]`, which provides

```rust
fn index_mut(&mut [u8], index: RangeFull) -> &mut [u8]
```

### Why double `&mut`?

The double `&mut` really bothered me for a while, since the common case may only have one in it.

After I made it clear, I found it is actually a simple problem of type. Let's go back to the code above again, and locate the line of code which we have a problem with:

```rust
println!("{:?}", ref_mut(&mut &mut node.value.borrow_mut()[..]));
```

In this line, we pass `&mut &mut node.value.borrow_mut()[..]` as a parameter into the function named `ref_mut`:

```rust
fn ref_mut<T: Write>(x: &mut T) -> &mut T {
    x
}
```

As [Trait Bound Syntax](https://doc.rust-lang.org/book/ch10-02-traits.html#trait-bound-syntax) says:

> The `impl Trait` syntax works for straightforward cases but is actually syntax sugar for a longer form, which is called a *trait bound*; it looks like this:
>
> ```rust
> pub fn notify<T: Summary>(item: &T) {
>     println!("Breaking news! {}", item.summarize());
> }
> ```
>
> This longer form is equivalent to the example in the previous section but is more verbose. We place trait bounds with the declaration of the generic type parameter after a colon and inside angle brackets.

so the type `T` we input to `ref_mut` should implement `Write`, which is the same as the `Write` in the problem, since the definition of the trait Write is very long, so let's go to the definition of the main method (`write` for a writer) in it:

```rust
#[stable(feature = "rust1", since = "1.0.0")]
#[doc(notable_trait)]
#[cfg_attr(not(test), rustc_diagnostic_item = "IoWrite")]
pub trait Write {
    // -- snip --
    #[stable(feature = "rust1", since = "1.0.0")]
    fn write(&mut self, buf: &[u8]) -> Result<usize>;
    // -- snip --
}
```

According to the method, the instance of `Write` should be a mutable reference of an array with `u8` type.

Now let's push it backwords, in order to satisfy the bound `Write`, the generic type in `ref_mut` has to be `&mut [u8]`, and we remove the generic type in `ref_mut` temporarily, which simply replaces T with `&mut [u8]`, besides, add some suitable lifetime parameters:

```rust
fn ref_mut<'a>(x: &'a mut &'a mut [u8]) -> &'a mut &'a mut [u8] {
    x
}
```

From now on, the problem is simple for everyone, we have a function that receives one parameter with the type: `&mut &mut [u8]`.

Here are the types of every part of `&mut &mut node.value.borrow_mut()[..]`:

* `node.value.borrow_mut()` has `RefMut<&mut [u8]>`
* `node.value.borrow_mut()[..]` has `[u8]`
* `&mut node.value.borrow_mut()[..]` has `&mut [u8]`
* `&mut &mut node.value.borrow_mut()[..]` has `&mut &mut [u8]`

To keep track of the actual writing position, we need a mutable reference to the mutable reference, and the input should have double `&mut` now.

Now the [auto dereferencing](https://doc.rust-lang.org/reference/expressions/method-call-expr.html) kicks in.

```rust
node.value.borrow_mut().index_mut(..)
```

And `RefMut<&mut [u8]>` implements [`DerefMut`](https://doc.rust-lang.org/std/ops/trait.DerefMut.html#impl-DerefMut-4) which have `Deref<Target = &mut [u8]>` as a super trait.

And `&mut [u8]` implements `DerefMut` with `Deref<Target = [u8]>` as a super trait.

As mentioned in the [reference](https://doc.rust-lang.org/reference/expressions/method-call-expr.html), the compiler will now take the receiver expression and dereference it repeatedly, so it gets a list of candidate types. It also adds for each type resulting from a dereference of the reference type and the mutable reference type to the list of candidate types. From these candidate types, it selects one providing the method to call.

1. `RefMut<&mut [u8]>` using `node.value.borrow_mut()`
2. `&RefMut<&mut [u8]>`
3. `&mut RefMut<&mut [u8]>`
4. `&mut [u8]` using `*node.value.borrow_mut().deref_mut()` (means dereferenced from `RefMut<&mut [u8]>`)
5. `&&mut [u8]`
6. `&mut &mut [u8]`
7. `[u8]` using `*(*node.value.borrow_mut().deref_mut())` (now dereferenced from `&mut [u8]`)
8. `&[u8]`
9. `&mut [u8]`

(In 7. we are dereferencing a pointer type `&mut [u8]` so no `DerefMut` the Trait is used.)

The first (and only) type in this list provides an `index_mut()` method is `&mut [u8]`, via the `IndexMut<FullRange>` implementation for `[u8]`, so `&mut [u8]` is selected as receiver type. The return type of `index_mut()` is `&mut [u8]` as well.

So now, we hopefully understand, the type of `*(node.value.borrow_mut().index_mut(..))` is `[u8]`.

Thanks to the discussion of dereferencing, `node.value.borrow_mut()` can also be dereferenced with `*`. Since `node.value` has type `RefMut<&mut [u8]>`, it will be `&mut [u8]` after dereferencing, which can get the actual value simply. Finally after adding one more `&mut`, we can also match the type the function needed:

```rust
println!("{:?}", ref_mut(&mut *node.value.borrow_mut()));
```

## Conclusion

It may be confused if you are familiar with the `*` and `&` operator in C++ when you just step into the reference in Rust. Since they are two different things, we should avoid using C++ references to think about Rust references.

According to the question [Why do references need to be explicitly dereferenced](https://users.rust-lang.org/t/solved-why-do-references-need-to-be-explicitly-dereferenced/7770), these words reminded me:

> So I’d treat `&` types in Rust like you would `*` types in C/C++, while keeping in mind the following points.
>
> 1. A Rust `&` type is stored as a pointer, sometimes with a length and other information (see below responses).
> 2. When you call `foo.bar()`, or access `foo.bar`, rust will automatically dereference foo if it has a type of `&Foo`.
> 3. There is a trait called `Deref` that some smart pointer types implement, to change how the \* operator works.

## Reference

1. [Solana Tutorial 101](https://learn.figment.io/pathways/solana-pathway)
2. [Borsh, binary serializer for security-critical projects](https://borsh.io/)
3. [Carte borsh](https://docs.rs/borsh/latest/borsh/)
4. [The base library for all Solana on-chain Rust programs](https://docs.rs/solana-program/1.10.8/solana_program/)
5. [Trouble understanding \&mut \&mut reference](https://stackoverflow.com/questions/69670357/trouble-understanding-mut-mut-reference)
6. [Trait Bound Syntax](https://doc.rust-lang.org/book/ch10-02-traits.html#trait-bound-syntax)
7. [Documentation about certain cases of indexing](https://doc.rust-lang.org/std/ops/trait.IndexMut.html)
8. [RangeFull](https://doc.rust-lang.org/std/ops/struct.RangeFull.html)
9. [SliceIndex<\[u8\]>](https://doc.rust-lang.org/std/ops/struct.RangeFull.html#impl-SliceIndex%3C%5BT%5D%3E)
10. [Blanket implementation](https://doc.rust-lang.org/std/ops/trait.IndexMut.html#impl-IndexMut%3CI%3E-1)
11. [Why do references need to be explicitly dereferenced?](https://users.rust-lang.org/t/solved-why-do-references-need-to-be-explicitly-dereferenced/7770)


# C++


# Reference


# Code for MS rand() and srand() in VC++ 6.0

My friend created a registration code generator for his software on Windows, and he wanted to transplant it into a web app.

He asked for my help. I think it seems really easy, so I agreed without hesitation. Then a long story began...

## The different results on Windows and Linux

As we know, `srand` will set the current number stored in the memory which is known as *seed*, and `rand` will use the *seed* to calculate and return a new number.

The source code of the registration code generator looks like this:

```cpp
for(int i=0; i<5; i++) {    
    srand(seed[i]);
    strKey.Format(strKey+_T("%c"), _T('A')+rand()%26);
}
```

The `seed` in the code above is generated from the user's machine id. Now it seems evident that we combine the usages of `rand` of `srand` to generate a static registration code.

I use `cgo` to wrap the origin C++ code, however, the result is not as expected. After some debugging, I found the executing result of `rand` on Linux is different from the one on Windows.

## Digging the source code

[The source code of Linux `rand`](https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;h=a393dd3c199b5b08a16f3044f2a3bc21f8e88410;hb=HEAD) is easy to find:

```c
/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
   congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
   same in all the other cases due to all the global variables that have been
   set up.  The basic operation is to add the number at the rear pointer into
   the one at the front pointer.  Then both pointers are advanced to the next
   location cyclically in the table.  The value returned is the sum generated,
   reduced to 31 bits by throwing away the "least random" low bit.
   Note: The code takes advantage of the fact that both the front and
   rear pointers can't wrap on the same call by not testing the rear
   pointer if the front one has wrapped.  Returns a 31-bit random number.  */

int
__random_r (buf, result)
     struct random_data *buf;
     int32_t *result;
{
  int32_t *state;

  if (buf == NULL || result == NULL)
    goto fail;

  state = buf->state;

  if (buf->rand_type == TYPE_0)
    {
      int32_t val = state[0];
      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
      state[0] = val;
      *result = val;
    }
  else
    {
      int32_t *fptr = buf->fptr;
      int32_t *rptr = buf->rptr;
      int32_t *end_ptr = buf->end_ptr;
      int32_t val;

      val = *fptr += *rptr;
      /* Chucking least random bit.  */
      *result = (val >> 1) & 0x7fffffff;
      ++fptr;
      if (fptr >= end_ptr)
    {
      fptr = state;
      ++rptr;
    }
      else
    {
      ++rptr;
      if (rptr >= end_ptr)
        rptr = state;
    }
      buf->fptr = fptr;
      buf->rptr = rptr;
    }
  return 0;

 fail:
  __set_errno (EINVAL);
  return -1;
}
```

The source code of Windows `rand` really took me a lot of time to discover the truth, and here let's skip my three-hour search and experimentation. The source code is finally found in [an ancient discussion in a forum which is posted in 2003](http://www.delphigroups.info/3/1/52500.html)...

Here is the source code of `rand` in VC++ 6.0(or still the same as the one today in Visual Studio 2022...):

```c
static long holdrand = 1L;
int __cdecl rand (void)
{
    return(((holdrand = holdrand * 214013L + 2531011L)>>16) & 0x7fff);
}
void __cdecl srand (unsigned int seed)
{
    holdrand = (long)seed;
}
```

and the functions are finally implemented into Typescript:

```typescript
class WinRandom {
  next: number;
  rand(this: WinRandom): number {
    this.next = this.next * 214013 + 2531011;
    return (this.next >> 16) & 0x7fff;
  }
  srand(this: WinRandom, seed: number) {
    this.next = seed;
  }
}
```

## Reference

1. [How can I get the sourcecode for rand() (C++)?](https://stackoverflow.com/questions/18969783/how-can-i-get-the-sourcecode-for-rand-c)
2. [Code for MS rand() and srand()](http://www.delphigroups.info/3/1/52500.html)


# Serials


# A Real-Time Cryptocurrency Ticker Dashboard

Today is March 30, 2022, and I hope laziness won't stop me from completing the first edition of this project in mid-2022...

I've just picked up basic front-end skills and I've developed a strong interest in cryptocurrencies. So I want to start with a simple project to get exposure to cryptocurrency and go deeper into front-end skills.

For these reasons, and you also saw my title above, I wanna to create a cryptocurrency ticker dashboad.

I think this a complete software project, so first of all, we should clarify the following points:

1. What is the core target?
2. The design and feature of the dashboard?
3. Program languages and frameworks selection?
4. Data source?
5. How to deploy?
6. How to test?

#### What is the core target?

Here are some screenshots of "Huobi", a global cryptocurrency leader:

![Market List](https://img.content.cc/a/2022/03/30/21-12-38-585-7c635c48510ae9cdd637532afdb28f7d-4663e7.png)

![Realtime Market Data](https://img.content.cc/a/2022/03/30/21-15-43-451-dcc9f82e32e1d0575238f4118982cc04-6cec84.png)

I want to create a website and an app just like the screenshots above. My target will have two step:

1. Create a real-time cryptocurrency ticker dashboard.
2. Base on step 1, build a crypto trading simulator.

#### The design and features of the dashboard?

In the early project, I will use the design just like "Huobi", maybe in step 2 I have to design something new for my project.

Let's talk about features, I splited the above pics with several red box.

The project will be mainly made up of two pages:

1. The index page
2. The detail page of a crypto

The index page displays some summary infomation of cryptos:

1. Several main cryptos
2. More cryptos as a list

![](https://img.content.cc/a/2022/03/31/21-33-33-589-0282ed3e7747ff8a66fcedf934db4157-9c1713.png)

The detail page of a crypto display all infos of its market:

1. Summary
2. Charts
3. Orderbook & Market Trades
4. Other cryptos as a list
5. Exchange (Trading Simulator), and this will be built in step 2

![](https://img.content.cc/a/2022/03/31/21-38-52-992-05fdfcae7f0066e3dba242411105c292-71da3a.png)

#### Program languages and frameworks selection?

Ha... This is my favourite part, maybe coding is the key to the future...

*This part will be updated whenever something new used during the project.*

For the frontend, I will choose these:

* Language: TypeScript
* Framework: [Next.js](https://nextjs.org)
* Tools: [Tailwind CSS](https://tailwindcss.com)

Now the backend, the following are my choice:

* Language: Golang, Node.js
* Famework: [go-kratos](https://go-kratos.dev)

#### How to deploy?

Since micro service is easy to use, I will deply my services on k8s, and I will use some SaaS or PaaS service to simplify this part. Besides, the target of this part is to use as less $ as possible.

*This part will be updated after which platform to use is decided.*

#### How to test?

This part is just the opposite of the above two parts, since test is boring and will take a long time to check every possible problem.

In order to make the service stable, this part is also very important, so maybe unit test is necessay during the project. *The detail should be considered before testing.*


# 0 - Some Preparation

If you are a pro, you may skip this chapter


# Frontend


# A Simple Progress Bar

Create a simple bilibili style progress bar with tailwind

## Code

```javascript
export function ProgressBar({ current, target }: { current?: number; target?: number }) {
  const progress = Math.floor((current / target) * 100);
  const progressStyle = {
    width: (progress > 100 ? 100 : progress < 0 ? 0 : progress) + "%",
  };
  return (
    <div className="relative h-2">
      <div className="h-full bg-[#f4f4f4] w-full rounded-full" />
      <div
        className="absolute top-0 h-full text-center overflow-hidden bg-[repeating-linear-gradient(-45deg,#EC91AA,#EC91AA_15px,#DD738F_15px,#DD738F_30px)] rounded-full"
        style={progressStyle}
      />
    </div>
  );
}
```

## Reference

![](https://img.content.cc/a/2022/03/30/11-33-04-859-cbc7de9362cf96f6860de229265d07ff-e26a7d.png)


# A React Ribbon Component

It realy took me a long time to create such a unremarkable ribbon

## Target

![](https://img.content.cc/a/2022/03/29/19-26-14-378-9bcd559be6672a46094b78041b3e8d37-bb5455.png)

## Code

```tsx
export default function Ribbon({
  width = 100,
  height = 20,
  text = "",
  color = "#4ade80",
}: {
  width?: number;
  height?: number;
  text?: string;
  color?: string;
}) {
  const sqrt2 = Math.sqrt(2);
  const tinyUnit = ((sqrt2 - 1) / 4) * width - (sqrt2 / 4) * height;
  const unitOffset = (1 / 2) * width + (sqrt2 / 2) * height + tinyUnit;
  const ribbonStyle = `
    .ribbonWrapper {
        position: absolute;
        right: 0;
        top: -${tinyUnit}px;
        right: -${tinyUnit}px;
        z-index: 10;
        width: ${width + tinyUnit}px;
        height: ${width + tinyUnit}px;
        overflow: hidden;
    }

    .ribbonWrapper::before {
        content: "";
        position: absolute;
        width: ${tinyUnit * 2}px;
        height: ${tinyUnit}px;
        right: ${unitOffset}px;
        border-top-left-radius: ${tinyUnit}px;
        background-color: ${color};
        background: -moz-linear-gradient(
          left,
          ${color} 1%,
          rgba(15, 51, 10, 1) 90%
        ); /* FF3.6+ */
        background: -webkit-gradient(
          linear,
          left top,
          right top,
          color-stop(1%, ${color}),
          color-stop(90%, rgba(15, 51, 10, 1))
        ); /* Chrome,Safari4+ */
        background: -webkit-linear-gradient(
          left,
          ${color} 1%,
          rgba(15, 51, 10, 1) 90%
        ); /* Chrome10+,Safari5.1+ */
        background: -o-linear-gradient(
          left,
          ${color} 1%,
          rgba(15, 51, 10, 1) 90%
        ); /* Opera 11.10+ */
        background: -ms-linear-gradient(
          left,
          ${color} 1%,ß
          rgba(15, 51, 10, 1) 90%
        ); /* IE10+ */
        background: linear-gradient(
          to right,
          ${color} 1%,
          rgba(15, 51, 10, 1) 90%
        ); /* W3C */
        filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#008a3b', endColorstr='#0f330a',GradientType=1 ); /* IE6-8 */
    }

    .ribbonWrapper::after {
        content: "";
        position: absolute;
        width: ${tinyUnit}px;
        height: ${tinyUnit * 2}px;
        top: ${unitOffset}px;
        right: 0px;
        border-bottom-right-radius: ${tinyUnit}px;
        background-color: #000;
        background: -moz-linear-gradient(
          top,
          rgba(15, 51, 10, 1) 10%,
          ${color} 99%
        ); /* FF3.6+ */
        background: -webkit-gradient(
          linear,
          left top,
          left bottom,
          color-stop(10%, rgba(15, 51, 10, 1)),
          color-stop(99%, ${color})
        ); /* Chrome,Safari4+ */
        background: -webkit-linear-gradient(
          top,
          rgba(15, 51, 10, 1) 10%,
          ${color} 99%
        ); /* Chrome10+,Safari5.1+ */
        background: -o-linear-gradient(
          top,
          rgba(15, 51, 10, 1) 10%,
          ${color} 99%
        ); /* Opera 11.10+ */
        background: -ms-linear-gradient(
          top,
          rgba(15, 51, 10, 1) 10%,
          ${color} 99%
        ); /* IE10+ */
        background: linear-gradient(
          to bottom,
          rgba(15, 51, 10, 1) 10%,
          ${color} 99%
        ); /* W3C */
        filter: progid:DXImageTransform.Microsoft.gradient( startColorstr='#0f330a', endColorstr='#008a3b',GradientType=0 ); /* IE6-8 */
    }

    .ribbonAnchor {
        position: absolute;
        bottom: 0;
        left: 0;
        width: ${width}px;
        height: ${width}px;
        #overflow: hidden;
    }

    .ribbon {
        position: relative;
        z-index: 10;
        top: ${width / 4 - height / 2}px;
        right: -${width / 4}px;
        --tw-rotate: 45deg;
        transform: var(--tw-transform);
        width: ${width}px;
        height: ${height}px;
        display: flex;
        justify-content: center;
        align-items: center;
        background-color: ${color};
    }
  `;
  return (
    <>
      <style>{ribbonStyle}</style>
      <div className="ribbonWrapper">
        <div className="ribbonAnchor">
          <div className="ribbon">
            <span className="text-sm text-white">{text}</span>
          </div>
        </div>
      </div>
    </>
  );
}
```

## Reference

The key to success is **AB**, LOL

The transition is moving the gray box to the red one, and the position of the **Center'** is at **a quarter to the top and a quarter to the right of the square**.

![](https://img.content.cc/a/2022/03/29/19-26-26-800-339269080ba1f7586be26b4513767ac1-dd53fb.png)

The following is the original version on paper:

![](https://img.content.cc/a/2022/03/29/19-26-43-334-b49f0145c6659ea506320277b979d39e-c0fe0c.png)

And idea from...

{% embed url="<https://codepen.io/CSS3fx/pen/AYwZjR>" %}


# An Easy to Use React DnD Sortable Component

I hope this is actually easy to use...

## Target

![](https://img.content.cc/a/2022/04/02/13-36-00-655-e68fe36331dc415113a95175f7d19964-c41319.gif)

* Easy to use
* Less code

## Code

You can simply copy the following code to a `dnd-sortable.tsx` file, and use as a component.

```typescript
import React, { FC, ReactNode, useCallback, useRef, useState } from "react";
import { useDrag, useDrop } from "react-dnd";
import type { XYCoord, Identifier } from "dnd-core";
import update from "immutability-helper";

export interface NodeProps {
  id: any;
  index: number;
  node: ReactNode;
  moveNode: (dragIndex: number, hoverIndex: number) => void;
}

interface DragItem {
  index: number;
  id: string;
  type: string;
}

export const Node: FC<NodeProps> = ({ id, index, node, moveNode: moveNode }) => {
  const ref = useRef<HTMLDivElement>(null);
  const [{ handlerId }, drop] = useDrop<DragItem, void, { handlerId: Identifier | null }>({
    accept: "item",
    collect(monitor) {
      return {
        handlerId: monitor.getHandlerId(),
      };
    },
    hover(item: DragItem, monitor) {
      if (!ref.current) {
        return;
      }
      const dragIndex = item.index;
      const hoverIndex = index;

      // Don't replace items with themselves
      if (dragIndex === hoverIndex) {
        return;
      }

      // Determine rectangle on screen
      const hoverBoundingRect = ref.current?.getBoundingClientRect();

      // Get vertical middle
      const hoverMiddleY = (hoverBoundingRect.bottom - hoverBoundingRect.top) / 2;

      // Determine mouse position
      const clientOffset = monitor.getClientOffset();

      // Get pixels to the top
      const hoverClientY = (clientOffset as XYCoord).y - hoverBoundingRect.top;

      // Only perform the move when the mouse has crossed half of the items' height
      // When dragging downwards, only move when the cursor is below 50%
      // When dragging upwards, only move when the cursor is above 50%

      // Dragging downwards
      if (dragIndex < hoverIndex && hoverClientY < hoverMiddleY) {
        return;
      }

      // Dragging upwards
      if (dragIndex > hoverIndex && hoverClientY > hoverMiddleY) {
        return;
      }

      // Time to actually perform the action
      moveNode(dragIndex, hoverIndex);

      // Note: we're mutating the monitor item here!
      // Generally it's better to avoid mutations,
      // but it's good here for the sake of performance
      // to avoid expensive index searches.
      item.index = hoverIndex;
    },
  });

  const [{ isDragging }, drag] = useDrag({
    type: "item",
    item: () => {
      return { id, index };
    },
    collect: (monitor: any) => ({
      isDragging: monitor.isDragging(),
    }),
  });

  const opacity = isDragging ? 0.5 : 1;
  drag(drop(ref));
  return (
    <div ref={ref} style={{ opacity }} data-handler-id={handlerId}>
      {node}
    </div>
  );
};

export interface Item {
  id: number;
  node: ReactNode;
}

export default function DndSortable({ nodeList }: { nodeList: Array<ReactNode> }) {
 // Set id for every react node for react-dnd to use
  const [itemList, setItemList] = useState(nodeList.map((node, index) => ({ id: index, node: node })));

  const moveNode = useCallback((dragIndex: number, hoverIndex: number) => {
    setItemList((prevNodes: Item[]) =>
      update(prevNodes, {
        $splice: [
          [dragIndex, 1],
          [hoverIndex, 0, prevNodes[dragIndex] as Item],
        ],
      })
    );
  }, []);

  const renderNode = useCallback((id: number, index: number, node: ReactNode) => {
    return <Node key={id} index={index} id={id} node={node} moveNode={moveNode} />;
    // eslint-disable-next-line react-hooks/exhaustive-deps
  }, []);

  return <>{itemList.map((item, index) => renderNode(item.id, index, item.node))}</>;
}
```

## Usage

```typescript
const cards = useRef([
  {
    id: 1,
    text: "Write a cool JS library",
  },
  {
    id: 2,
    text: "Make it generic enough",
  },
  {
    id: 3,
    text: "Write README",
  },
  {
    id: 4,
    text: "Create some examples",
  },
  {
    id: 5,
    text: "Spam in Twitter and IRC to promote it (note that this element is taller than the others)",
  },
  {
    id: 6,
    text: "The origin text here is a symbol that is not ok",
  },
  {
    id: 7,
    text: "PROFIT",
  },
]);

...

<DndSortable
  nodeList={cards.current.map((card, i) => {
    return (
      <div key={i} className="dnd-sortable">
        {card.text}
      </div>
    );
  })}
/>
```

## Example

{% embed url="<https://codesandbox.io/s/bold-benz-srkg21>" %}

## Reference

1. The react-dnd official simple sortable example: [Sortable Simple](https://react-dnd.github.io/react-dnd/examples/sortable/simple)
2. [React DnD](https://github.com/react-dnd/react-dnd/)


# Sticky Header, Sticky Footer and Fluid Content

This title came from an ancient question on stack overflow, which is asked over 8 years ago...

## What do I want to create?

As is mentioned in the description, this post comes from "[Sticky header, sticky footer (variable height), fluid middle?](https://stackoverflow.com/questions/19220582/sticky-header-sticky-footer-variable-height-fluid-middle)".

My target is really simple, the contains are as followed:

* A sticky(maybe it is fixed) header is always at the top.
* A sticky(it can also be fixed) footer is always at the bottom.
* No matter header or footer, it must not overlap with the content.

So... Technically, I want it to be like the following images, they are large, so it may take a while to load:

<div align="center"><img src="https://img.content.cc/a/2022/04/22/01-10-24-940-98773aea7d661d52dd56666dd3e7d4ff-a93d48.gif" alt="Page with a long enough content"></div>

![Page with content which can not fullfill all the empty place](https://img.content.cc/a/2022/04/22/01-22-44-883-1dcd3a291e74b86605295fc681cbc274-4e8f48.png)

It seems easy, but I met several problems during coding.

## How to create?

First of all, just let me show you the core code of the solution. I create these all in React using Next.js.

Here is the code in the `index.tsx`:

```tsx
import styles from "./index.module.css";

export default function Index() {
  return (
    <div className={styles.container}>
      <header className={styles.header}>This is a header.</header>
      <div className={styles.content}>
        These are very long contents.
        <br />
      </div>
      <footer className={styles.footer}>This is a footer.</footer>
    </div>
  );
}
```

and now `index.modul.css`:

```css
.container {
  width: 100%;
  height: 100%;
  display: flex;
  flex-direction: column;
}

.header {
  position: sticky;
  top: 0;
  width: 100%;
  background-color: red;
}

.footer {
  position: sticky;
  bottom: 0;
  width: 100%;
  background-color: blue;
}

.content {
  flex: 1;
  width: 100%;
  font-size: 48px;
}
```

And you also need to modify your `html` and `body`, which are in `globals.css`:

```css
html,
body {
  font-family: "PingFang SC", "Hiragino Sans GB", "Heiti SC", "Microsoft YaHei",
    "WenQuanYi Micro Hei";
  min-width: 100vw;
  background-color: yellow;
  box-sizing: border-box;
  margin: 0;
  padding: 0;
}

html {
  height: 100%;
}

body {
  min-height: 100%;
  display: flex;
  flex-direction: column;
}

/* We will talk about this in the next section. */
body > div:first-child,
div#__next,
div#__next > div {
  flex: 1;
  display: flex;
  flex-direction: column;
}
```

In this way, you can create a page just like the images above.

This sandbox is a minimal example for your reference:

{% embed url="<https://codesandbox.io/s/sticky-header-sticky-footer-and-fluid-content-2mqovt>" %}

If you don't want to listen to my rough and rugged paths, you don't have to read the following parts.

## Rough and Rugged Paths

### A Magic `__next` Class

This problem may only exit in Next.js.

After I changed the height of html and body, I found my custom container did not inhreit from them.

I looked into the elements, and I found these was a `div` with id `__next` between `body` and my custom elements. It looks like:

```html
<html>
  <!-- snip -->
  <body data-new-gr-c-s-check-loaded="14.1057.0" data-gr-ext-installed="">
    <div id="__next">
<!-- snip -->    
```

The `div` with id `__next` does't have any styles, so if we want to make its child element has a height inhreited, we should also give it some styles just like the part in the `globals.css` with a comment:

```css
body > div:first-child,
div#__next,
div#__next > div {
  flex: 1;
  display: flex;
  flex-direction: column;
}
```

This solution is reminded by "[How to make a page full height in Next.js](https://gist.github.com/dmurawsky/d45f068097d181c733a53687edce1919)". Maybe I should review the basic knowledge of HTML and CSS, since this is a simple problem but bothered me for a long time.

### Why `flex` both in `body` and `div#__next`?

`flex` helps us a lot, but it can only work when the container is big enough.

In my code, the key to success is `flex: 1;` is a shorthand for `flex-grow: 1;`. The `flex-grow` CSS property sets the flex grow factor of a flex item's [main size](https://www.w3.org/TR/css-flexbox/#main-size).

> **main size**
>
> **main size property**
>
> The width or height of a [flex container](https://www.w3.org/TR/css-flexbox/#flex-container) or [flex item](https://www.w3.org/TR/css-flexbox/#flex-item), whichever is in the [main dimension](https://www.w3.org/TR/css-flexbox/#main-dimension), is that box’s ***main size***. Its ***main size property*** is thus either its [width](https://www.w3.org/TR/CSS21/visudet.html#propdef-width) or [height](https://www.w3.org/TR/CSS21/visudet.html#propdef-height) property, whichever is in the [main dimension](https://www.w3.org/TR/css-flexbox/#main-dimension). Similarly, its ***min*** and ***max main size properties*** are its [min-width](https://www.w3.org/TR/CSS21/visudet.html#propdef-min-width)/[max-width](https://www.w3.org/TR/CSS21/visudet.html#propdef-max-width) or [min-height](https://www.w3.org/TR/CSS21/visudet.html#propdef-min-height)/[max-height](https://www.w3.org/TR/CSS21/visudet.html#propdef-max-height) properties, whichever is in the [main dimension](https://www.w3.org/TR/css-flexbox/#main-dimension), and determine its ***min***/***max main size***.

Let's go back to my code, which I set `height: 100%` for `html` to make the global container has an initial height. A `min-height: 100%` for `body`, and this can help long content to grow more than the height set using the same background.

We have talked about the `div#__next` between `body` and custom elements earlier, because of the box model, if we want our custom elements to be flexible, their parents should be flexible first. So flex attributes in the body can make `div#__next` with `flex: 1;` grow to the height of the page, which is set in `html` and `body`.

Now, we just need to repeat these steps, make `div#__next` also flexible, and make the content grow as the main size.

These are because we have a container between `body` and custom elements happened in the Next.js, maybe you only need one flexible parent in your own code.

## Reference

1. [Sticky header, sticky footer (variable height), fluid middle?](https://stackoverflow.com/questions/19220582/sticky-header-sticky-footer-variable-height-fluid-middle)
2. [How to make a page full height in Next.js](https://gist.github.com/dmurawsky/d45f068097d181c733a53687edce1919)
3. [flex](https://developer.mozilla.org/en-US/docs/Web/CSS/flex)


# How To Set Same Height As Width In CSS

I am pretty sure this is a frequently asked question from frontend beginners like me...

## What I wanna build?

![HaHa\~ Four Square Boxes Sit In A Row](https://img.content.cc/a/2022/04/28/15-49-09-964-71caf424f1fd0ae2c8530201e5c1f8e7-0cb88c.png)

I want to create square boxes, however, it really bothered me for a while.

## Let's go straight to the code!

The following examples were created in React and based on [Tailwind CSS](https://tailwindcss.com/), and the information on class names I used can be found [here](https://tailwindcss.com/docs).

### For the best compatibility

```tsx
<div className="inline-block relative w-1/4">
  <div className="mt-[100%]"></div>
  <div className="absolute top-0 bottom-0 left-0 right-0 border-2"></div>
</div>
```

The key to success is a magic `mt-[100%]`. It works because when using **margin/padding-top/bottom** with **percentage**, the value is determined according to the **width** of the containing element which is `w-1/4` for `width: 25%` in my code. Essentially, we have a situation where "vertical" properties can be sized with respect to a "horizontal" property. This isn't an exploit or a hack, because this is how the CSS specification is defined.

### For modern browsers

```tsx
<div className="relative w-1/4 aspect-[1] border-2"></div>
```

Yes! You can actually solve this century problem with a simple `aspect-[1]`, which repesents `aspect-radio: 1;` in CSS.

> The **`aspect-ratio`** [CSS](https://developer.mozilla.org/en-US/docs/Web/CSS) property sets a **preferred aspect ratio** for the box, which will be used in the calculation of auto sizes and some other layout functions.

Thanks to modern browsers, this solution is elegant and easy to understand, and here is the browser compatibility:

![Browser Compability Of aspect-ratio](https://img.content.cc/a/2022/04/28/16-21-46-068-afd7128636c43c60d21ecfa2ee9a2076-5181df.png)

and you can also check it on [Can I Use](https://caniuse.com/?search=aspect-ratio).

## Reference

1. [Height equal to dynamic width (CSS fluid layout)](https://stackoverflow.com/a/6615994)
2. [Maintain the aspect ratio of a div with CSS](https://stackoverflow.com/questions/1495407/maintain-the-aspect-ratio-of-a-div-with-css)


# Alphabet


# MySQL

## Usage

### Alter table

#### Add a column to a table

We can add a column to a table with a specified order with the keyword `FIRST` to the front of all columns or `` AFTER `exist_column_name` `` to after the column `` `exist_column_name` ``.

```sql
ALTER TABLE `table_name` ADD COLUMN `new_column_name` VARCHAR ( 255 ) NOT NULL DEFAULT '' COMMENT 'some_comments' AFTER `exist_column_name`;
```

#### Change the data type of a column

```sql
ALTER TABLE `table_name` MODIFY COLUMN `exist_column_name` VARCHAR ( 255 ) NOT NULL DEFAULT '' COMMENT 'some_comments';
```


# FFmpeg

Maybe I can handle every media with ffmpeg...

## Usage

### Cut Video

```shell
ffmpeg -ss 00:00:07.2 -to 00:00:12 -i input.mov output.mp4
```

Some people will have problems with the black frames at the beginning/end of the procedure video, the parameter `-c copy` may be the trouble-maker. the following reason may help you fix the problem.

> When specifying `-c copy`, ffmpeg will cut the video without modifying the actual bitstream. In other words, it will take the frames as-is and copy them to the output file. In some cases (simply put, when the starting time does not correspond to an [I-frame](https://en.wikipedia.org/wiki/Intra-frame_coding)), ffmpeg needs to include some more frames that are needed to properly decode the first frame to be displayed. Those will get a negative timestamp, so they shouldn't be shown.
>
> Reference: [Black frames at beginning of video file when file cut](https://superuser.com/a/1222834)

### Video to GIF

```shell
ffmpeg -i output.mp4 -vf "fps=10,scale=320:-1:flags=lanczos,split[s0][s1];[s0]palettegen[p];[s1][p]paletteuse" -loop 0 output.gif
```

I simply use the answer from google, and this works well, no in-depth research.

Reference: [How do I convert a video to GIF using ffmpeg, with reasonable quality?](https://superuser.com/a/556031)

### Combine Multiple M3U8 Files into a Single File

For combining multiple M3U8 files into a single AAC audio file, you can use the following FFmpeg command:

```sh
ffmpeg -i example.m3u8 -c copy output.aac
```

This command copies the audio codec from the input M3U8 files without encoding, resulting in a consolidated AAC file named `output.aac`.


# Algorithm


# Diary


# 2022


# 07


# 2022-07-02

## [69. Sqrt(x)](https://leetcode.com/problems/sqrtx/)

### Description

Given a non-negative integer `x`, compute and return *the square root of* `x`.

Since the return type is an integer, the decimal digits are **truncated**, and only **the integer part** of the result is returned.

**Note:** You are not allowed to use any built-in exponent function or operator, such as `pow(x, 0.5)` or `x ** 0.5`.

**Example 1:**

```
Input: x = 4
Output: 2
```

**Example 2:**

```
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
```

**Constraints:**

* `0 <= x <= 2^31 - 1`

### Solution

#### Approach #0: **Binary Search**

```go
func mySqrt(x int) (ans int) {
    l, r := 0, x
    for l <= r {
        mid := l + (r-l)/2
        if mid*mid <= x {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return
}
```


# 2022-07-01

## [67. Add Binary](https://leetcode.com/problems/add-binary/)

### Description

Given two binary strings `a` and `b`, return *their sum as a binary string*.

**Example 1:**

```
Input: a = "11", b = "1"
Output: "100"
```

**Example 2:**

```
Input: a = "1010", b = "1011"
Output: "10101"
```

**Constraints:**

* `1 <= a.length, b.length <= 10^4`
* `a` and `b` consist only of `'0'` or `'1'` characters.
* Each string does not contain leading zeros except for the zero itself.

### Solution

#### Approach #0

```go
func addBinary(a string, b string) (ans string) {
    lenA, lenB := len(a), len(b)
    c := max(lenA, lenB)
    t := 0
    for i := 0; i < c; i++ {
        if i < lenA {
            t += int(a[lenA-i-1] - '0')
        }
        if i < lenB {
            t += int(b[lenB-i-1] - '0')
        }
        ans = strconv.Itoa(t%2) + ans
        t /= 2
    }
    if t > 0 {
        ans = "1" + ans
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```


# 06


# 2022-06-30

## [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)

### Description

Given the `root` of a binary tree, return *the inorder traversal of its nodes' values*.

**Example 1:**

![](https://img.content.cc/a/2022/06/30/16-03-37-558-680cedc2eafece9406e0b00f9958fdf5-aee3a8.png)

```
Input: root = [1,null,2,3]
Output: [1,3,2]
```

**Example 2:**

```
Input: root = []
Output: []
```

**Example 3:**

```
Input: root = [1]
Output: [1]
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 100]`.
* `-100 <= Node.val <= 100`

### Solution

#### Approach #0: **Recursive**

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        ans = append(ans, node.Val)
        dfs(node.Right)
    }
    dfs(root)
    return
}
```

#### Approach #1: **Iterative**

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (ans []int) {
    st := []*TreeNode{}
    for root != nil || len(st) > 0 {
        for root != nil {
            st = append(st, root)
            root = root.Left
        }
        root = st[len(st)-1]
        st = st[:len(st)-1]
        ans = append(ans, root.Val)
        root = root.Right
    }
    return
}
```


# 2022-06-29

## [535. Encode and Decode TinyURL](https://leetcode.com/problems/encode-and-decode-tinyurl/)

### Description

> Note: This is a companion problem to the [System Design](https://leetcode.com/discuss/interview-question/system-design/) problem: [Design TinyURL](https://leetcode.com/discuss/interview-question/124658/Design-a-URL-Shortener-\(-TinyURL-\)-System/).

TinyURL is a URL shortening service where you enter a URL such as `https://leetcode.com/problems/design-tinyurl` and it returns a short URL such as `http://tinyurl.com/4e9iAk`. Design a class to encode a URL and decode a tiny URL.

There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Implement the `Solution` class:

* `Solution()` Initializes the object of the system.
* `String encode(String longUrl)` Returns a tiny URL for the given `longUrl`.
* `String decode(String shortUrl)` Returns the original long URL for the given `shortUrl`. It is guaranteed that the given `shortUrl` was encoded by the same object.

**Example 1:**

```
Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after deconding it.
```

**Constraints:**

* `1 <= url.length <= 10^4`
* `url` is guranteed to be a valid URL.

### Solution

#### Approach #0

```go
type Codec struct {
    id int
    m map[string]string
}


func Constructor() Codec {
    return Codec{m:make(map[string]string)}
}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) (tiny string) {
	this.id++
    tiny=strconv.Itoa(this.id)
    this.m[tiny]=longUrl
    return
}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
    return this.m[shortUrl]
}


/**
 * Your Codec object will be instantiated and called as such:
 * obj := Constructor();
 * url := obj.encode(longUrl);
 * ans := obj.decode(url);
 */
```


# 2022-06-28

## [24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)

### Description

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

**Example 1:**

![](https://img.content.cc/a/2022/06/28/10-24-44-723-3a2452cf85b78ed8b3c5f4fc03f980ed-8357a2.png)

```
Input: head = [1,2,3,4]
Output: [2,1,4,3]
```

**Example 2:**

```
Input: head = []
Output: []
```

**Example 3:**

```
Input: head = [1]
Output: [1]
```

**Constraints:**

* The number of nodes in the list is in the range `[0, 100]`.
* `0 <= Node.val <= 100`

### Solution

#### Approach #0

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        next := cur.Next
        cur.Val, next.Val = next.Val, cur.Val
        cur = next.Next
    }
    return head
}
```


# 2022-06-27

## [112. Path Sum](https://leetcode.com/problems/path-sum/)

### Description

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a **root-to-leaf** path such that adding up all the values along the path equals `targetSum`.

A **leaf** is a node with no children.

**Example 1:**

![](https://img.content.cc/a/2022/06/27/11-13-10-134-742c651c576f3ecd182f1ad76ef48299-d4ba03.png)

```
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
```

**Example 2:**

![](https://img.content.cc/a/2022/06/27/11-13-20-136-9e59eea0963a921ebdc0f48f2e375e29-46f9d3.png)

```
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
```

**Example 3:**

```
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 5000]`.
* `-1000 <= Node.val <= 1000`
* `-1000 <= targetSum <= 1000`

### Solution

#### Approach #0: DFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }
    return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}
```

#### Approach #1: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    nodeQ := []*TreeNode{root}
    valQ := []int{0}
    for len(nodeQ) > 0 {
        node := nodeQ[0]
        nodeQ = nodeQ[1:]
        val := valQ[0]
        valQ = valQ[1:]
        if node.Left == nil && node.Right == nil && val+node.Val == targetSum {
            return true
        }
        if node.Left != nil {
            nodeQ = append(nodeQ, node.Left)
            valQ = append(valQ, node.Val+val)
        }
        if node.Right != nil {
            nodeQ = append(nodeQ, node.Right)
            valQ = append(valQ, node.Val+val)
        }
    }
    return false
}
```


# 2022-06-26

## [2274. Maximum Consecutive Floors Without Special Floors](https://leetcode.com/problems/maximum-consecutive-floors-without-special-floors/)

### Description

Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be **special floors**, used for relaxation only.

You are given two integers `bottom` and `top`, which denote that Alice has rented all the floors from `bottom` to `top` (**inclusive**). You are also given the integer array `special`, where `special[i]` denotes a special floor that Alice has designated for relaxation.

Return *the **maximum** number of consecutive floors without a special floor*.

**Example 1:**

```
Input: bottom = 2, top = 9, special = [4,6]
Output: 3
Explanation: The following are the ranges (inclusive) of consecutive floors without a special floor:
- (2, 3) with a total amount of 2 floors.
- (5, 5) with a total amount of 1 floor.
- (7, 9) with a total amount of 3 floors.
Therefore, we return the maximum number which is 3 floors.
```

**Example 2:**

```
Input: bottom = 6, top = 8, special = [7,6,8]
Output: 0
Explanation: Every floor rented is a special floor, so we return 0.
```

**Constraints:**

* `1 <= special.length <= 10^5`
* `1 <= bottom <= special[i] <= top <= 10^9`
* All the values of `special` are **unique**.

### Solution

#### Approach #0

```go
func maxConsecutive(bottom int, top int, special []int) (ans int) {
    special = append(special, bottom-1, top+1)
    sort.Ints(special)
    for i := 1; i < len(special); i++ {
        ans = max(ans, special[i]-special[i-1]-1)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```


# 2022-06-25

## [66. Plus One](https://leetcode.com/problems/plus-one/)

### Description

You are given a **large integer** represented as an integer array `digits`, where each `digits[i]` is the `ith` digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading `0`'s.

Increment the large integer by one and return *the resulting array of digits*.

**Example 1:**

```
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
```

**Example 2:**

```
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].
```

**Example 3:**

```
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].
```

**Constraints:**

* `1 <= digits.length <= 100`
* `0 <= digits[i] <= 9`
* `digits` does not contain any leading `0`'s.

### Solution

#### Approach #0

```go
func plusOne(digits []int) []int {
    digits[len(digits)-1]++
    for i := len(digits) - 1; i >= 0; i-- {
        if i > 0 {
            if digits[i] >= 10 {
                digits[i] -= 10
                digits[i-1]++
            }
        } else {
            if digits[i] >= 10 {
                digits[i] -= 10
                digits = append([]int{1}, digits...)
            }
        }
    }
    return digits
}
```


# 2022-06-24

## [515. Find Largest Value in Each Tree Row](https://leetcode.com/problems/find-largest-value-in-each-tree-row/)

### Description

Given the `root` of a binary tree, return *an array of the largest value in each row* of the tree **(0-indexed)**.

**Example 1:**

![](https://img.content.cc/a/2022/06/24/19-48-58-253-ebcc9691b584d98fbb7c867c84a0f536-37871d.png)

```
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
```

**Example 2:**

```
Input: root = [1,2,3]
Output: [1,3]
```

**Constraints:**

* The number of nodes in the tree will be in the range `[0, 10^4]`.
* `-2^31 <= Node.val <= 2^31 - 1`

### Solution

#### Approach #0: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func largestValues(root *TreeNode) (ans []int) {
    if root == nil {
        return
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        big := queue[0].Val
        for i := 0; i < size; i++ {
            cell := queue[i]
            big = max(big, cell.Val)
            if cell.Left != nil {
                queue = append(queue, cell.Left)
            }
            if cell.Right != nil {
                queue = append(queue, cell.Right)
            }
        }
        ans = append(ans, big)
        queue = queue[size:]
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

#### Approach #1: DFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func largestValues(root *TreeNode) (ans []int) {
    if root == nil {
        return
    }
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }
        if len(ans) <= depth {
            ans = append(ans, node.Val)
        } else {
            ans[depth] = max(ans[depth], node.Val)
        }
        dfs(node.Left, depth+1)
        dfs(node.Right, depth+1)
    }
    dfs(root, 0)
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```


# 2022-06-23

## [58. Length of Last Word](https://leetcode.com/problems/length-of-last-word/)

### Description

Given a string `s` consisting of words and spaces, return *the length of the **last** word in the string.*

A **word** is a maximal substring consisting of non-space characters only.

**Example 1:**

```
Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.
```

**Example 2:**

```
Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.
```

**Example 3:**

```
Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.
```

**Constraints:**

* `1 <= s.length <= 10^4`
* `s` consists of only English letters and spaces `' '`.
* There will be at least one word in `s`.

### Solution

#### Approach #0

```go
func lengthOfLastWord(s string) int {
    l := strings.Split(strings.Trim(s, " "), " ")
    return len(l[len(l)-1])
}
```


# 2022-06-22

## [513. Find Bottom Left Tree Value](https://leetcode.com/problems/find-bottom-left-tree-value/)

### Description

Given the `root` of a binary tree, return the leftmost value in the last row of the tree.

**Example 1:**

![](https://img.content.cc/a/2022/06/22/07-13-02-721-4ecf0611746881b7fc7955a2b15a5870-86fa20.png)

```
Input: root = [2,1,3]
Output: 1
```

**Example 2:**

![](https://img.content.cc/a/2022/06/22/07-13-14-094-5e00013b246721ea83bb5be7510ce76c-ec9d00.png)

```
Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 10^4]`.
* `-23^1 <= Node.val <= 23^1 - 1`

### Solution

#### Approach #0: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) (ans int) {
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[i]
            if i == 0 {
                ans = node.Val
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        queue = queue[size:]
    }
    return
}
```

#### Approach #1: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) (ans int) {
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        ans = node.Val
    }
    return
}
```

#### Approach #2: DFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) (ans int) {
    var cur int
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }
        depth++
        dfs(node.Left, depth)
        dfs(node.Right, depth)
        if depth > cur {
            cur = depth
            ans = node.Val
        }
    }
    dfs(root, 0)
    return
}
```


# 2022-06-21

## [1108. Defanging an IP Address](https://leetcode.com/problems/defanging-an-ip-address/)

### Description

Given a valid (IPv4) IP `address`, return a defanged version of that IP address.

A *defanged IP address* replaces every period `"."` with `"[.]"`.

**Example 1:**

```
Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"
```

**Example 2:**

```
Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"
```

**Constraints:**

* The given `address` is a valid IPv4 address.

### Solution

#### Approach #0

```go
func defangIPaddr(address string) string {
    return strings.ReplaceAll(address, ".", "[.]")
}
```


# 2022-06-20

## [13. Roman to Integer](https://leetcode.com/problems/roman-to-integer/)

### Description

Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.

```
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
```

For example, `2` is written as `II` in Roman numeral, just two ones added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

* `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.&#x20;
* `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.&#x20;
* `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

**Example 1:**

```
Input: s = "III"
Output: 3
Explanation: III = 3.
```

**Example 2:**

```
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
```

**Example 3:**

```
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```

**Constraints:**

* `1 <= s.length <= 15`
* `s` contains only the characters `('I', 'V', 'X', 'L', 'C', 'D', 'M')`.
* It is **guaranteed** that `s` is a valid roman numeral in the range `[1, 3999]`.

### Solution

#### Approach #0

```go
var (
    m = map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
)

func romanToInt(s string) (ans int) {
    var last int
    for i := len(s) - 1; i >= 0; i-- {
        v := m[s[i]]
        if v >= last {
            ans += v
        } else {
            ans -= v
        }
        last = v
    }
    return
}
```


# 2022-06-19

## [508. Most Frequent Subtree Sum](https://leetcode.com/problems/most-frequent-subtree-sum/)

### Description

Given the `root` of a binary tree, return the most frequent **subtree sum**. If there is a tie, return all the values with the highest frequency in any order.

The **subtree sum** of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

**Example 1:**

![](https://img.content.cc/a/2022/06/19/09-55-18-226-508a6058cf402606df058c843103c9e3-7d1de7.png)

```
Input: root = [5,2,-3]
Output: [2,-3,4]
```

**Example 2:**

![](https://img.content.cc/a/2022/06/19/09-55-30-362-b0fb9e0922b7f32486e9750232b128fd-7b17ad.png)

```
Input: root = [5,2,-5]
Output: [2]
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 10^4]`.
* `-10^5 <= Node.val <= 10^5`

### Solution

#### Approach #0

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findFrequentTreeSum(root *TreeNode) (ans []int) {
    m := make(map[int]int)
    var big int
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        sum := node.Val + dfs(node.Left) + dfs(node.Right)
        m[sum]++
        if m[sum] > big {
            big = m[sum]
        }
        return sum
    }
    dfs(root)

    for k, v := range m {
        if v == big {
            ans = append(ans, k)
        }
    }
    return
}

```


# 2022-06-18

## [6. Zigzag Conversion](https://leetcode.com/problems/zigzag-conversion/)

### Description

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

```
P   A   H   N
A P L S I I G
Y   I   R
```

And then read line by line: `"PAHNAPLSIIGYIR"`

Write the code that will take a string and make this conversion given a number of rows:

```
string convert(string s, int numRows);
```

**Example 1:**

```
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
```

**Example 2:**

```
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
```

**Example 3:**

```
Input: s = "A", numRows = 1
Output: "A"
```

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consists of English letters (lower-case and upper-case), `','` and `'.'`.
* `1 <= numRows <= 1000`

### Solution

#### Approach #0

```go
func convert(s string, numRows int) string {
    n, r := len(s), numRows
    if r == 1 || n <= r {
        return s
    }
    t := 2*r - 2
    c := int(math.Ceil(float64(n)/float64(t))) * (r - 1)
    mat := make([][]byte, r)
    for i := 0; i < r; i++ {
        mat[i] = make([]byte, c)
    }
    x, y := 0, 0
    for i, ch := range s {
        mat[x][y] = byte(ch)
        if i%t < r-1 {
            x++
        } else {
            x--
            y++
        }
    }
    var ans []byte
    for i := 0; i < r; i++ {
        for j := 0; j < c; j++ {
            if mat[i][j] > 0 {
                ans = append(ans, mat[i][j])
            }
        }
    }
    return string(ans)
}
```


# 2022-06-17

## [1089. Duplicate Zeros](https://leetcode.com/problems/duplicate-zeros/)

### Description

Given a fixed-length integer array `arr`, duplicate each occurrence of zero, shifting the remaining elements to the right.

**Note** that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

**Example 1:**

```
Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]
```

**Example 2:**

```
Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]
```

**Constraints:**

* `1 <= arr.length <= 10^4`
* `0 <= arr[i] <= 9`

### Solution

#### Approach #0

```go
func duplicateZeros(arr []int) {
    n := len(arr)
    i, top := -1, 0
    for top < n {
        i++
        if arr[i] == 0 {
            top += 2
        } else {
            top++
        }
    }
    j := n - 1
    if top == n+1 {
        arr[j] = 0
        j--
        i--
    }
    for j > 0 {
        arr[j] = arr[i]
        j--
        if arr[i] == 0 {
            arr[j] = arr[i]
            j--
        }
        i--
    }
}
```


# 2022-06-16

## [384. Shuffle an Array](https://leetcode.com/problems/shuffle-an-array/)

### Description

Given an integer array `nums`, design an algorithm to randomly shuffle the array. All permutations of the array should be **equally likely** as a result of the shuffling.

Implement the `Solution` class:

* `Solution(int[] nums)` Initializes the object with the integer array `nums`.
* `int[] reset()` Resets the array to its original configuration and returns it.
* `int[] shuffle()` Returns a random shuffling of the array.

**Example 1:**

```
Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]
```

**Constraints:**

* `1 <= nums.length <= 50`
* `-10^6 <= nums[i] <= 10^6`
* All the elements of `nums` are **unique**.
* At most `10^4` calls **in total** will be made to `reset` and `shuffle`.

### Solution

#### Approach #0

```go
type Solution struct {
    nums, original []int
}

func Constructor(nums []int) Solution {
    return Solution{nums, append([]int(nil), nums...)}
}

func (this *Solution) Reset() []int {
    copy(this.nums, this.original)
    return this.nums
}

func (this *Solution) Shuffle() []int {
    shuffle := make([]int, len(this.nums))
    for i := range shuffle {
        j := rand.Intn(len(this.nums))
        shuffle[i] = this.nums[j]
        this.nums = append(this.nums[:j], this.nums[j+1:]...)
    }
    this.nums = shuffle
    return this.nums
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Reset();
 * param_2 := obj.Shuffle();
 */
```

#### Approach #1

```go
type Solution struct {
    nums, original []int
}

func Constructor(nums []int) Solution {
    return Solution{nums, append([]int(nil), nums...)}
}

func (this *Solution) Reset() []int {
    copy(this.nums, this.original)
    return this.nums
}

func (this *Solution) Shuffle() []int {
    n := len(this.nums)
    for i := range this.nums {
        j := i + rand.Intn(n-i)
        this.nums[i], this.nums[j] = this.nums[j], this.nums[i]
    }
    return this.nums
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Reset();
 * param_2 := obj.Shuffle();
 */
```

## [202. Happy Number](https://leetcode.com/problems/happy-number/)

### Description

Write an algorithm to determine if a number `n` is happy.

A **happy number** is a number defined by the following process:

* Starting with any positive integer, replace the number by the sum of the squares of its digits.
* Repeat the process until the number equals 1 (where it will stay), or it **loops endlessly in a cycle** which does not include 1.
* Those numbers for which this process **ends in 1** are happy.

Return `true` *if* `n` *is a happy number, and* `false` *if not*.

**Example 1:**

```
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
```

**Example 2:**

```
Input: n = 2
Output: false
```

**Constraints:**

* `1 <= n <= 2^31 - 1`

### Solution

#### Approach #0: Fast ans slow pointer

```go
func isHappy(n int) bool {
    slow, fast := n, step(n)
    for fast != 1 && fast != slow {
        slow = step(slow)
        fast = step(step(fast))
    }
    return fast == 1
}

func step(n int) int {
    var sum int
    for n > 0 {
        sum += (n % 10) * (n % 10)
        n /= 10
    }
    return sum
}
```

## [149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)

### Description

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the **X-Y** plane, return *the maximum number of points that lie on the same straight line*.

**Example 1:**

![](https://img.content.cc/a/2022/06/16/12-09-16-209-cbe6aba7765e7f7058ce81a5d6b81fdc-a2150a.png)

```
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
```

**Example 2:**

![](https://img.content.cc/a/2022/06/16/12-09-31-367-55b7e0bb7e5fbe9d168655dfb0b8e1fa-d6246d.png)

```
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
```

**Constraints:**

* `1 <= points.length <= 300`
* `points[i].length == 2`
* `-104 <= xi, yi <= 104`
* All the `points` are **unique**.

### Solution

#### Approach #0

```go
func maxPoints(points [][]int) (ans int) {
    n := len(points)
    if n <= 2 {
        return n
    }
    for i, p := range points {
        if ans >= n-i || ans > n/2 {
            break
        }
        cnt := make(map[int]int)
        for _, q := range points[i+1:] {
            x, y := p[0]-q[0], p[1]-q[1]
            if x == 0 {
                y = 1
            }
            if y == 0 {
                x = 1
            }
            if y < 0 {
                x, y = -x, -y
            }
            g := gcd(abs(x), abs(y))
            x /= g
            y /= g
            cnt[y+20001*x]++
        }
        for _, c := range cnt {
            ans = max(ans, c+1)
        }
    }
    return
}

func gcd(a, b int) int {
    for a > 0 {
        a, b = b%a, a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [532. K-diff Pairs in an Array](https://leetcode.com/problems/k-diff-pairs-in-an-array/)

### Description

Given an array of integers `nums` and an integer `k`, return *the number of **unique** k-diff pairs in the array*.

A **k-diff** pair is an integer pair `(nums[i], nums[j])`, where the following are true:

* `0 <= i, j < nums.length`
* `i != j`
* `nums[i] - nums[j] == k`

**Notice** that `|val|` denotes the absolute value of `val`.

**Example 1:**

```
Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
```

**Example 2:**

```
Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
```

**Example 3:**

```
Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
```

**Constraints:**

* `1 <= nums.length <= 10^4`
* `-10^7 <= nums[i] <= 10^7`
* `0 <= k <= 10^7`

### Solution

#### Approach #0

```go
func findPairs(nums []int, k int) (ans int) {
    sort.Ints(nums)
    j, n := 0, len(nums)
    for i, num := range nums {
        if i == 0 || nums[i-1] != num {
            for j < n && (nums[j] < k+num || j <= i) {
                j++
            }
            if j < n && nums[j] == k+num {
                ans++
            }
        }
    }
    return
}
```


# 2022-06-15

## [201. Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/)

### Description

Given two integers `left` and `right` that represent the range `[left, right]`, return *the bitwise AND of all numbers in this range, inclusive*.

**Example 1:**

```
Input: left = 5, right = 7
Output: 4
```

**Example 2:**

```
Input: left = 0, right = 0
Output: 0
```

**Example 3:**

```
Input: left = 1, right = 2147483647
Output: 0 
```

**Constraints:**

* `0 <= left <= right <= 2^31 - 1`

### Solution

#### Approach #0

```go
func rangeBitwiseAnd(left int, right int) int {
    shift := 0
    for left < right {
        left, right = left>>1, right>>1
        shift++
    }
    return left << shift
}
```

#### Approach #1

```go
func rangeBitwiseAnd(left int, right int) int {
    for left < right {
        right &= (right - 1)
    }
    return right
}
```


# 2022-06-14

## [72. Edit Distance](https://leetcode.com/problems/edit-distance/)

### Description

Given two strings `word1` and `word2`, return *the minimum number of operations required to convert `word1` to `word2`*.

You have the following three operations permitted on a word:

* Insert a character
* Delete a character
* Replace a character

**Example 1:**

```
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
```

**Example 2:**

```
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
```

**Constraints:**

* `0 <= word1.length, word2.length <= 500`
* `word1` and `word2` consist of lowercase English letters.

### Solution

#### Approach #0

```go
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := 0; i < m+1; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for i := 0; i < n+1; i++ {
        dp[0][i] = i
    }

    for i := 1; i < m+1; i++ {
        for j := 1; j < n+1; j++ {
            a, b, c := dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]
            if word1[i-1] != word2[j-1] {
                c += 1
            }
            dp[i][j] = min(a, min(b, c))
        }
    }
    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

#### Approach #1

```go
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([]int, n+1)
    for i := 0; i < n+1; i++ {
        dp[i] = i
    }

    var ld int
    for i := 1; i < m+1; i++ {
        ld = dp[0]
        dp[0] = i
        for j := 1; j < n+1; j++ {
            a, b, c := dp[j-1]+1, dp[j]+1, ld
            if word1[i-1] != word2[j-1] {
                c += 1
            }
            ld = dp[j]
            dp[j] = min(a, min(b, c))
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [322. Coin Change](https://leetcode.com/problems/coin-change/)

### Description

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return *the fewest number of coins that you need to make up that amount*. If that amount of money cannot be made up by any combination of the coins, return `-1`.

You may assume that you have an infinite number of each kind of coin.

**Example 1:**

```
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
```

**Example 2:**

```
Input: coins = [2], amount = 3
Output: -1
```

**Example 3:**

```
Input: coins = [1], amount = 0
Output: 0
```

**Constraints:**

* `1 <= coins.length <= 12`
* `1 <= coins[i] <= 2^31 - 1`
* `0 <= amount <= 10^4`

### Solution

#### Approach #0

```go
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i < amount+1; i++ {
        dp[i] = amount + 1
    }
    for i := 1; i <= amount; i++ {
        for _, v := range coins {
            if v <= i {
                dp[i] = min(dp[i], dp[i-v]+1)
            }
        }
    }
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [343. Integer Break](https://leetcode.com/problems/integer-break/)

### Description

Given an integer `n`, break it into the sum of `k` **positive integers**, where `k >= 2`, and maximize the product of those integers.

Return *the maximum product you can get*.

**Example 1:**

```
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
```

**Example 2:**

```
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
```

**Constraints:**

* `2 <= n <= 58`

### Solution

#### Approach #0

```go
func integerBreak(n int) int {
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        var cur int
        for j := 1; j < i; j++ {
            cur = max(cur, max(j*(i-j), j*dp[i-j]))
        }
        dp[i] = cur
    }
    return dp[n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [498. Diagonal Traverse](https://leetcode.com/problems/diagonal-traverse/)

### Description

Given an `m x n` matrix `mat`, return *an array of all the elements of the array in a diagonal order*.

**Example 1:**

![](https://img.content.cc/a/2022/06/14/14-21-57-121-9fb789fa7f0058abb43d383316bbf442-c2a0bc.png)

```
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
```

**Example 2:**

```
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
```

**Constraints:**

* `m == mat.length`
* `n == mat[i].length`
* `1 <= m, n <= 10^4`
* `1 <= m * n <= 10^4`
* `-10^5 <= mat[i][j] <= 10^5`

### Solution

#### Approach #0

```go
func findDiagonalOrder(mat [][]int) []int {
    m, n := len(mat), len(mat[0])
    ans := make([]int, 0, m*n)
    for i := 0; i < m+n-1; i++ {
        if i%2 == 1 {
            x := max(i-n+1, 0)
            y := min(i, n-1)
            for x < m && y >= 0 {
                ans = append(ans, mat[x][y])
                x++
                y--
            }
        } else {
            x := min(i, m-1)
            y := max(i-m+1, 0)
            for x >= 0 && y < n {
                ans = append(ans, mat[x][y])
                x--
                y++
            }
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```


# 2022-06-13

## [1143. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/)

### Description

Given two strings `text1` and `text2`, return *the length of their longest **common subsequence**.* If there is no **common subsequence**, return `0`.

A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

* For example, `"ace"` is a subsequence of `"abcde"`.

A **common subsequence** of two strings is a subsequence that is common to both strings.

**Example 1:**

```
Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.
```

**Example 2:**

```
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
```

**Example 3:**

```
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0. 
```

**Constraints:**

* `1 <= text1.length, text2.length <= 1000`
* `text1` and `text2` consist of only lowercase English characters.

### Solution

#### Approach #0

```go
func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := 0; i < m+1; i++ {
        dp[i] = make([]int, n+1)
    }
    for i, c1 := range text1 {
        for j, c2 := range text2 {
            if c1 == c2 {
                dp[i+1][j+1] = dp[i][j] + 1
            } else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            }
        }
    }
    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [583. Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)

### Description

Given two strings `word1` and `word2`, return *the minimum number of **steps** required to make* `word1` *and* `word2` *the same*.

In one **step**, you can delete exactly one character in either string.

**Example 1:**

```
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
```

**Example 2:**

```
Input: word1 = "leetcode", word2 = "etco"
Output: 4
```

**Constraints:**

* `1 <= word1.length, word2.length <= 500`
* `word1` and `word2` consist of only lowercase English letters.

### Solution

#### Approach #0: Just find the longest common subsequence

```go
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := 0; i < m+1; i++ {
        dp[i] = make([]int, n+1)
    }
    for i, c1 := range word1 {
        for j, c2 := range word2 {
            if c1 == c2 {
                dp[i+1][j+1] = dp[i][j] + 1
            } else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            }
        }
    }
    return m + n - 2*dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

#### Approach #1

```go
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := 0; i < m+1; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0]=i
    }
    for j:=0;j<n+1;j++ {
        dp[0][j]=j
    }
    for i, c1 := range word1 {
        for j, c2 := range word2 {
            if c1 == c2 {
                dp[i+1][j+1] = dp[i][j]
            } else {
                dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j])+1
            }
        }
    }
    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [1051. Height Checker](https://leetcode.com/problems/height-checker/)

### Description

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in **non-decreasing order** by height. Let this ordering be represented by the integer array `expected` where `expected[i]` is the expected height of the `ith` student in line.

You are given an integer array `heights` representing the **current order** that the students are standing in. Each `heights[i]` is the height of the `ith` student in line (**0-indexed**).

Return *the **number of indices** where* `heights[i] != expected[i]`.

**Example 1:**

```
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
heights:  [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.
```

**Example 2:**

```
Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights:  [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.
```

**Example 3:**

```
Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights:  [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.
```

**Constraints:**

* `1 <= heights.length <= 100`
* `1 <= heights[i] <= 100`

### Solution

#### Approach #0

```go
func heightChecker(heights []int) (ans int) {
    expected := append([]int(nil), heights...)
    sort.Ints(expected)
    for i, h := range heights {
        if h != expected[i] {
            ans++
        }
    }
    return
}
```

#### Approach #1

```go
func heightChecker(heights []int) (ans int) {
    cnt := make([]int, 101)
    for _, h := range heights {
        cnt[h]++
    }
    index := 0
    for i, c := range cnt {
        for ; c > 0; c-- {
            if heights[index] != i {
                ans++
            }
            index++
        }
    }
    return
}
```


# 2022-06-12

## [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)

### Description

Given an integer array `nums`, return the length of the longest strictly increasing subsequence.

A **subsequence** is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, `[3,6,2,7]` is a subsequence of the array `[0,3,1,6,2,2,7]`.

**Example 1:**

```
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
```

**Example 2:**

```
Input: nums = [0,1,0,3,2,3]
Output: 4
```

**Example 3:**

```
Input: nums = [7,7,7,7,7,7,7]
Output: 1
```

**Constraints:**

* `1 <= nums.length <= 2500`
* `-10^4 <= nums[i] <= 10^4`

**Follow up:** Can you come up with an algorithm that runs in `O(n log(n))` time complexity?

### Solution

#### Approach #0

```go
func lengthOfLIS(nums []int) (ans int) {
    n := len(nums)
    dp := make([]int, n)
    dp[0] = 1
    ans = 1
    for i := 1; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        ans = max(ans, dp[i])
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [673. Number of Longest Increasing Subsequence](https://leetcode.com/problems/number-of-longest-increasing-subsequence/)

### Description

Given an integer array `nums`, return *the number of longest increasing subsequences.*

**Notice** that the sequence has to be **strictly** increasing.&#x20;

**Example 1:**

```
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
```

**Example 2:**

```
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
```

**Constraints:**

* `1 <= nums.length <= 2000`
* `-10^6 <= nums[i] <= 10^6`

### Solution

#### Approach #0

```go
func findNumberOfLIS(nums []int) (ans int) {
    n := len(nums)
    dp := make([]int, n)
    cnt := make([]int, n)
    maxLen := 0
    for i := 0; i < n; i++ {
        dp[i] = 1
        cnt[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                if dp[j]+1 == dp[i] {
                    cnt[i] += cnt[j]
                }
                if dp[j]+1 > dp[i] {
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j]
                }
            }
        }
        if dp[i] > maxLen {
            maxLen = dp[i]
            ans = cnt[i]
        } else if dp[i] == maxLen {
            ans += cnt[i]
        }
    }
    return
}
```

## [890. Find and Replace Pattern](https://leetcode.com/problems/find-and-replace-pattern/)

### Description

Given a list of strings `words` and a string `pattern`, return *a list of* `words[i]` *that match* `pattern`. You may return the answer in **any order**.

A word matches the pattern if there exists a permutation of letters `p` so that after replacing every letter `x` in the pattern with `p(x)`, we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

**Example 1:**

```
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.
```

**Example 2:**

```
Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"] 
```

**Constraints:**

* `1 <= pattern.length <= 20`
* `1 <= words.length <= 50`
* `words[i].length == pattern.length`
* `pattern` and `words[i]` are lowercase English letters.

### Solution

#### Approach #0

```go
func findAndReplacePattern(words []string, pattern string) (ans []string) {
    if len(pattern) == 1 {
        return words
    }
    for _, word := range words {
        if match(word, pattern) && match(pattern, word) {
            ans = append(ans, word)
        }
    }
    return
}

func match(word, pattern string) bool {
    m := make(map[rune]byte)
    for i, a := range word {
        b := pattern[i]
        if m[a] == 0 {
            m[a] = b
        } else {
            if m[a] != b {
                return false
            }
        }
    }
    return true
}
```


# 2022-06-11

## [91. Decode Ways](https://leetcode.com/problems/decode-ways/)

### Description

A message containing letters from `A-Z` can be **encoded** into numbers using the following mapping:

```
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
```

To **decode** an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"11106"` can be mapped into:

* `"AAJF"` with the grouping `(1 1 10 6)`
* `"KJF"` with the grouping `(11 10 6)`

Note that the grouping `(1 11 06)` is invalid because `"06"` cannot be mapped into `'F'` since `"6"` is different from `"06"`.

Given a string `s` containing only digits, return *the **number** of ways to **decode** it*.

The test cases are generated so that the answer fits in a **32-bit** integer.

**Example 1:**

```
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
```

**Example 2:**

```
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
```

**Example 3:**

```
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
```

**Constraints:**

* `1 <= s.length <= 100`
* `s` contains only digits and may contain leading zero(s).

### Solution

#### Approach #0

```go
func numDecodings(s string) int {
    n := len(s)
    a, b, c := 0, 1, 0
    for i := 1; i <= n; i++ {
        c = 0
        if s[i-1] != '0' {
            c = b
        }
        if i > 1 && s[i-2] != '0' && (s[i-2]-'0')*10+(s[i-1]-'0') <= 26 {
            c += a
        }
        a, b = b, c
    }
    return c
}
```

## [139. Word Break](https://leetcode.com/problems/word-break/)

### Description

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**Example 1:**

```
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
```

**Example 2:**

```
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
```

**Example 3:**

```
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
```

**Constraints:**

* `1 <= s.length <= 300`
* `1 <= wordDict.length <= 1000`
* `1 <= wordDict[i].length <= 20`
* `s` and `wordDict[i]` consist of only lowercase English letters.
* All the strings of `wordDict` are **unique**.

### Solution

#### Approach #0

```go
func wordBreak(s string, wordDict []string) bool {
    m := make(map[string]bool)
    for _, word := range wordDict {
        m[word] = true
    }
    dp := make([]bool, len(s)+1)
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && m[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}
```


# 2022-06-10

## [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)

### Description

Given a string `s`, return *the longest palindromic substring* in `s`.

**Example 1:**

```
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
```

**Example 2:**

```
Input: s = "cbbd"
Output: "bb"
```

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consist of only digits and English letters.

### Solution

#### Approach #0

```go
func longestPalindrome(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }
    dp := make([][]bool, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]bool, n)
        dp[i][i] = true
    }

    maxLen := 1
    start := 0

    for c := 2; c <= n; c++ {
        for i := 0; i < n; i++ {
            j := c + i - 1
            if j >= n {
                break
            }

            if s[i] != s[j] {
                dp[i][j] = false
            } else {
                if j-i < 3 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
            }

            if dp[i][j] && j-i+1 > maxLen {
                maxLen = j - i + 1
                start = i
            }
        }
    }
    return s[start : start+maxLen]
}
```

## [413. Arithmetic Slices](https://leetcode.com/problems/arithmetic-slices/)

### Description

An integer array is called arithmetic if it consists of **at least three elements** and if the difference between any two consecutive elements is the same.

* For example, `[1,3,5,7,9]`, `[7,7,7,7]`, and `[3,-1,-5,-9]` are arithmetic sequences.

Given an integer array `nums`, return *the number of arithmetic **subarrays** of* `nums`.

A **subarray** is a contiguous subsequence of the array.

**Example 1:**

```
Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.
```

**Example 2:**

```
Input: nums = [1]
Output: 0
```

**Constraints:**

* `1 <= nums.length <= 5000`
* `-1000 <= nums[i] <= 1000`

### Solution

#### Approach #0: Too much memory used

```go
func numberOfArithmeticSlices(nums []int) (ans int) {
    n := len(nums)
    if n < 3 {
        return 0
    }
    v := make([]int, n-1)
    for i := 0; i < n-1; i++ {
        v[i] = nums[i+1] - nums[i]
    }

    for c := 3; c <= n; c++ {
        for i := 0; i < n; i++ {
            if i+c > n {
                break
            }
            p := true
            for j := i; j < i+c-2; j++ {
                p = p && v[j] == v[j+1]
                if !p {
                    break
                }
            }
            if p {
                ans++
            }
        }
    }
    return
}
```

#### Approach #1

```go
func numberOfArithmeticSlices(nums []int) (ans int) {
    n := len(nums)
    if n == 1 {
        return
    }
    d, t := nums[1]-nums[0], 0
    for i := 2; i < n; i++ {
        if nums[i]-nums[i-1] == d {
            t++
        } else {
            d, t = nums[i]-nums[i-1], 0
        }
        ans += t
    }
    return
}
```


# 2022-06-09

## [45. Jump Game II](https://leetcode.com/problems/jump-game-ii/)

### Description

Given an array of non-negative integers `nums`, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

**Example 1:**

```
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
```

**Example 2:**

```
Input: nums = [2,3,0,1,4]
Output: 2
```

**Constraints:**

* `1 <= nums.length <= 10^4`
* `0 <= nums[i] <= 1000`

### Solution

#### Approach #0

```go
func jump(nums []int) (ans int) {
    p, maxPos := 0, 0
    for i := 0; i < len(nums)-1; i++ {
        maxPos = max(maxPos, i+nums[i])
        if p == i {
            p = maxPos
            ans++
        }
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}45
```

## [62. Unique Paths](https://leetcode.com/problems/unique-paths/)

### Description

There is a robot on an `m x n` grid. The robot is initially located at the **top-left corner** (i.e., `grid[0][0]`). The robot tries to move to the **bottom-right corner** (i.e., `grid[m - 1][n - 1]`). The robot can only move either down or right at any point in time.

Given the two integers `m` and `n`, return *the number of possible unique paths that the robot can take to reach the bottom-right corner*.

The test cases are generated so that the answer will be less than or equal to `2 * 109`.

**Example 1:**

![](https://img.content.cc/a/2022/06/09/20-24-23-439-fbb03ffaf44b37bc4bd6c377d1d667b9-11a4f1.png)

```
Input: m = 3, n = 7
Output: 28
```

**Example 2:**

```
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
```

**Constraints:**

* `1 <= m, n <= 100`

### Solution

#### Approach #0

```go
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for i := 1; i < n; i++ {
        dp[0][i] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}
```


# 2022-06-08

## [213. House Robber II](https://leetcode.com/problems/house-robber-ii/)

### Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle.** That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array `nums` representing the amount of money of each house, return *the maximum amount of money you can rob tonight **without alerting the police***.

**Example 1:**

```
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
```

**Example 2:**

```
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
```

**Example 3:**

```
Input: nums = [1,2,3]
Output: 3
```

**Constraints:**

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 1000`

### Solution

#### Approach #0

```go
func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    if n == 2 {
        return max(nums[0], nums[1])
    }
    return max(_rob(nums[:n-1]), _rob(nums[1:]))
}

func _rob(nums []int) int {
    first, second := nums[0], max(nums[0], nums[1])
    for _, num := range nums[2:] {
        first, second = second, max(first+num, second)
    }
    return second
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [55. Jump Game](https://leetcode.com/problems/jump-game/)

### Description

You are given an integer array `nums`. You are initially positioned at the array's **first index**, and each element in the array represents your maximum jump length at that position.

Return `true` *if you can reach the last index, or* `false` *otherwise*.

**Example 1:**

```
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
```

**Example 2:**

```
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
```

**Constraints:**

* `1 <= nums.length <= 10^4`
* `0 <= nums[i] <= 10^5`

### Solution

#### Approach #0

```go
func canJump(nums []int) bool {
    right := 0
    for i, num := range nums {
        if i > right {
            return false
        }
        right = max(right, i+num)
        if right >= len(nums)-1 {
            return true
        }
    }
    return false
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [1037. Valid Boomerang](https://leetcode.com/problems/valid-boomerang/)

### Description

Given an array `points` where `points[i] = [xi, yi]` represents a point on the **X-Y** plane, return `true` *if these points are a **boomerang***.

A **boomerang** is a set of three points that are **all distinct** and **not in a straight line**.

**Example 1:**

```
Input: points = [[1,1],[2,3],[3,2]]
Output: true
```

**Example 2:**

```
Input: points = [[1,1],[2,2],[3,3]]
Output: false
```

**Constraints:**

* `points.length == 3`
* `points[i].length == 2`
* `0 <= x[i], y[i] <= 100`

### Solution

#### Approach #0

```go
func isBoomerang(points [][]int) bool {
    v1 := [2]int{points[1][0] - points[0][0], points[1][1] - points[0][1]}
    v2 := [2]int{points[2][0] - points[1][0], points[2][1] - points[1][1]}
    return v1[0]*v2[1]-v2[0]*v1[1] != 0
}
```


# 2022-06-07

## [17. Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)

### Description

Given a string containing digits from `2-9` inclusive, return all possible letter combinations that the number could represent. Return the answer in **any order**.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

![](https://img.content.cc/a/2022/06/07/13-29-24-602-b197f2cad4c616b374b89c2ed0444780-b2acd8.png)

**Example 1:**

```
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
```

**Example 2:**

```
Input: digits = ""
Output: []
```

**Example 3:**

```
Input: digits = "2"
Output: ["a","b","c"]
```

**Constraints:**

* `0 <= digits.length <= 4`
* `digits[i]` is a digit in the range `['2', '9']`.

### Solution

#### Approach #0

```go
var keyboard = map[byte]string {
    '2':"abc",
    '3':"def",
    '4':"ghi",
    '5':"jkl",
    '6':"mno",
    '7':"pqrs",
    '8':"tuv",
    '9':"wxyz",
}
func letterCombinations(digits string) (ans []string) {
    n:=len(digits)
    if n==0 {
        return
    }
    var b func(cur int, str string)
    b=func(cur int, str string) {
        if cur==n {
            ans = append(ans, str)
            return
        }
        for _, ch := range keyboard[digits[cur]] {
            b(cur+1, str+string(ch))
        }
    }
    b(0,"")
    return
}
```

## [22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)

### Description

Given `n` pairs of parentheses, write a function to *generate all combinations of well-formed parentheses*.

**Example 1:**

```
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
```

**Example 2:**

```
Input: n = 1
Output: ["()"]
```

**Constraints:**

* `1 <= n <= 8`

### Solution

#### Approach #0

```go
func generateParenthesis(n int) (ans []string) {
    var tmp []byte
    var b func(left, right int)
    b = func(left, right int) {
        if len(tmp) == n*2 {
            ans = append(ans, string(tmp))
            return
        }
        if left < n {
            tmp = append(tmp, '(')
            b(left+1, right)
            tmp = tmp[:len(tmp)-1]
        }
        if right < left {
            tmp = append(tmp, ')')
            b(left, right+1)
            tmp = tmp[:len(tmp)-1]
        }
    }
    b(0, 0)
    return
}
```

## [79. Word Search](https://leetcode.com/problems/word-search/)

### Description

Given an `m x n` grid of characters `board` and a string `word`, return `true` *if* `word` *exists in the grid*.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

**Example 1:**

![](https://img.content.cc/a/2022/06/07/14-13-19-918-ab76dd0b1a371e0c27351ea17d1fdc75-b5aa49.png)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
```

**Example 2:**

![](https://img.content.cc/a/2022/06/07/14-13-35-465-1cfbb079ff914b5b58e7b49de59b55cf-046f8c.png)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
```

**Example 3:**

![](https://img.content.cc/a/2022/06/07/14-13-47-964-34311952a774f4e210dd93c176874bfc-edccd0.png)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

**Constraints:**

* `m == board.length`
* `n = board[i].length`
* `1 <= m, n <= 6`
* `1 <= word.length <= 15`
* `board` and `word` consists of only lowercase and uppercase English letters.

**Follow up:** Could you use search pruning to make your solution faster with a larger `board`?

### Solution

#### Approach #0

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    vis := make([][]bool, m)
    for i := range vis {
        vis[i] = make([]bool, n)
    }
    var b func(x, y, index int) bool
    b = func(x, y, index int) bool {
        if board[x][y] != word[index] {
            return false
        }
        if index == len(word)-1 {
            return true
        }
        vis[x][y] = true
        defer func() { vis[x][y] = false }()
        for i := 0; i < 4; i++ {
            xx, yy := x+dx[i], y+dy[i]
            if xx >= 0 && xx < m && yy >= 0 && yy < n && !vis[xx][yy] {
                if b(xx, yy, index+1) {
                    return true
                }
            }
        }
        return false
    }
    for i, row := range board {
        for j := range row {
            if b(i, j, 0) {
                return true
            }
        }
    }
    return false
}
```


# 2022-06-06

## [47. Permutations II](https://leetcode.com/problems/permutations-ii/)

### Description

Given a collection of numbers, `nums`, that might contain duplicates, return *all possible unique permutations **in any order**.*

**Example 1:**

```
Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
```

**Example 2:**

```
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```

**Constraints:**

* `1 <= nums.length <= 8`
* `-10 <= nums[i] <= 10`

### Solution

#### Approach #0

```go
func permuteUnique(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    vis := make([]bool, len(nums))
    var tmp []int
    var backtrack func(int)
    backtrack = func(cur int) {
        if cur == n {
            ans = append(ans, append([]int(nil), tmp...))
            return
        }
        for i, num := range nums {
            if vis[i] || i > 0 && !vis[i-1] && nums[i-1] == num {
                continue
            }
            vis[i] = true
            tmp = append(tmp, num)
            backtrack(cur + 1)
            tmp = tmp[:len(tmp)-1]
            vis[i] = false
        }
    }
    backtrack(0)
    return
}
```

## [39. Combination Sum](https://leetcode.com/problems/combination-sum/)

### Description

Given an array of **distinct** integers `candidates` and a target integer `target`, return *a list of all **unique combinations** of* `candidates` *where the chosen numbers sum to* `target`*.* You may return the combinations in **any order**.

The **same** number may be chosen from `candidates` an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is **guaranteed** that the number of unique combinations that sum up to `target` is less than `150` combinations for the given input.

**Example 1:**

```
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
```

**Example 2:**

```
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
```

**Example 3:**

```
Input: candidates = [2], target = 1
Output: []
```

**Constraints:**

* `1 <= candidates.length <= 30`
* `1 <= candidates[i] <= 200`
* All elements of `candidates` are **distinct**.
* `1 <= target <= 500`

### Solution

#### Approach #0

```go
func combinationSum(candidates []int, target int) (ans [][]int) {
    sort.Ints(candidates)
    n := len(candidates)
    var t []int
    var backtrack func(cur, index int)
    backtrack = func(cur, index int) {
        if cur == target {
            ans = append(ans, append([]int(nil), t...))
            return
        }
        if cur > target {
            return
        }
        for i := index; i < n; i++ {
            t = append(t, candidates[i])
            backtrack(cur+candidates[i], i)
            t = t[:len(t)-1]
        }
    }
    backtrack(0, 0)
    return
}
```

## [40. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/)

### Description

Given a collection of candidate numbers (`candidates`) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sum to `target`.

Each number in `candidates` may only be used **once** in the combination.

**Note:** The solution set must not contain duplicate combinations.

**Example 1:**

```
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
```

**Example 2:**

```
Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]
```

**Constraints:**

* `1 <= candidates.length <= 100`
* `1 <= candidates[i] <= 50`
* `1 <= target <= 30`

### Solution

#### Approach #0

```go
func combinationSum2(candidates []int, target int) (ans [][]int) {
    sort.Ints(candidates)
    n := len(candidates)
    vis := make([]bool, n)
    var t []int
    var backtrack func(index, cur int)
    backtrack = func(index, cur int) {
        if cur == target {
            ans = append(ans, append([]int(nil), t...))
            return
        }
        if cur > target {
            return
        }
        for i := index; i < n; i++ {
            if i > 0 && !vis[i-1] && candidates[i-1] == candidates[i] {
                continue
            }
            t = append(t, candidates[i])
            vis[i] = true
            backtrack(i+1, cur+candidates[i])
            vis[i] = false
            t = t[:len(t)-1]
        }
    }
    backtrack(0, 0)
    return
}
```


# 2022-06-05

## [78. Subsets](https://leetcode.com/problems/subsets/)

### Description

Given an integer array `nums` of **unique** elements, return *all possible subsets (the power set)*.

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

```
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

**Example 2:**

```
Input: nums = [0]
Output: [[],[0]]
```

**Constraints:**

* `1 <= nums.length <= 10`
* `-10 <= nums[i] <= 10`
* All the numbers of `nums` are **unique**.

### Solution

#### Approach #0

```go
func subsets(nums []int) (ans [][]int) {
    n := len(nums)
    for p := 0; p < 1<<n; p++ {
        var a []int
        for i, num := range nums {
            if p>>i&1 > 0 {
                a = append(a, num)
            }
        }
        ans = append(ans, a)
    }
    return
}
```

#### Approach #1

```go
func subsets(nums []int) (ans [][]int) {
    n := len(nums)
    var tmp []int
    var dfs func(int)
    dfs = func(cur int) {
        if cur == n {
            ans = append(ans, append([]int(nil), tmp...))
            return
        }
        tmp = append(tmp, nums[cur])
        dfs(cur + 1)
        tmp = tmp[:len(tmp)-1]
        dfs(cur + 1)
    }
    dfs(0)
    return
}
```

## [90. Subsets II](https://leetcode.com/problems/subsets-ii/)

### Description

Given an integer array `nums` that may contain duplicates, return *all possible subsets (the power set)*.

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

```
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
```

**Example 2:**

```
Input: nums = [0]
Output: [[],[0]]
```

**Constraints:**

* `1 <= nums.length <= 10`
* `-10 <= nums[i] <= 10`

### Solution

#### Approach #0

```go
func subsetsWithDup(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
outer:
    for p := 0; p < 1<<n; p++ {
        var a []int
        for i, num := range nums {

            if p>>i&1 > 0 {
                if i > 0 && p>>(i-1)&1 == 0 && nums[i-1] == num {
                    continue outer
                }
                a = append(a, num)
            }

        }
        ans = append(ans, append([]int(nil), a...))
    }
    return
}
```

#### Approach #1

```go
func subsetsWithDup(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    var tmp []int
    var dfs func(bool, int)
    dfs = func(choosePre bool, cur int) {
        if cur == n {
            ans = append(ans, append([]int(nil), tmp...))
            return
        }
        dfs(false, cur+1)
        if !choosePre && cur > 0 && nums[cur-1] == nums[cur] {
            return
        }
        tmp = append(tmp, nums[cur])
        dfs(true, cur+1)
        tmp = tmp[:len(tmp)-1]
    }
    dfs(false, 0)
    return
}
```


# 2022-06-04

## [1091. Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/)

### Description

Given an `n x n` binary matrix `grid`, return *the length of the shortest **clear path** in the matrix*. If there is no clear path, return `-1`.

A **clear path** in a binary matrix is a path from the **top-left** cell (i.e., `(0, 0)`) to the **bottom-right** cell (i.e., `(n - 1, n - 1)`) such that:

* All the visited cells of the path are `0`.
* All the adjacent cells of the path are **8-directionally** connected (i.e., they are different and they share an edge or a corner).

The **length of a clear path** is the number of visited cells of this path.

**Example 1:**

![](https://img.content.cc/a/2022/06/04/10-03-09-028-6ffef4b29ebb3a0d845822ebfbe7239b-76bd2a.png)

```
Input: grid = [[0,1],[1,0]]
Output: 2
```

**Example 2:**

![](https://img.content.cc/a/2022/06/04/10-03-26-219-114abb4aa73b0dc42d5dd0ab459a8603-207c64.png)

```
Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
```

**Example 3:**

```
Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
```

**Constraints:**

* `n == grid.length`
* `n == grid[i].length`
* `1 <= n <= 100`
* `grid[i][j] is 0 or 1`

### Solution

#### Approach #0

```go
var (
    dx = []int{-1, -1, -1, 0, 1, 1, 1, 0}
    dy = []int{-1, 0, 1, 1, 1, 0, -1, -1}
)

func shortestPathBinaryMatrix(grid [][]int) int {
    if grid[0][0] == 1 {
        return -1
    }
    m, n := len(grid), len(grid[0])
    if m == 1 && n == 1 && grid[0][0] == 0 {
        return 1
    }
    queue := [][]int{{0, 0}}
    depth := 1
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            x, y := queue[i][0], queue[i][1]
            for j := 0; j < 8; j++ {
                xx, yy := x+dx[j], y+dy[j]
                if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 0 {
                    if xx == m-1 && yy == n-1 {
                        return depth + 1
                    }
                    grid[xx][yy] = 1
                    queue = append(queue, []int{xx, yy})
                }
            }
        }
        queue = queue[size:]
        depth += 1
    }
    return -1
}
```

## [130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)

### Description

Given an `m x n` matrix `board` containing `'X'` and `'O'`, *capture all regions that are 4-directionally surrounded by* `'X'`.

A region is **captured** by flipping all `'O'`s into `'X'`s in that surrounded region.

**Example 1:**

![](https://img.content.cc/a/2022/06/04/15-49-29-287-33613919125e92a385ea8d9b4e7e339a-01179b.jpeg)

```
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
```

**Example 2:**

```
Input: board = [["X"]]
Output: [["X"]] 
```

**Constraints:**

* `m == board.length`
* `n == board[i].length`
* `1 <= m, n <= 200`
* `board[i][j]` is `'X'` or `'O'`.

### Solution

#### Approach #0: BFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func solve(board [][]byte) {
    m, n := len(board), len(board[0])
    var queue [][]int
    for i := 0; i < n; i++ {
        if board[0][i] != 'X' {
            board[0][i] = '-'
            queue = append(queue, []int{0, i})
        }
        if board[m-1][i] != 'X' {
            board[m-1][i] = '-'
            queue = append(queue, []int{m - 1, i})
        }
    }
    for i := 1; i < m-1; i++ {
        if board[i][0] != 'X' {
            board[i][0] = '-'
            queue = append(queue, []int{i, 0})
        }
        if board[i][n-1] != 'X' {
            board[i][n-1] = '-'
            queue = append(queue, []int{i, n - 1})
        }
    }
    for len(queue) > 0 {
        x, y := queue[0][0], queue[0][1]
        queue = queue[1:]
        for i := 0; i < 4; i++ {
            xx, yy := x+dx[i], y+dy[i]
            if xx >= 0 && xx < m && yy >= 0 && yy < n && board[xx][yy] == 'O' {
                queue = append(queue, []int{xx, yy})
                board[xx][yy] = '-'
            }
        }
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == '-' {
                board[i][j] = 'O'
            } else {
                board[i][j] = 'X'
            }
        }
    }
}
```

#### Approach #1: DFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func solve(board [][]byte) {
    m, n := len(board), len(board[0])
    var dfs func(board [][]byte, x, y int)
    dfs = func(board [][]byte, x, y int) {
        if x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O' {
            return
        }
        board[x][y] = '-'
        for i := 0; i < 4; i++ {
            xx, yy := x+dx[i], y+dy[i]
            dfs(board, xx, yy)
        }
    }
    for i := 0; i < n; i++ {
        dfs(board, 0, i)
        dfs(board, m-1, i)
    }
    for i := 1; i < m-1; i++ {
        dfs(board, i, 0)
        dfs(board, i, n-1)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == '-' {
                board[i][j] = 'O'
            } else {
                board[i][j] = 'X'
            }
        }
    }
}


```

## [797. All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/)

### Description

Given a directed acyclic graph (**DAG**) of `n` nodes labeled from `0` to `n - 1`, find all possible paths from node `0` to node `n - 1` and return them in **any order**.

The graph is given as follows: `graph[i]` is a list of all nodes you can visit from node `i` (i.e., there is a directed edge from node `i` to node `graph[i][j]`).&#x20;

**Example 1:**

![](https://img.content.cc/a/2022/06/04/15-49-50-789-4c89521e939db09aa9f0e87c65fec2ff-2b6834.jpeg)

```
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
```

**Example 2:**

![](https://img.content.cc/a/2022/06/04/15-50-06-395-447710b4ce98179a2c5048b119c2efe6-d8d29d.jpeg)

```
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
```

**Constraints:**

* `n == graph.length`
* `2 <= n <= 15`
* `0 <= graph[i][j] < n`
* `graph[i][j] != i` (i.e., there will be no self-loops).
* All the elements of `graph[i]` are **unique**.
* The input graph is **guaranteed** to be a **DAG**.

### Solution

#### Approach #0: DFS

```go
func allPathsSourceTarget(graph [][]int) (ans [][]int) {
    n:=len(graph)
    
    var dfs func(index int, cur []int)
    dfs = func(index int, cur []int) {
        cur=append(cur, index)
        for _,i:=range graph[index] {
            if i+1==n {
                c:=make([]int,len(cur))
                copy(c,cur)
                c=append(c,i)
                ans=append(ans,c)
                continue
            }
            dfs(i,cur)
        }
    }
    var cur []int
    dfs(0,cur)
    return
}
```

#### Approach #1: BFS

```go
func allPathsSourceTarget(graph [][]int) (ans [][]int) {
    n := len(graph)
    queue := [][]int{{0}}
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            l := queue[i]
            last := len(l) - 1
            if l[last] == n-1 {
                a := make([]int, len(l))
                copy(a, l)
                ans = append(ans, a)
                continue
            }
            for _, e := range graph[l[last]] {
                a := make([]int, len(l))
                copy(a, l)
                a = append(a, e)
                queue = append(queue, a)
            }
        }
        queue = queue[size:]
    }
    return
}
```


# 2022-06-03

## [117. Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)

### Description

Given a binary tree

```
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
```

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

**Example 1:**

![](https://img.content.cc/a/2022/06/03/10-01-15-281-099321a3abf9e1118186bb2b101338c9-2bafb8.png)

```
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
```

**Example 2:**

```
Input: root = []
Output: []
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 6000]`.
* `-100 <= Node.val <= 100`

**Follow-up:**

* You may only use constant extra space.
* The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

### Solution

#### Approach #0

```go
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    var pre *Node
    queue := []*Node{root}
    for len(queue) > 0 {
        size := len(queue)
        pre = nil
        for i := 0; i < size; i++ {
            cell := queue[i]
            if pre != nil {
                pre.Next = cell
            }
            pre = cell
            if cell.Left != nil {
                queue = append(queue, cell.Left)
            }
            if cell.Right != nil {
                queue = append(queue, cell.Right)
            }
        }
        queue = queue[size:]
    }
    return root
}
```

#### Approach #1

```go
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    start := root
    for start != nil {
        var nextStart, pre *Node
        handle := func(cur *Node) {
            if cur == nil {
                return
            }
            if nextStart == nil {
                nextStart = cur
            }
            if pre != nil {
                pre.Next = cur
            }
            pre = cur
        }
        for p := start; p != nil; p = p.Next {
            handle(p.Left)
            handle(p.Right)
        }
        start = nextStart
    }
    return root
}
```

## [572. Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/)

### Description

Given the roots of two binary trees `root` and `subRoot`, return `true` if there is a subtree of `root` with the same structure and node values of `subRoot` and `false` otherwise.

A subtree of a binary tree `tree` is a tree that consists of a node in `tree` and all of this node's descendants. The tree `tree` could also be considered as a subtree of itself.&#x20;

**Example 1:**

![](https://img.content.cc/a/2022/06/03/10-04-50-538-ec0f6cde6f335ed28ebbb11449663bc8-d31652.jpeg)

```
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
```

**Example 2:**

![](https://img.content.cc/a/2022/06/03/10-05-05-860-9ceb9c50bbeae84f1b37f98b2c54f152-14c1fb.jpeg)

```
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
```

**Constraints:**

* The number of nodes in the `root` tree is in the range `[1, 2000]`.
* The number of nodes in the `subRoot` tree is in the range `[1, 1000]`.
* `-10^4 <= root.val <= 10^4`
* `-10^4 <= subRoot.val <= 10^4`

### Solution

#### Approach #0

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return false
    }
    return cmp(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)

}

func cmp(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil && subRoot == nil {
        return true
    }
    if root == nil || subRoot == nil {
        return false
    }
    if root.Val == subRoot.Val {
        return cmp(root.Left, subRoot.Left) && cmp(root.Right, subRoot.Right)
    }
    return false
}
```


# 2022-06-02

## [200. Number of Islands](https://leetcode.com/problems/number-of-islands/)

### Description

Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return *the number of islands*.

An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

**Example 1:**

```
Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
```

**Example 2:**

```
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
```

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 300`
* `grid[i][j]` is `'0'` or `'1'`.

### Solution

#### Approach #0: BFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func numIslands(grid [][]byte) (ans int) {
    if len(grid) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])
    var queue [][]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '0' {
                continue
            }
            ans++
            queue = append(queue, []int{i, j})
            for len(queue) > 0 {
                x, y := queue[0][0], queue[0][1]
                queue = queue[1:]
                if grid[x][y] == '0' {
                    continue
                }
                grid[x][y] = '0'
                for k := 0; k < 4; k++ {
                    xx, yy := x+dx[k], y+dy[k]
                    if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] > '0' {
                        queue = append(queue, []int{xx, yy})
                    }
                }
            }
        }
    }
    return ans
}
```

#### Approach #1: DFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func numIslands(grid [][]byte) (ans int) {
    if len(grid) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])
    var dfs func(x, y int)
    dfs = func(x, y int) {
        if grid[x][y] == '0' {
            return
        }
        grid[x][y] = '0'
        for i := 0; i < 4; i++ {
            xx, yy := x+dx[i], y+dy[i]
            if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] > '0' {
                dfs(xx, yy)
            }
        }
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '0' {
                continue
            }
            ans++
            dfs(i, j)
        }
    }
    return ans
}
```

## [547. Number of Provinces](https://leetcode.com/problems/number-of-provinces/)

### Description

There are `n` cities. Some of them are connected, while some are not. If city `a` is connected directly with city `b`, and city `b` is connected directly with city `c`, then city `a` is connected indirectly with city `c`.

A **province** is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an `n x n` matrix `isConnected` where `isConnected[i][j] = 1` if the `ith` city and the `jth` city are directly connected, and `isConnected[i][j] = 0` otherwise.

Return *the total number of **provinces***.

**Example 1:**

![](https://img.content.cc/a/2022/06/02/11-25-17-523-314bbc33f9978523cac2568f40a62823-9812a9.jpeg)

```
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
```

**Example 2:**

![](https://img.content.cc/a/2022/06/02/11-26-45-058-5d71df9065d2692b588c3876300432bc-551a9a.jpeg)

```
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3 
```

**Constraints:**

* `1 <= n <= 200`
* `n == isConnected.length`
* `n == isConnected[i].length`
* `isConnected[i][j]` is `1` or `0`.
* `isConnected[i][i] == 1`
* `isConnected[i][j] == isConnected[j][i]`

### Solution

#### Approach #0

```go
func findCircleNum(isConnected [][]int) (ans int) {
    if len(isConnected) == 0 {
        return 0
    }
    m := len(isConnected)
    var dfs func(x, y int)
    dfs = func(x, y int) {
        for i := 0; i < m; i++ {
            if isConnected[y][i] == 0 {
                continue
            }
            isConnected[y][i] = 0
            if isConnected[i][y] > 0 {
                dfs(y, i)
            }
        }
    }
    for i := 0; i < m; i++ {
        for j := 0; j < m; j++ {
            if isConnected[i][j] == 0 {
                continue
            }
            ans++
            if isConnected[j][i] > 0 {
                dfs(i, j)
            }
        }
    }
    return ans
}
```

#### Approach #1

```go
func findCircleNum(isConnected [][]int) (ans int) {
    if len(isConnected) == 0 {
        return 0
    }
    m := len(isConnected)
    vis := make([]bool, m)
    var queue []int
    for i, ok := range vis {
        if !ok {
            ans++
            queue = append(queue, i)
            for len(queue) > 0 {
                j := queue[0]
                vis[j] = true
                queue = queue[1:]
                for k := 0; k < m; k++ {
                    if isConnected[j][k] == 1 && !vis[k] {
                        queue = append(queue, k)
                    }
                }
            }
        }
    }
    return ans
}
```

## [450. Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/)

### Description

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

**Example 1:**

![](https://img.content.cc/a/2022/06/02/14-45-40-503-b016522688b499cfdd953d6ddfb1f730-e0dcb2.jpeg)

```
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
```

**Example 2:**

```
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.
```

**Example 3:**

```
Input: root = [], key = 0
Output: []
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 10^4]`.
* `-10^5 <= Node.val <= 10^5`
* Each node has a **unique** value.
* `root` is a valid binary search tree.
* `-10^5 <= key <= 10^5`&#x20;

**Follow up:** Could you solve it with time complexity `O(height of tree)`?

### Solution

#### Approach #0

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    var pre *TreeNode
    cur := root
    for cur != nil {
        if cur.Val == key {
            if cur.Left == nil {
                if cur == root {
                    return root.Right
                }
                if pre.Val > cur.Val {
                    pre.Left = cur.Right
                } else {
                    pre.Right = cur.Right
                }
                return root
            }
            if cur.Right == nil {
                if cur == root {
                    return root.Left
                }
                if pre.Val > cur.Val {
                    pre.Left = cur.Left
                } else {
                    pre.Right = cur.Left
                }
                return root
            }
            target := cur
            pre = cur
            cur = cur.Right
            for cur.Left != nil {
                pre = cur
                cur = cur.Left
            }
            if pre.Val > cur.Val {
                pre.Left = cur.Right
            } else {
                pre.Right = cur.Right
            }
            target.Val = cur.Val
            return root
        }
        pre = cur
        if cur.Val > key {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    return root
}
```

#### Approach #1: **Recursive**

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    switch {
    case root == nil:
        return nil
    case root.Val > key:
        root.Left = deleteNode(root.Left, key)
    case root.Val < key:
        root.Right = deleteNode(root.Right, key)
    case root.Left == nil:
        return root.Right
    case root.Right == nil:
        return root.Left
    default:
        cur := root.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        cur.Right = deleteNode(root.Right, cur.Val)
        cur.Left = root.Left
        return cur
    }
    return root
}
```


# 2022-06-01

## [438. Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/)

### Description

Given two strings `s` and `p`, return *an array of all the start indices of* `p`*'s anagrams in* `s`. You may return the answer in **any order**.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

**Example 1:**

```
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
```

**Example 2:**

```
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
```

**Constraints:**

* `1 <= s.length, p.length <= 3 * 104`
* `s` and `p` consist of lowercase English letters.

### Solution

#### Approach #0

```go
func findAnagrams(s string, p string) (ans []int) {
    target, current := make([]int, 26), make([]int, 26)
    count := 0
    for _, ch := range p {
        target[ch-'a']++
    }
    for _, t := range target {
        if t != 0 {
            count++
        }
    }
    i, j, sig := 0, 0, 0
    for j < len(s) {
        in := s[j] - 'a'
        j++
        if target[in] > 0 {
            current[in]++
            if target[in] == current[in] {
                sig++
            }
        }
        for j-i >= len(p) {
            if sig == count {
                ans = append(ans, i)
            }
            out := s[i] - 'a'
            i++
            if target[out] > 0 {
                if current[out] == target[out] {
                    sig--
                }
                current[out]--
            }
        }
    }
    return ans
}
```

## [713. Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/)

### Description

Given an array of integers `nums` and an integer `k`, return *the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than* `k`.

**Example 1:**

```
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
```

**Example 2:**

```
Input: nums = [1,2,3], k = 0
Output: 0
```

**Constraints:**

* `1 <= nums.length <= 3 * 10^4`
* `1 <= nums[i] <= 1000`
* `0 <= k <= 10^6`

### Solution

#### Approach #0

```go
func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
    cur := 1
    i, j := 0, 0
    for i < len(nums) {
        if j >= len(nums) {
            cur = 1
            i++
            j = i
            continue
        }
        in := nums[j]
        if cur*in < k {
            ans++
            cur = cur * in
            j++
        } else {
            cur = 1
            i++
            j = i
        }
    }
    return ans
}
```

#### Approach #1

```go
func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
    i, cur := 0, 1
    for j, num := range nums {
        cur *= num
        for ; i <= j && cur >= k; i++ {
            cur /= nums[i]
        }
        ans += j - i + 1
    }
    return
}
```

## [209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)

### Description

Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a **contiguous subarray** `[numsl, numsl+1, ..., numsr-1, numsr]` of which the sum is greater than or equal to `target`. If there is no such subarray, return `0` instead.

**Example 1:**

```
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
```

**Example 2:**

```
Input: target = 4, nums = [1,4,4]
Output: 1
```

**Example 3:**

```
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
```

**Constraints:**

* `1 <= target <= 10^9`
* `1 <= nums.length <= 10^5`
* `1 <= nums[i] <= 10^5`

**Follow up:** If you have figured out the `O(n)` solution, try coding another solution of which the time complexity is `O(n log(n))`.

### Solution

#### Approach #0

```go
func minSubArrayLen(target int, nums []int) (ans int) {
    ans = len(nums) + 1
    i, cur := 0, 0
    for j, num := range nums {
        cur += num
        for ; i <= j && cur >= target; i++ {
            if cur >= target {
                ans = min(ans, j-i+1)
            }
            cur -= nums[i]
        }
    }
    if ans == len(nums)+1 {
        ans = 0
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```


# 05


# 2022-05-31

## [844. Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/)

### Description

Given two strings `s` and `t`, return `true` *if they are equal when both are typed into empty text editors*. `'#'` means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

**Example 1:**

```
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".
```

**Example 2:**

```
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".
```

**Example 3:**

```
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".
```

**Constraints:**

* `1 <= s.length, t.length <= 200`
* `s` and `t` only contain lowercase letters and `'#'` characters.&#x20;

**Follow up:** Can you solve it in `O(n)` time and `O(1)` space?

### Solution

#### Approach #0

```go
func backspaceCompare(s string, t string) bool {
    m, n := len(s), len(t)
    i, j := m-1, n-1
    for i >= 0 || j >= 0 {
        i, j = goBack(s, i), goBack(t, j)
        if i >= 0 && j >= 0 && s[i] != t[j] {
            return false
        }
        i--
        j--
    }
    return i == j
}

func goBack(s string, i int) int {
    count := 0
    j := i
    for j >= 0 && (s[j] == '#' || count > 0) {
        if s[j] != '#' {
            count--
        } else {
            count++
        }
        j--
    }
    return j
}
```

#### Approach #1

```go
func backspaceCompare(s string, t string) bool {
    return build(s) == build(t)
}

func build(s string) string {
    var st []rune
    for _, ch := range s {
        if ch == '#' {
            n := len(st)
            if n > 0 {
                st = st[:n-1]
            }
        } else {
            st = append(st, ch)
        }
    }
    return string(st)
}
```

## [986. Interval List Intersections](https://leetcode.com/problems/interval-list-intersections/)

### Description

You are given two lists of closed intervals, `firstList` and `secondList`, where `firstList[i] = [start[i], end[i]]` and `secondList[j] = [start[j], end[j]]`. Each list of intervals is pairwise **disjoint** and in **sorted order**.

Return *the intersection of these two interval lists*.

A **closed interval** `[a, b]` (with `a <= b`) denotes the set of real numbers `x` with `a <= x <= b`.

The **intersection** of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of `[1, 3]` and `[2, 4]` is `[2, 3]`.

**Example 1:**

![](https://img.content.cc/a/2022/05/31/08-42-02-011-cc562333c497dcf782c38a52753cc7cd-286873.png)

```
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
```

**Example 2:**

```
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
```

**Constraints:**

* `0 <= firstList.length, secondList.length <= 1000`
* `firstList.length + secondList.length >= 1`
* `0 <= start[i] < end[i] <= 10^9`
* `end[i] < start[i+1]`
* `0 <= start[j] < end[j] <= 10^9`
* `end[j] < start[j+1]`

### Solution

#### Approach #0

```go
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    i, j := 0, 0
    m, n := len(firstList), len(secondList)
    var ans [][]int
    for i < m && j < n {
        a1, b1 := firstList[i][0], firstList[i][1]
        a2, b2 := secondList[j][0], secondList[j][1]
        if a1 <= b2 && b1 >= a2 {
            x, y := a1, b2
            if a1 <= a2 {
                x = a2
            }
            if b1 <= b2 {
                y = b1
            }
            ans = append(ans, []int{x, y})
        }
        if b1 < b2 {
            i++
        } else {
            j++
        }
    }
    return ans
}
```

#### Approach #1

```go
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    i, j := 0, 0
    var ans [][]int
    for i < len(firstList) && j < len(secondList) {
        low := max(firstList[i][0], secondList[j][0])
        high := min(firstList[i][1], secondList[j][1])
        if low <= high {
            ans = append(ans, []int{low, high})
        }
        if firstList[i][1] < secondList[j][1] {
            i++
        } else {
            j++
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)

### Description

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `ith` line are `(i, 0)` and `(i, height[i])`.

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return *the maximum amount of water a container can store*.

**Notice** that you may not slant the container.

**Example 1:**

![](https://img.content.cc/a/2022/05/31/08-43-53-733-9daebb6ebbdb925763fbd31e9a7aa329-db83c2.jpeg)

```
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
```

**Example 2:**

```
Input: height = [1,1]
Output: 1
```

**Constraints:**

* `n == height.length`
* `2 <= n <= 10^5`
* `0 <= height[i] <= 10^4`

### Solution

#### Approach #0

```go
func maxArea(height []int) int {
    n := len(height)
    i, j := 0, n-1
    var ans int
    for i < j {
        ans = max(ans, (j-i)*min(height[i], height[j]))
        if height[i] < height[j] {
            i++
        } else {
            j--
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```


# 2022-05-30

## [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

### Description

Given the `head` of a sorted linked list, *delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list*. Return *the linked list **sorted** as well*.

**Example 1:**

![](https://img.content.cc/a/2022/05/30/09-39-04-987-660f952a3b16aa11de97081f306cf666-c03202.jpeg)

```
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
```

**Example 2:**

![](https://img.content.cc/a/2022/05/30/09-39-20-908-e5ea2dae9e9a33fea2ef4d8acf2289a0-c8e5e7.jpeg)

```
Input: head = [1,1,1,2,3]
Output: [2,3]
```

**Constraints:**

* The number of nodes in the list is in the range `[0, 300]`.
* `-100 <= Node.val <= 100`
* The list is guaranteed to be **sorted** in ascending order.

### Solution

#### Approach #0

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    return dfs(head, -101)
}

func dfs(cur *ListNode, val int) *ListNode {
    if cur == nil {
        return nil
    }
    if cur.Val == val || (cur.Next != nil && cur.Next.Val == cur.Val) {
        return dfs(cur.Next, cur.Val)
    }
    cur.Next = dfs(cur.Next, cur.Val)
    return cur
}
```

#### Approach #1

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    newHead := &ListNode{Next: head}
    cur := newHead
    for cur.Next != nil && cur.Next.Next != nil {
        if cur.Next.Val == cur.Next.Next.Val {
            v := cur.Next.Val
            for cur.Next != nil && cur.Next.Val == v {
                cur.Next = cur.Next.Next
            }
        } else {
            cur = cur.Next
        }
    }
    return newHead.Next
}
```

## [15. 3Sum](https://leetcode.com/problems/3sum/)

### Description

Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`.

Notice that the solution set must not contain duplicate triplets.

**Example 1:**

```
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
```

**Example 2:**

```
Input: nums = []
Output: []
```

**Example 3:**

```
Input: nums = [0]
Output: [] 
```

**Constraints:**

* `0 <= nums.length <= 3000`
* `-10^5 <= nums[i] <= 10^5`

### Solution

#### Approach #0

```go
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    var res [][]int
    for i := 0; i < n; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        k := n - 1
        for j := i + 1; j < n; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            for j < k && nums[i]+nums[j]+nums[k] > 0 {
                k--
            }
            if j == k {
                break
            }
            if nums[i]+nums[j]+nums[k] == 0 {
                res = append(res, []int{nums[i], nums[j], nums[k]})
            }
        }
    }
    return res
}
```

## [1022. Sum of Root To Leaf Binary Numbers](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/)

### Description

You are given the `root` of a binary tree where each node has a value `0` or `1`. Each root-to-leaf path represents a binary number starting with the most significant bit.

* For example, if the path is `0 -> 1 -> 1 -> 0 -> 1`, then this could represent `01101` in binary, which is `13`.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return *the sum of these numbers*.

The test cases are generated so that the answer fits in a **32-bits** integer.

**Example 1:**

![](https://img.content.cc/a/2022/05/30/14-30-21-934-36029c6aea051f3a535267cd23ce9342-6f931c.png)

```
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
```

**Example 2:**

```
Input: root = [0]
Output: 0 
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 1000]`.
* `Node.val` is `0` or `1`.

### Solution

#### Approach #0

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    return sum(root, 0)
}

func sum(node *TreeNode, num int) int {
    if node.Left != nil && node.Right != nil {
        return sum(node.Left, num<<1+node.Val) + sum(node.Right, num<<1+node.Val)
    }
    if node.Left != nil {
        return sum(node.Left, num<<1+node.Val)
    }
    if node.Right != nil {
        return sum(node.Right, num<<1+node.Val)
    }
    return num<<1 + node.Val
}
```

#### Approach #1

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    var val, res int
    var stack []*TreeNode
    var pre *TreeNode
    for root != nil || len(stack) > 0 {
        for root != nil {
            val = val<<1 | root.Val
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        if root.Right == nil || root.Right == pre {
            if root.Left == nil && root.Right == nil {
                res = res + val
            }
            val = val >> 1
            stack = stack[:len(stack)-1]
            pre = root
            root = nil
        } else {
            root = root.Right
        }
    }
    return res
}
```


# 2022-05-29

## [153. Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

### Description

Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times. For example, the array `nums = [0,1,2,4,5,6,7]` might become:

* `[4,5,6,7,0,1,2]` if it was rotated `4` times.
* `[0,1,2,4,5,6,7]` if it was rotated `7` times.

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

Given the sorted rotated array `nums` of **unique** elements, return *the minimum element of this array*.

You must write an algorithm that runs in `O(log n) time.`

**Example 1:**

```
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
```

**Example 2:**

```
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
```

**Example 3:**

```
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 
```

**Constraints:**

* `n == nums.length`
* `1 <= n <= 5000`
* `-5000 <= nums[i] <= 5000`
* All the integers of `nums` are **unique**.
* `nums` is sorted and rotated between `1` and `n` times.

### Solution

#### Approach #0

```go
func findMin(nums []int) int {
    n := len(nums)
    i, j := 0, n-1
    for i < j {
        mid := (j-i)/2 + i
        if nums[mid] < nums[n-1] {
            j = mid
        } else {
            i = mid + 1
        }
    }
    return nums[i]
}
```

## [162. Find Peak Element](https://leetcode.com/problems/find-peak-element/)

### Description

A peak element is an element that is strictly greater than its neighbors.

Given an integer array `nums`, find a peak element, and return its index. If the array contains multiple peaks, return the index to **any of the peaks**.

You may imagine that `nums[-1] = nums[n] = -∞`.

You must write an algorithm that runs in `O(log n)` time.

**Example 1:**

```
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
```

**Example 2:**

```
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
```

**Constraints:**

* `1 <= nums.length <= 1000`
* `-2^31 <= nums[i] <= 2^31 - 1`
* `nums[i] != nums[i + 1]` for all valid `i`.

### Solution

#### Approach #0

```go
func findPeakElement(nums []int) int {
    res := 0
    for i, num := range nums {
        if num > nums[res] {
            res = i
        }
    }
    return res
}
```

#### Approach #1

```go
func findPeakElement(nums []int) int {
    n := len(nums)
    get := func(i int) int {
        if i < 0 || i >= n {
            return math.MinInt64
        }
        return nums[i]
    }

    i, j := 0, n-1
    for {
        mid := (j-i)/2 + i
        if get(mid-1) < get(mid) && get(mid) > get(mid+1) {
            return mid
        }
        if get(mid) < get(mid+1) {
            i = mid + 1
        } else {
            j = mid - 1
        }
    }
}
```

## [468. Validate IP Address](https://leetcode.com/problems/validate-ip-address/)

### Description

Given a string `queryIP`, return `"IPv4"` if IP is a valid IPv4 address, `"IPv6"` if IP is a valid IPv6 address or `"Neither"` if IP is not a correct IP of any type.

**A valid IPv4** address is an IP in the form `"x1.x2.x3.x4"` where `0 <= xi <= 255` and `xi` **cannot contain** leading zeros. For example, `"192.168.1.1"` and `"192.168.1.0"` are valid IPv4 addresses while `"192.168.01.1"`, `"192.168.1.00"`, and `"192.168@1.1"` are invalid IPv4 addresses.

**A valid IPv6** address is an IP in the form `"x1:x2:x3:x4:x5:x6:x7:x8"` where:

* `1 <= xi.length <= 4`
* `xi` is a **hexadecimal string** which may contain digits, lowercase English letter (`'a'` to `'f'`) and upper-case English letters (`'A'` to `'F'`).
* Leading zeros are allowed in `xi`.

For example, "`2001:0db8:85a3:0000:0000:8a2e:0370:7334"` and "`2001:db8:85a3:0:0:8A2E:0370:7334"` are valid IPv6 addresses, while "`2001:0db8:85a3::8A2E:037j:7334"` and "`02001:0db8:85a3:0000:0000:8a2e:0370:7334"` are invalid IPv6 addresses.

**Example 1:**

```
Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".
```

**Example 2:**

```
Input: queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
Output: "IPv6"
Explanation: This is a valid IPv6 address, return "IPv6".
```

**Example 3:**

```
Input: queryIP = "256.256.256.256"
Output: "Neither"
Explanation: This is neither a IPv4 address nor a IPv6 address.
```

**Constraints:**

* `queryIP` consists only of English letters, digits and the characters `'.'` and `':'`.

### Solution

#### Approach #0

```go
func validIPAddress(queryIP string) string {
    if parts := strings.Split(queryIP, "."); len(parts) == 4 {
        for _, part := range parts {
            if len(part) > 1 && part[0] == '0' {
                return "Neither"
            }
            if v, err := strconv.Atoi(part); err != nil || v > 255 {
                return "Neither"
            }
        }
        return "IPv4"
    }
    if parts := strings.Split(queryIP, ":"); len(parts) == 8 {
        for _, part := range parts {
            if len(part) > 4 {
                return "Neither"
            }
            if _, err := strconv.ParseUint(part, 16, 64); err != nil {
                return "Neither"
            }
        }
        return "IPv6"
    }
    return "Neither"
}
```


# 2022-05-28

## [190. Reverse Bits](https://leetcode.com/problems/reverse-bits/)

### Description

Reverse bits of a given 32 bits unsigned integer.

**Note:**

* Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
* In Java, the compiler represents the signed integers using [2's complement notation](https://en.wikipedia.org/wiki/Two%27s_complement). Therefore, in **Example 2** above, the input represents the signed integer `-3` and the output represents the signed integer `-1073741825`.

**Example 1:**

```
Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
```

**Example 2:**

```
Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
```

**Constraints:**

* The input must be a **binary string** of length `32`

**Follow up:** If this function is called many times, how would you optimize it?

### Solution

#### Approach #0

```go
func reverseBits(num uint32) uint32 {
    var res uint32
    for i := 0; i < 32 && num > 0; i++ {
        res |= num & 1 << (31 - i)
        num >>= 1
    }
    return res
}
```

#### Approach #1: Divide And Conquer

Without reading the official solution, this approach will never come into my mind...

```go
const (
    m1 = 0x55555555 // 01010101010101010101010101010101
    m2 = 0x33333333 // 00110011001100110011001100110011
    m4 = 0x0f0f0f0f // 00001111000011110000111100001111
    m8 = 0x00ff00ff // 00000000111111110000000011111111
)

func reverseBits(n uint32) uint32 {
    n = n>>1&m1 | n&m1<<1
    n = n>>2&m2 | n&m2<<2
    n = n>>4&m4 | n&m4<<4
    n = n>>8&m8 | n&m8<<8
    return n>>16 | n<<16
}
```

## [136. Single Number](https://leetcode.com/problems/single-number/)

### Description

Given a **non-empty** array of integers `nums`, every element appears *twice* except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

**Example 1:**

```
Input: nums = [2,2,1]
Output: 1
```

**Example 2:**

```
Input: nums = [4,1,2,1,2]
Output: 4
```

**Example 3:**

```
Input: nums = [1]
Output: 1
```

**Constraints:**

* `1 <= nums.length <= 3 * 10^4`
* `-3 * 10^4 <= nums[i] <= 3 * 10^4`
* Each element in the array appears twice except for one element which appears only once.

### Solution

#### Approach #0

```go
func singleNumber(nums []int) int {
    res := 0
    for _, num := range nums {
        res ^= num
    }
    return res
}
```

## [1021. Remove Outermost Parentheses](https://leetcode.com/problems/remove-outermost-parentheses/)

### Description

A valid parentheses string is either empty `""`, `"(" + A + ")"`, or `A + B`, where `A` and `B` are valid parentheses strings, and `+` represents string concatenation.

* For example, `""`, `"()"`, `"(())()"`, and `"(()(()))"` are all valid parentheses strings.

A valid parentheses string `s` is primitive if it is nonempty, and there does not exist a way to split it into `s = A + B`, with `A` and `B` nonempty valid parentheses strings.

Given a valid parentheses string `s`, consider its primitive decomposition: `s = P1 + P2 + ... + Pk`, where `Pi` are primitive valid parentheses strings.

Return `s` *after removing the outermost parentheses of every primitive string in the primitive decomposition of* `s`.

**Example 1:**

```
Input: s = "(()())(())"
Output: "()()()"
Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
```

**Example 2:**

```
Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation: 
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
```

**Example 3:**

```
Input: s = "()()"
Output: ""
Explanation: 
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".
```

**Constraints:**

* `1 <= s.length <= 105`
* `s[i]` is either `'('` or `')'`.
* `s` is a valid parentheses string.

### Solution

#### Approach #0

```go
func removeOuterParentheses(s string) string {
    var res, stack []rune
    for _, ch := range s {
        if ch == ')' {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            res = append(res, ch)
        }
        if ch == '(' {
            stack = append(stack, ch)
        }
    }
    return string(res)
}
```

## [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

### Description

Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value.

If `target` is not found in the array, return `[-1, -1]`.

You must write an algorithm with `O(log n)` runtime complexity.

**Example 1:**

```
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
```

**Example 2:**

```
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
```

**Example 3:**

```
Input: nums = [], target = 0
Output: [-1,-1]
```

**Constraints:**

* `0 <= nums.length <= 10^5`
* `-10^9 <= nums[i] <= 10^9`
* `nums` is a non-decreasing array.
* `-10^9 <= target <= 10^9`

### Solution

#### Approach #0

```go
func binarySearch(nums []int, target int, lower bool) (res int) {
    res = len(nums)
    for i, j := 0, len(nums)-1; i <= j; {
        mid := (i + j) / 2
        if nums[mid] > target || (lower && nums[mid] >= target) {
            j = mid - 1
            res = mid
        } else {
            i = mid + 1
        }
    }
    return
}

func searchRange(nums []int, target int) []int {
    low := binarySearch(nums, target, true)
    high := binarySearch(nums, target, false) - 1
    if low <= high && high < len(nums) && nums[low] == nums[high] {
        return []int{low, high}
    }
    return []int{-1, -1}
}
```

#### Approach #1

```go
func searchRange(nums []int, target int) []int {
    low := sort.SearchInts(nums, target)
    if low >= len(nums) || nums[low] != target {
        return []int{-1, -1}
    }
    high := sort.SearchInts(nums, target+1) - 1
    return []int{low, high}
}
```

## [33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)

### Description

There is an integer array `nums` sorted in ascending order (with **distinct** values).

Prior to being passed to your function, `nums` is **possibly rotated** at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`.

Given the array `nums` **after** the possible rotation and an integer `target`, return *the index of* `target` *if it is in* `nums`*, or* `-1` *if it is not in* `nums`.

You must write an algorithm with `O(log n)` runtime complexity.

**Example 1:**

```
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```

**Example 2:**

```
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
```

**Example 3:**

```
Input: nums = [1], target = 0
Output: -1
```

**Constraints:**

* `1 <= nums.length <= 5000`
* `-10^4 <= nums[i] <= 10^4`
* All values of `nums` are **unique**.
* `nums` is an ascending array that is possibly rotated.
* `-10^4 <= target <= 10^4`

### Solution

#### Approach #0

```go
func search(nums []int, target int) int {
    n := len(nums)
    if n == 0 {
        return -1
    }
    if n == 1 {
        if nums[0] == target {
            return 0
        }
        return -1
    }

    for i, j := 0, n-1; i <= j; {
        mid := (i + j) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[0] <= nums[mid] {
            if nums[0] <= target && target < nums[mid] {
                j = mid - 1
            } else {
                i = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[n-1] {
                i = mid + 1
            } else {
                j = mid - 1
            }
        }
    }
    return -1
}
```

## [74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)

### Description

Write an efficient algorithm that searches for a value `target` in an `m x n` integer matrix `matrix`. This matrix has the following properties:

* Integers in each row are sorted from left to right.
* The first integer of each row is greater than the last integer of the previous row.

**Example 1:**

![](https://img.content.cc/a/2022/05/28/12-50-58-439-ccc80b991260d3c4cd95b328c1edf562-43c888.jpeg)

```
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
```

**Example 2:**

![](https://img.content.cc/a/2022/05/28/12-51-15-724-7adaf830e264910d53e5d9ed1aeef15b-49240d.jpeg)

```
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
```

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 100`
* `-10^4 <= matrix[i][j], target <= 10^4`

### Solution

#### Approach #0

```go
func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    i, j := -1, m-1
    for i < j {
        mid := (j-i+1)/2 + i
        if matrix[mid][0] <= target {
            i = mid
        } else {
            j = mid - 1
        }
    }
    if i == -1 {
        return false
    }
    for p, q := 0, n-1; p <= q; {
        mid := (p-q)/2 + q
        if matrix[i][mid] == target {
            return true
        }
        if matrix[i][mid] > target {
            q = mid - 1
        } else {
            p = mid + 1
        }
    }
    return false
}
```

#### Approach #1

```go
func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    row := sort.Search(m, func(i int) bool { return matrix[i][0] > target }) - 1
    if row < 0 {
        return false
    }
    column := sort.SearchInts(matrix[row], target)
    return column < n && matrix[row][column] == target
}
```

#### Approach #2

```go
func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    i := sort.Search(m*n, func(i int) bool { return matrix[i/n][i%n] >= target })
    return i < m*n && matrix[i/n][i%n] == target
}
```


# 2022-05-27

## [231. Power of Two](https://leetcode.com/problems/power-of-two/)

### Description

Given an integer `n`, return *`true` if it is a power of two. Otherwise, return `false`*.

An integer `n` is a power of two, if there exists an integer `x` such that `n == 2x`.

**Example 1:**

```
Input: n = 1
Output: true
Explanation: 20 = 1
```

**Example 2:**

```
Input: n = 16
Output: true
Explanation: 24 = 16
```

**Example 3:**

```
Input: n = 3
Output: false
```

**Constraints:**

* `-2^31 <= n <= 2^31 - 1`&#x20;

**Follow up:** Could you solve it without loops/recursion?

### Solution

#### Approach #0

```go
func isPowerOfTwo(n int) bool {
    return n > 0 && n&(n-1) == 0
}
```

#### Approach #1

```go
func isPowerOfTwo(n int) bool {
    big := 1 << 30
    return n > 0 && big%n == 0
}
```

## [191. Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/)

### Description

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the [Hamming weight](http://en.wikipedia.org/wiki/Hamming_weight)).

**Note:**

* Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
* In Java, the compiler represents the signed integers using [2's complement notation](https://en.wikipedia.org/wiki/Two%27s_complement). Therefore, in **Example 3**, the input represents the signed integer. `-3`.

**Example 1:**

```
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
```

**Example 2:**

```
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
```

**Example 3:**

```
Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
```

**Constraints:**

* The input must be a **binary string** of length `32`.

**Follow up:** If this function is called many times, how would you optimize it?

### Solution

#### Approach #0

```go
func hammingWeight(num uint32) int {
    count := 0
    for num > 0 {
        num = num & (num - 1)
        count++
    }
    return count
}
```

#### Approach #1

```go
func hammingWeight(num uint32) int {
    count := 0
    for i := 0; i < 32; i++ {
        if 1<<i&num > 0 {
            count++
        }
    }
    return count
}
```

## [223. Rectangle Area](https://leetcode.com/problems/rectangle-area/)

### Description

Given the coordinates of two **rectilinear** rectangles in a 2D plane, return *the total area covered by the two rectangles*.

The first rectangle is defined by its **bottom-left** corner `(ax1, ay1)` and its **top-right** corner `(ax2, ay2)`.

The second rectangle is defined by its **bottom-left** corner `(bx1, by1)` and its **top-right** corner `(bx2, by2)`.

**Example 1:**

![](https://img.content.cc/a/2022/05/27/11-17-28-606-300350bb515c93bfcecdfb2cfbc48194-2d1f1f.png)

```
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
```

**Example 2:**

```
Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16
```

**Constraints:**

* `-10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4`

### Solution

#### Approach #0

```go
func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
    area1 := (ax2 - ax1) * (ay2 - ay1)
    area2 := (bx2 - bx1) * (by2 - by1)
    overlapWidth := min(ax2, bx2) - max(ax1, bx1)
    overlapHeight := min(ay2, by2) - max(ay1, by1)
    overlapArea := max(overlapWidth, 0) * max(overlapHeight, 0)
    return area1 + area2 - overlapArea
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```


# 2022-05-26

## [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)

### Description

You are climbing a staircase. It takes `n` steps to reach the top.

Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?

**Example 1:**

```
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
```

**Example 2:**

```
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
```

**Constraints:**

* `1 <= n <= 45`

### Solution

#### Approach #0

```go
func climbStairs(n int) int {
    p, q, r := 0, 0, 1
    for i := 0; i < n; i++ {
        p = q
        q = r
        r = p + q
    }
    return r
}
```

## [198. House Robber](https://leetcode.com/problems/house-robber/)

### Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array `nums` representing the amount of money of each house, return *the maximum amount of money you can rob tonight **without alerting the police***.

**Example 1:**

```
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
```

**Example 2:**

```
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
```

**Constraints:**

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 400`

### Solution

#### Approach #0

```go
func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    r0, r1 := 0, nums[0]
    for i := 1; i < len(nums); i++ {
        r0, r1 = r1, max(r1, r0+nums[i])
    }
    return r1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [120. Triangle](https://leetcode.com/problems/triangle/)

### Description

Given a `triangle` array, return *the minimum path sum from top to bottom*.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index `i` on the current row, you may move to either index `i` or index `i + 1` on the next row.

**Example 1:**

```
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
```

**Example 2:**

```
Input: triangle = [[-10]]
Output: -10
```

**Constraints:**

* `1 <= triangle.length <= 200`
* `triangle[0].length == 1`
* `triangle[i].length == triangle[i - 1].length + 1`
* `-104 <= triangle[i][j] <= 104`

**Follow up:** Could you do this using only `O(n)` extra space, where `n` is the total number of rows in the triangle?

### Solution

#### Approach #0: Better than the official solution

```go
func minimumTotal(triangle [][]int) int {
    if len(triangle) == 1 {
        return triangle[0][0]
    }
    for i := 1; i < len(triangle); i++ {
        size := len(triangle[i])
        triangle[i][0] = triangle[i-1][0] + triangle[i][0]
        for j := 1; j < size-1; j++ {
            triangle[i][j] = min(triangle[i-1][j], triangle[i-1][j-1]) + triangle[i][j]
        }
        triangle[i][size-1] = triangle[i-1][size-2] + triangle[i][size-1]
    }
    r := triangle[len(triangle)-1][0]
    for _, item := range triangle[len(triangle)-1] {
        r = min(r, item)
    }
    return r
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

## [699. Falling Squares](https://leetcode.com/problems/falling-squares/)

### Description

There are several squares being dropped onto the X-axis of a 2D plane.

You are given a 2D integer array `positions` where `positions[i] = [lefti, sideLengthi]` represents the `ith` square with a side length of `sideLengthi` that is dropped with its left edge aligned with X-coordinate `lefti`.

Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands **on the top side of another square** or **on the X-axis**. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.

After each square is dropped, you must record the **height of the current tallest stack of squares**.

Return *an integer array* `ans` *where* `ans[i]` *represents the height described above after dropping the* `ith` *square*.&#x20;

**Example 1:**

![](https://img.content.cc/a/2022/05/26/12-35-30-530-706edef22e335f893d0d594575afbd48-389932.jpeg)

```
Input: positions = [[1,2],[2,3],[6,1]]
Output: [2,5,5]
Explanation:
After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of [2, 5, 5].
```

**Example 2:**

```
Input: positions = [[100,100],[200,100]]
Output: [100,100]
Explanation:
After the first drop, the tallest stack is square 1 with a height of 100.
After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
Thus, we return an answer of [100, 100].
Note that square 2 only brushes the right side of square 1, which does not count as landing on it.
```

**Constraints:**

* `1 <= positions.length <= 1000`
* `1 <= lefti <= 10^8`
* `1 <= sideLengthi <= 10^6`

### Solution

#### Approach #0

```go
func fallingSquares(positions [][]int) []int {
    n := len(positions)
    heights := make([]int, n)
    for i, p := range positions {
        left1, right1 := p[0], p[1]+p[0]-1
        heights[i] = p[1]
        for j, q := range positions[:i] {
            left2, right2 := q[0], q[1]+q[0]-1
            if left1 <= right2 && right1 >= left2 {
                heights[i] = max(heights[i], heights[j]+p[1])
            }
        }
    }
    for i := 1; i < n; i++ {
        heights[i] = max(heights[i], heights[i-1])
    }
    return heights
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [27. Remove Element](https://leetcode.com/problems/remove-element/)

### Description

Given an integer array `nums` and an integer `val`, remove all occurrences of `val` in `nums` [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm). The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.

Return `k` *after placing the final result in the first* `k` *slots of* `nums`.

Do **not** allocate extra space for another array. You must do this by **modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) with O(1) extra memory.

**Custom Judge:**

The judge will test your solution with the following code:

```
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}
```

If all assertions pass, then your solution will be **accepted**.

**Example 1:**

```
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
```

**Example 2:**

```
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).
```

**Constraints:**

* `0 <= nums.length <= 100`
* `0 <= nums[i] <= 50`
* `0 <= val <= 100`

### Solution

#### Approach #0

```go
func removeElement(nums []int, val int) int {
    i := 0
    for j := 0; j < len(nums); j++ {
        if nums[j] != val {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    return i
}
```

#### Approach #1

```go
func removeElement(nums []int, val int) int {
    i, j := 0, len(nums)
    for i < j {
        if nums[i] != val {
            i++
        } else {
            nums[i] = nums[j-1]
            j--
        }
    }
    return i
}
```


# 2022-05-25

## [77. Combinations](https://leetcode.com/problems/combinations/)

### Description

Given two integers `n` and `k`, return *all possible combinations of* `k` *numbers out of the range* `[1, n]`.

You may return the answer in **any order**.

**Example 1:**

```
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
```

**Example 2:**

```
Input: n = 1, k = 1
Output: [[1]]
```

**Constraints:**

* `1 <= n <= 20`
* `1 <= k <= n`

### Solution

#### Approach #0: DFS

```go
func combine(n int, k int) [][]int {
    res := [][]int{}
    item := []int{}
    var dfs func(int)
    dfs = func(start int) {
        if len(item) == k {
            a := make([]int, k)
            copy(a, item)
            res = append(res, a)
            return
        }
        for i := start; i <= n; i++ {
            item = append(item, i)
            dfs(i + 1)
            item = item[:len(item)-1]
        }
    }
    dfs(1)
    return res
}
```

#### Approach #1: Alphabetical Order

```go
func combine(n int, k int) [][]int {
    var temp []int
    for i := 1; i <= k; i++ {
        temp = append(temp, i)
    }
    temp = append(temp, n+1)

    var res [][]int
    for j := 0; j < k; {
        item := make([]int, k)
        copy(item, temp[:k])
        res = append(res, item)

        for j = 0; j < k && temp[j]+1 == temp[j+1]; j++ {
            temp[j] = j + 1
        }
        temp[j]++
    }
    return res
}
```

## [46. Permutations](https://leetcode.com/problems/permutations/)

### Description

Given an array `nums` of distinct integers, return *all the possible permutations*. You can return the answer in **any order**.

**Example 1:**

```
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```

**Example 2:**

```
Input: nums = [0,1]
Output: [[0,1],[1,0]]
```

**Example 3:**

```
Input: nums = [1]
Output: [[1]]
```

**Constraints:**

* `1 <= nums.length <= 6`
* `-10 <= nums[i] <= 10`
* All the integers of `nums` are **unique**.

### Solution

#### Approach #0

```go
func permute(nums []int) [][]int {
    var res [][]int
    var item []int
    m := make(map[int]struct{})

    n := len(nums)
    var dfs func([]int, map[int]struct{})
    dfs = func(item []int, m map[int]struct{}) {
        if len(item) == n {
            a := make([]int, n)
            copy(a, item)
            res = append(res, a)
            return
        }
        for i := 0; i < n; i++ {
            if _, ok := m[nums[i]]; ok {
                continue
            }
            item = append(item, nums[i])
            m[nums[i]] = struct{}{}
            dfs(item, m)
            delete(m, nums[i])
            item = item[:len(item)-1]
        }
    }
    dfs(item, m)
    return res
}
```

#### Approach #1

```go
func permute(nums []int) [][]int {
    var res [][]int

    n := len(nums)
    var backtrack func(int)
    backtrack = func(first int) {
        if first == n {
            a := make([]int, n)
            copy(a, nums)
            res = append(res, a)
            return
        }
        for i := first; i < n; i++ {
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]
        }
    }
    backtrack(0)
    return res
}
```

## [784. Letter Case Permutation](https://leetcode.com/problems/letter-case-permutation/)

### Description

Given a string `s`, you can transform every letter individually to be lowercase or uppercase to create another string.

Return *a list of all possible strings we could create*. Return the output in **any order**.

**Example 1:**

```
Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]
```

**Example 2:**

```
Input: s = "3z4"
Output: ["3z4","3Z4"]
```

**Constraints:**

* `1 <= s.length <= 12`
* `s` consists of lowercase English letters, uppercase English letters, and digits.

### Solution

#### Approach #0: Too Slow

```go
func letterCasePermutation(s string) []string {
    sList := []rune(s)
    n := len(s)

    var res []string
    var backtrace func(int)
    backtrace = func(start int) {
        if start == n {
            res = append(res, string(sList))
            return
        }
        for i := start; i < len(sList); i++ {
            backtrace(i + 1)
            if !unicode.IsLetter(sList[i]) {
                continue
            }
            if unicode.IsLower(sList[i]) {
                sList[i] = unicode.ToUpper(sList[i])
                backtrace(i + 1)
                sList[i] = unicode.ToLower(sList[i])
            }
            if unicode.IsUpper(sList[i]) {
                sList[i] = unicode.ToLower(sList[i])
                backtrace(i + 1)
                sList[i] = unicode.ToUpper(sList[i])
            }
        }
    }
    backtrace(0)

    m := make(map[string]struct{})
    var a []string
    for _, ss := range res {
        if _, ok := m[ss]; ok {
            continue
        }
        a = append(a, ss)
        m[ss] = struct{}{}
    }
    return a
}
```

#### Approach #1: Much Better

```go
func letterCasePermutation(s string) []string {
    res := []string{""}
    for _, ch := range s {
        n := len(res)
        if unicode.IsLetter(rune(ch)) {
            for i := 0; i < n; i++ {
                res = append(res, res[i]+string(unicode.ToLower(rune(ch))))
                res[i] = res[i] + string(unicode.ToUpper(rune(ch)))
            }
        } else {
            for i := 0; i < n; i++ {
                res[i] = res[i] + string(ch)
            }
        }
    }
    return res
}
```


# 2022-05-24

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

### Description

You are given the heads of two sorted linked lists `list1` and `list2`.

Merge the two lists in a one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

**Example 1:**

![](https://img.content.cc/a/2022/05/24/09-52-03-654-2b038dbe54fad2913610d24cf6831806-823b97.jpeg)

```
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
```

**Example 2:**

```
Input: list1 = [], list2 = []
Output: []
```

**Example 3:**

```
Input: list1 = [], list2 = [0]
Output: [0]
```

**Constraints:**

* The number of nodes in both lists is in the range `[0, 50]`.
* `-100 <= Node.val <= 100`
* Both `list1` and `list2` are sorted in **non-decreasing** order.

### Solution

#### Approach #0

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    root := &ListNode{}
    cur := root
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            cur.Next = list1
            cur = cur.Next
            list1 = list1.Next
        } else {
            cur.Next = list2
            cur = cur.Next
            list2 = list2.Next
        }
    }
    if list1 != nil {
        cur.Next = list1
    }
    if list2 != nil {
        cur.Next = list2
    }
    return root.Next
}
```

#### Approach #1: **Recursive**

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }
    if list1.Val < list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    } else {
        list2.Next = mergeTwoLists(list1, list2.Next)
        return list2
    }
}

```

## [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

### Description

Given the `head` of a singly linked list, reverse the list, and return *the reversed list*.

**Example 1:**

![](https://img.content.cc/a/2022/05/24/09-52-24-768-49f3322c7abc9a0c7cf637264e677bc2-5a3f8d.jpeg)

```
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
```

**Example 2:**

![](https://img.content.cc/a/2022/05/24/09-52-46-964-dac276cabb172665269e9078356513aa-c97bb0.jpeg)

```
Input: head = [1,2]
Output: [2,1]
```

**Example 3:**

```
Input: head = []
Output: [] 
```

**Constraints:**

* The number of nodes in the list is the range `[0, 5000]`.
* `-5000 <= Node.val <= 5000`

**Follow up:** A linked list can be reversed either iteratively or recursively. Could you implement both?

### Solution

#### Approach #0: **Iterative**

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    cur := head
    var prev *ListNode
    for cur.Next != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    cur.Next = prev
    return cur
}
```

#### Approach #1: **Recursive**

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    return reverse(head, nil)
}

func reverse(cur, prev *ListNode) *ListNode {
    next := cur.Next
    cur.Next = prev
    if next == nil {
        return cur
    } else {
        return reverse(next, cur)
    }
}
```

## [1480. Running Sum of 1d Array](https://leetcode.com/problems/running-sum-of-1d-array/)

### Description

Given an array `nums`. We define a running sum of an array as `runningSum[i] = sum(nums[0]…nums[i])`.

Return the running sum of `nums`.

**Example 1:**

```
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
```

**Example 2:**

```
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
```

**Example 3:**

```
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]
```

**Constraints:**

* `1 <= nums.length <= 1000`
* `-10^6 <= nums[i] <= 10^6`

### Solution

#### Approach #0

```go
func runningSum(nums []int) []int {
    for i := 1; i < len(nums); i++ {
        nums[i] = nums[i] + nums[i-1]
    }
    return nums
}
```

## [383. Ransom Note](https://leetcode.com/problems/ransom-note/)

### Description

Given two strings `ransomNote` and `magazine`, return `true` *if* `ransomNote` *can be constructed from* `magazine` *and* `false` *otherwise*.

Each letter in `magazine` can only be used once in `ransomNote`.

**Example 1:**

```
Input: ransomNote = "a", magazine = "b"
Output: false
```

**Example 2:**

```
Input: ransomNote = "aa", magazine = "ab"
Output: false
```

**Example 3:**

```
Input: ransomNote = "aa", magazine = "aab"
Output: true
```

**Constraints:**

* `1 <= ransomNote.length, magazine.length <= 10^5`
* `ransomNote` and `magazine` consist of lowercase English letters.

### Solution

#### Approach #0

```go
func canConstruct(ransomNote string, magazine string) bool {
    var m [26]int
    for i := 0; i < len(magazine); i++ {
        m[magazine[i]-'a']++
    }
    for i := 0; i < len(ransomNote); i++ {
        m[ransomNote[i]-'a']--
        if m[ransomNote[i]-'a'] < 0 {
            return false
        }
    }
    return true
}
```

## [965. Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)

### Description

A binary tree is **uni-valued** if every node in the tree has the same value.

Given the `root` of a binary tree, return `true` *if the given tree is **uni-valued**, or* `false` *otherwise.*&#x20;

**Example 1:**

![](https://img.content.cc/a/2022/05/24/11-47-21-248-5229ab18994b6ea8876a5d6ef753cb14-7c1d35.png)

```
Input: root = [1,1,1,1,1,null,1]
Output: true
```

**Example 2:**

![](https://img.content.cc/a/2022/05/24/11-47-36-955-f40b1953bc650c023d232cb4a03459f6-28a14f.png)

```
Input: root = [2,2,2,5,2]
Output: false
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 100]`.
* `0 <= Node.val < 100`

### Solution

#### Approach #0: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isUnivalTree(root *TreeNode) bool {
    queue := []*TreeNode{root}
    v := root.Val
    for i := 0; i < len(queue); i++ {
        if queue[i].Val != v {
            return false
        }
        if queue[i].Left != nil {
            queue = append(queue, queue[i].Left)
        }
        if queue[i].Right != nil {
            queue = append(queue, queue[i].Right)
        }
    }
    return true
}
```

#### Approach #1: DFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isUnivalTree(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if root.Left != nil && root.Val != root.Left.Val || !isUnivalTree(root.Left) {
        return false
    }
    if root.Right != nil && root.Val != root.Right.Val || !isUnivalTree(root.Right) {
        return false
    }
    return true
}
```


# 2022-05-23

## [542. 01 Matrix](https://leetcode.com/problems/01-matrix/)

### Description

Given an `m x n` binary matrix `mat`, return *the distance of the nearest* `0` *for each cell*.

The distance between two adjacent cells is `1`.

**Example 1:**

![](https://img.content.cc/a/2022/05/23/19-29-42-885-5362838c3aa004246f109b39f73f2703-6e6211.jpeg)

```
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
```

**Example 2:**

![](https://img.content.cc/a/2022/05/23/19-30-11-789-e52361d105f13159883dd2340e186d13-a94720.jpeg)

```
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
```

**Constraints:**

* `m == mat.length`
* `n == mat[i].length`
* `1 <= m, n <= 10^4`
* `1 <= m * n <= 10^4`
* `mat[i][j]` is either `0` or `1`.
* There is at least one `0` in `mat`.

### Solution

#### Approach #0: BFS (Time Limit Exceeded) ❌

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func updateMatrix(mat [][]int) [][]int {
    if len(mat) == 0 {
        return mat
    }
    m, n := len(mat), len(mat[0])

    res := make([][]int, m)
    for i := 0; i < m; i++ {
        res[i] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            queue := [][]int{{i, j}}
            depth := -1
            t := make([][]int, m)
            for i := 0; i < m; i++ {
                t[i] = make([]int, n)
            }
            for len(queue) > 0 {
                size := len(queue)
                for k := 0; k < size; k++ {
                    x, y := queue[k][0], queue[k][1]
                    t[x][y] = 1
                    if mat[x][y] == 0 {
                        queue = queue[:0]
                        break
                    } else {
                        for p := 0; p < 4; p++ {
                            xx, yy := x+dx[p], y+dy[p]
                            if xx >= 0 && xx < m && yy >= 0 && yy < n && t[xx][yy] != 1 {
                                queue = append(queue, []int{xx, yy})
                            }
                        }
                    }
                }
                depth++
                if len(queue) > 0 {
                    queue = queue[size:]
                }

            }
            res[i][j] = depth
        }
    }
    return res
}
```

#### Approach #1: BFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func updateMatrix(mat [][]int) [][]int {
    if len(mat) == 0 {
        return mat
    }
    m, n := len(mat), len(mat[0])

    res := make([][]int, m)
    checked := make([][]int, m)
    for i := 0; i < m; i++ {
        res[i] = make([]int, n)
        checked[i] = make([]int, n)
    }

    var queue [][]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 0 {
                queue = append(queue, []int{i, j})
                checked[i][j] = 1
            }
        }
    }

    depth := 0
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            x, y := queue[i][0], queue[i][1]
            res[x][y] = depth
            for p := 0; p < 4; p++ {
                xx, yy := x+dx[p], y+dy[p]
                if xx >= 0 && xx < m && yy >= 0 && yy < n && checked[xx][yy] != 1 {
                    checked[xx][yy] = 1
                    queue = append(queue, []int{xx, yy})
                }
            }
        }
        depth++
        queue = queue[size:]
    }

    return res
}
```

## [994. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)

### Description

You are given an `m x n` `grid` where each cell can have one of three values:

* `0` representing an empty cell,
* `1` representing a fresh orange, or
* `2` representing a rotten orange.

Every minute, any fresh orange that is **4-directionally adjacent** to a rotten orange becomes rotten.

Return *the minimum number of minutes that must elapse until no cell has a fresh orange*. If *this is impossible, return* `-1`.

**Example 1:**

![](https://img.content.cc/a/2022/05/23/19-30-36-297-461a69dd506a0a1b5d67b4ecfd535eb2-1ce1e5.png)

```
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
```

**Example 2:**

```
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
```

**Example 3:**

```
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
```

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 10`
* `grid[i][j]` is `0`, `1`, or `2`.

### Solution

#### Approach #0: BFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func orangesRotting(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])
    all1 := 0
    var queue [][]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                all1++
            }
            if grid[i][j] == 2 {
                queue = append(queue, []int{i, j})
            }
        }
    }
    if len(queue) == 0 && all1 == 0 {
        return 0
    }

    depth := -1
    count1 := -len(queue)
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            x, y := queue[i][0], queue[i][1]
            count1++
            for j := 0; j < 4; j++ {
                xx, yy := x+dx[j], y+dy[j]
                if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 1 {
                    grid[xx][yy] = 2
                    queue = append(queue, []int{xx, yy})
                }
            }

        }
        fmt.Println(all1, count1)
        depth++
        queue = queue[size:]
    }
    if all1 > count1 {
        return -1
    }
    return depth
}
```


# 2022-05-22

## [617. Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/)

### Description

You are given two binary trees `root1` and `root2`.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return *the merged tree*.

**Note:** The merging process must start from the root nodes of both trees.

**Example 1:**

<img src="https://img.content.cc/a/2022/05/22/11-22-16-983-fe9ac992cc296f5a7ac4e70bb56ed347-51b1e6.jpeg" alt="" data-size="original">

```
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
```

**Example 2:**

```
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
```

**Constraints:**

* The number of nodes in both trees is in the range `[0, 2000]`.
* `-10^4 <= Node.val <= 10^4`

### Solution

#### Approach #0: DFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    root1.Val = root1.Val + root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}
```

#### Approach #1: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    queue := [][]*TreeNode{{root1, root2}}
    for i := 0; i < len(queue); i++ {
        a, b := queue[i][0], queue[i][1]
        if b != nil {
            a.Val = a.Val + b.Val
            if a.Left != nil && b.Left != nil {
                queue = append(queue, []*TreeNode{a.Left, b.Left})
            } else {
                if a.Left != nil {
                    queue = append(queue, []*TreeNode{a.Left, nil})
                }
                if b.Left != nil {
                    a.Left = &TreeNode{Val: 0}
                    queue = append(queue, []*TreeNode{a.Left, b.Left})
                }
            }
            if a.Right != nil && b.Right != nil {
                queue = append(queue, []*TreeNode{a.Right, b.Right})
            } else {
                if a.Right != nil {
                    queue = append(queue, []*TreeNode{a.Right, nil})
                }
                if b.Right != nil {
                    a.Right = &TreeNode{Val: 0}
                    queue = append(queue, []*TreeNode{a.Right, b.Right})
                }
            }
        } else {
            if a.Left != nil {
                queue = append(queue, []*TreeNode{a.Left, nil})
            }
            if a.Right != nil {
                queue = append(queue, []*TreeNode{a.Right, nil})
            }
        }

    }
    return root1
}
```

## [116. Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)

### Description

You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

```
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
```

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

**Example 1:**

![](https://img.content.cc/a/2022/05/22/11-45-16-680-d4af01ea9ac3ca3193f50caa8b6a7b8b-0f56c3.png)

```
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
```

**Example 2:**

```
Input: root = []
Output: []
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 2^12 - 1]`.
* `-1000 <= Node.val <= 1000`

**Follow-up:**

* You may only use constant extra space.
* The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

### Solution

#### Approach #0: BFS

```go
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    queue := []*Node{root}
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            if i+1 < size {
                queue[i].Next = queue[i+1]
            }
            if queue[i].Left != nil {
                queue = append(queue, queue[i].Left, queue[i].Right)
            }

        }
        queue = queue[size:]
    }
    return root
}
```

#### Approach #1: DFS (**Iterative**)

```go
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root == nil {
        return root
    }

    for l := root; l.Left != nil; l = l.Left {
        for node := l; node != nil; node = node.Next {
            node.Left.Next = node.Right
            if node.Next != nil {
                node.Right.Next = node.Next.Left
            }
        }
    }
    return root
}
```

#### Approach #2: DFS (**Recursive**)

```go
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    dfs(root, nil)
    return root
}

func dfs(left, next *Node) {
    if left == nil {
        return
    }
    left.Next = next
    dfs(left.Left, left.Right)
    if left.Next == nil {
        dfs(left.Right, nil)
    } else {
        dfs(left.Right, left.Next.Left)
    }
}
```


# 2022-05-21

## [733. Flood Fill](https://leetcode.com/problems/flood-fill/)

### Description

An image is represented by an `m x n` integer grid `image` where `image[i][j]` represents the pixel value of the image.

You are also given three integers `sr`, `sc`, and `newColor`. You should perform a **flood fill** on the image starting from the pixel `image[sr][sc]`.

To perform a **flood fill**, consider the starting pixel, plus any pixels connected **4-directionally** to the starting pixel of the same color as the starting pixel, plus any pixels connected **4-directionally** to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with `newColor`.

Return *the modified image after performing the flood fill*.

**Example 1:**

![](https://img.content.cc/a/2022/05/21/12-18-09-325-4ab3dd289ed8562296ab9c4ec0218c1d-c93280.jpeg)

```
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.
```

**Example 2:**

```
Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
Output: [[2,2,2],[2,2,2]]
```

**Constraints:**

* `m == image.length`
* `n == image[i].length`
* `1 <= m, n <= 50`
* `0 <= image[i][j], newColor < 2^16`
* `0 <= sr < m`
* `0 <= sc < n`

### Solution

#### Approach #0: DFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
    if image[sr][sc] != newColor {
        originColor := image[sr][sc]
        dfs(image, sr, sc, originColor, newColor)
    }
    return image
}

func dfs(image [][]int, sr int, sc int, originColor, newColor int) {
    if image[sr][sc] == originColor {
        image[sr][sc] = newColor
        for i := 0; i < 4; i++ {
            newSr, newSc := sr+dx[i], sc+dy[i]
            if newSr >= 0 && newSr < len(image) && newSc >= 0 && newSc < len(image[0]) {
                dfs(image, newSr, newSc, originColor, newColor)
            }
        }
    }
}
```

#### Approach #1: BFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
    if image[sr][sc] == newColor {
        return image
    }
    originColor := image[sr][sc]
    image[sr][sc] = newColor
    queue := [][]int{[]int{sr, sc}}
    for i := 0; i < len(queue); i++ {
        for j := 0; j < 4; j++ {
            x, y := queue[i][0]+dx[j], queue[i][1]+dy[j]
            if x >= 0 && x < len(image) && y >= 0 && y < len(image[0]) && image[x][y] == originColor {
                image[x][y] = newColor
                queue = append(queue, []int{x, y})

            }
        }
    }
    return image
}

```

## [695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/)

### Description

You are given an `m x n` binary matrix `grid`. An island is a group of `1`'s (representing land) connected **4-directionally** (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The **area** of an island is the number of cells with a value `1` in the island.

Return *the maximum **area** of an island in* `grid`. If there is no island, return `0`.

**Example 1:**

![](https://img.content.cc/a/2022/05/21/14-04-44-545-c462d022e77d90bc42de4f86e1ed4e9b-75ba3e.jpeg)

```
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
```

**Example 2:**

```
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
```

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 50`
* `grid[i][j]` is either `0` or `1`.

### Solution

#### Approach #0: BFS

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func maxAreaOfIsland(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])

    res := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 0 {
                continue
            }
            grid[i][j] = 0
            queue := [][]int{{i, j}}
            area := 1
            for ii := 0; ii < len(queue); ii++ {
                cell := queue[ii]
                for jj := 0; jj < 4; jj++ {
                    x, y := cell[0]+dx[jj], cell[1]+dy[jj]
                    if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0 {
                        grid[x][y] = 0
                        area++
                        queue = append(queue, []int{x, y})
                    }
                }
            }
            res = max(res, area)
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

#### Approach #1: DFS (**Recursive**)

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func maxAreaOfIsland(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }

    res := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 0 {
                continue
            }
            area := dfs(grid, i, j)
            res = max(res, area)
        }
    }
    return res
}

func dfs(grid [][]int, x, y int) int {
    grid[x][y] = 0
    res := 1
    for i := 0; i < 4; i++ {
        xx, yy := x+dx[i], y+dy[i]
        if xx >= 0 && xx < len(grid) && yy >= 0 && yy < len(grid[0]) && grid[xx][yy] > 0 {
            res = res + dfs(grid, xx, yy)
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

#### Approach #2: DFS + Stack (**Iterative**)

```go
var (
    dx = []int{0, 1, 0, -1}
    dy = []int{1, 0, -1, 0}
)

func maxAreaOfIsland(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }

    res := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            s := [][]int{{i, j}}
            area := 0
            for len(s) > 0 {
                cell := s[len(s)-1]
                s = s[:len(s)-1]
                x, y := cell[0], cell[1]
                if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) || grid[x][y] == 0 {
                    continue
                }
                grid[x][y] = 0
                area++
                for i := 0; i < 4; i++ {
                    xx, yy := x+dx[i], y+dy[i]
                    s = append(s, []int{xx, yy})
                }

            }
            res = max(res, area)
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```


# 2022-05-20

## [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

### Description

Given a string `s`, find the length of the **longest substring** without repeating characters.

**Example 1:**

```
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```

**Example 2:**

```
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
```

**Example 3:**

```
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
```

**Constraints:**

* `0 <= s.length <= 5 * 10^4`
* `s` consists of English letters, digits, symbols and spaces.

### Solution

#### Approach #0

```go
func lengthOfLongestSubstring(s string) (res int) {
    sList := []rune(s)

    for i := 0; i < len(sList); i++ {
        tmp := 0
        m := make(map[rune]struct{})
        for j := i; j < len(sList); j++ {
            if _, ok := m[sList[j]]; ok {
                break
            }
            m[sList[j]] = struct{}{}
            tmp++
        }
        res = max(res, tmp)
        delete(m, sList[i])
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

#### Approach #1

Approach #1, #2 and #3 shows different process when counting the right side of the window.

```go
func lengthOfLongestSubstring(s string) (res int) {
    m := make(map[byte]struct{})
    i, j := 0, 0
    for ; j < len(s); j++ {
        for ; i < j; i++ {
            if _, ok := m[s[j]]; !ok {
                break
            }
            delete(m, s[i])
        }
        m[s[j]] = struct{}{}
        res = max(res, j-i+1)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

#### Approach #2

```go
func lengthOfLongestSubstring(s string) (res int) {
    m := make(map[byte]struct{})
    i, j := 0, 0
    for j < len(s) {
        in := s[j]
        j++
        if _, ok := m[in]; ok {
            for i < j {
                out := s[i]
                i++
                if out == in {
                    break
                }
                delete(m, out)
            }
        }
        m[in] = struct{}{}
        res = max(res, j-i)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

#### Approach #3

```go
func lengthOfLongestSubstring(s string) (res int) {
    m := make(map[byte]int)
    i := -1
    for j := 0; j < len(s); j++ {
        in := s[j]
        if last, ok := m[in]; ok {
            i = max(last, i)
        }
        m[in] = j
        res = max(res, j-i)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [567. Permutation in String](https://leetcode.com/problems/permutation-in-string/)

### Description

Given two strings `s1` and `s2`, return `true` *if* `s2` *contains a permutation of* `s1`*, or* `false` *otherwise*.

In other words, return `true` if one of `s1`'s permutations is the substring of `s2`.

**Example 1:**

```
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
```

**Example 2:**

```
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
```

**Constraints:**

* `1 <= s1.length, s2.length <= 10^4`
* `s1` and `s2` consist of lowercase English letters.

### Solution

#### Approach #0

```go
func checkInclusion(s1 string, s2 string) bool {
    current := make(map[byte]int)
    target := make(map[byte]int)
    for i := 0; i < len(s1); i++ {
        target[s1[i]]++
    }

    i, j := 0, 0
    valid := 0
    for j < len(s2) {
        in := s2[j]
        j++
        if _, ok := target[in]; ok {
            current[in]++
            if current[in] == target[in] {
                valid++
            }
        }

        for j-i >= len(s1) {
            if valid == len(target) {
                return true
            }
            out := s2[i]
            i++
            if _, ok := target[out]; ok {
                if current[out] == target[out] {
                    valid--
                }
                current[out]--
            }
        }
    }
    return false
}
```

#### Approach #1: Two Pointers

```go
func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    m := make(map[byte]int)
    for i := 0; i < len(s1); i++ {
        m[s1[i]]++
    }

    i, j := 0, 0
    for ; j < len(s2); j++ {
        m[s2[j]]--
        for m[s2[j]] < 0 {
            m[s2[i]]++
            i++
        }
        if j-i+1 == len(s1) {
            return true
        }
    }
    return false
}
```


# 2022-05-19

## [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)

### Description

Given the `head` of a singly linked list, return *the middle node of the linked list*.

If there are two middle nodes, return **the second middle** node.

**Example 1:**

![](https://img.content.cc/a/2022/05/19/08-59-37-482-7b33914b686ad5b8b41b13bcaeb18af6-944d01.jpeg)

```
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
```

**Example 2:**

![](https://img.content.cc/a/2022/05/19/09-00-08-265-4c1a7e6c2b93740ccdbb6bd9873922a5-ae0913.jpeg)

```
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
```

**Constraints:**

* The number of nodes in the list is in the range `[1, 100]`.
* `1 <= Node.val <= 100`

### Solution

#### Approach #0: Single Pointer

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    first, second := head, head
    count := 0
    for first.Next != nil {
        count++
        first = first.Next
    }

    for i := 0; i < count/2+count%2; i++ {
        second = second.Next
    }
    return second
}
```

#### Approach #1: **Fast and Slow Pointer**

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    first, second := head, head
    for second != nil && second.Next != nil {
        first = first.Next
        second = second.Next.Next
    }
    return first
}
```

#### Approach #2: Output to Array

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    var l []*ListNode
    for head != nil {
        l = append(l, head)
        head = head.Next
    }
    return l[len(l)/2]
}
```

## [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

### Description

Given the `head` of a linked list, remove the `nth` node from the end of the list and return its head.

**Example 1:**

![](https://img.content.cc/a/2022/05/19/09-18-34-896-da94924691c022d09f800646b9b72e35-995240.jpeg)

```
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
```

**Example 2:**

```
Input: head = [1], n = 1
Output: []
```

**Example 3:**

```
Input: head = [1,2], n = 1
Output: [1]
```

**Constraints:**

* The number of nodes in the list is `sz`.
* `1 <= sz <= 30`
* `0 <= Node.val <= 100`
* `1 <= n <= sz`

**Follow up:** Could you do this in one pass?

### Solution

#### Approach #0

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    first := head
    count := 0
    for first != nil {
        count++
        first = first.Next
    }
    newHead := &ListNode{0, head}
    second := newHead
    for i := 0; i < count-n; i++ {
        second = second.Next
    }
    second.Next = second.Next.Next
    return newHead.Next
}
```

#### Approach #1

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    var nodeList []*ListNode
    newHead := &ListNode{0, head}
    for cur := newHead; cur != nil; cur = cur.Next {
        nodeList = append(nodeList, cur)
    }
    prev := nodeList[len(nodeList)-n-1]
    prev.Next = prev.Next.Next
    return newHead.Next
}
```

#### Approach #2

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    newHead := &ListNode{0, head}
    fast, slow := newHead, newHead
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    for fast != nil && fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return newHead.Next
}
```


# 2022-05-18

## [344. Reverse String](https://leetcode.com/problems/reverse-string/)

### Description

Write a function that reverses a string. The input string is given as an array of characters `s`.

You must do this by modifying the input array [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) with `O(1)` extra memory.

**Example 1:**

```
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
```

**Example 2:**

```
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
```

**Constraints:**

* `1 <= s.length <= 105`
* `s[i]` is a [printable ascii character](https://en.wikipedia.org/wiki/ASCII#Printable_characters).

### Solution

```go
func reverseString(s []byte) {
    for i, j := 0, len(s)-1; i < j; {
        s[i], s[j] = s[j], s[i]
        i++
        j--
    }
}
```

## [557. Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/)

### Description

Given a string `s`, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

**Example 1:**

```
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
```

**Example 2:**

```
Input: s = "God Ding"
Output: "doG gniD" 
```

**Constraints:**

* `1 <= s.length <= 5 * 104`
* `s` contains printable **ASCII** characters.
* `s` does not contain any leading or trailing spaces.
* There is **at least one** word in `s`.
* All the words in `s` are separated by a single space.

### Solution

#### Approach #0

```go
func reverseWord(s []rune) string {
    for i, j := 0, len(s)-1; i < j; {
        s[i], s[j] = s[j], s[i]
        i++
        j--
    }
    return string(s)
}

func reverseWords(s string) string {
    sList := strings.Split(s, " ")
    var res []string
    for _, aS := range sList {
        res = append(res, reverseWord([]rune(aS)))
    }
    return strings.Join(res, " ")
}
```

#### Approach #1

```go
func reverseWord(s []rune) {
    for i, j := 0, len(s)-1; i < j; {
        s[i], s[j] = s[j], s[i]
        i++
        j--
    }
}

func reverseWords(s string) string {
    r := []rune(s)
    l := 0
    for i, letter := range r {
        if string(letter) == " " {
            reverseWord(r[l:i])
            l = i + 1
        }
    }
    reverseWord(r[l:])
    return string(r)
}
```


# 2022-05-17

## [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/)

### Description

Given an integer array `nums`, move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.

**Note** that you must do this in-place without making a copy of the array.

**Example 1:**

```
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
```

**Example 2:**

```
Input: nums = [0]
Output: [0]
```

**Constraints:**

* `1 <= nums.length <= 104`
* `-231 <= nums[i] <= 231 - 1`

**Follow up:** Could you minimize the total number of operations done?

### Solution

```go
func moveZeroes(nums []int) {
    for i, j := 0, 0; j < len(nums); {
        if nums[j] != 0 {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
        j++
    }
}
```

## [167. Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)

### Description

Given a **1-indexed** array of integers `numbers` that is already ***sorted in non-decreasing order***, find two numbers such that they add up to a specific `target` number. Let these two numbers be `numbers[index1]` and `numbers[index2]` where `1 <= index1 < index2 <= numbers.length`.

Return *the indices of the two numbers,* `index1` *and* `index2`*, **added by one** as an integer array* `[index1, index2]` *of length 2.*

The tests are generated such that there is **exactly one solution**. You **may not** use the same element twice.

Your solution must use only constant extra space.

**Example 1:**

```
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
```

**Example 2:**

```
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
```

**Example 3:**

```
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
```

**Constraints:**

* `2 <= numbers.length <= 3 * 104`
* `-1000 <= numbers[i] <= 1000`
* `numbers` is sorted in **non-decreasing order**.
* `-1000 <= target <= 1000`
* The tests are generated such that there is **exactly one solution**.

### Solution

#### Approach #0

```go
func twoSum(numbers []int, target int) []int {
    for i := 0; i < len(numbers); i++ {
        for j := i + 1; j < len(numbers); j++ {
            if numbers[i]+numbers[j] == target {
                return []int{i + 1, j + 1}
            }
        }
    }
    return []int{}
}
```

#### Approach #1

```go
func twoSum(numbers []int, target int) []int {
    for i, j := 0, len(numbers)-1; i < j; {
        sum := numbers[i] + numbers[j]
        if sum == target {
            return []int{i + 1, j + 1}
        }
        if sum > target {
            j--
        } else {
            i++
        }

    }
    return []int{}
}
```


# 2022-05-16

## [977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)

### Description

Given an integer array `nums` sorted in **non-decreasing** order, return *an array of **the squares of each number** sorted in non-decreasing order*.

**Example 1:**

```
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
```

**Example 2:**

```
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
```

**Constraints:**

* `1 <= nums.length <= 10^4`
* `-10^4 <= nums[i] <= 10^4`
* `nums` is sorted in **non-decreasing** order.

**Follow up:** Squaring each element and sorting the new array is very trivial, could you find an `O(n)` solution using a different approach?

### Solution

```go
func sortedSquares(nums []int) []int {
    length := len(nums)
    left, right := 0, length-1
    res := make([]int, length)

    for pos := length - 1; pos >= 0; pos-- {
        if l, r := nums[left]*nums[left], nums[right]*nums[right]; l > r {
            res[pos] = l
            left++
        } else {
            res[pos] = r
            right--
        }
    }
    return res
}
```

## [189. Rotate Array](https://leetcode.com/problems/rotate-array/)

### Description

Given an array, rotate the array to the right by `k` steps, where `k` is non-negative.

**Example 1:**

```
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
```

**Example 2:**

```
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
```

**Constraints:**

* `1 <= nums.length <= 105`
* `-231 <= nums[i] <= 231 - 1`
* `0 <= k <= 105`

**Follow up:**

* Try to come up with as many solutions as you can. There are at least **three** different ways to solve this problem.
* Could you do it in-place with `O(1)` extra space?

### Solution

```go
func rev(nums []int) {
    length := len(nums)
    for i, j := 0, length-1; i < length/2; i++ {
        nums[i], nums[j-i] = nums[j-i], nums[i]
    }
}

func rotate(nums []int, k int) {
    k %= len(nums)
    rev(nums)
    rev(nums[k:])
    rev(nums[:k])
}
```


# 2022-05-15

## [704. Binary Search](https://leetcode.com/problems/binary-search/)

### Description

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`.

You must write an algorithm with `O(log n)` runtime complexity.

**Example 1:**

```
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
```

**Example 2:**

```
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
```

**Constraints:**

* `1 <= nums.length <= 10^4`
* `-10^4 < nums[i], target < 10^4`
* All the integers in `nums` are **unique**.
* `nums` is sorted in ascending order.

### Solution

```go
func search(nums []int, target int) int {
    low := 0
    high := len(nums) - 1

    for low <= high {
        mid := (low + high) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}
```

## [278. First Bad Version](https://leetcode.com/problems/first-bad-version/)

### Description

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)` which returns whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

**Example 1:**

```
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
```

**Example 2:**

```
Input: n = 1, bad = 1
Output: 1
```

**Constraints:**

* `1 <= bad <= n <= 2^31 - 1`

### Solution

#### Approach #0

```go
/**
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return            true if current version is bad
 *                    false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
    low := 1
    high := n

    for low < high {
        mid := (low + high) / 2
        if isBadVersion(mid) {
            high = mid
            continue
        } else {
            low = mid + 1
        }
    }
    return high
}
```

#### Approach #1

Using package `sort`:

```go
/**
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return            true if current version is bad
 *                    false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
    return sort.Search(n, func(version int) bool { return isBadVersion(version) }
}
```

In this problem, the giving constraints define the range of `n` will not over `2^31-1`. However, in the real world, the value of `mid` may probably overflow. The official sort package shows a way to avoid overflow when computing mid with `int(uint(i+j) >> 1)`.

Deep into the source code of `Search`, and we can know it also uses binary search:

```go
package sort

// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.)
// Search calls f(i) only for i in the range [0, n).
//
// A common use of Search is to find the index i for a value x in
// a sorted, indexable data structure such as an array or slice.
// In this case, the argument f, typically a closure, captures the value
// to be searched for, and how the data structure is indexed and
// ordered.
//
// For instance, given a slice data sorted in ascending order,
// the call Search(len(data), func(i int) bool { return data[i] >= 23 })
// returns the smallest index i such that data[i] >= 23. If the caller
// wants to find whether 23 is in the slice, it must test data[i] == 23
// separately.
//
// Searching data sorted in descending order would use the <=
// operator instead of the >= operator.
//
// To complete the example above, the following code tries to find the value
// x in an integer slice data sorted in ascending order:
//
//    x := 23
//    i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
//    if i < len(data) && data[i] == x {
//        // x is present at data[i]
//    } else {
//        // x is not present in data,
//        // but i is the index where it would be inserted.
//    }
//
// As a more whimsical example, this program guesses your number:
//
//    func GuessingGame() {
//        var s string
//        fmt.Printf("Pick an integer from 0 to 100.\n")
//        answer := sort.Search(100, func(i int) bool {
//            fmt.Printf("Is your number <= %d? ", i)
//            fmt.Scanf("%s", &s)
//            return s != "" && s[0] == 'y'
//        })
//        fmt.Printf("Your number is %d.\n", answer)
//    }
//
func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
        h := int(uint(i+j) >> 1) // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {
            i = h + 1 // preserves f(i-1) == false
        } else {
            j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}
```

## [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/)

### Description

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with `O(log n)` runtime complexity.

**Example 1:**

```
Input: nums = [1,3,5,6], target = 5
Output: 2
```

**Example 2:**

```
Input: nums = [1,3,5,6], target = 2
Output: 1
```

**Example 3:**

```
Input: nums = [1,3,5,6], target = 7
Output: 4
```

**Constraints:**

* `1 <= nums.length <= 10^4`
* `-10^4 <= nums[i] <= 10^4`
* `nums` contains **distinct** values sorted in **ascending** order.
* `-10^4 <= target <= 10^4`

### Solution

```go
func searchInsert(nums []int, target int) int {
    low, high := 0, len(nums)-1

    for low <= high {
        mid := int(uint(low+high) >> 1)
        if nums[mid] == target {
            return mid
        }
        if nums[mid] > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return low
}
```


# Troubleshooting


# A Weird Python Command Not Found Problem

## Problem Statement

I met a weird problem with the following output:

```shell-session
$ python
pyenv: python: command not found

The `python' command exists in these Python versions:
  3.9.11

Note: See 'pyenv help global' for tips on allowing both
      python2 and python3 to be found.
```

What happened??? I just took a nap and turned my computer back on, why did *python* get lost???

## Resolution

Ok... Let me check these paths: `/usr/bin` and `/usr/local/bin` :

```shell-session
$ ls /usr/bin /usr/local/bin | grep python
python3
```

OMG! ONLY `python3` EXISTS!

At that moment, I started to recall if I did anything stupid which removed the system `python` by mistake.&#x20;

After half an hour of useless attempts, it flashed through my mind that I had just upgraded to macOS Monterey 12.3.1 before I went to sleep, and let me check the [release notes](https://developer.apple.com/documentation/macos-release-notes/macos-12_3-release-notes#Python):

> #### Python <a href="#python" id="python"></a>
>
> **Deprecations**
>
> * Python 2.7 was removed from macOS in this update. Developers should use Python 3 or an alternative language instead. (39795874)

Now the truth is out, Apple took a shot at me.

This problem can be fixed simply as I have had another python3 installed by Homebrew.

```shell-session
$ brew install python3
-- snip --
Warning: python@3.9 3.9.12 is already installed and up-to-date.
To reinstall 3.9.12, run:
  brew reinstall python@3.9
```

And now you can simply create a symbolic link to it by:

```shell
sudo ln -s /opt/homebrew/bin/python3 /usr/local/bin/python
```

Finally, try `python` again:

```shell-session
$ python
Python 3.9.12 (main, Mar 26 2022, 15:44:31)
[Clang 13.1.6 (clang-1316.0.21.2)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 
```

## Conclusion

Maybe I should read every release note carefully before I click *UPGRADE NOW.*

## Reference

1. [macOS Monterey 12.3 Release Notes](https://developer.apple.com/documentation/macos-release-notes/macos-12_3-release-notes#Python)