Binary Search 二分法

374. Guess Number Higher or Lower 猜數(shù)字大小

有人會(huì)在1至n之間選一個(gè)數(shù)字，你來根據(jù)那個(gè)人的提示猜數(shù)字，那個(gè)人返回-1，說明我們猜的小了 ，1說明猜大了，0說明我們找到了那個(gè)數(shù)組
“那個(gè)人”在題目里用函數(shù)guess(int num) 表示

使用到的思想：二分法

class Solution {
public:
    int guessNumber(int n) {
        if (guess(n) == 0) return n;
        int left = 1, right = n;
        while (left < right) 
        {
            int mid = left + (right - left) / 2, t = guess(mid);
            if (t == 0) return mid;
            else if (t == 1) left = mid;
            else right = mid;
        }
        return left;
    }
};

33. Search in Rotated Sorted Array 在旋轉(zhuǎn)有序數(shù)組中搜索

給一個(gè)升序的數(shù)組，這個(gè)數(shù)組的一部分元素可能被旋轉(zhuǎn)：
例如 [0,1,2,4,5,6,7] 旋轉(zhuǎn)完后可能變?yōu)?[4,5,6,7,0,1,2]。
現(xiàn)在去查找給出的一個(gè)元素是否在數(shù)組中存在，存在則返回下標(biāo)，否則返回-1.

使用到的數(shù)據(jù)結(jié)構(gòu)：vector
使用到的思想：二叉搜索

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size(); 
        if (n == 0) return -1;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            //如果mid值小于right值，說明數(shù)組右半部分是遞增的，例如7 8 1 2 3 4 5 6
            else if (nums[mid] < nums[right]) {
                //如果target值為5，則把left設(shè)置為mid+1
                if (nums[mid] < target && nums[right] >= target) 
                    left = mid + 1;
                //如果target值為8，則把right值設(shè)置為mid-1
                else right = mid - 1;
            //如果mid值大于right值，說明數(shù)組右半部分是有旋轉(zhuǎn)的，例如4 5 6 7 8 1 2
            } else {
                //這時(shí)如果target為4，把right設(shè)置為mid-1
                if (nums[left] <= target && nums[mid] > target) 
                    right = mid - 1;
                //如果target為1，則把left設(shè)置為mid+1
                else left = mid + 1;
            }
        }
        return -1;
    }
};

Hash Table 哈希表

49. Group Anagrams 分組錯(cuò)位圖

將單詞進(jìn)行分組，不同單詞分在一組的依據(jù)是組成單詞的字母是一樣的，順序可以不一致。例如：
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

使用到的數(shù)據(jù)結(jié)構(gòu)：unordered_map
使用到的算法技巧：先排序

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> mv;
        for (int i= 0; i < strs.size(); ++i) {
            string t = strs[i];
            //將strs中的元素排序，排序完的t作為key，原本的strs[i]作為value
            sort(t.begin(), t.end());
            mv[t].push_back(strs[i]);
        }
        //c++中一種遍歷map的快捷方式
        for (auto a : mv) {
            res.push_back(a.second);
        }
        return res;
    }
};

如果不使用排序，我們就要把strs中的元素映射到一個(gè)26位的數(shù)組中，然后重新按照26位字母順序組成key值

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string> >res;
        unordered_map<string,vector<string>> mv;
        for(int i= 0; i < strs.size(); ++i)
        {
            vector<int> cnt(26,0);
            string t = "";
            for(char c: strs[i])
            {
                ++cnt[c-'a'];
            }
            for(int d:cnt)
            {
                t += to_string(d)+"/";
            }
            mv[t].push_back(strs[i]);
        }
        for(auto a:mv)
        {
            res.push_back(a.second);
        }
        return res;
    }
};

347. Top K Frequent Elements 前k個(gè)高頻元素

給一個(gè)整數(shù)數(shù)組，讓我們統(tǒng)計(jì)元素出現(xiàn)次數(shù)，并按出現(xiàn)次數(shù)從高到低排序，讓我們返回前k個(gè)頻次最高的元素。例如：
Given [1,1,1,2,2,3] and k = 2, return [1,2].

使用到的數(shù)據(jù)結(jié)構(gòu)：unordered_map priority_queue vector

class Solution {
public:
   vector<int> topKFrequent(vector<int>& nums, int k) {
       unordered_map<int, int> um;
       priority_queue<pair<int, int>> p;
       vector<int> res;
       for (auto a : nums) 
           ++um[a];
       for (auto it : um) 
           p.push({it.second, it.first});
       for (int i = 0; i < k; ++i) 
       {
           res.push_back(p.top().second); 
           p.pop();
       }
       return res;
   }
};`

怎樣應(yīng)對(duì)IT面試與筆試-（一）
怎樣應(yīng)對(duì)IT面試與筆試-（二）
怎樣應(yīng)對(duì)IT面試與筆試-（三）
怎樣應(yīng)對(duì)IT面試與筆試-（四）
怎樣應(yīng)對(duì)IT面試與筆試-（五）
怎樣應(yīng)對(duì)IT面試與筆試-（五-1）
怎樣應(yīng)對(duì)IT面試與筆試-（六）
怎樣應(yīng)對(duì)IT面試與筆試-（七）
怎樣應(yīng)對(duì)IT面試與筆試-（八）
怎樣應(yīng)對(duì)IT面試與筆試-（九）
怎樣應(yīng)對(duì)IT面試與筆試-（十）
怎樣應(yīng)對(duì)IT面試與筆試-（十一）
怎樣應(yīng)對(duì)IT面試與筆試-（十二）
怎樣應(yīng)對(duì)IT面試與筆試-（十三）
怎樣應(yīng)對(duì)IT面試與筆試-（十四）
怎樣應(yīng)對(duì)IT面試與筆試-（十五）
怎樣應(yīng)對(duì)IT面試與筆試-（十六）