Welcome everyone

腾讯 PCG 三面

面试 汪明鑫 324浏览 0评论

QQ语音面试

 

  • 自我介绍
  • 为啥想来深圳
  • 负载均衡 及 策略
  • 缓存穿透 及 解决办法
  • 分布式服务治理
  • synchronized 和 lock
  • 大代码 用 synchronized 还是 lock
  • HashMap底层
  • HashTable和ConcurrentHashMap
  • DNS解析
  • TCP三次握手,如果第三次数据传输丢失怎么办?
  • 60% 喜欢篮球,70%喜欢足球,80%喜欢排球,求同时喜欢篮球和足球的
  • 算法题( QQ 共享屏幕 + 摄像头) 求最大回文子串  见leetcode第五题(中等难度)

 

package pers.wmx.interview;

/**
 * @author wmx
 * @date 2020-02-25
 *
 * 算法实现:
 *  * 在大文本中查找最长的回文串(至少2个字符,该字符串反序之后同原字符串一样),
 *  * 并返回(如果没有返回Null)【测试用例:aaabbaccbababac,返回babab】。
 */
public class Main1 {

    public static void main(String[] args) {
        String str = "aaabbaccbababac";
        String result = findStr(str);
        System.out.println(result);
    }

    /**
     * 求最长的回文串
     *
     * @param str
     * @return String
     * @throws
     */
    public static String findStr(String str) {

        //参数校验
        if (str == null || str.length() == 0 || str.length() == 1) {
            return null;
        }

        //初始化结果
        int maxLen = 1;
        String res = str.substring(0, 1);

        // 中心位置枚举到 len - 2 即可
        for (int i = 0; i < str.length() - 1; i++) {

            //基数个回文串 如 aba
            String  oddStr= centerSpread(str, i, i);

            //偶数个回文串 如 aa
            String evenStr = centerSpread(str, i, i + 1);

            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > maxLen) {
                //重置结果
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }

    /**
     * 从中心向两边扩
     *
     * left = right 的时候,此时回文中心是一个字符,回文串的长度是奇数
     * right = left + 1 的时候,此时回文中心是一个空隙,回文串的长度是偶数
     *
     * @param str
     * @param left
     * @param right
     * @return String
     * @throws
     */
    private static String centerSpread(String str, int left, int right) {
        int len = str.length();
        int i = left;
        int j = right;
        //从中间向两边扩
        while (i >= 0 && j < len) {
            if (str.charAt(i) == str.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        return str.substring(i + 1, j);
    }

}

 

 

 

转载请注明:汪明鑫的个人博客 » 腾讯 PCG 三面

喜欢 (0)

说点什么

您将是第一位评论人!

提醒
avatar
wpDiscuz