leecode题目记录

1 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

java 遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {};
    }
}

go 遍历

1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i++ {
      k := target - nums[i]
      if v, ok := m[k]; ok {
        return []int{v, i}
      }
      m[nums[i]] = i
    }
    return nil
}

2 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

java 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      if (l1 == null && l2 == null) {
        return null;
      }
      if (l1 == null) {
        return l2;
      }
      if (l2 == null) {
        return l1;
      }
      int sum = l1.val + l2.val;
      ListNode nextNode = addTwoNumbers(l1.next, l2.next);
      if (sum < 10) {
        ListNode result = new ListNode(sum);
        result.next = nextNode;
        return result;
      } else {
        ListNode temp = new ListNode(1);
        ListNode result = new ListNode(sum - 10);
        result.next = addTwoNumbers(nextNode, temp);
        return result;
      }
    }
}

go 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  if (l1 == nil && l2 == nil) {
    return nil
  }
  if (l1 == nil) {
    return l2
  }
  if (l2 == nil) {
    return l1
  }
  sum := l1.Val + l2.Val
  nextNode := addTwoNumbers(l1.Next, l2.Next)
  if sum < 10 {
    return &ListNode{Val:sum, Next:nextNode}
  } else {
    tempNode := &ListNode{Val:1, Next:nil}
    return &ListNode{Val:sum - 10, Next:addTwoNumbers(nextNode, tempNode)}
  }
}

121 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

java 暴力循环 或者 寻找历史最高值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 寻找历史最高值
class Solution {
  public int maxProfit(int[] prices) {
    int min = Integer.MAX_VALUE;
    int maxValue = 0;
    for (int i = 0; i < prices.length; i++) {
      if (prices[i] < min) {
        min = prices[i];
      } else if (prices[i] - min > maxValue) {
        maxValue = prices[i] - min;
      }
    }
    return maxValue;
  }
}
	
// 循环
public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

go 求数组中最大和子集合

1
2
3
4
5
6
7
8
9
10
11
12
func maxProfit(prices []int) int {
  var min int = 0x7FFFFFFF
  maxValue := 0
  for i:=0; i<len(prices); i++ {
    if min > prices[i] {
      min = prices[i]
    } else if prices[i] - min > maxValue {
      maxValue = prices[i] - min
    }
  }
  return maxValue
}

206 反转链表

反转一个单链表。

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
      ListNode rev = null;
      while (head != null) {
        ListNode next = head.next;
        head.next = rev;
        rev = head;
        head = next;
      }
      return rev;
    }
}

go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
  var rev *ListNode = nil
  for head!=nil {
    next := head.Next
    head.Next = rev
    rev = head
    head = next
  }
  return rev
}

322 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

1
2
3
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

java DFS(深度优先搜索)+去除多余的分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  int ans=Integer.MAX_VALUE;
  public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    dfs(coins, coins.length-1, amount, 0);
    return ans==Integer.MAX_VALUE? -1: ans;
  }

  public void dfs(int[] coins, int index, int amount, int cnt) {
    if(index < 0){
      // 结束搜索
      return;
    }
    for (int c = amount/coins[index]; c>=0; c--) {
      int newAmount = amount - c * coins[index];
      int newCnt = cnt + c;
      // 已经有解再向下减少大硬币不是最少解了
      if (newAmount == 0) {
        ans=Math.min(ans,newCnt);
        break;
      }
      // 多加一个硬币的结果大于等于现存结果硬币数 也没必要继续搜索下去了
      if (newCnt + 1 >= ans) {
        break;
      }
      dfs(coins, index-1, newAmount, newCnt);
    }
  }
 }

go DFS(深度优先搜索)+去除多余的分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func coinChange(coins []int, amount int) int {
  var ans int = 0x7FFFFFFF
  sort.Ints(coins)
  dfs(coins, len(coins)-1, amount, 0, &ans)
  if ans < 0x7FFFFFFF {
    return ans
  }
  return -1
}

func dfs(coins []int, index int, amount int, cnt int, ans *int) {
  if (index < 0) {
    return
  }
  for c := amount/coins[index]; c >= 0; c-- {
    newAmount := amount - c*coins[index]
    newCnt := cnt + c
    if newAmount == 0 {
      *ans = min(*ans, newCnt)
      break
    }
    if (newCnt+1 >= *ans) {
      break
    }
    dfs(coins, index-1, newAmount, newCnt, ans)
  }
}

func min(a, b int) int {
  if a > b {
    return b
  } else {
    return a
  }
}

409 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

1
2
3
4
5
输入:
"abccccdd"

输出:
7

java 最大回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
  public int longestPalindrome(String s) {
    // 存储字符出现的次数
    int[] arr = new int[128];
    for(char c : s.toCharArray()) {
      arr[c]++;
    }
    int count = 0;
    // 记录奇数个的字符个数
    for (int i : arr) {
      count += (i % 2);
    }
    return count == 0 ? s.length() : (s.length() - count + 1);
  }
}

543 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

1
2
3
4
5
6
7
给定二叉树
		  1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]

java 深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  int result;
  public int diameterOfBinaryTree(TreeNode root) {
    result = 1;
    dfs(root);
    return result - 1;
  }

  public int dfs(TreeNode root) {
    if (root == null) {
      return 0;
    }
    int l = dfs(root.left);
    int r = dfs(root.right);
    result = Math.max(result, l + r + 1);
    return Math.max(l, r) + 1;
  }
}

go 深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
  result:=0
  //现有的最长直径
  max:=&result
  if root==nil{
    return 0
  }
  dfs(root,max)
  return *max
}

func dfs(root *TreeNode,max *int)int{
  if root==nil{
    return 0
  }
  a:=dfs(root.Left,max)
  b:=dfs(root.Right,max)
  //此节点的直径和现有的最长直径比较
  *max =int(math.Max(float64(a+b),float64(*max)))
  //返回深度
  return int(math.Max(float64(a),float64(b)))+1
}

695 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

1
2
3
4
5
6
7
8
9
10
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

输出 6

java 沉岛算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 沉岛算法
class Solution {
  public int maxAreaOfIsland(int[][] grid) {
    int res = 0; 
    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[i].length; j++) {
        if (grid[i][j] == 1) {
          res = Math.max(res, dfs(i, j, grid));
        }
      }
    } 
    return res;
  }

  private int dfs(int i, int j, int[][] grid) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) { 
      return 0;
    } 
    grid[i][j] = 0;
    int num = 1;
    num += dfs(i + 1, j, grid);
    num += dfs(i - 1, j, grid);
    num += dfs(i, j + 1, grid);
    num += dfs(i, j - 1, grid);
    return num;
  }
}

836 矩形重叠

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。

如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形，判断它们是否重叠并返回结果。

1
2
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

java 模拟

1
2
3
4
5
6
7
8
9
class Solution {
  public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    return !(
      rec1[2] <= rec2[0] ||   // 左侧
      rec1[3] <= rec2[1] ||   // 底面
      rec1[0] >= rec2[2] ||   // 右侧
      rec1[1] >= rec2[3]);    // 顶面
  }
}

994 腐烂的橘子

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

1
2
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

java BFS(多维广度优先搜索)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
  // 存储四个腐化方向
  int[] dx = new int[]{-1, 0, 1, 0};
  int[] dy = new int[]{0, -1, 0, 1};

  public int orangesRotting(int[][] grid) {
    int X = grid.length, Y = grid[0].length;
    Queue<Integer> queue = new ArrayDeque();
    Map<Integer, Integer> depth = new HashMap();
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        if (grid[x][y] == 2) {
          // 腐化位置转化为唯一索引
          int code = x * Y + y;
          // 队列存储腐烂索引
          queue.add(code);
          // 记录腐化时间
          depth.put(code, 0);
        }
      }
    }
    // 记录耗时
    int ans = 0;
    // 模拟腐化进行BFS
    while (!queue.isEmpty()) {
      int code = queue.remove();
      int x = code/Y, y = code%Y;
      // 循环判断上下左右四个点是否腐化
      for (int k=0; k<4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (0 <= nx && nx < X && 0 <= ny && ny < Y && grid[nx][ny] == 1) {
          // 腐化并存入队列
          grid[nx][ny] = 2;
          int ncode = nx * Y + ny;
          queue.add(ncode);
          // 腐化耗时+1
          depth.put(ncode, depth.get(code) + 1);
          ans = depth.get(ncode);
        }
      }
    }

    // 检查grid,如果存在未腐化的返回-1
    for (int[] row : grid) {
      for (int v : row) {
        if (v == 1) {
          return -1;
        }
      }
    }

    return ans;
  }
}

go BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
func orangesRotting(grid [][]int) int {
    if grid==nil || len(grid)==0{
      return 0
    }
    dx:=[]int{-1,0,1,0}
    dy:=[]int{0,1,0,-1}
    //行列值
    row:=len(grid)
    col:=len(grid[0])
    //腐烂完成的时间
    res:=0
    queue:=make([]int,0)
    //首先找到一开始就是腐烂的橘子，将其作为一层
    for i:=0;i<row;i++{
      for j:=0;j<col;j++{
        if grid[i][j]==2{
          // 存入队列
          queue=append(queue,i*col+j)
        }
      }
    }
    //bfs搜索
    for len(queue)!=0{
      res++ //每搜完一层，则时间加一分钟
      cursize:=len(queue)//保存当前层的长度
      for i:=0;i<cursize;i++{
        node:=queue[0]
        queue=queue[1:]
        r,c:=node/col,node%col
        for k:=0;k<4;k++{
          nr:=r+dx[k]
          nc:=c+dy[k]
          if nr>=0 && nr<row && nc>=0 && nc<col && grid[nr][nc]==1{
            grid[nr][nc]=2  //将新鲜橘子腐烂
            queue=append(queue,nr*col+nc)//将腐烂橘子入队
          } 
        }
      }
    }
    //判断还有没有新鲜橘子，有就返回-1
    for i:=0;i<row;i++{
      for j:=0;j<col;j++{
        if grid[i][j]==1{
          return -1
        }
      }
    }
    //因为res在计算层的时候，把最开始的腐烂橘子也记为一层，
    //所以结果为res-1
    //存在一个特殊情况，及[[0]]，此时，res就为0，所以不需要-1
    if res==0{
      return res
    }else{
      return res-1
    }
}

1013 将数组分成和相等的三个部分

给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

1
2
3
4
5
6
输出：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

java 直接寻找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public boolean canThreePartsEqualSum(int[] A) {
    int sum = 0;
    for (int i : A) {
      sum += i;
    }
    if (sum % 3 != 0) {
      return false;
    }
    int flag = 0;
    int s = 0;
    for (int i : A) {
      s += i;
      if (sum/3 == s) {
        s = 0;
        flag ++;
      }
    }
    return flag >= 3;
  }
}

1071 字符串的最大公因子

对于字符串 S 和 T，只有在 S = T + … + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

1
2
3
4
5
6
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
输入：str1 = "LEET", str2 = "CODE"
输出：

go 辗转相除法求出最大公约字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 辗转相除求最大公约数
func gcdOfStrings(str1 string, str2 string) string {
  len1 := len(str1)
  len2 := len(str2)

  if len2 > len1 {
    return gcdOfStrings(str2, str1)
  }
  if len1 == len2 {
    if str1 == str2 {
      return str1
    } else {
      return ""
    }
  }
  for i:=0;i<len2;i++ {
    if str2[i] != str1[i] {
      return ""
    }
  }
  return gcdOfStrings(str1[len2:], str2)
}

Java 辗转相除 用index代替

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
  public String gcdOfStrings(String str1, String str2) {
    if (str1.equals(str2)) {
      return str1;
    }
    int index1=0,index2=0;
    while(str1.length()>=str2.length() && index1<str1.length() && index2<str2.length()){
      if(str1.charAt(index1)!=str2.charAt(index2)) 
        return "";
      index2++;
      index1++;
    }
    return gcdOfStrings(str2,str1.substring(index1,str1.length()));
  }
}

1103 分糖果 II

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）

1
2
3
4
5
6
7
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

java 模拟

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
  public int[] distributeCandies(int candies, int num_people) {
    int[] result = new int[num_people];
    int i = 0;
    while (candies != 0) {
      result[i%num_people] += Math.min(candies, i + 1);
      candies -= Math.min(candies, i + 1);
      i++;
    }
    return result;
  }
}

go 模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func distributeCandies(candies int, num_people int) []int {
  result := make([]int, num_people)
  i := 0
  for (candies > 0) {
    result[i%num_people] += min(candies, i + 1)
    candies -= min(candies, i + 1)
    i += 1
  }
  return result
}

func min(a, b int) int {
  if (a > b) {
    return b
  }else {
    return a
  }
}

1160 拼写单词

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

1
2
输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6

java 统计字符对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int countCharacters(String[] words, String chars) {
    //统计字符表中的字符
    int[] charsOfCase = new int[26];
    //单词长度之和
    int count = 0;
    //统计字符表中的字符
    for(char c : chars.toCharArray()) {
      charsOfCase[c-'a']++;
    }
    for(String str : words) {
      int[] temp = new int[26];
      boolean flag = true;
      //存储统计词汇表中单词的字符
      for(char c : str.toCharArray()) {
        temp[c-'a']++;
      }
      //对比两个统计数据
      for(int i = 0; i < charsOfCase.length; i++) {
        if(temp[i] > charsOfCase[i]) {
          flag = false;
          break;
        }
      }
      if(flag) 
        count += str.length();
    }
    return count;
  }
}

10.01 合并排序的数组

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

1
2
3
4
5
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
      int index = 0;
      int indexA,indexB;
      System.arraycopy(A, 0, A, n, m);
      for (indexA=n,indexB=0;indexA<(m+n)&&indexB<n;) {
        if (A[indexA] < B[indexB]) {
          A[index++] = A[indexA++];
        } else {
          A[index++] = B[indexB++];
        }
      }

      while (indexA < m + n) {
        A[index++] = A[indexA++];
      }

      while (indexB < n) {
        A[index++] = B[indexB++];
      }
    }
}

01.06 字符串压缩

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

1
2
输入："aabcccccaaa"
输出："a2b1c5a3"

java 程序模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public String compressString(String S) {
    if (S == null || S.length() <= 2) {
      return S;
    }
    StringBuilder sb = new StringBuilder().append(S.charAt(0));
    int cnt = 1;
    for (int i = 1; i < S.length(); i++) {
      // 如果i与i-1相同，cnt累加
      if (S.charAt(i) == S.charAt(i - 1)) {
        cnt++;
      } else { 
        // 否则拼接上i-1的次数，从i开始重新计数
        sb.append(cnt).append(S.charAt(i));
        cnt = 1;
      }
    }
    return sb.append(cnt).length() < S.length()? sb.toString(): S;
  }
}

05 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String replaceSpace(String s) {
      StringBuilder builder = new StringBuilder();
      char[] charList = s.toCharArray();
      for (int i=0; i<charList.length; i++) {
        if (charList[i] == ' ') {
          builder.append("%20");
        } else {
          builder.append(charList[i]);
        }
      }
      return builder.toString();
    }
}

go

1
2
3
4
5
6
7
8
9
10
11
func replaceSpace(s string) string {
  build := make([]rune, 0, len(s)*3)
  for _, si := range s {
    if si == ' ' {
      build = append(build, '%', '2', '0')
    } else {
      build = append(build, si)
    }
  }
  return string(build)
}

57 - II 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

1
2
输入：target = 9
输出：[[2,3,4],[4,5]]

java 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int[][] findContinuousSequence(int target) {
    int l = 1;
    int r = 1;
    int sum = 0;
    List<int[]> res = new ArrayList<>();
    while (l <= target/2) {
      if (sum < target) {
        sum += r;
        r++;
      } else if (sum > target) {
        sum -= l;
        l++;
      } else {
        int[] arr = new int[r-l];
        for (int k=l; k<r; k++) {
          arr[k-l] = k;
        }
        res.add(arr);
        sum -= l;
        l++;
      }
    }
    return res.toArray(new int[res.size()][]);
  }
}

go 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func findContinuousSequence(target int) [][]int {
  l:=1
  r:=1
  sum:=0
  result := make([][]int, 0)
  for (l <= target/2) {
    if sum < target {
      sum += r
      r += 1
    } else if sum > target {
      sum -= l
      l += 1
    } else {
      temp := make([]int, 0)
      for k:=l; k<r; k++ {
        temp = append(temp, k)
      }
      result = append(result, temp)
      sum -= l
      l += 1
    }
  }
  return result
}

59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

1
2
3
4
输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MaxQueue {
  int[] queue;
  int queueHead = 0;
  int queueTail = 0;
  int[] maxQueue;
  int maxQueueHead = 0;
  int maxQueueTail = 0;

    public MaxQueue() {
      queue = new int[10000];
      maxQueue = new int[10000];
    }
    
    public int max_value() {
      if (maxQueueTail == maxQueueHead) {
        return -1;
      }
      return maxQueue[maxQueueHead];
    }
    
    public void push_back(int value) {
      queue[queueTail++] = value;
      while (maxQueueTail != maxQueueHead && maxQueue[maxQueueTail-1] < value) {
        maxQueueTail--;
      }
      maxQueue[maxQueueTail++] = value;
    }
    
    public int pop_front() {
      if (queueHead == queueTail) {
        return -1;
      }
      int result = queue[queueHead];
      if (result == maxQueue[maxQueueHead]) {
        maxQueueHead++;
      }
      queueHead++;
      return result;
    }
}

go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
type MaxQueue struct {
  queue []int
  maxQueue []int
}

func Constructor() MaxQueue {
  return MaxQueue{
    make([]int, 0),
    make([]int, 0),
  }
}

func (this *MaxQueue) Max_value() int {
  if 0 == len(this.maxQueue) {
    return -1
  }
  return this.maxQueue[0]
}

func (this *MaxQueue) Push_back(value int)  {
  this.queue = append(this.queue, value)
  for len(this.maxQueue) != 0 && this.maxQueue[len(this.maxQueue)-1] < value {
    this.maxQueue = this.maxQueue[:len(this.maxQueue)-1]
  }
  this.maxQueue = append(this.maxQueue, value)
}


func (this *MaxQueue) Pop_front() int {
  if 0 == len(this.queue) {
    return -1
  }
  result := this.queue[0]
  this.queue = this.queue[1:]
  if result == this.maxQueue[0] {
    this.maxQueue = this.maxQueue[1:]
  }
  return result;
}