风云的ARTS打卡(第三周)

第3周

Algorithm: 

最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。

解:

可以用“中心扩展法”,难点是要处理好奇数字符回文和偶数字符回文的情况。

class Solution {

    public String longestPalindrome(String str) {

        int n = str.length();

        if (n <= 1) return str;

        int lMax = 0;

        int beginIdx = 0, endIdx = 0;

        for (int i = 0; i < n; ++i) {

            int r = 1;

            int r1 = 1;

            // abcba的情况

            while (true) {

                if ((i - r) >= 0 && (i + r) <= (n - 1) && str.charAt(i - r) == str.charAt(i + r)) {

                    if (r*2+1 > lMax) {

                        lMax = 2*r+1;

                        beginIdx = i - r;

                        endIdx = i + r;

                    }

                    ++r;

                } else {

                    break;

                }

            } // while(true)


            //abba的情况

            while (true) {

                if ((i - r1 + 1) >= 0 && (i + r1) <= (n - 1) &&

                    str.charAt(i - r1 + 1) == str.charAt(i + r1)) {

                        if (r1*2 > lMax) {

                            lMax = r1*2;

                            beginIdx = i - r1 + 1;

                            endIdx = i + r1;

                }

                ++r1;

                } else {

                    break;

                }

            } // while(true)

        }

        String subStr = str.substring(beginIdx, endIdx+1); //如果没找到回文,默认返回第一个字符

        return subStr;       

    }

}

后续:

这道题有O(n)的算法,后面要再思考、学习一下。


Review:  

 因为项目中发现的mysql死锁问题,在搜索引擎里挑了一篇排在前面的关于mysql锁的英文文章读了一下。

Explaining InnoDB Explicit Locking Mechanisms

文章讲解了mysql锁的基本机制,但其实太基本了,没有深入原理,内容太少。所以其实有些英文文章也不是都很好的。


Tip:

项目中发生mysql死锁。

场景:并发insert_update(insert,如果没有主键重则插入,如果主键重则update)同一条记录。

原因:insert会在记录上加上排他意向锁、update会加上排他锁,在多线程并发操作同一条记录时会相互冲突产生死锁。具体产生死锁的过程,还需要详细分析,详见下面Share部分的链接文章。

解决办法:

1、不同线程用id来区分操作的数据,避免不同事务操作同一条记录;

2、先查询是否存在记录;如果存在,则执行update;如果不存在,则执行insert。


Share:

mysql insert锁机制(insert死锁)

这篇中文博文写的很相识,比上文那篇英文文章深入很多,值得细读。更深入研究的话,可以进一步学习文章引用的资料,其实mysql的官方文档中关于innodb锁机制的描述最应该认真学习。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • <center>#1 Two Sum</center> link Description:Given an arr...
    铛铛铛clark阅读 2,226评论 0 3
  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔...
    开心的锣鼓阅读 3,353评论 0 9
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,425评论 0 2
  • 单纯,她是一个人。 一个远离世俗,空无一物的人。 她简单,她纯真,她有说不完的好, 纵使包袱万千,路途万里,艰辛万...
    残影末路阅读 201评论 0 0
  • 一个人最应突破的网,是自己! 一个人最难突破的网,是自己!
    二小姐的马阅读 310评论 1 2