- 限制：
1 <= n < 2^31< code><!--=-->
数字范围较大，暴力会超时
class Solution {
public int countDigitOne(int n) {
int sum = 0;
int cur = n%10, digit = 1, high = n/10 , low = 0;
while(cur != 0 || high != 0){
if(cur==0) sum += high*digit;
else if(cur == 1) sum+= high*digit + low + 1;
else sum+= high*digit + digit;
low = cur*digit + low;
cur = high %10;
high = high /10;
digit *=10;
}
return sum;
}
}
本题的思路很精巧，可以试着思考行李箱上的密码锁，确定每个数位为1的情况有多少种。
当前位为0，意味着假如说 2301，则只有0010-2219的数字是符合条件的，这里面有229+1个情况。
当前位为1，假如说 2314，则只有0010-2314是符合条件的，234+1个情况。
当前位大于1，假如说2334，则有0010-2319是符合条件的，239+1个情况。
这里的思想并不麻烦，但是要注意每个数位的处理过程，很可能少减一次1，结果就截然不同了。
class Solution {
public int findNthDigit(int n) {
int digit = 1;
long start = 1;
long count = 9;
while (n > count) { // 1.
n -= count;
digit += 1;
start *= 10;
count = digit * start * 9;
}
long num = start + (n - 1) / digit; // 2.
return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
}
}
2，3步中的-1需要仔细理解。
class Solution {
public String minNumber(int[] nums) {
String[] res1 = new String[nums.length];
for(int i = 0 ; i(x+y).compareTo(y+x));
StringBuilder res = new StringBuilder();
for(String s : res1)
res.append(s);
return res.toString();
}
}
该题其实就是一个快速排序，只是需要将判断条件由(x,y)->(x-y)升序 改为 (x,y)-> (x+y).compareTo(y+x) （该内容为字符串比较）。该方式为lamda表达式。
class Solution {
public String minNumber(int[] nums) {
String[] res1 = new String[nums.length];
for(int i = 0 ; i=r) return ;
int i = l , j = r;
String tmp = str[l];
while(i=0 && i
快排完整版
class Solution {
int count = 0;
public int translateNum(int num) {
dfs(String.valueOf(num));
return count;
}
public void dfs(String s) {
if(s.length()
这题的思路也是比较简单，DFS即可。树形递归的时间复杂度在O(2^N)
动态规划解法：
public int translateNum(int num) {
String s = String.valueOf(num);
int a = 1, b = 1;
for(int i = 2; i = 0 && tmp.compareTo("25")
a为dp0，b为dp1。
典型的动态规划
每次状态为向上一步的最优值或者向左一步最优值的最大者。
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < n ; j++) {
if(i==0 && j==0) continue;
else if(i==0) grid[i][j]+=grid[i][j-1];
else if(j==0) grid[i][j]+=grid[i-1][j];
else{
grid[i][j] = Math.max(grid[i][j]+grid[i][j-1], grid[i][j]+grid[i-1][j]);
}
}
return grid[m-1][n-1];
}
}
动态规划，其中利用了hash表标记元素位置
class Solution {
public int lengthOfLongestSubstring(String s) {
Map map = new HashMap<>();
int tmp = 0, res = 0;
for(int i = 0 ; i < s.length() ; i++) {
int j = map.getOrDefault(s.charAt(i),-1);
map.put(s.charAt(i),i);
tmp = tmp < i-j ? tmp+1 : i-j;
res = res > tmp ? res : tmp;
}
return res;
}
}
假设字符串abcab，则循环到a时，检测到0位置上为重复元素，判断tmp为3，i-j即当前元素距重复元素距离3，则说明子串中含有a，更新为i-j。
class Solution {
public int nthUglyNumber(int n) {
int[] factor = {2,3,5};
int ans=0;
Set set = new HashSet<>() {{add(1L);}};
PriorityQueue res = new PriorityQueue<>() {{offer(1L);}};
for(int i = 1 ; i
注意，题目只要求包含质因子2，3，5，因此必须用每个丑数再乘2，3，5获取新的丑数，并判断不重复，PriorityQueue不会自动判别重复元素。
利用哈希表遍历
class Solution {
public char firstUniqChar(String s) {
char res =' ';
if(s.length()==0)
return ' ';
Map map = new HashMap<>();
for(int i = 0 ; i < s.length() ; i++) {
if(map.getOrDefault(s.charAt(i),-1)==-1)
map.put(s.charAt(i),0);
else map.put(s.charAt(i),1);
}
for(int i = 0 ; i < s.length() ; i++) {
if(map.get(s.charAt(i))==0) {
res = s.charAt(i);
break;
}
}
return res;
}
}
class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int len = nums.length;
tmp = new int[len];
return mergeSort(nums,0,len-1);
}
public int mergeSort(int[] nums, int l, int r) {
if(l>=r)
return 0;
int m = (l+r)/2, i = l, j = m+1;
int res = mergeSort(nums,l,m) + mergeSort(nums,m+1,r);
for(int k = l ; k
在归并的每一步合并中，进行逆序对计数。注意各个临界点的判断。
利用哈希表遍历，要善于利用hashset和map，但是要注意.equal的实现机制。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set set = new HashSet<>();
while(headA!=null){
set.add(headA);
headA = headA.next;
}
while(headB!=null){
if(!set.add(headB))
break;
headB = headB.next;
}
return headB;
}
}
Original: https://www.cnblogs.com/gaoyuan206/p/15411637.html
Author: GaoYuan206
Title: LeetCode剑指Offer刷题总结（五）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/578960/
转载文章受原作者版权保护。转载请注明原作者出处！