240.搜索二维矩阵II
/*编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例: 现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/ class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.size()){ int len1 = matrix[0].size()-1; int p = 0; while(len1>=0&&p<matrix.size()){ if(target == matrix[p][len1]) return true; else if(target > matrix[p][len1]) {p++;continue;} else {len1--;continue;} } return false; } return false; } };
剑指offer11.旋转数组的最小数字
/*把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。 示例 1： 输入：[3,4,5,1,2] 输出：1 示例 2： 输入：[2,2,2,0,1] 输出：0 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/ class Solution { public: int minArray(vector<int>& numbers) { int end = numbers.size()-1; int start = 0; int mid; while(start<end){ mid = (start+end)>>1; if(numbers[end] < numbers[mid]) start = mid+1; else if(numbers[end] == numbers[mid]) end--; else end = mid; } return numbers[start]; } };33.旋转数组的查找（要考虑重复元素的存在）
55.跳跃游戏
/*给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/jump-game 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/ class Solution { public: bool canJump(vector<int>& nums) { // int count = 0; // for(int i = 0;i<nums.size();++i){ // if(nums[i] == 0) count++; // } // if(!count) return true; // if(nums.size()<2) return true; int max_dis = nums[0]; for(int i = 1;i<nums.size();++i){ if(i<=max_dis) max_dis = max(max_dis,i+nums[i]); else break; } return max_dis>=nums.size()-1; } };237.删除链表中的节点
/*请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。 现有一个链表 -- head = [4,5,1,9]，它可以表示为: 示例 1: 输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2: 输入: head = [4,5,1,9], node = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void deleteNode(ListNode* node) { node->val = node->next->val; node->next = node->next->next; } };653.两数之和，输入BST
/*给定一个二叉搜索树和个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。 案例 1: 输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 输出: True 案例 2: 输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 输出: False 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool findTarget(TreeNode* root, int k) { vector<int> path; inorder(root,path); for(int i = 0;i<path.size();++i){ int need = k-path[i]; for(int j = i+1;j<path.size()&&path[j]<=need;++j){ if(need == path[j]) return true; } } return false; } void inorder(TreeNode* root,vector<int>& path){ if(root){ inorder(root->left,path); path.push_back(root->val); inorder(root->right,path); } } };
