Deduct questions 169, 171, 189, 198, 202

Posted Jun 28, 20205 min read

Deduct questions 169, 171, 189, 198, 202

169, most elements

image.png

Code:

class Solution {
    public int majorityElement(int[]nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}
  1. The serial number of the Excel table

Problem solving ideas:

  • Tags:string traversal, hex conversion
  • Initialization result ans = 0, each letter is subtracted from A during traversal, because A represents 1, so after the subtraction, each number needs to add 1, calculate its representative
  • Numeric value = letter- A + 1
  • Because there are 26 letters, it is equivalent to 26 hexadecimal, and every 26 numbers will advance one digit
  • So each traversal one ans = ans * 26 + num
  • Taking ZY as an example, the value of Z is 26 and the value of Y is 25, then the result is 26 * 26 + 25=701
  • Time complexity:O(n)

Code:

class Solution {
    public int titleToNumber(String s) {
        int ans = 0;
        for(int i=0;i<s.length();i++) {
            int num = s.charAt(i)-'A' + 1;
            ans = ans * 26 + num;
        }
        return ans;
    }
}

189, turn array

image.png

Solution one:

The easiest way is to rotate k times, rotating the array 1 element at a time.

Complexity analysis

Time complexity:O(n*k). Each element is moved 1 step O(n) k times O(k).

Space complexity:O(1). No extra space is used.

Code one:

public class Solution {
    public void rotate(int[]nums, int k) {
        int temp, previous;
        for(int i = 0; i <k; i++) {
            previous = nums[nums.length-1];
            for(int j = 0; j <nums.length; j++) {
                temp = nums[j];
                nums[j]= previous;
                previous = temp;
            }
        }
    }
}

Problem solving idea 2:

We can use an extra array to put each element in the correct position, that is, the subscript i in the original array, we put it at(i+k)%of the array length. Then copy the new array into the original array.

Code two:

class Solution {
    public void rotate(int[]nums, int k) {
        int[]a=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            a[(i+k)%nums.length]=nums[i];
        }
        for(int i=0;i<nums.length;i++){
            nums[i]=a[i];
        }
    }
}
  1. Fighting at home

Question:

You are a professional thief and plan to steal houses along the street. There is a certain amount of cash hidden in each room. The only limiting factor for your theft is that the adjacent houses are equipped with an interconnected anti-theft system. If two adjacent houses are hacked into by the same night, the system will automatically call the police .

Given a non-negative integer array representing the amount of money stored in each house, calculate the maximum amount that can be stolen in one night without touching the alarm device.

Example 1:

Input:[1,2,3,1]Output:4 Explanation:Theft of house 1(amount = 1), then theft of house 3(amount = 3). The maximum amount stolen = 1 + 3 = 4.

Example 2:

Input:[2,7,9,3,1]Output:12 Explanation:Theft of house 1(amount = 2), theft of house 3(amount = 9), then theft of house 5(amount = 1)). The maximum amount stolen = 2 + 9 + 1 = 12.

Tips:

0 <= nums.length <= 100 0 <= nums[i]<= 400

Problem solving ideas:

Consider the simplest case first. If there is only one house, then stealing the house can steal the maximum total amount. If there are only two houses, the two houses are adjacent and cannot be stolen at the same time. Only one of them can be stolen. Therefore, the house with the higher amount of money can be stolen to the highest total amount.

1. If there are more than two houses, how should I calculate the maximum total amount that can be stolen? For the k~(k>2) houses, there are two options:

2. If you steal the kth house, then you cannot steal the k-1th house. The total amount of theft is the sum of the highest total amount of the first k-2 houses and the kth house.

The k-th house is not stolen, and the total amount of theft is the highest total amount of the first k-1 houses.

Choose the option with the larger total amount of theft among the two options. The total amount of theft corresponding to this option is the highest total amount that can be stolen from the first k houses.

Using dp[i]to represent the maximum total amount of money that can be stolen from the first i houses, then there is the following state transfer equation:

dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);

Code:

class Solution {
    public int rob(int[]nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        int length=nums.length;
        if(length==1){
            return nums[0];
        }
        int[]dp=new int[length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<length;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[length-1];
    }
}

202, happy number

Question:

Write an algorithm to determine whether a number n is a happy number.

"Happy number" is defined as:for a positive integer, each time the number is replaced by the sum of the squares of the numbers in each position, and then repeat this process until the number becomes 1, it may also be an infinite loop but never change To 1. If it can become 1, then this number is the happy number.

If n is a happy number, return True; otherwise, return False.

Examples:

Input:19 Output:true Explanation:12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

Solution one:

The algorithm is divided into two parts, we need to design and write code.

1. Given a number n, what is its next number?

2. According to a series of numbers to judge whether we have entered a cycle.

In the first part, we do the digital separation according to the requirements of the problem and find the sum of squares.

Part 2 can be done using HashSet. Each time the next number in the chain is generated, we check whether it is already in the HashSet.

- If it is not in the HashSet, we should add it.

- If it is in a HashSet, it means we are in a loop, so it should return false.

The reason we use HashSet instead of vectors, lists, or arrays is because we repeatedly check for the presence of a number. It takes O(1) time to check whether the number is in the hash set, and O(n) time for other data structures. Choosing the right data structure is a key part of solving these problems.

The core idea is to use a HashSet and recursion. Through recursion we can determine whether the result 1 will appear at the end. Through HashSet we can know whether it is a loop.

Code one:

class Solution {

    private int getNext(int n) {
        int totalSum = 0;
        while(n> 0) {
            int d = n%10;
            n = n/10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while(n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

Problem solving idea 2:

The principle is that we pass two pointers, one fast and one slow. If it is a happy number, then the fast pointer will reach the number 1 first, which is the end. If it is not a happy number, then fast and slow The pointer will finally meet on a certain number. In the code writing, we can make the fast pointer execute one more step each time, that is, fastRunner = getNext(getNext(fastRunner));

Code two:

class Solution {
    public int getNext(int n){
        int totalSum=0;
        while(n>0){
            int d=n%10;
            n=n/10;
            totalSum+=d*d;
        }
        return totalSum;
    }
    public boolean isHappy(int n) {
        int slowRunner=n;
        int fastRunner=getNext(n);
        while(fastRunner!=1&&slowRunner!=fastRunner){
            slowRunner=getNext(slowRunner);
            fastRunner=getNext(getNext(fastRunner));
        }
        return fastRunner==1;
    }
}