leetcode解题思路分析（十）64-70题

心已赠人 2023-07-03 04:45 5阅读 0赞

1.  最小路径和  
    给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。  
    说明：每次只能向下或者向右移动一步。

**本题和上面两题属于衔接性的题目，稍作修改即可**

class Solution { 
    public:
        int minPathSum(vector<vector<int>>& grid) { 
            int x, y;
            int m = grid.size();
            int n = grid[0].size();
            int dp[m][n] = { 0};
    
            for (x = m - 1; x >= 0; x--)
            { 
                for (y = n - 1; y >= 0; y--)
                { 
                    if (x == m - 1 && y == n - 1)
                        dp[x][y] = grid[x][y];
                    else if (x == m - 1 && n - y >= 2)
                        dp[x][y] = dp[x][y + 1] + grid[x][y];
                    else if (y == n - 1 && m - x >= 2)
                        dp[x][y] = dp[x + 1][y] + grid[x][y];
                    else if (n - y >= 2 && m - x >= 2)
                        dp[x][y] = min(dp[x + 1][y], dp[x][y + 1]) + grid[x][y];         
                }
            }
            return dp[0][0];       
        }
    };

1.  有效数字  
    验证给定的字符串是否可以解释为十进制数字。

**本题较为无聊，只要画出状态机然后轮询检测每一位即可**

class Solution { 
    public:
        bool isNumber(string &s) { 
            // regex r("\\s*[+-]?(\\d+\\.?\\d*|\\.\\d+)(e[+-]?\\d+)?\\s*$");
            int i=s.find_first_not_of(' ');
            int d1=0, dot=0, d2=0, e=0, d3=0;
            if(s[i]=='+' || s[i]=='-') ++i;
            for(; i<s.length() && isdigit(s[i]); d1=++i);
            if(i<s.length() && s[i]=='.') dot=++i;
            for(; i<s.length() && isdigit(s[i]); d2=++i);
            if(dot && !d1 && !d2) return false;
            if(i<s.length() && (d1||d2) && s[i]=='e') e=++i;
            if(i<s.length() && e && (s[i]=='+'|s[i]=='-')) ++i;
            for(; i<s.length() && isdigit(s[i]); d3=++i);
            if(e && (!(d1||d2) || !d3)) return false;
            for(; i<s.length() && s[i]==' '; ++i);
            return i==s.length();
        }
    };

1.  加一  
    给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

**本题主要是判断第一位是否越位，其他没啥好说的**

class Solution { 
    public:
        vector<int> plusOne(vector<int>& digits) { 
            int size = digits.size();
            if (digits[size - 1] < 9)
            { 
                digits[size - 1]++;
                return digits;
            }
            else
            { 
                while (digits[size - 1] == 9)
                { 
                    digits[size - 1] = 0;
                    size--;
                    if (size <= 0)
                    { 
                        digits.insert(digits.begin(), 1);
                        return digits;
                    }
                }
                digits[size - 1] += 1;
                return digits;
            }
        }
    };

1.  二进制求和  
    给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。

**对长度不一样的以0补齐后进行计算较为方便，然后注意首位是否需要进位即可**

class Solution { 
    public:
        string addBinary(string a, string b) { 
            int al = a.size();
            int bl = b.size();
            while(al < bl) //让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引
            { 
                a = '0' + a;
                ++ al;
            }
            while(al > bl)
            { 
                b = '0' + b;
                ++ bl;
            }
            for(int j = a.size() - 1; j > 0; -- j) //从后到前遍历所有的位数，同位相加
            { 
                a[j] = a[j] - '0' + b[j];
                if(a[j] >=  '2') //若大于等于字符‘2’，需要进一
                { 
                    a[j] = (a[j] - '0') % 2 + '0';
                    a[j-1] = a[j-1] + 1;
                }
            }
            a[0] = a[0] - '0' + b[0]; //将ab的第0位相加
            if(a[0] >= '2') //若大于等于2，需要进一
            { 
                a[0] = (a[0] - '0') % 2 + '0';
                a = '1' + a;
            }
            return a;
        }
    };

1.  文本左右对齐  
    给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。文本的最后一行应为左对齐，且单词之间不插入额外的空格。

**挨个判断即可**

class Solution { 
    public:
    	vector<string> fullJustify(vector<string>& words, int maxWidth) { 
    		vector<string> res;
    		int n = words.size();
    		for (int i = 0; i < n;)
    		{ 
    			int len = 0, num = -1;//len是单词的总长度，num是空格的最少个数，也就是单词个数-1
    			while (len + num <= maxWidth && i < n)
    			{ 
    				len += words[i].length();
    				++num;
    				++i;
    			}
    			if (len + num > maxWidth)
    			{ 
    				--i;;
    				--num;
    				len -= words[i].length();
    			}
    			if (i != n)
    			{ 
    				i -= num + 1;
    				int blank = maxWidth - len;
    				if (num > 0)
    				{ 
    					vector<int> blanks = vector<int>(num, blank / num);
    					for (int j = 0; j < blank%num; ++j)
    					{ 
    						blanks[j] += 1;
    					}
    					string s;
    					int j;
    					int m = blanks.size();
    					for (j = 0; j < m; ++j)
    					{ 
    						s.append(words[i + j]);
    						s.append(blanks[j], ' ');
    					}
    					for (; j < num + 1; ++j)
    					{ 
    						s.append(words[i + j]);
    					}
    					res.push_back(s);
    				}
    				else
    				{ 
    					string s = words[i];
    					s.append(blank, ' ');
    					res.push_back(s);
    				}
    			}
    			else
    			{ 
    				i -= num + 1;
    				string s;
    				for (int j = 0; j < num; ++j)
    				{ 
    					s.append(words[i + j]);
    					s.append(" ");
    				}
    				s.append(words[i + num]);
    				s.append(maxWidth - len - num, ' ');
    				res.push_back(s);
    			}
    			i += num + 1;
    		}
    		return res;
    	}
    };

1.  x的平方根

**本题解法可以采用二分法，也可以用牛顿迭代法**

class Solution { 
    public:
        int mySqrt(int x) { 
            //注：在中间过程计算平方的时候可能出现溢出，所以用long long。
            long long i=0;
            long long j=x/2+1;//对于一个非负数n，它的平方根不会大于（n/2+1）
            while(i<=j)
            { 
                long long mid=(i+j)/2;
                long long res=mid*mid;
                if(res==x) return mid;
                else if(res<x) i=mid+1;
                else j=mid-1;
            }
            return j;
        }
    };

class Solution { 
    public:
        int mySqrt(int x) { 
            if (x == 0) return 0;
            double last=0;
            double res=1;
            while(res!=last)
            { 
                last=res;
                res=(res+x/res)/2;
            }
            return int(res);
        }
    };

1.  爬楼梯  
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。  
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**典型的动态规划问题：从最后开始算知道dp\[n - 1\]的值，之后dp\[i\] = dp\[i + 1\] + dp\[i + 2\]即可**

class Solution { 
    public:
        int climbStairs(int n) { 
            int dp[n] = { 0};
            
            if (n == 1) return 1;
            dp[n - 1] = 1;
            dp[n - 2] = 2;
            for (int i = n - 3; i >= 0; i--)
            { 
                dp[i] = dp[i + 1] + dp[i + 2];
            }
            return dp[0];
        }
    };