8.31 Tencent interview

8.31 Tencent interview

Two arithmetic questions

Enter a set of numbers , Output the second largest number . Avoid using the sorting function that comes with the language

requirement ： Use one-time traversal to realize

Thought analysis

Find the first k Big element , We need to learn to maintain a small top stack to achieve , If the element is larger than the top of the heap, put it in the heap , Here is the second element, which is relatively simple .

Code implementation

public int getSecond(int[] nums) {
    
        //a  Is the maximum value.  b  Is the second largest value 
        int a = Integer.MIN_VALUE, b = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
    
            if (nums[i] > a) {
    b = a; a = nums[i];}
            else if (nums[i] > b) b = nums[i];
        }
        return b;
    }

Enter two integers n and m, From the sequence 1,2,3…….n Take a few numbers at random , Make the sum equal to m , Ask for a list of all possible combinations , Arrange from small to large

Thought analysis

List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
// From  index  To  n  Middle sum is m Result 
public void dfs(int index, int m, int n) {
    
    if (m == 0) {
    
        res.add(new ArrayList<>(list));
    } else {
    
        for (int i = index; i <= m && i <= n; i++) {
    
            list.add(i);
            dfs(i + 1, m - i, n);
            list.remove(list.size() - 1);
        }
    }
}

The type of the second question can be changed into , Get the number of conditions from the array , Similar topics are

• 77. Combine

• 46. Full Permutation

• 47. Full Permutation II