算法入门

leetcode题目

167.两数之和

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> v;
        for (int i = 0; i < numbers.size(); i++){
            int t = target - numbers[i], l = i + 1, r = numbers.size() - 1;
            while (l <= r){
                int mid = (l + r) / 2;
                if (numbers[mid] == t){
                    v.push_back(i + 1);
                    v.push_back(mid + 1);
                    return v;
                }
                if (numbers[mid] < t){
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return v;
    }
};

7、整数反转

给出一个32位的整数，需要将这个整数中每位上的数字进行反转。

class Solution {
public:
    int reverse(int x) {
        long long ans = 0;
        while (x) {
            ans = ans * 10 + x % 10;
            x /= 10;
        }
        if (ans < INT_MIN || ans > INT_MAX){
            return 0;
        }
        return (int)ans;
    }
};
//小的类型会越界，则添加一个大的类型将其存储，并在后面添加判断语句。

9、判断回文数

判断一个整数是否是回文数；即从右往左和从左往右一样；其实就是将该数反转调过来。

class Solution {
public:
    bool isPalindrome(int x) {
        long long y = 0, z = x;
        if (z < 0){
            return false;
        }
        while (z){
            y = y * 10 + z % 10;
            z /= 10;
        }
        return y == x;
    }
};

13、罗马数字转整数

14、最长公共前缀

编写一个函数来查找字符串数组中最长公共前缀，不存在则返回空字符串。关键在于用两个for循环，一个用于遍历字符串数组，另一个用于遍历每个字符串中字符。

相当于就是两个for循环来分别遍历字符串和字符串内字符，然后break用于提前退出来节省时间。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0){
            return "";
        }
        string ans = strs[0];
        for (int i = 1; i < strs.size(); i++){
            string t = ans;
            ans = "";
            for (int j = 0; j < t.size() && j < strs[i].size(); j++){
                if (t[j] == strs[i][j]){
                    ans += t[j];
                }else{
                    break;
                }
            }
            if (ans == ""){
                break;
            }
        }
        return ans;
    }
};

20、有效的括号

完全包含问题则适用于栈来进行处理

class Solution {
public:
    bool isValid(string s) {
        stack <char> sta;
        for (int i = 0; i < s.size(); i++){
            if (s[i] == '(' || s[i] == '[' || s[i] == '{'){
                sta.push(s[i]);
            }
            else{
                if (sta.empty() ||  (s[i] == ')' && sta.top() != '(') ||
                                    (s[i] == ']' && sta.top() != '[') ||
                                    (s[i] == '}' && sta.top() != '{')  ){
                    return false;
                }
                sta.pop();
            }
        }
        return sta.empty();  
    }
};

21、合并两个有序链表

将两个升序链表合并成一个新的升序链表并返回，新链表由拼接给定的两个链表的所有节点组成；关键在于链表的操作以及判断边界条件。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    var ans = new ListNode();
    var root = ans;
    while (l1 != null || l2 != null){
        if (l1=== null){
            root.next = l2;
            break;
        }
        if (l2 === null){
            root.next = l1;
            break
        }
        if (l1.val < l2.val){
            root.next = l1;
            l1 = l1.next;
        }
        else{
            root.next = l2;
            l2 = l2.next;
        }
        root = root.next;
    }
    return ans.next;
};

26、删除排序数组重复项

双指针法

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let left = 0, right = 1;
    while(right < nums.length){
        if(nums[left] !== nums[right]){
            nums[++left] = nums[right];
        }
        right++;
    }
    return left + 1;
};

27、移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素

var removeElement = function(nums, val) {
    let ind = 0;
    for (let i = 0; i < nums.length; i++){
        if (nums[i] != val){
            nums[ind++] = nums[i];
        }
    }
    return ind;
};