后台工程师职业能力提升之道

// A ServerCodec implements reading of RPC requests and writing of
// RPC responses for the server side of an RPC session.
// The server calls ReadRequestHeader and ReadRequestBody in pairs
// to read requests from the connection, and it calls WriteResponse to
// write a response back. The server calls Close when finished with the
// connection. ReadRequestBody may be called with a nil
// argument to force the body of the request to be read and discarded.
// See NewClient's comment for information about concurrent access.
type ServerCodec interface {
   ReadRequestHeader(*Request) error
   ReadRequestBody(interface{}) error
   WriteResponse(*Response, interface{}) error

   // Close can be called multiple times and must be idempotent.
   Close() error
}

int spp_handle_input(unsigned flow, void* arg1, void* arg2)

// Reader is the interface that wraps the basic Read method.
//
// Read reads up to len(p) bytes into p. It returns the number of bytes
// read (0 <= n <= len(p)) and any error encountered. Even if Read
// returns n < len(p), it may use all of p as scratch space during the call.
// If some data is available but not len(p) bytes, Read conventionally
// returns what is available instead of waiting for more.
//
// When Read encounters an error or end-of-file condition after
// successfully reading n > 0 bytes, it returns the number of
// bytes read. It may return the (non-nil) error from the same call
// or return the error (and n == 0) from a subsequent call.
// An instance of this general case is that a Reader returning
// a non-zero number of bytes at the end of the input stream may
// return either err == EOF or err == nil. The next Read should
// return 0, EOF.
//
// Callers should always process the n > 0 bytes returned before
// considering the error err. Doing so correctly handles I/O errors
// that happen after reading some bytes and also both of the
// allowed EOF behaviors.
//
// Implementations of Read are discouraged from returning a
// zero byte count with a nil error, except when len(p) == 0.
// Callers should treat a return of 0 and nil as indicating that
// nothing happened; in particular it does not indicate EOF.
//
// Implementations must not retain p.
type Reader interface {
   Read(p []byte) (n int, err error)
}

// Writer is the interface that wraps the basic Write method.
//
// Write writes len(p) bytes from p to the underlying data stream.
// It returns the number of bytes written from p (0 <= n <= len(p))
// and any error encountered that caused the write to stop early.
// Write must return a non-nil error if it returns n < len(p).
// Write must not modify the slice data, even temporarily.
//
// Implementations must not retain p.
type Writer interface {
   Write(p []byte) (n int, err error)
}

// Closer is the interface that wraps the basic Close method.
//
// The behavior of Close after the first call is undefined.
// Specific implementations may document their own behavior.
type Closer interface {
   Close() error
}

// Seeker is the interface that wraps the basic Seek method.
//
// Seek sets the offset for the next Read or Write to offset,
// interpreted according to whence:
// SeekStart means relative to the start of the file,
// SeekCurrent means relative to the current offset, and
// SeekEnd means relative to the end.
// Seek returns the new offset relative to the start of the
// file and an error, if any.
//
// Seeking to an offset before the start of the file is an error.
// Seeking to any positive offset is legal, but the behavior of subsequent
// I/O operations on the underlying object is implementation-dependent.
type Seeker interface {
   Seek(offset int64, whence int) (int64, error)
}

// ReadWriter is the interface that groups the basic Read and Write methods.
type ReadWriter interface {
   Reader
   Writer
}

// ReadCloser is the interface that groups the basic Read and Close methods.
type ReadCloser interface {
   Reader
   Closer
}

// WriteCloser is the interface that groups the basic Write and Close methods.
type WriteCloser interface {
   Writer
   Closer
}

// ReadWriteCloser is the interface that groups the basic Read, Write and Close methods.
type ReadWriteCloser interface {
   Reader
   Writer
   Closer
}

// ReadSeeker is the interface that groups the basic Read and Seek methods.
type ReadSeeker interface {
   Reader
   Seeker
}

// WriteSeeker is the interface that groups the basic Write and Seek methods.
type WriteSeeker interface {
   Writer
   Seeker
}

// ReadWriteSeeker is the interface that groups the basic Read, Write and Seek methods.
type ReadWriteSeeker interface {
   Reader
   Writer
   Seeker
}

*
 * @lc app=leetcode id=212 lang=golang
 *
 * [212] Word Search II
 *
 * https://leetcode.com/problems/word-search-ii/description/
 *
 * algorithms
 * Hard (27.69%)
 * Total Accepted:    100.6K
 * Total Submissions: 363.4K
 * Testcase Example:  '[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]\n["oath","pea","eat","rain"]'
 *
 * Given a 2D board and a list of words from the dictionary, find all words in
 * the board.
 *
 * Each word must be constructed from letters of sequentially adjacent cell,
 * where "adjacent" cells are those horizontally or vertically neighboring. The
 * same letter cell may not be used more than once in a word.
 *
 * Example:
 *
 *
 * Input:
 * words = ["oath","pea","eat","rain"] and board =
 * [
 * ⁠ ['o','a','a','n'],
 * ⁠ ['e','t','a','e'],
 * ⁠ ['i','h','k','r'],
 * ⁠ ['i','f','l','v']
 * ]
 *
 * Output: ["eat","oath"]
 *
 *
 * Note:
 * You may assume that all inputs are consist of lowercase letters a-z.
 */
public List<String> findWords(char[][] board, String[] words) {}

public List<String> findWords(char[][] board, String[] words) {
    List<String> res = new ArrayList<>();
    TrieNode root = buildTrie(words);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs (board, i, j, root, res);
        }
    }
    return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
    char c = board[i][j];
    if (c == '#' || p.next[c - 'a'] == null) return;
    p = p.next[c - 'a'];
    if (p.word != null) {   // found one
        res.add(p.word);
        p.word = null;     // de-duplicate
    }

    board[i][j] = '#';
    if (i > 0) dfs(board, i - 1, j ,p, res); 
    if (j > 0) dfs(board, i, j - 1, p, res);
    if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
    if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
    board[i][j] = c;
}

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode p = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (p.next[i] == null) p.next[i] = new TrieNode();
            p = p.next[i];
       }
       p.word = w;
    }
    return root;
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}

func findWords(board [][]byte, words []string) []string {
  listBoard := constructListBoard(board)
  bMap := constructDict(listBoard)

  resultTmpMap := make(map[string]uint8)
  var found bool
  for i := range words {
    _, found = resultTmpMap[words[i]]
    if found {
      continue
    }
    if search([]byte(words[i]), bMap) {
      resultTmpMap[words[i]] = 0
    }
  }

  result := make([]string, 0, len(resultTmpMap))
  for k, _ := range resultTmpMap {
    result = append(result, k)
  }
  return result
}

func constructListBoard(board [][]byte) (listBoard [][]*fourWayNode) {
  lineCount := len(board)
  listBoard = make([][]*fourWayNode, lineCount)
  colCount := len(board[0])

  for i := range listBoard {
    listBoard[i] = make([]*fourWayNode, colCount)
    for j := range listBoard[i] {
      listBoard[i][j] = &fourWayNode{
        b:    board[i][j],
        line: i,
        col:  j,
      }
    }
  }

  for i := range board {
    for j := range board[i] {
      // above
      if i-1 >= 0 {
        listBoard[i][j].above = listBoard[i-1][j]
      }
      // right
      if j+1 < colCount {
        listBoard[i][j].right = listBoard[i][j+1]
      }
      // below
      if i+1 < lineCount {
        listBoard[i][j].below = listBoard[i+1][j]
      }
      // left
      if j-1 >= 0 {
        listBoard[i][j].left = listBoard[i][j-1]
      }
    }
  }
  return
}

func constructDict(listBoard [][]*fourWayNode) (result map[string][]*searchPath) {
  result = make(map[string][]*searchPath)
  var tmp []*searchPath
  for i := range listBoard {
    for j := range listBoard[i] {
      tmp, _ = result[string(listBoard[i][j].b)]
      result[string(listBoard[i][j].b)] = append(tmp, createPath(nil, listBoard[i][j], fmt.Sprintf("%d_%d", i, j)))
    }
  }
  return
}

func search(word []byte, bMap map[string][]*searchPath) bool {
  found := true
  var tmp, startVec, nextStartVec []*searchPath

  var tmpSlice string
  for k := range word {
    tmpSlice = string(word[:k+1])
    if found {
      tmp, found = bMap[tmpSlice]
      if found {
        if k == len(word)-1 {
          return true
        }
        startVec = tmp
        continue
      }
    }

    for j := range startVec {
      nextStartVec = append(nextStartVec, anyMatch(startVec[j], word[k])...)
    }
    if len(nextStartVec) > 0 {
      bMap[tmpSlice] = nextStartVec
      if k == len(word)-1 {
        return true
      }
    }
    if len(nextStartVec) == 0 {
      break
    }
    startVec = nextStartVec
    nextStartVec = nil
  }
  return false
}

type searchPath struct {
  goThrough map[string]uint8
  current   *fourWayNode
}

func createPath(lastStep *searchPath, newStep *fourWayNode, newKey string) (newPath *searchPath) {
  var outPath searchPath
  outPath.goThrough = make(map[string]uint8)
  if lastStep != nil {
    for k, _ := range lastStep.goThrough {
      outPath.goThrough[k] = 0
    }
  }
  outPath.goThrough[newKey] = 0
  outPath.current = newStep
  return &outPath
}

func anyMatch(path *searchPath, b byte) (out []*searchPath) {
  var tmpKey string
  var found bool

  if path.current.above != nil && path.current.above.b == b {
    tmpKey = fmt.Sprintf("%d_%d", path.current.above.line, path.current.above.col)
    _, found = path.goThrough[tmpKey]
    if !found {
      out = append(out, createPath(path, path.current.above, tmpKey))
    }
  }
  if path.current.right != nil && path.current.right.b == b {
    tmpKey = fmt.Sprintf("%d_%d", path.current.right.line, path.current.right.col)
    _, found = path.goThrough[tmpKey]
    if !found {
      out = append(out, createPath(path, path.current.right, tmpKey))
    }
  }
  if path.current.below != nil && path.current.below.b == b {
    tmpKey = fmt.Sprintf("%d_%d", path.current.below.line, path.current.below.col)
    _, found = path.goThrough[tmpKey]
    if !found {
      out = append(out, createPath(path, path.current.below, tmpKey))
    }
  }
  if path.current.left != nil && path.current.left.b == b {
    tmpKey = fmt.Sprintf("%d_%d", path.current.left.line, path.current.left.col)
    _, found = path.goThrough[tmpKey]
    if !found {
      out = append(out, createPath(path, path.current.left, tmpKey))
    }
  }
  return
}

type fourWayNode struct {
  b    byte
  line int
  col  int

  above *fourWayNode
  right *fourWayNode
  below *fourWayNode
  left  *fourWayNode
}