73. 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶：
一个直观的解决方案是使用 O(m*n) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
题目分析:
水题
AC代码
#include<bits/stdc++.h> using namespace std; void setZeroes(vector<vector<int>>& matrix) { //memset(col,0,sizeof(col)); int m = matrix.size(); int n = matrix[0].size(); int col[m] = {0},row[n] = {0}; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(!matrix[i][j]) { col[i] = 1; row[j] = 1; } } } //遍历所有元素,该元素所在行/列有一个为0,则该元素也就为0 for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(col[i] || row[j]){ matrix[i][j] = 0; } } } } int main() { vector<vector<int>> matrix = {{0,1,2,0},{3,4,5,2},{1,3,1,5}}; setZeroes( matrix); int m = matrix.size(); int n = matrix[0].size(); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { cout<<matrix[i][j]<<" "; } cout<<endl; } return 0; }
387. 字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例：
s = "leetcode" 返回 0
s = "loveleetcode" 返回 2
思路分析:
水题
AC代码:
#include<bits/stdc++.h> using namespace std; int firstUniqChar(string s) { int arr[30] = {0}; for(int i = 0; i < s.size();i++){ int temp = s[i]-'a'; arr[temp]++; } for(int i = 0; i < s.size();i++){ int temp = s[i]-'a'; if(arr[temp]==1){ return i; } } return -1; } int main() { string s = "loveleetcode"; cout<<firstUniqChar(s)<<endl; return 0; }
383. 赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true
参考代码
#include<bits/stdc++.h> using namespace std; bool canConstruct(string ransomNote, string magazine) { if(ransomNote.size()>magazine.size()){ return false; } sort(ransomNote.begin(),ransomNote.end()); sort(magazine.begin(),magazine.end()); //cout<<ransomNote<<"--"<<magazine<<endl; int i,j; for(i = 0,j = 0;i < ransomNote.size();i++,j++){ if(j>=magazine.size()){//j不能越界. return false; } if(ransomNote[i]==magazine[j]){ continue; }else if(ransomNote[i]>magazine[j]){// 后者更小,则前者不变,继续遍历后者. i--; }else{//magazine中有ransomNote没有的字符. return false; } } return true; } int main() { string ransomNote = "fihjjjjei", magazine = "hjibagacbhadfaefdjaeaebgi"; cout<<canConstruct(ransomNote,magazine)<<endl; return 0; }
