몇 가지 재 미 있 는 인터넷 면접 문제 총화 (업데이트)

하나.
빈 정수 가 아 닌 배열 을 지정 합 니 다. 특정한 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 두 번 씩 나타 납 니 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾 아 라.
설명:
너의 알고리즘 은 선형 시간 복잡 도 를 가 져 야 한다.당신 은 추가 공간 을 사용 하지 않 고 실현 할 수 있 습 니까?
예시 1:
입력: [2, 2, 1] 출력: 1
예시 2:
입력: [4, 1, 2, 1, 2] 출력: 4

비트 연산.
하나의 수가 다 르 거나 그 와 같은 수의 결 과 는 0 이다.
0 이상 또는 하나의 숫자 결 과 는 이 숫자 자체 이다.
그래서 처음부터 끝까지 모든 수 를 한 번 또는 한 번 으로 얻 은 결 과 는 한 번 만 나타 난 수 이 고 다른 수 는 모두 상쇄 되 었 다.


class Solution
{
  public:
    int singleNumber(vector &nums)
    {
        if(nums.size() == 1)
            return nums[0];
        int temp = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            temp = temp ^ nums[i];
        }
        return temp;
    }
};

 
    
          n    ，       。               ⌊ n/2 ⌋    。 
             ，             。 
     1: 
    : [3,2,3]   : 3 
     2: 
    : [2,2,1,1,1,2,2]   : 2 
     ： 
       map       。 
   
class Solution
{
  public:
    int majorityElement(vector &nums)
    {
        map check;
        for (int i = 0; i < nums.size(); i++)
        {
            check[nums[i]]++;
            if(check[nums[i]] > nums.size() / 2)
            {
                return nums[i];
            }
        }
        return 0;
    }
};
  
     ： 
     
   
class Solution
{
  public:
    int majorityElement(vector &nums)
    {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};
  
     ： 
        
   
class Solution
{
  public:
    int majorityElement(vector &nums)
    {
        int temp = -1;
        int count = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if(count == 0)
            {
                temp = nums[i];
                count = 1;
            }
            else
            {
                if(temp == nums[i])
                {
                    count++;
                }
                else
                {
                    count--;
                }
                
            }
            
            
        }
        return temp;
    }
};
  
    
         II 
               m x n    matrix         target。         ： 
   
                。 
                。 
   
    : 
       matrix   ： 
  [ [1, 4, 7, 11, 15], 
  [2, 5, 8, 12, 19], 
  [3, 6, 9, 16, 22], 
  [10, 13, 14, 17, 24], 
  [18, 21, 23, 26, 30] ] 
     target = 5，   true。 
     target = 20，   false。 
    
   
class Solution
{
  public:
    bool searchMatrix(vector> &matrix, int target)
    {
        int row = matrix.size();
        if(row <= 0)
        {
            return false;
        }
        int col = matrix[0].size();
        int i = 0, j = col - 1;
        while(i >= 0 && i < row && j >= 0 && j < col)
        {
            if(matrix[i][j] > target)
            {
                j--;
            }
            else if(matrix[i][j] < target)
            {
                i++;
            }
            else
            {
                return true;
            }
            
        }
        return false;
    }
};
  
   
    
             nums1   nums2，  nums2     nums1  ，   num1         。 
    : 
   
       nums1   nums2          m   n。 
         nums1       （          m + n）    nums2     。 
   
    : 
    : nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3   : [1,2,2,3,5,6] 
    
    
      ，  nums1       nums1      。 
   
   
class Solution
{
  public:
    void merge(vector &nums1, int m, vector &nums2, int n)
    {
        int size = nums1.size();
        int i, j;
        for (i = size - 1, j = m - 1; j >= 0; i--, j--)
        {
            nums1[i] = nums1[j];
        }
        i++, j++;
        int k = 0;
        while(i < size && j < n)
        {
            if(nums1[i] < nums2[j])
            {
                nums1[k++] = nums1[i++];
            }
            else
            {
                nums1[k++] = nums2[j++];
            }
        }
        while(i < size)
        {
            nums1[k++] = nums1[i++];
        }
        while(j < n)
        {
            nums1[k++] = nums2[j++];
        }
    }
};

몇 가지 재 미 있 는 인터넷 면접 문제 총화 (업데이트)

좋은 웹페이지 즐겨찾기