每日一题aaa~

1. 最长回文子串

题目描述

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

input : "babad"
ouput : "bab"
注意 : "aba" 也是一个有效答案

题解 : https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

暴力解法:

public static String longestPalindrome( String str ){
        if (str.length() < 2)
            return str;
        int maxLength = 1;
        int startIndex = 0;
        char[] chars = str.toCharArray();

        for (int i = 0; i < chars.length - 1; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (j - i + 1 > maxLength && isPalindrome(chars , i , j)) {
                    maxLength = j - i + 1;
                    startIndex = i;
                }
            }
        }
        return str.substring(startIndex , startIndex + maxLength);
    }

    public static boolean isPalindrome(char[] chars , int left , int right){

        while (left < right){
            if (chars[left] != chars[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

中心扩展:

public static String longestPalindrome( String str ){
        if (str == null || str.length() < 1) return "";
        int startIndex = 0;
        int endIndex = 0;

        for (int i = 0; i < str.length(); i++) {
            int len1 = expandAroundCenter(str , i , i);
            int len2 = expandAroundCenter(str , i , i + 1);

            int len = Math.max(len1 , len2);
            if (len > endIndex - startIndex){
                startIndex = i - (len - 1) / 2;
                endIndex = i + len / 2;
            }
        }
        return str.substring(startIndex , endIndex + 1);
    }
    public static int expandAroundCenter(String str , int left , int right){
        int leftIndex = left;
        int rightIndex = right;

        while (leftIndex >= 0 && rightIndex < str.length() && str.charAt(leftIndex) == str.charAt(rightIndex)) {
            leftIndex--;
            rightIndex++;
        }
        return rightIndex - leftIndex - 1;
    }

2. 重建二叉树

根据二叉树的中序遍历和先序遍历求恢复二叉树


static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    static HashMap indexMap = new HashMap<>();
    public static TreeNode buildTree(int[] preorder , int[] inorder){
        if (preorder.length != inorder.length) return null;
        //存中序遍历的值和节点
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i] , i);
        }
        return RebuildTree(preorder , 0, preorder.length - 1, 0);
    }

    /**
     *
     * @param preOrder 前序遍历数组
     * @param preLeft  前序遍历开始的index
     * @param preRight 前序遍历结束的下标
     * @param inLeft   子树在中序遍历的第一个下标
     * @return
     */
    public static TreeNode RebuildTree(int[] preOrder , int preLeft , int preRight , int inLeft){
        //System.out.println(inLeft);
        if (preLeft > preRight)
            return null;
        // 构建由中序遍历的得到的根节点
        TreeNode root = new TreeNode(preOrder[preLeft]);
        // 得到根节点在中序遍历的索引
        int inIndex = indexMap.get(root.val);
        // 由根节点所在索引和左边界得到左子树的大小
        int leftTreeSize = inIndex - inLeft;

        System.out.println(inLeft);
        // 当前根节点的左子节点在当前节点的下一个
        // 左子树的前序遍历区间在pLeft + 1...pLeft + leftTreeSize , 左子树的前序遍历的第一个节点在中序遍历中的第一个位置
        root.left = RebuildTree(preOrder , preLeft + 1 , preLeft + leftTreeSize , inLeft);

        // 当前根节点的右子节点在当前节点的下一个的下一个
        // 右子树的前序遍历的区间在pLeft + leftTreeSize + 1 ...preRight
        root.right = RebuildTree(preOrder , preLeft + leftTreeSize + 1 , preRight , inLeft + leftTreeSize + 1);
        return root;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int[] pre = new int[length];
        int[] in = new int[length];
        for (int i = 0; i < length; i++) {
            pre[i] = scanner.nextInt();
        }
        for (int i = 0; i < length; i++) {
            in[i] = scanner.nextInt();
        }
        System.out.println(buildTree(pre, in).val);
    }

3. 最小覆盖字串

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
public static String minWindow(String s, String t) {
        if (t == null ||t.length() < 1)
            return "";
        if (s == null || s.length() < 1)
            return "";

        int[] need = new int[128];
        int[] search = new int[128];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        int left = 0;
        int right = 0;
        int count = 0;
        int[] min = new int[]{0 , s.length()};
        while (right < s.length()){
            char c = s.charAt(right);
            // 记录s中的字母数量,如果是need里出现过的,则count++ count < need[].max
            search[c]++;
            if (need[c] > 0 && need[c] >= search[c])
                count++;
            //如果s中的字母在t中全部找到了 , 则左侧开始缩小
            while (count == t.length()){
                c = s.charAt(left);
                if (need[c] > 0 && need[c] >= search[c])
                    count--;
                //如果找到了更小的窗口 , 则更新
                if (right - left < min[1] - min[0]){
                    min[0] = left;
                    min[1] = right;
                }
                search[c]--;
                left++;
            }
            right++;
        }

        return min[1] == s.length() ? "" : s.substring(min[0] , min[1] + 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        System.out.println(minWindow(s, t));
    }

4 寻找两个数组的中位数

public double findMedianSortedArrays(int[] nums1, int[] nums2){
        int[] merge = merge(nums1, nums2);
        return merge.length % 2 == 0 ? (merge[merge.length / 2 - 1] + merge[merge.length / 2]) / 2.0 : merge[merge.length / 2];
    }
    public int[] merge(int[] nums1 , int[] nums2){
        int[] helper = new int[nums1.length + nums2.length];
        int helperIndex = 0;
        int leftIndex1 = 0;
        int leftIndex2 = 0;
        while (leftIndex1 <= nums1.length - 1 && leftIndex2 <= nums2.length - 1){
            helper[helperIndex++] = nums1[leftIndex1] < nums2[leftIndex2] ? nums1[leftIndex1++] : nums2[leftIndex2++];
        }
        while (leftIndex1 <= nums1.length - 1){
            helper[helperIndex++] = nums1[leftIndex1++];
        }
        while (leftIndex2 <= nums2.length - 1){
            helper[helperIndex++] = nums2[leftIndex2++];
        }
        return helper;
    }

5. 找出克隆二叉树中相同的节点


public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (original == null)
            return null;
        if (original == target)
            return cloned;
        //递归
        TreeNode targetCopy = getTargetCopy(original.left, cloned.left, target);
        if (targetCopy != null)
            return targetCopy;
        targetCopy = getTargetCopy(original.right , cloned.right , target);
        if (targetCopy != null)
            return targetCopy;

        return null;
    }

6. 数组中重复的数字

public static int findDuplicate(int[] nums){
        int slow = 0;
        int fast = 0;
        do {
         slow = nums[slow];
         fast = nums[nums[fast]];
        }while (slow != fast);
        slow = 0;
        while (slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

7. 字符串解析

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
int ptr;
    public String decodeString(String s) {
            LinkedList stk = new LinkedList<>();
            ptr = 0;

            while (ptr < s.length()){
                char cur = s.charAt(ptr);
                if (Character.isDigit(cur)){
                    //获取第一个数字进栈
                    String digits = getDigits(s);
                    stk.addLast(digits);
                }
                else if (Character.isLetter(cur) || cur == '['){
                    //获取第一个字母进栈
                    stk.addLast(String.valueOf(s.charAt(ptr++)));
                }
                else {
                    ++ptr;
                    LinkedList sub = new LinkedList<>();
                    while (!"[".equals(stk.peekLast())){
                        sub.addLast(stk.removeLast());
                    }
                    Collections.reverse(sub);
                    //左边括号出栈
                    stk.removeLast();
                    int remTime = Integer.parseInt(stk.removeLast());
                    StringBuffer t = new StringBuffer();
                    String o = getString(sub);
                    while (remTime-- > 0){
                        t.append(o);
                    }
                    stk.addLast(t.toString());
                }
            }

            return getString(stk);
        }
    private String getString(LinkedList sub) {
            StringBuffer res = new StringBuffer();
            for (String s : sub){
                res.append(s);
            }
            return res.toString();
        }


    public String getDigits(String string){
            StringBuffer res = new StringBuffer();
            while (Character.isDigit(string.charAt(ptr))){
                res.append(string.charAt(ptr++));
            }
            return res.toString();
        }

8. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

也是一个比较经典的题了

public int rob(int[] nums){
        if (nums == null || nums.length == 0)
            return 0;
        int length = nums.length;
        if (length == 1)
            return nums[0];
        int first  = nums[0] ;
        int second = Math.max(nums[0] , nums[1]);

        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i] , second);
            first = temp;
        }

        return second;

9. 对称二叉树

public int rob(int[] nums){
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMi(root,root);
    }
    public boolean isMi(TreeNode node1 , TreeNode node2){
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        
        return (node1.val == node2.val) && isMi(node1.right , node2.left) && isMi(node1.left , node2.right);
    }
}

10.拥有最多糖果的孩子

给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。 对每一个孩子,检查是否存在一种方案,将额外的 extraCandies 个糖果分配给孩子们之后,此孩子有 最多 的糖果。注意,允许有多个孩子同时拥有 最多 的糖果数目。

public int rob(int[] nums){
        public List kidsWithCandies(int[] candies, int extraCandies) {
        int n = candies.length;
        int maxCandies = 0;
        for (int i = 0; i < n; ++i) {
            maxCandies = Math.max(maxCandies, candies[i]);
        }
        List ret = new ArrayList();
        for (int i = 0; i < n; ++i) {
            ret.add(candies[i] + extraCandies >= maxCandies);
        }
        return ret;
    }

11. 新21点

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏,描述如下:

爱丽丝以 0 分开始,并在她的得分少于 K 分时抽取数字。 抽取时,她从 [1, W] 的范围中随机获得一个整数作为分数进行累计,其中 W 是整数。 每次抽取都是独立的,其结果具有相同的概率。

当爱丽丝获得不少于 K 分时,她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少?

public int rob(int[] nums){
        public double new21Game(int N, int K, int W) {
        if(K == 0 || N >= (K + W -1))
            return 1;

        double[] dp = new double[K+W];
        for(int i = 0 ;  i <= N ; i++)
            dp[i] = 1;
        dp[K-1]  = 1.0 * (N - K + 1) / W;
        for (int i= K-2 ; i>=0 ;i--)
            dp[i] = dp[i+1] - (dp[i+1+W] - dp[i+1]) / W;

        return dp[0];
    }

12. 乘积数组

剑指原题

public int rob(int[] nums){
        public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] B = new int[n];
        for(int i  = 0, product = 1 ; i < n ; product *= nums[i] , i++)
            B[i] = product;
        for(int i = n - 1 , product = 1 ; i >= 0; product *=nums[i] , i--)
            B[i] *= product;
        return B;
    }

13. 顺时针打印矩阵

今天还是剑指原题

public int rob(int[] nums){
        public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        ArrayList ret = new ArrayList<>();
        int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            for (int i = c1; i <= c2; i++)
                ret.add(matrix[r1][i]);
            for (int i = r1 + 1; i <= r2; i++)
                ret.add(matrix[i][c2]);
            if (r1 != r2)
                for (int i = c2 - 1; i >= c1; i--)
                    ret.add(matrix[r2][i]);
            if (c1 != c2)
                for (int i = r2 - 1; i > r1; i--)
                    ret.add(matrix[i][c1]);
            r1++; r2--; c1++; c2--;
        }
        int[] res = new int[ret.size()];
        for(int i = 0 ; i < ret.size() ; i++){
            res[i] = ret.get(i);
        }
        return res;
    }

14. 最长连续子序列

给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

public int rob(int[] nums){
public int longestConsecutive(int[] nums) {
    HashSet set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
    }
    int max = 0;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        //n - 1 是否存在
        if (!set.contains(num - 1)) {
            int count = 0;
            while (set.contains(num)) {
                count++;
                num += 1;
            }
            max = Math.max(max, count);
        }
    }
    return max;
}

15. 单词接龙II

太难了,CV工程师到此一游。 给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则: 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明: 1. 如果不存在这样的转换序列,返回一个空列表。 2. 所有单词具有相同的长度。 3. 所有单词只由小写字母组成。 4. 字典中不存在重复的单词。 5. 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

public int rob(int[] nums){
class Solution {
    private Map> map;      // 存储构建好的无向图
    private Map> nxtMap;  // 记录每个搜索层次上的candidate节点
    private List> ans;            // 存储答案
    private int minDist;                       // 转化序列的最短长度
    public List> findLadders(String beginWord, String endWord, List wordList) {
        wordList.add(beginWord);
        this.map = new HashMap<>();
        this.nxtMap = new HashMap<>();
        this.ans = new ArrayList<>();
        int n = wordList.size();

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                String a = wordList.get(i), b = wordList.get(j);
                if (check(a, b)) {
                    map.putIfAbsent(a, new HashSet<>());
                    map.putIfAbsent(b, new HashSet<>());
                    map.get(a).add(b);
                    map.get(b).add(a);
                }
            }
        }

        minDist = BFS(beginWord, endWord);
        // 如果minDist为-1,说明不存在这样的转化序列,直接返回空集
        if (minDist == -1) return ans;
        DFS(beginWord, endWord, new HashSet(), new ArrayList());
        return ans;
        
    }

    private void DFS(String cur, String end, Set visit, List path) {
        visit.add(cur);
        path.add(cur);
        if (path.size() == minDist) {
            if (cur.compareTo(end)==0) {
                ans.add(new ArrayList<>(path));
            }
        } else {
            for (String nxt : map.get(cur)) {
                // 优化: 取当前未访问过,且在该层次候选集合中的节点
                if (visit.contains(nxt) || !nxtMap.get(path.size()).contains(nxt)) continue;
                DFS(nxt, end, visit, path);
            }
        }
        visit.remove(cur);
        path.remove(path.size()-1);
       
    }

    private int BFS(String beginWord, String endWord) {
        int level = 0;
        Set visit = new HashSet<>();
        Queue queue = new LinkedList<>();
        queue.offer(beginWord);
        visit.add(beginWord);

        while (!queue.isEmpty()) {
            int size = queue.size();
            nxtMap.put(level+1, new HashSet<>());
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.compareTo(endWord)==0) return level+1;
                for (String nxt : map.getOrDefault(cur, new HashSet<>())) {
                    if (visit.contains(nxt)) continue;
                    visit.add(nxt);
                    queue.offer(nxt);
                    nxtMap.get(level+1).add(nxt);
                }
            }
            level++;
        }
        return -1;
    }

    // 判断字符串a能否通过只改变一个字母转化为b
    private boolean check(String a, String b) {
        int cnt = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) cnt++;
            if (cnt > 1) return false;
        }
        return cnt == 1;
    }
}

16. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。 只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。 示例:

输入:["a==b","b!=a"]
输出:false
解释:如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

艰难的CV工程师

public int rob(int[] nums){
class Solution {
    public boolean equationsPossible(String[] equations) {
        int length = equations.length;
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        for (String str : equations) {
            if (str.charAt(1) == '=') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                union(parent, index1, index2);
            }
        }
        for (String str : equations) {
            if (str.charAt(1) == '!') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                if (find(parent, index1) == find(parent, index2)) {
                    return false;
                }
            }
        }
        return true;
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        while (parent[index] != index) {
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
}

17. 数字翻译位字符串

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。 示例:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

public int rob(int[] nums){
class Solution {
    public int translateNum(int num) {
        if (num < 10)
            return 1;

        int tail = num % 100;
        //当后两位小于9(即后两位为0)或大于26 那么就只能一位一位的分解
        //反之,可以分解一位,也可分解两位

return translateNum(num / 10) + ((9 26) ? translateNum(num / 100) : 0);

}

}

18. 每日温度

请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。


class Solution {
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] ans = new int[length];
        Deque stack = new LinkedList();
        for (int i = 0; i < length; i++) {
            int temperature = T[i];
            while (!stack.isEmpty() && temperature > T[stack.peek()]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }
}

19. 三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。



class Solution {
    public List> threeSum(int[] nums) {
    Arrays.sort(nums);
        List> res = new ArrayList<>();
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break;
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    while(i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while(i < j && nums[j] == nums[--j]);
                } else {
                    res.add(new ArrayList(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}

20. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。



class Solution {
    public int climbStairs(int target) {
        if(target < 3) return target;
        int f1 = 1;
        int f2 = 2;
        int f3 = f1 + f2;
        for (int i = 3 ; i <= target ; i++){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
}

21. 转变数组后最接近目标值的数组和

给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近  target (最接近表示两者之差的绝对值最小)。 如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。 请注意,答案不一定是 arr 中的数字。



class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int len = arr.length;
        int[] pre = new int[len + 1];
        for (int i = 1; i <= len; ++i) {
            pre[i] = pre[i - 1] + arr[i - 1];
        }
        int r = arr[len - 1];
        int res = 0, diff = target;
        for (int i = 1; i <= r; ++i) {
            int index = Arrays.binarySearch(arr, i);
            if (index < 0) {
                index = -index - 1;
            }
            int cur = pre[index] + (len - index) * i;
            if (Math.abs(cur - target) < diff) {
                res = i;
                diff = Math.abs(cur - target);
            }
        }
        return res;
    }
}

22. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。



class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0){
            return "";
        }
        String result = strs[0];
        for(int i = 0 ; i < strs.length ; i++){
            while(strs[i].indexOf(result) != 0){
                result = result.substring(0, result.length() - 1);
                if(result.length() == 0){
                    return "";
                }
            }
        }
        return result;
    }
}

33. 搜索旋转数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。



public class Solution {

    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left  + 1) / 2;
            if (nums[mid] < nums[right]) {
                if (nums[mid] <= target && target <= nums[right]) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            } else {
                if (nums[left] <= target && target <= nums[mid - 1]) {
                    right = mid - 1;
                } else {
                    left = mid;
                }
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
}

34. 最佳观光组合

给定正整数数组 A,A[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的距离为 j - i。 一对景点(i < j)组成的观光组合的得分为(A[i] + A[j] + i - j):景点的评分之和减去它们两者之间的距离。 返回一对观光景点能取得的最高分。



class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        int ans = 0, mx = A[0] + 0;
        for (int j = 1; j < A.length; ++j) {
            ans = Math.max(ans, mx + A[j] - j);
            mx = Math.max(mx, A[j] + j);
        }
        return ans;
    }
}

35.验证回文字符串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明:本题中,我们将空字符串定义为有效的回文串。



class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer str = new StringBuffer();
        for (int i = 0 ; i < s.length() ; i++){
            char ch = s.charAt(i);
            if(Character.isLetterOrDigit(ch)){
                str.append(Character.toLowerCase(ch));
            }
        }
        return str.toString().equals(str.reverse().toString());
    }
}
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复