【第三届字节跳动青训营｜刷题打卡】

 // A symbol is any exported variable or function.
 func (p *Plugin) Lookup(symName string) (Symbol, error) {
    return lookup(p, symName)
 }

int subArr(vector<int> &arr, int target) {
    int slow = 0, fast = 0;
    int res = 0;
    for (; slow < arr.size(); slow++) {
        int temp = 1;
        for (fast = slow; fast < arr.size(); fast++) {
            temp *= arr[fast];
            if (temp <= target) {
                res++;
            } else {
                break;
            }
        }
    }
    return res;
}

int subArr(vector<int> &arr, int target) {
    int slow = 0;
    int res = 0;
    int mul = 1;
    for (int fast = 0; fast < arr.size(); fast++) {
        // 计算当前的乘积
        mul *= arr[fast];
        // 如果乘积超过了慢指针就要开始移动。
        while (mul > target) {
            // mul = mul/arr[slow];
            // slow ++; 的简写
            mul /= arr[slow++];
        }
        // 快指针每向有移动一次增加的符合条件的个数。
        res += (fast - slow + 1);

    }
    return res;
}

#include<iostream>
#include<vector>

using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;

    Node(int x) : val(x), left(nullptr), right(nullptr) {}

    Node(int x, Node *left, Node *right) : val(x), left(left), right(right) {}
};
// 获得树的高度
int getTreeHeight(Node *tree) {
    if (tree == nullptr) {
        return 0;
    }
    int left = getTreeHeight(tree->left);
    int right = getTreeHeight(tree->right);
    return left > right ? left + 1 : right + 1;
}

bool isBalance(Node *tree) {
    if (tree == nullptr) {
        return true;
    }
    // 拿到左子树的高度
    int leftHeight = getTreeHeight(tree->left);
    // 拿到右子树的高度
    int rightHeight = getTreeHeight(tree->right);
    // 是否满足要求
    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    // 判断左子树和右子树是否是二叉平衡树
    return isBalance(tree->right) && isBalance(tree->left);
}

int main() {
    Node *node = new Node(1,
                          new Node(1,
                                   new Node(3,
                                            new Node(4),
                                            nullptr),
                                   new Node(1)),
                          new Node(1));
    cout << isBalance(node) << endl;
    Node *node1 = new Node(1,
                           new Node(1),
                           new Node(1));
    cout << isBalance(node1) << endl;
    return 0;
}

bool IsBalanced(Node *node, int *depth) {
    // 为空高度为0
    if (node == nullptr) {
        *depth = 0;
        return true;
    }

    int nLeftDepth, nRightDepth;
    // 左子树
    bool bLeft = IsBalanced(node->left, &nLeftDepth);
    // 右子树
    bool bRight = IsBalanced(node->right, &nRightDepth);

    if (bLeft && bRight) {
        int diff = nRightDepth - nLeftDepth;
        if (abs(diff) < 2) //左右字树高度差绝对值不超过1
        {
            *depth = 1 + (nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);
            return true;
        }
    }
    return false;
}

bool IsBalanced(Node *pRoot) {
    int depth = 0;

    return IsBalanced(pRoot, &depth);
}

int IsBalanced(Node *node) {
    // 为空高度为0
    if (node == nullptr) {
        return 0;
    }

    // 左子树
    int left = IsBalanced(node->left);
    if (left == -1) return -1;
    int right = IsBalanced(node->right);
    if (right == -1) return -1;
    // -1 表示不满足高度要求
    return abs(left - right) < 2 ? max(left, right) + 1 : -1;

}

bool isBalanced(Node *pRoot) {
    return IsBalanced(pRoot) != -1;
}

SELECT product_type, AVG(sale_price)
FROM Product
where product_create_at >1650434852 
GROUP BY product_type
HAVING AVG(sale_price) >= 2500; 

package exp5

import "sync"

// 自己的map的数据结构
type MyMap struct {
 data map[string]string
    // 加读写锁
 lock sync.RWMutex
}

func NewMyMap() *MyMap {
 return &MyMap{
  data: make(map[string]string),
 }
}

func (myMap *MyMap) Set(key, value string) {
 if myMap.data == nil {
  myMap.data = make(map[string]string)
 }
    // 加锁
 myMap.lock.Lock()
 defer myMap.lock.Unlock()
 myMap.data[key] = value

}

func (myMap *MyMap) Get(key string) string {
 if myMap.data == nil {
  return ""
 }
    // 加 读锁
 myMap.lock.RLock()
 defer myMap.lock.RUnlock()
 return myMap.data[key]
}

func (myMap *MyMap) Del(key string) {
 if myMap.data == nil {
  return
 }
 myMap.lock.Lock()
 delete(myMap.data, key)
 myMap.lock.Unlock()
}

func createMap(t *testing.T) *MyMap {
 m := NewMyMap()
 require.NotNil(t, m)
 return m
}

func TestMyMap(t *testing.T) {
 m := createMap(t)
 n := 10000
 for i := 0; i < n; i++ {
  j := i
  // 开启 1000 个协程，每个协程都会调用 Get 方法
  for k := 0; k < 1000; k++ {
   k := k
   go func() {
    m.Set(strconv.Itoa(j), strconv.Itoa(j+k))
   }()
  }
 }

 for i := 0; i < n; i++ {
  j := i
  // 开启 1000 个协程，每个协程都会调用 Get 方法
  for k := 0; k < 1000; k++ {
   go func() {
    _ = m.Get(strconv.Itoa(j))
   }()
  }

 }

 for i := 0; i < n; i++ {
  j := i
  // 开启 1000 个协程，每个协程都会调用 Del 方法
  for k := 0; k < 1000; k++ {
   go func() {
    m.Del(strconv.Itoa(j))
   }()
  }

 }
}

>>> a = 5
>>> id(5)
1844502817200
>>> id(a)
1844502817200
>>> a = '444'
>>> id(a)
1844504907376
>>> id('444')
1844504907376

def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1) * n 

factorial(4)
factorial(3) * 4
factorial(2) * 3 * 4
factorial(1) * 2 * 3 * 4
factorial(0) * 1 * 2 * 3 * 4
1 * 1 * 2 * 3 * 4
1 * 2 * 3 * 4
2 * 3 * 4
6 * 4
24

def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n - 1, n * acc)

factorial(4, 1)
factorial(3, 4)
factorial(2, 12)
factorial(1, 24)
factorial(0, 24)
24

def foo():
    return foo()

def foo():
    return foo() + 1  # return 1 + foo() 也一样

package main

import "sync"

//二、给定包含 N 个任务 task 的数组 tasks 和整数 K，和一个可并发调用的执行函数 execute，要求实现以下逻辑：
//execute并发调用次数不超过10
//以最快速度执行完所有task
//使用golang的channel实现

func foo(tasks []int, execute func(task int)) {
   wg := &sync.WaitGroup{}
   ch := make(chan struct{}, 10)
   for _, task := range tasks {
      ch <- struct{}{}
      wg.Add(1)
      task := task
      go func() {
         execute(task)
         wg.Done()
         <-ch
      }()

   }
   wg.Wait()
}

func execute(task int) {
   println(task)
}
func main() {
   foo([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, execute)
}

var s struct{}
fmt.Println(unsafe.Sizeof(s)) // prints 0

type S struct {   
    A struct{}
    B struct{}
}
var s S
fmt.Println(unsafe.Sizeof(s)) // prints 0

ListNode *sort(ListNode *head) {
    // 处理空和一个元素
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    // 截断链表
    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *brk = nullptr;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        if (fast == nullptr || fast->next == nullptr) {
            brk = slow;
        }
        slow = slow->next;
    }
    brk->next = nullptr;

    ListNode *headLeft = sort(head);
    ListNode *headRight = sort(slow);

    // 合并

    ListNode dump(0);
    ListNode *cur = &dump;
    // 两个都不为空
    while (headLeft != nullptr && headRight != nullptr) {
        // 降序排列
        if (headLeft->val >= headRight->val) {
            cur->next = headLeft;
            headLeft = headLeft->next;
            cur = cur->next;
        } else {
            cur->next = headRight;
            headRight = headRight->next;
            cur = cur->next;
        }
    }
    if (headLeft != nullptr) {
        cur->next = headLeft;
    }
    if (headRight != nullptr) {
        cur->next = headRight;
    }
    return dump.next;
}
int findK(ListNode *head, int k) {
    ListNode *cur = head;
    while (k-- && cur) {
        cur = cur->next;
    }
    return cur->val;
}

ListNode *merge(ListNode *head1, ListNode *head2) {
    auto *dummyHead = new ListNode(0);
    ListNode *temp = dummyHead, *temp1 = head1, *temp2 = head2;
    while (temp1 != nullptr && temp2 != nullptr) {
        if (temp1->val <= temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        } else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != nullptr) {
        temp->next = temp1;
    } else if (temp2 != nullptr) {
        temp->next = temp2;
    }
    return dummyHead->next;
}

ListNode *sortList(ListNode *head) {
    if (head == nullptr) {
        return head;
    }
    // 计算链表的长度
    int length = 0;
    ListNode *node = head;
    while (node != nullptr) {
        length++;
        node = node->next;
    }
    // 头节点
    auto *dummyHead = new ListNode(0, head);
//  每次将链表拆分成若干个长度为subLen的子链表 , 并按照每两个子链表一组进行合并
    for (int subLength = 1; subLength < length; subLength <<= 1) {
        // curr用于记录拆分链表的位置
        ListNode *prev = dummyHead, *curr = dummyHead->next;
        // 如果链表没有被拆完
        while (curr != nullptr) {
            // 第一个链表的头 即 curr初始的位置
            ListNode *head1 = curr;
            // 拆分出长度为subLen的链表1
            for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                curr = curr->next;
            }
//            拆分subLen长度的链表2



            ListNode *head2 = curr->next; // 第二个链表的头  即 链表1尾部的下一个位置
            curr->next = nullptr; // 断开第一个链表和第二个链表的链接
            curr = head2; // 第二个链表头 重新赋值给curr
//            / 再拆分出长度为subLen的链表2
            for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                curr = curr->next;
            }
//            再次断开 第二个链表最后的next的链接
            ListNode *next = nullptr;
            if (curr != nullptr) {
                next = curr->next; // next用于记录 拆分完两个链表的结束位置
                curr->next = nullptr;
            }

//            合并两个subLen长度的有序链表
            ListNode *merged = merge(head1, head2);
            prev->next = merged;
            while (prev->next != nullptr) {
                prev = prev->next;  // 将prev移动到 subLen*2 的位置后去
            }
            curr = next;  // next用于记录 拆分完两个链表的结束位置
        }
    }
    return dummyHead->next;
}

type Content struct {
 foo string
}

type Queue struct {
 ch chan Content
}

func NewQueue(bufSize int) *Queue {
 return &Queue{
  ch: make(chan Content, bufSize),
 }
}

func (q *Queue) Push(c Content) {
 q.ch <- c
}

func (q *Queue) Pop() Content {
 return <-q.ch
}

import (
 "strconv"
 "testing"
)

func BenchmarkNewQueue(b *testing.B) {
 bufSize := 10
 q := NewQueue(bufSize)
 for i := 0; i < b.N; i++ {
  i := i
  go func() {
   q.Push(Content{foo: strconv.Itoa(i)})
  }()
 }
 for i := 0; i < b.N; i++ {
  go func() {
   q.Pop()
  }()
 }
}

package exp8

import (
 "fmt"
 "log"
 "sync"
)

type Content struct {
 foo string
}

type Queue struct {
 ch       []Content           // 处理的内容
 index    int                 // 下一个要放的的位置
 tail     int                 // 当前队列的尾部
 mutex    sync.Mutex          // 互斥锁
 auditing map[string]struct{} // 已经处理过的内容
 size     int                 // 队列的大小
}

func NewQueue(bufSize int) *Queue {
 return &Queue{
  ch:       make([]Content, bufSize),
  auditing: make(map[string]struct{}, bufSize),
  size:     bufSize,
  index:    0,
  tail:     0,
 }
}

func (q *Queue) Push(c Content) error {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 // 如果已经在队列中了，忽略
 if _, ok := q.auditing[c.foo]; ok {
  return fmt.Errorf("error: %s already in queue", c.foo)
 }
 // 如果队列已满，忽略
 if (q.index+1)%q.size == q.tail {
  return fmt.Errorf("error: queue is full")
 }
 q.ch[q.index] = c
 q.auditing[c.foo] = struct{}{}
 q.index = (q.index + 1) % q.size
 log.Print("push: ", c.foo, " index:", q.index, " tail:", q.tail, " content:", q.ch)
 return nil
}

func (q *Queue) Pop() (Content, error) {
 q.mutex.Lock()
 defer q.mutex.Unlock()
 // 如果队列为空，忽略
 if q.tail == q.index {
  return Content{}, fmt.Errorf("error: queue is empty")
 }
 c := q.ch[q.tail]
 q.ch[q.tail] = Content{}
 delete(q.auditing, c.foo)

 q.tail = (q.tail + 1) % q.size
 log.Print("pop: ", c.foo, " index:", q.index, " tail:", q.tail)
 return c, nil
}

package exp8

import (
 "strconv"
 "sync"
 "testing"
)

func BenchmarkNewQueue(b *testing.B) {
 bufSize := 10
 q := NewQueue(bufSize)
 b.Log(b.N)
 for i := 0; i < b.N; i++ {
  i := i
  go func() {
   q.Push(Content{foo: strconv.Itoa(i)})
  }()
 }
 for i := 0; i < b.N; i++ {
  go func() {
   b.Log(q.Pop())
  }()
 }
}

func TestNewQueue(t *testing.T) {
 q := NewQueue(10)
 n := 100
 wg := &sync.WaitGroup{}
 for i := 0; i < n; i++ {
  i := i
  wg.Add(1)
  go func() {
   c, err := q.Pop()
   if err != nil {
    t.Log(err)
   } else {
    t.Logf("get %v", c)
   }
   wg.Done()
  }()
  // 消费者多于生产者，队列会为空等待
  if i%2 == 0 {
   wg.Add(1)
   go func() {
    err := q.Push(Content{foo: strconv.Itoa(i % 10)})
    if err != nil {
     t.Log(err)
    } else {
     t.Logf("push %d", i%10)
    }
    wg.Done()
   }()
  }

 }
 wg.Wait()
}

=== RUN   TestNewQueue
    chan_test.go:36: error: queue is empty
    chan_test.go:36: error: queue is empty
    chan_test.go:36: error: queue is empty
    chan_test.go:36: error: queue is empty
2022/04/21 14:19:51 push: 0 index:1 tail:0 content:[{0} {} {} {} {} {} {} {} {} {}]
    chan_test.go:49: push 0
2022/04/21 14:19:51 pop: 0 index:1 tail:1
    chan_test.go:38: get {0}
    chan_test.go:36: error: queue is empty
2022/04/21 14:19:51 push: 4 index:2 tail:1 content:[{} {4} {} {} {} {} {} {} {} {}]
    chan_test.go:49: push 4
2022/04/21 14:19:51 pop: 4 index:2 tail:2
    chan_test.go:38: get {4}
    chan_test.go:36: error: queue is empty
...