LeetCode Easy

9 flashcards · Computer Science · by Matthias Lang

1. Write a function that takes a string as input and returns the string reversed. Example: Given s = "hello", return "olleh".

   class Solution { public: string reverseString(string s) { int left = 0, right = s.size() - 1; while(left < right) { int t = s[left]; s[left++] = s[right]; s[right--] = t; } return s; } };

2. Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

   class Solution { public: int reverse(int x) { long answer = 0; while (x != 0) { answer = answer * 10 + x % 10; if (answer > INT_MAX || answer < INT_MIN) return 0; x /= 10; } return (int)answer; } };

3. Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. Examples: s = "leetcode" return 0. s = "loveleetcode", return 2. Note: You may assume the string contain only lowercase letters.

   class Solution { public: int firstUniqChar(string s) { vector<int> counts(26, 0); for (char c : s) counts[c - 'a']++;; for (int i = 0; i < s.size(); ++i) if (counts[s[i] - 'a'] == 1) return i; return -1; } };

4. Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false. Note: You may assume the string contains only lowercase alphabets. Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case?

   class Solution { public: bool isAnagram(string s, string t) { int arr[26] = {}; for (int i = 0; i < s.size(); i++) { arr[s[i] - 'a']++; } for (int i = 0; i < t.size(); i++) { arr[t[i] - 'a']--; } for (int i = 0; i < 26; i++) { if (arr[i] != 0) return false; } return true; } };

5. Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Examples: "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

   bool isPalindrome(string s) { for (int i = 0, j = s.size() - 1; i < j; i++, j--) { // Move 2 pointers from each end until they collide while (isalnum(s[i]) == false && i < j) i++; // Increment left pointer if not alphanumeric while (isalnum(s[j]) == false && i < j) j--; // Decrement right pointer if no alphanumeric if (toupper(s[i]) != toupper(s[j])) return false; // Exit and return error if not match } return true; }

6. Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases. Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting fr…

   class Solution { public: int myAtoi(string str) { long solution = 0; int i = 0; int sign = 1; while (str[i] == ' ') i++; if (str[i] == 43 || str[i] == 45) { sign = (str[i++] == '-')? -1 : 1; } while (str[i] >= '0' && str[i] <= '9') { solution = solution*10 + str[i++] - '0'; if (solution*sign >= INT_MAX) return INT_MAX; if (solution*sign <= INT_MIN) return INT_MIN; } return sign*solution; } };

7. Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 Example 2: Input: haystack = "aaaaa", needle = "bba" Output: -1

   class Solution { public: int strStr(string haystack, string needle) { int m = haystack.length(), n = needle.length(); if (needle.size() == 0) return 0; for (int i = 0; i < m-n+1; i++) { if (haystack[i] == needle[0]) { for (int j = 0; j < n; j++) { if (haystack[i+j] != needle[j]) { break; } if (j == n-1) return i; } } } return -1; } };

8. The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth term of the count-and-say sequence. Note: Each term of the sequence of integers will be represented as a string. Example 1: Input: 1 Output: "1" Example 2: Input: 4 Output: "1211"

   #include <stdlib.h> class Solution { public: string countAndSay(int n) { string begin ="1"; int count; while (--n){ string tmp = ""; for (int i = 0; i < begin.size(); i++) { count = 0; count++; while (begin[i] == begin[i+1] && i< begin.size()-1){ count++; i++; } tmp = tmp + to_string(count) + begin [i]; } begin = tmp; } return begin; } };

9. Write a function to find the longest common prefix string amongst an array of strings.

   class Solution { public: string longestCommonPrefix(vector<string>& strs) { string prefix = ""; for(int idx=0; strs.size()>0; prefix+=strs[0][idx], idx++) for(int i=0; i<strs.size(); i++) if(idx >= strs[i].size() ||(i > 0 && strs[i][idx] != strs[i-1][idx])) return prefix; return prefix; } };