leetcode解题思路分析（十二）78-84题

短命女 2023-07-06 04:49 10阅读 0赞

1.  子集  
    给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

**本题可以照例采用回溯法：func(chose i ); func (not chose i); 也可以采用位运算的方式进行：二进制位数的自增对应选择或者不选该位数组的数字000 001 010 100 101 110 111**

class Solution { 
    public:
        vector<vector<int>> ans;
        vector<int> tmp;
        void find(int dep, vector<int>& nums)
        { 
            // 已经处理完最后一位，将目前存储的集合存入 ans ，并回溯
            if(dep <= 0)
            { 
                ans.push_back(tmp);
                return;
            }
            // 情况一：集合中有该元素
            tmp.push_back(nums[dep - 1]);
            find(dep - 1, nums);
            tmp.pop_back();
            // 情况二：集合中无该元素
            find(dep - 1, nums);
        }
    
        vector<vector<int>> subsets(vector<int>& nums) { 
            find(nums.size(), nums);
            return ans;
        }
    };

class Solution { 
    public:
        vector<vector<int>> subsets(vector<int>& nums) { 
            int size=nums.size();   //数组大小
            vector<vector<int>> res;
            
            unsigned int map=0;
            vector<int> tmp;
            int end=1<<size;    //停止边界
    
            while(map<end)
            { 
                for(int i=0;i<size;i++)
                    if((1<<i)&map) tmp.push_back(nums[i]);  //寻找要加入的下标
                res.push_back(tmp);
                tmp.clear();
                map++;
            }
        return res;
        }
    };

1.  单词搜索  
    给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

**采用回溯法求解**

class Solution { 
    public:
        bool exist(vector<vector<char>>& board, string word) { 
            if(board.size() == 0) return false;
            for (int i=0;i<board.size();i++){ 
                for(int j=0;j<board[0].size();j++){ 
                    if (dfs(board,word,i,j,0)){ 
                        return true;
                    }
                }
            }
            return false;
        }
    
        bool dfs(vector<vector<char>>& board, string& word, int i,int j,int length){ 
            if(i>=board.size()||j>=board[0].size()||i<0||j<0||length>=word.size()||word[length]!=board[i][j]){ 
                return false;
            }
            if(length==word.size()-1&&word[length]==board[i][j]){ 
                return true;
            }
            char temp=board[i][j];
            board[i][j]='0';
            bool flag=dfs(board,word,i,j+1,length+1)||dfs(board,word,i,j-1,length+1)||dfs(board,word,i+1,j,length+1)||dfs(board,word,i-1,j,length+1);
            board[i][j]=temp;
            return flag;
        }
    };

class Solution { 
    public:
        bool exist(vector<vector<char>>& board, string word) { 
            for (int i = 0; i < board[0].size(); i++)
            { 
                for (int j = 0; j < board.size(); j++)
                { 
                    if (board[i][j] == word[0])
                    { 
                        if (find(board, word, i, j, 0))
                            return true;
                    }
                }
            }
            return false;
        }
        bool find(vector<vector<char>>& board, string &word, int posx, int posy, int ptr)
        { 
            if (posx >= board[0].size() || posy >= board.size()
            || posx < 0 || posy < 0)
                return false;
    
            if (board[posx][posy] == word[ptr])
            { 
                if (ptr == word.size() - 1)
                    return true;
                else        
                { 
                    ptr++;
                    char temp=board[posx][posy];
                    board[posx][posy]='0';
                    bool flag = (find(board, word, posx, posy + 1, ptr)
                        || find(board, word, posx + 1, posy, ptr)
                        || find(board, word, posx - 1, posy, ptr)
                        || find(board, word, posx, posy - 1, ptr)); 
                    board[posx][posy] = temp;
                    return flag;
                }
         
            }
            else
                return false;
        }
    
    };

1.  删除排序数组中的重复项  
    给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

**本题和26题类似，但是因为最多两个重复元素，因此需要加上一个判断**

class Solution { 
    public:
        int removeDuplicates(vector<int>& nums) { 
            int n = nums.size();
            if(n <= 2)
            { 
                return n;
            }
            int sp = 1;
            for(int fp = 2; fp < n; fp++)
            { 
                if(nums[fp] != nums[sp - 1])
                { 
                    nums[++sp] = nums[fp];
                }
            }
            return sp + 1;
        }
    };

1.  搜索旋转排序数组2  
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 \[0,0,1,2,2,5,6\] 可能变为 \[2,5,6,0,0,1,2\] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

**相比于33题，只需要增加一个排除重复数字即可**

class Solution { 
    public:
        bool search(vector<int>& nums, int target) { 
            int left=0,right=nums.size()-1;
            int mid;
            while(left<=right){ 
                mid=left+(right-left)/2;
                if(nums[mid]==target) return true;
                if(nums[left]==nums[mid]){ 
                    left++;
                    continue;
                }
                if(nums[left]<=nums[mid]){   //左边有序
                    if(nums[left]<=target&&target<=nums[mid]) right=mid-1; //在左边
                    else left=mid+1;
                }else{   //右边有序
                    if(nums[mid]<=target&&target<=nums[right]) left=mid+1; //在右边
                    else right=mid-1;
                }
            }
            return false;
        }
    };

1.  删除链表重复元素

**简单的链表操作**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* deleteDuplicates(ListNode* head) { 
            if (head == NULL)
                return head;
            ListNode *ptr = head, *last;
            ListNode *ahead = new ListNode(-1);
            ahead->next = head;
            last = ahead;
            
            while (ptr->next != NULL)
            { 
                if (ptr->val == ptr->next->val)
                { 
                    while (ptr->next != NULL && ptr->val == ptr->next->val)
                    { 
                        ptr = ptr->next;
                    }
                    last->next = ptr->next;
                    ptr = ptr->next;
                    if (ptr == NULL)
                        return ahead->next;
                }
                else
                { 
                    last = ptr;
                    ptr = ptr->next;
                }
            }
            return ahead->next;
        }
    };

1.  删除排序链表中的重复元素  
    给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

**和上一题的区别在于，本题只删除重复元素，而上题是有重复的话，该元素彻底删除，其实解法都一样**

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* deleteDuplicates(ListNode* head) 
        { 
        if(head == NULL)  //如果所给链表为空直接返回，否则在执行ptr->next这部操作时会因为ptr为NULL而造成执行时错误
            return head;
    	ListNode* ptr{  head };  //遍历的指针
    	while (ptr->next != NULL)  //遍历首个元素到第倒数第二个元素，因为是逐个向后比较，最后一个元素会被比较到，这样是正确的
    	{ 
    		if (ptr->val == ptr->next->val)  //和后一个元素比较
    		{ 
    			ListNode* p = ptr->next;  
    			ptr->next = p->next;  //删除操作
    			delete p;  //释放空间
    		}
    		else
    		{ 
    			ptr = ptr->next;  //移动到后一个元素
    		}
    	}
    	return head;  //返回首个节点
        }
    };

1.  柱状图中最大的矩形  
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

**本题和42题接雨水类似，均可以采用栈的方式去记录一个递增/递减序列从而顺序存储一个值，如果遇到不符合条件则出栈。也可以采用双指针滑动的方式求解。**

class Solution { 
    public:
        int largestRectangleArea(vector<int>& heights) { 
            stack<int> s;
            s.push(-1);
            int max_area = 0, height, width;
            for(int i = 0; i < heights.size(); ++i) { 
                while(s.top() != -1 && heights[i] <= heights[s.top()]) { 
                    height = heights[s.top()];
                    s.pop();
                    width = i-s.top()-1;
                    max_area = max(max_area, width*height);
                }
                s.push(i);
            }
            while(s.top() != -1) { 
                height = heights[s.top()];
                s.pop();
                width = heights.size() - s.top() - 1;
                max_area = max(max_area, width*height);
            }
            return max_area;
        }
    };