Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

leetcode > leetcode > Flashcards

leetcode Flashcards

1
Q
  1. Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
    Input: nums = [1,3,5,6], target = 5
    Output: 2
A 
int searchInsert(vector& nums, int target) {        
        int l = 0;
        int h = nums.size()-1;
    while (l<=h){
        int mid = l + (h-l)/2;
            if (target == nums[mid]){
                return mid;
            }
            else if (target < nums[mid]){
                h = mid-1;
            }
            else{
                l = mid+1;
            }
        }
    return l;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q 
278. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version.
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
A 
int firstBadVersion(int n) {
        int l= 1;
        int h = n;
        int result = n;
    while (l<=h){
        int mid = l+(h-l)/2;
            if (isBadVersion(mid)){
                result = mid;
                h = mid-1;
            }
            else{
                l = mid+1;
            }
        }
    return result;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q
  1. Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
    Input: nums = [-1,0,3,5,9,12], target = 9
    Output: 4
A 
int search(vector& nums, int target) {
        int l = 0;
        int r = nums.size()-1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if (nums[mid] == target){
                return mid;
            }
            else if (nums[mid] > target){
                r = mid-1;
            }
            else {
                l = mid+1;
            }
        }
    return -1;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q
  1. You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

numberOfBoxesi is the number of boxes of type i.
numberOfUnitsPerBoxi is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

A 
int maximumUnits(vector>& boxTypes, int truckSize) {
        priority_queue> pq;
    for(int i=0; i
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q
  1. Tic-tac-toe is played by two players A and B on a 3 x 3 grid. Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. return the winner of the game if it exists (A or B). In case the game ends in a draw return “Draw”. If there are still movements to play return “Pending”.
    Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
    Output: “A”
A 
string tictactoe(vector>& moves) {
        int n=3;
    if (moves.size() < 5){
        return "Pending";
    }
        vector x (n,0);
        vector y (n,0);
        vector diag (2,0);
    int player = 1;

    for(int i=0; i
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

937.You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

Letter-logs: All words (except the identifier) consist of lowercase English letters.
Digit-logs: All words (except the identifier) consist of digits.
Reorder these logs so that:

The letter-logs come before all digit-logs.
The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
The digit-logs maintain their relative ordering.
Return the final order of the logs.
Input: logs = [“dig1 8 1 5 1”,”let1 art can”,”dig2 3 6”,”let2 own kit dig”,”let3 art zero”]
Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]

A 
vector reorderLogFiles(vector& logs) {
        map>  sortedLetterLogs;
        vector digitLogs;
    vector r;

    for(auto val : logs){
        int index = val.find(' ');

        if(isdigit(val[index+1])){
            digitLogs.push_back(val);
        }
        else{
            sortedLetterLogs[val.substr(index+1,val.length()-1)].insert(val);
        }
    }
        for(auto m : sortedLetterLogs){
            for(auto l : m.second){
                r.push_back(l);
            }    
        }
    for (auto v : digitLogs){
        r.push_back(v);
    }

    return r;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
  1. Write a function that reverses a string in-place. The input string is given as an array of characters s.
    Input: s = [“h”,”e”,”l”,”l”,”o”]
    Output: [“o”,”l”,”l”,”e”,”h”]
A 
void reverseString(vector& s) {
        int l=0;
        int h=s.size()-1;
    while(l
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q
  1. Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
    Input: s = “Let’s take LeetCode contest”
    Output: “s’teL ekat edoCteeL tsetnoc”
A

string reverseWords(string s) {

    for(int i=0, j=0 ; i<=s.size(); i++){
        if(s[i]==' ' || i == s.size()){
            swap(s,j,i-1);
            j=i+1;
        }
    }

    return s;
}
    void swap(string& s, int l, int h){
        while(l
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
  1. Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

A 
vector twoSum(vector& numbers, int target) {
        int l=0;
        int h=numbers.size()-1;
        while(lval){
                l++;
            }
            else{
                h--;
            }
        }
    return vector{l+1,h+1};
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q
  1. Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
    Input: nums = [0,1,0,3,12]
    Output: [1,3,12,0,0]
A 
void moveZeroes(vector& nums) {
        int l = 0;
        for(int r=0; r& nums, int l, int r){
        int inter = nums[l];
        nums[l] = nums[r];
        nums[r] = inter;
    }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q
  1. Given an array, rotate the array to the right by k steps, where k is non-negative.
    Input: nums = [1,2,3,4,5,6,7], k = 3
    Output: [5,6,7,1,2,3,4]
A 
void rotate(vector& nums, int k) {
        if (k==0 || k%nums.size()==0) return;
        swap(nums, 0, nums.size()-1);
        k = k%nums.size();
        swap(nums, 0, k-1);
        swap(nums, k, nums.size()-1);
    }
    void swap(vector& nums, int l, int h){
        while(l
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q
  1. Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
    Input: nums = [-4,-1,0,3,10]
    Output: [0,1,9,16,100]
A 
vector sortedSquares(vector& nums) {
        vector res(nums.size(), 0);
        int l = 0;
        int h = nums.size()-1;
        int i = h;
        while(l<=h){
            res[i--] = abs(nums[l]) < abs(nums[h]) ? nums[h]*nums[h--] : nums[l]*nums[l++];
        }        
        return res;
    }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
  1. An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

A

vector> floodFill(vector>& image, int sr, int sc, int newColor) {
if (image[sr][sc] == newColor)
return image;

    dpsFill(image, sr, sc, image[sr][sc], newColor);

    return image;
}
    void dpsFill(vector>& image, int sr, int sc, int sColor, int newColor){
        if(sr<0 || sc<0 || sr>=image.size() || sc>=image[0].size() || image[sr][sc] != sColor)
            return;
    image[sr][sc] = newColor;
    dpsFill(image, sr-1, sc, sColor, newColor);
    dpsFill(image, sr+1, sc, sColor, newColor);
    dpsFill(image, sr, sc-1, sColor, newColor);
    dpsFill(image, sr, sc+1, sColor, newColor);
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q
  1. You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

A 
int maxAreaOfIsland(vector>& grid) {
        set> seen;
        int max_area = 0;
    for (int i=0; i>& grid, int r, int c, set>& seen){
    if (r < 0 || r>= grid.size() || c <0 || c>=grid[0].size() || seen.find({r,c}) != seen.end() || grid[r][c] == 0)
        return 0;

    seen.insert({r,c});

    return (1 + areaCal(grid, r-1, c, seen) + areaCal(grid, r+1, c, seen) + areaCal(grid, r, c-1, seen) + areaCal(grid, r, c+1, seen));
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Convert 1D to 2D array given m rows and ncols.
Input: [1,2,3,4], m=2, n=2
output: [[1,2], [3,4]]

A 
vector> multidimension (vector A, int m, int n){
         if (m*n != A.size())
               return null;
         vector> res(m, vector(n));
         for(int i=0; i
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

116.You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

A

Node* connect(Node* root) {
if (root == NULL)
return NULL;

    queue q;
    Node* cur = root;

    q.push(cur);
        while(q.size() >0){
            int size = q.size();
            for(int i=0; i< size; i++){
                Node* n = q.front();
                q.pop();
                if (inext = q.front();
                }
                if (n->left != NULL){
                    q.push(n->left);
                }
                if (n->right != NULL){
                    q.push(n->right);
                }
            }
        }
    return root;
}
17
Q

to keep right most 1- bit

to flip rightmost 1 bit

A

to keep: x & (-x)
for power of two : x & (-x) = x;

to flip: x & (x-1)
for power of two: x & (x-1) = 0

18
Q
  1. You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

A

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* l1 = list1;
ListNode* l2 = list2;

    ListNode dummy;
    ListNode* head = &dummy;
    ListNode* cur = head;
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
            cur->next = NULL;
        }
    if (l1 != NULL){
        cur->next = l1;
    }

    if (l2 != NULL){
        cur->next = l2;
    }

    return head->next;
}
18
Q
  1. You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

A

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* l1 = list1;
ListNode* l2 = list2;

    ListNode dummy;
    ListNode* head = &dummy;
    ListNode* cur = head;
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
            cur->next = NULL;
        }
    if (l1 != NULL){
        cur->next = l1;
    }

    if (l2 != NULL){
        cur->next = l2;
    }

    return head->next;
}
19
Q
  1. Given the head of a singly linked list, reverse the list, and return the reversed list.
    Input: head = [1,2,3,4,5]
    Output: [5,4,3,2,1]
A

ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;

        while(cur){
            ListNode* nextTemp = cur->next;
            cur->next = prev;
            prev=cur;
            cur = nextTemp;
        }
        return prev;
    }
ListNode* solution2(ListNode* head){
    if (head == nullptr || head->next == nullptr)
        return head;
        ListNode* p = solution2(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }

leetcode (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions