Kosmos

我以兴趣为饵,钓起生活的大鱼

目录
算法|随便刷刷LeetCode
/  

算法|随便刷刷LeetCode

无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 **最长子串 **的长度。

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
class Solution {
    public int lengthOfLongestSubstring(String s) {
       LinkedList<Character> a= new LinkedList<>();
        int max = 0;
        int length = 0;
        char[] as = s.toCharArray();
        for (char value : as) {
            while(a.contains(value))
                a.removeFirst();
            a.add(value);
            length = a.size();
            if (max < length) {
                max = length;
            }
        }
        return max;
    }
}

拼写单词

给你一份『词汇表』(字符串数组) `words` 和一张『字母表』(字符串) `chars`。

假如你可以用 `chars` 中的『字母』(字符)拼写出 `words` 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。

注意:每次拼写时,`chars` 中的每个字母都只能用一次。

返回词汇表 `words` 中你掌握的所有单词的 **长度之和**。
class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] a = new int[26];
        boolean c = false;
        int count = 0;
        for(int i = 0;i<chars.length();i++)
        {
            a[chars.charAt(i)-'a']++;
        }
        for(int i = 0;i<words.length;i++)
        {
            int[] b = Arrays.copyOf(a,a.length);
            for(int j = 0;j<words[i].length();j++)
            {
                if(--b[words[i].charAt(j)-'a']<0)
                {
                    c = true;
                 break;
                }
            }
            if(c)
            {
                c=!c;
            }
            else{
                count = count+words[i].length();
            }
        }
        return count;
    }
}

最大层内元素和

给你一个二叉树的根节点 `root`。设根节点位于二叉树的第 `1` 层,而根节点的子节点位于第 `2` 层,依此类推。

请你找出层内元素之和 **最大** 的那几层(可能只有一层)的层号,并返回其中 **最小** 的那个。
输入:[1,7,0,7,-8,null,null]
输出:2
解释:
第 1 层各元素之和为 1,
第 2 层各元素之和为 7 + 0 = 7,
第 3 层各元素之和为 7 + -8 = -1,
所以我们返回第 2 层的层号,它的层内元素之和最大
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxLevelSum(TreeNode root) {
        if(root == null)
        {
            return -1;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        int value = root.val;
        int min = 1;
        int ret = 1;
        while(!queue.isEmpty())
        {
            int v = 0;
            int num = queue.size();
            while(num-- > 0){
                TreeNode node = queue.poll();
                if(node.left!=null)
                {
                    queue.offer(node.left);
                    v = v+node.left.val;
                }
                if(node.right!=null)
                {
                    queue.offer(node.right);
                    v = v+node.right.val;
                }
            }
            min++;
            if(v>value)
            {
                value = v;
                ret = min;
            }
        }
        return ret;
    }
}

便于测试,写了一个数组转换成树的方法
返回以index开始的树的头结点

public static TreeNode GenerateTree(Integer[] a,int index)
    {
        if(index>a.length-1)
        {
            return null;
        }
        if(a[index] == null)
        {
            return null;
        }
        TreeNode Head = new TreeNode(a[index]);
        Head.left = GenerateTree(a,2*index+1);
        Head.right = GenerateTree(a,2*index+2);
        return Head;
    }


今日诗词 标题:算法|随便刷刷LeetCode
作者:ellenbboe
地址:https://zdone.top/articles/2019/08/18/1566125443482.html

评论