Skip to content

Latest commit

 

History

History
120 lines (93 loc) · 3.34 KB

arts-0007.md

File metadata and controls

120 lines (93 loc) · 3.34 KB

1.Algorithm

[5]  Longest Palindromic Substring

Medium    string    Dynamic Programming

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example2:

Input: "cbbd"
Output: "bb"

解答 本题可以采用暴力方式或者动态规划方法来进行处理

(1).暴力方式, 3 层循环，时间复杂度 O(n^3)
func longestPalindrome1(s string) string {
	length := len(s)
	if length < 2 {
		return s
	}

	begin, maxLength := 0, 1
	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			if j-i+1 > maxLength && validPalindromic(s, i, j) {
				maxLength = j - i + 1
				begin = i
			}
		}
	}
	return s[begin : begin+maxLength]
}

func validPalindromic(s string, begin, end int) bool {
	for begin < end {
		if s[begin] != s[end] {
			return false
		}
		begin++
		end--
	}
	return true
}

2.Review

How does a HashMap work in JAVA

  • V put(K key, V value)

  • V get(Object key)

  • V remove(Object key)

  • Boolean containsKey(Object key)

  • A HashMap stores data into multiple singly linked lists of entries (also called buckets or bins)

  • All the keys with the same hash value are put in the same linked list (bucket). Keys with different hash values can end-up in the same bucket.

  • a part of the Entry implementation in JAVA 7:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
…
}

JAVA 8 improvements

  • By inheritance, the inner table can contain both Node (linked list ) and TreeNode (red-black tree). Oracle decided to use both data structures with the following rules: – If for a given index (bucket) in the inner table there are more than 8 nodes, the linked list is transformed into a red black tree – If for a given index (bucket) in the inner table there are less than 6 nodes, the tree is transformed into a linked list

  • a part of the Node implementation in JAVA 8:

static class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;
     ....
}
  • A TreeNode is a red-black tree structure that stores really more information so that it can add, delete or get an element in O(log(n)).

3.Tip

本周暂时无分享的知识点，上线系统中我觉得需要做好以下几个方面：

  • 程序的运行日志：
    • 日志的级别
    • 应该打印哪些日志，一方面如果日志比较多，无法定义问题，等于没有日志
  • 监控：
    • 只有加入了监控，才能进行比对，有比较的基准
    • 这周主机加入了Zabix监控，目前基础的监控指标待进行深入学习

4.Share

这周末开始学习编译原理方面的知识了，目前主要跟着极客时间上的<<编译原理之美>>和<<编译原理实战课>>学习，前期主要把编译原理的基础知识过一遍，这样能更好的学习比较各种语言的优劣及语言的编程范式。

  • 词法分析
  • 语法分析
  • 语义分析