This is the fourth day of my participation in the August Text Challenge.More challenges in August

611. Number of valid triangles

Given an array of non-negative integers, your task is to count the number of triples that can form the three sides of a triangle.

Example 1:

Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3 Note:

The length of the array cannot exceed 1000. The integer range in the array is [0, 1000].

Their thinking

  1. The condition for forming a triangle is that the longest side is less than the sum of the other sides, so we can first enumerate the longest side A and the lesser side B, and we can get that the minimum length of the triangle is a-b+1
  2. Through the dichotomy method we can find the position of the smallest side length. Anything greater than the smallest side length satisfies the question and is added to the result

code

class Solution {
    public int triangleNumber(int[] nums) {

        int n=nums.length,res=0;
        Arrays.sort(nums);
        for (int i=n-1; i>=2; i--) {for (int j=i-1; j>=1; j--) {int tar=nums[i]-nums[j]+1;
                int l=0,r=j-1;
                while (l<=r)
                {
                    int mid=(r-l)/2+l;
                    if (nums[mid]>=tar)
                        r=mid-1;
                    else l=mid+1; } res+=j-l; }}returnres; }}Copy the code

3. The oldest string without repeating characters

Given a string s, find the length of the smallest string that does not contain repeating characters.

  • Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

  • Example 2:

Input: s = “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1.

  • Example 3:

Input: s = “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wKE”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.

  • Example 4:

Input: s = “output: 0

Their thinking

Use a sliding window to maintain a range of no duplicate letters. Use set to maintain the type of letters in the window

  1. Enumerated right border, add the right boundary element window, if the set contains the right boundary of letters, that window is repeating elements, so we need to constantly move the left border, until you find repeating elements, will strip out the repeat element, we can add right border to the window, the window is a legitimate window
  2. For all legal Windows, find the maximum length

code

class Solution {
    public int lengthOfLongestSubstring(String s) {

        Set<Character> set=new HashSet<>();
        int l=0,r=0,n=s.length(),max=0;
        while (r<n)
        {
            if (set.contains(s.charAt(r))) {
                while(s.charAt(l)! =s.charAt(r)) { set.remove(s.charAt(l)); l++; } l++; } set.add(s.charAt(r)); r++; max=Math.max(max,r-l); }returnmax; }}Copy the code