?3，1，42，200，15

121，128，49，25，88

5，146，70，2，4

21，33，55，27，560

11，20，31，53，236

300，26，215，279，438

135，148，9，169，76

22，101，14，54，56

72，206，152，80，39

46，62，104，122，179

3. Longest Substring Without Repeating Characters

Medium

Given a string?s, find the length of the?longest?substring?without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        char[] ch = s.toCharArray();
        int left = 0;
        int count = 0;
        int ans = 0;
        for(int right = 0; right < ch.length; right++){
            if(!set.contains(ch[right])){
                set.add(ch[right]);
                count = count + 1;
                ans = Math.max(ans, count);
            }else{
                while(set.contains(ch[right])){
                    set.remove(ch[left]);
                    left++;
                    count--;
                }
                set.add(ch[right]);
                count++;
            }
        }
        return ans;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] ch = new int[128];
        for(int i=0;i<128;i++){
            ch[i]=-1;
        }
        int ans=0;
        int st=0;
        for(int i=0;i<s.length();i++){
            int c = s.charAt(i);
            if(ch[c]!=-1){
                st=Math.max(st,ch[c]);
            }
            ans=Math.max(ans,i-st+1);
            ch[c]=i+1;
        }
        return ans;
    }
}

1. Two Sum

Easy

Given an array of integers?nums?and an integer?target, return?indices of the two numbers such that they add up to?target.

You may assume that each input would have?exactly?one solution, and you may not use the?same?element twice.

You can return the answer in any order.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

42. Trapping Rain Water

Hard

Given?n?non-negative integers representing an elevation map where the width of each bar is?1, compute how much water it can trap after raining.

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}

200. Number of Islands

Medium

Given an?m x n?2D binary grid?grid?which represents a map of?'1's (land) and?'0's (water), return?the number of islands.

An?island?is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

15. 3Sum

Medium

Given an integer array nums, return all the triplets?[nums[i], nums[j], nums[k]]?such that?i != j,?i != k, and?j != k, and?nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

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

121. Best Time to Buy and Sell Stock

Easy

You are given an array?prices?where?prices[i]?is the price of a given stock on the?ith?day.

You want to maximize your profit by choosing a?single day?to buy one stock and choosing a?different day in the future?to sell that stock.

Return?the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return?0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 1) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];//dp[i][0]表示第i天持有股票的最大收益，dp[i][1]表示第i天不持有股票的最大收益
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0],  -prices[i]);//分為是不是今天買(mǎi)入
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//分為是不是今天買(mǎi)
        }
        return dp[prices.length - 1][1];
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for (int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

128. Longest Consecutive Sequence

Medium

Given an unsorted array of integers?nums, return?the length of the longest consecutive elements sequence.

You must write an algorithm that runs in?O(n)?time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

?

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longestLength = 0;

        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentLength += 1;
                }
                longestLength = Math.max(longestLength, currentLength);
            }
        }

        return longestLength;
    }
}

49. Group Anagrams

Solved

Medium

Topics

Companies

Given an array of strings?strs, group?the anagrams?together. You can return the answer in?any order.

An?Anagram?is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

?

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 將每個(gè)出現(xiàn)次數(shù)大于 0 的字母和出現(xiàn)次數(shù)按順序拼接成字符串，作為哈希表的鍵
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

?

25. Reverse Nodes in k-Group

Hard

Topics

Companies

Given the?head?of a linked list, reverse the nodes of the list?k?at a time, and return?the modified list.

k?is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of?k?then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分長(zhǎng)度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子鏈表重新接回原鏈表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }
}

?

88. Merge Sorted Array

Easy

You are given two integer arrays?nums1?and?nums2, sorted in?non-decreasing order, and two integers?m?and?n, representing the number of elements in?nums1?and?nums2?respectively.

Merge?nums1?and?nums2?into a single array sorted in?non-decreasing order.

The final sorted array should not be returned by the function, but instead be?stored inside the array?nums1. To accommodate this,?nums1?has a length of?m + n, where the first?m?elements denote the elements that should be merged, and the last?n?elements are set to?0?and should be ignored.?nums2?has a length of?n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

?

5. Longest Palindromic Substring

Medium

Given a string?s, return?the longest?

palindromic substring?in?s.

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

146. LRU Cache

Medium

Topics

Companies

Design a data structure that follows the constraints of a?Least Recently Used (LRU) cache.

Implement the?LRUCache?class:

• LRUCache(int capacity)?Initialize the LRU cache with?positive?size?capacity.
• int get(int key)?Return the value of the?key?if the key exists, otherwise return?-1.
• void put(int key, int value)?Update the value of the?key?if the?key?exists. Otherwise, add the?key-value?pair to the cache. If the number of keys exceeds the?capacity?from this operation,?evict?the least recently used key.

The functions?get?and?put?must each run in?O(1)?average time complexity.

class LRUCache {
    class Node{
        int key;
        int value;

        Node prev;
        Node next;

        Node(int key, int value){
            this.key= key;
            this.value= value;
        }
    }

    public Node[] map;
    public int count, capacity;
    public Node head, tail;
    
    public LRUCache(int capacity) {
        
        this.capacity= capacity;
        count= 0;
        
        map= new Node[10_000+1];
        
        head= new Node(0,0);
        tail= new Node(0,0);
        
        head.next= tail;
        tail.prev= head;
        
        head.prev= null;
        tail.next= null;
    }
    
    public void deleteNode(Node node){
        node.prev.next= node.next;
        node.next.prev= node.prev;       
        
        return;
    }
    
    public void addToHead(Node node){
        node.next= head.next;
        node.next.prev= node;
        node.prev= head;
        
        head.next= node;      
        
        return;
    }
    
    public int get(int key) {
        
        if( map[key] != null ){
            
            Node node= map[key];
            
            int nodeVal= node.value;
            
            deleteNode(node);
            
            addToHead(node);
            
            return nodeVal;
        }
        else
            return -1;
    }
    
    public void put(int key, int value) {
        
        if(map[key] != null){
            
            Node node= map[key];
            
            node.value= value;
            
            deleteNode(node);
            
            addToHead(node);
            
        } else {
            
            Node node= new Node(key,value);
            
            map[key]= node;
            
            if(count < capacity){
                count++;
                addToHead(node);
            } 
            else {
                
                map[tail.prev.key]= null;
                deleteNode(tail.prev);
                
                addToHead(node);
            }
        }
        
        return;
    }
    
}

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用偽頭部和偽尾部節(jié)點(diǎn)
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通過(guò)哈希表定位，再移到頭部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，創(chuàng)建一個(gè)新的節(jié)點(diǎn)
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加進(jìn)哈希表
            cache.put(key, newNode);
            // 添加至雙向鏈表的頭部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，刪除雙向鏈表的尾部節(jié)點(diǎn)
                DLinkedNode tail = removeTail();
                // 刪除哈希表中對(duì)應(yīng)的項(xiàng)
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通過(guò)哈希表定位，再修改 value，并移到頭部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

?

22. Generate Parentheses

Medium

Given?n?pairs of parentheses, write a function to?generate all combinations of well-formed parentheses.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

101. Symmetric Tree

Easy

Given the?root?of a binary tree,?check whether it is a mirror of itself?(i.e., symmetric around its center).

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return compare(left.right, right.left) && compare(left.left, right.right);
    }
}

14. Longest Common Prefix

Easy

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string?"".文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-861150.html

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}

到了這里，關(guān)于字節(jié)跳動(dòng)高頻題目(1)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！