“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

49. Grouping of letter heterotopic words

I. Title Description:

You are given an array of strings, and you are asked to combine alphabetic anagram words. The list of results can be returned in any order.

An anagram is a new word made by rearranging the letters of the source word, and all the letters in the source word are usually used exactly once.

Example 1:

Input: STRS = [” eat “, “tea”, “tan”, “ate” and “NAT” and “bat”]

Output: [[” bat “], [” NAT “, “tan”], [” ate “, “eat”, “tea”]]

Hash table, Map<String, List>, calculate key for each String

  • Sort, eat -> aet
  • Count. eat -> a1e1t1

Iii. AC Code:

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for(String s : strs){ char[] c = s.toCharArray(); Arrays.sort(c); String key = String.valueOf(c); List<String> value = map.getOrDefault(key, new ArrayList<>()); value.add(s); map.put(key, value); } return new ArrayList<>(map.values()); }}Copy the code

53. Maximum subarray sum

I. Title Description:

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] output: 6 explanation: the maximum sum of consecutive subarrays [4,-1,2,1] is 6.Copy the code

Ii. Analysis of Ideas:

Dynamic programming

Dp [I] is the largest sum of subarrays ending in I

State transition: dp[I] = dp[i-1] > 0? dp[i – 1] + nums[i] : nums[i];

The state transition is only associated with the previous position, so the DP array can be compressed and replaced with a variable

Iii. AC Code:

class Solution { public int maxSubArray(int[] nums) { int dp = nums[0], ans = dp; for(int i = 1; i < nums.length; i++){ dp = dp < 0 ? nums[i] : dp + nums[i]; ans = Math.max(ans, dp); } return ans; }}Copy the code