数据结构算法相关题(LeetCode相关问题)

1. 斐波那契数列求和

斐波那契数列（0，1，1，2，3，5 . . .）求和

- (NSInteger )fb:(NSInteger)n{
    if (n <= 1) {
        return n;
    }
    NSInteger first = 0;
    NSInteger second = 1;
    NSInteger sum = 0;
    for (NSInteger i = 0; i < n-1; i++) {
        sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}

2. 反转链表(反转链表)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
  public ListNode reverseList(ListNode head) {
        
        ListNode preNode = null;
        ListNode curNode = head;
        
        while ( curNode != null ){
            
            ListNode nextNode = curNode.next;
            
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        
        return preNode;
    }

3. 合并链表( 合并两个有序链表)

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

public:
   ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        if (l1 == NULL){
            
            return l2;
            
        }else if(l2 == NULL){
            
            return l1;
            
        }
        
        ListNode *mergedNode = NULL;
        
        if(l1->val < l2->val){
            
            mergedNode = l1;
            mergedNode->next = mergeTwoLists(mergedNode->next,l2);
            
        }else{
            
            mergedNode = l2;
            mergedNode->next = mergeTwoLists(l1, mergedNode->next);
        }
        
        return mergedNode;
    }

4.查找链表倒数第k个元素( 面试题 02.02. 返回倒数第 k 个节点)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
    if(head == NULL )
        return -1;
    
    ListNode *pAhead = head;
    ListNode *pBehind = head;
    for(int i = 0;i < k - 1;i++)
    {
        if(pAhead->next != NULL)
            pAhead = pAhead->next;
        else
        {
            return -1;
        }
    }

    while(pAhead->next != NULL)
    {
        pAhead = pAhead->next;
        pBehind = pBehind->next;
    }

    return pBehind->val;
    }
};

5.倒序打印链表的值

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


void PrintListReversingly(ListNode* pHead)
{
    if(pHead != NULL)
    {
        if (pHead->next != NULL)
        {
            PrintListReversingly(pHead->next);
        }
        
        printf("%d\t", pHead->val);
    }
}

6.删除某个节点( 删除链表中的节点)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    if(node == NULL || node->next == NULL){
        return;
    }
    node->val = node->next->val;
    node->next = node->next->next;
}

7. 删除值为val的节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode *head, int val){

        ListNode *dummyHead = new ListNode(-1);
        dummyHead->next = head;

        ListNode *cur = dummyHead;
        
        while (cur->next != NULL){
            
            if (cur->next->val == val){
                
                ListNode *delNode = cur->next;
                cur->next = delNode->next;
                delete delNode;
                
            } else{
                
                cur = cur->next;
                
            }
        }

        ListNode *returnNode = dummyHead->next;
        delete dummyHead;

        return returnNode;
    }
};

8. 二叉树转链表( 114. 二叉树展开为链表)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    TreeNode prev ;
    public void flatten(TreeNode root) {
        if (root == null)
        return;
       
        flatten(root.right);
        flatten(root.left);
        if (prev != null){
            root.right = prev;
            root.left = null;
        }
        prev = root;
    }
}

64. 最小路径和

 int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        assert(n > 0);
        int m = grid[0].size();
        assert(m > 0);
        vector<vector<int>> res = grid;
        for (int i = 1;i < n;i++){          
            res[i][0] = grid[i][0] + res[i-1][0];
        }
        for (int i = 1;i < m;i++){
            res[0][i] = grid[0][i] + res[0][i-1];
        }
        for (int i = 1;i<n;i++){
            for (int j = 1;j<m;j++){
                res[i][j] = min(res[i-1][j],res[i][j-1])+grid[i][j];
            }
        }
        return res[n-1][m-1];
    }

5. 最长回文子串

   string longestPalindrome(string s) {
        if(s.size() <= 1) return s;
        int maxLen = 1;
        int begin = 0;
        int i = 0;
        while(i<s.size()){
            int l = i-1;
            int r = i;
            while(++r < s.size() && s[r] == s[i]){
                
            }
            i = r;
            while(l>=0 && r<s.size() && s[l]== s[r]){
                l--;
                r++;
            }
            int len = r-l-1;
            if(maxLen < len){
                maxLen = len;
                begin = l+1;
            }
        }
        return s.substr(begin,maxLen);
    }

236. 二叉树的最近公共祖先

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q){
            return root;
        }
        TreeNode *left = lowestCommonAncestor(root->left,p,q);
        TreeNode *right = lowestCommonAncestor(root->right,p,q);
        if(left != NULL && right != NULL){
            return root;
        }
        return (left != NULL)?left:right;
    }