텐센트, 아리교 면접 진제 - 흔한 명제

[텐센트] 2018 여름방학 실습 면접 문제

제목 주소:

최대 하위 그룹과
https://leetcode.com/problems/maximum-subarray/

문제 해결 방법:

배열은nums[0,1,......]
pp[i]는 처음부터 i번째 위치까지의 최대 하위 그룹과
그러면 dp[i]=nums[i]+max(0,dp[i-1))
이 때의 dp[i]는 i라는 위치를 끝으로 해야 하는 하위 그룹의 최대 합을 나타낸다.
따라서 전역 최대 dp[0,1,......]중 가장 큰 것이면 된다.
우리는 dp[i]가 dp[i-1]와만 관련이 있다는 것을 발견했다. 저장 공간을 절약하기 위해 우리는 순환수조의 개념을 사용할 수 있다!

AC 코드:

class Solution {
public:
    int maxSubArray(vector& nums) {
        int len = nums.size();
        int cur = nums[0], ret = nums[0];
        for (int i = 1; i < len; i++) {
            cur = nums[i] + max(0, cur);
            ret = max(cur, ret);
        }
        return ret;
    }
};

 

제목 주소:

계단을 오르다
한 번에 1층이나 2층 계단을 올라갈 수 있는데 n층까지 올라가는 데 몇 가지 상법이 있는지 물어본다.
https://leetcode.com/problems/climbing-stairs/

문제 해결 방법:

1층에는 1가지 상법이 있고, 2층에는 2가지 상법이 있다(2,1->2)
dp[i](i>=3)는 제i층의 상법 총수를 나타낸다. 그러면 i-1, i-2 두 가지로만 올라가는 방법이다.
그래서 dp[i] = dp[i-1] + dp[i-2]
우리는 dp[i]가 dp[i-1], dp[i-2]와만 관련이 있다는 것을 발견했다. 저장 공간을 절약하기 위해 우리는 순환수조의 개념을 사용할 수 있다!
사실 본제도 고전적인 피포나치 이마수열입니다. [오늘의 수프=어제의 수프+그저께 수프...]

AC 코드:

class Solution {
public:
    int climbStairs(int n) {
        //        
        vector dp;
        dp.push_back(1);
        dp.push_back(2);
        
        for(int i = 3; i <= n; i++) {
            dp[1 - i&1] += dp[i&1];
        }
        return dp[1 - n&1];
    }
};

 

[아리] 2019 아리교 모집 시험문제

(수구산구 면접문제)

제목 주소:

무질서한 그룹에서 K번째 큰 원소를 찾습니다
https://leetcode.com/problems/kth-largest-element-in-an-array/

문제 해결 방법:

가장 소박한 방법은 먼저 수조를 정렬한 후 상응하는 위치의 원소를 취하는 것이다.[시간이 걸리고 그룹의 위치가 변경되었습니다.]
최대 더미를 구축하여 매번 더미의 꼭대기를 팝업하면 K번째가 K번째 원소이다.[구축더미, 조정더미의 코드를 써야 한다]
간단한 사고방식은 빠른 정렬에서 추축의 개념을 선택하는 것이다.피봇을 사용하여 세그먼트를 수행하면 K-요소 크기의 절반을 알 수 있습니다.

AC 코드:

class Solution {
public:
    //        
    int findKthLargestHelper(vector& nums, int l, int r, int k) {
        if(l < r) {
            int i = l, j = r, x = nums[i];
            while(i < j) {
                while(i < j && x <= nums[j]) {
                    j--;
                }
                if(i < j) {
                    nums[i++] = nums[j];
                }
                while(i < j && nums[i] < x) {
                    i++;
                }
                if(i < j) {
                    nums[j--] = nums[i];
                }
            }
            nums[i] = x;
            if (i == k) {
                return x;
            } 
            if (i < k) {
                return findKthLargestHelper(nums, i + 1, r, k);
            }
            if (i > k) {
                return findKthLargestHelper(nums, l, i - 1, k);
            }
        }
        return nums[l];
    }
    
    int findKthLargest(vector& nums, int k) {
        int len = nums.size();
        return findKthLargestHelper(nums, 0, len - 1, len - k);
    }
};