剑指offer3

61、

剑指 Offer II 061. 和最小的 k 个数对

给定两个升序数组，找到前n小的数对

#include <queue>
#include <tuple>
#include <vector>

using namespace std;

vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2,
                                   int k) {
  vector<vector<int>> ans;
  auto comp = [](const pair<int, int> &a, const pair<int, int> &b) {
    return a.first + a.second > b.first + b.second;
  };

  priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)>
      minHeap(comp);

  int m = nums1.size(), n = nums2.size();
  for (int i = 0; i < k && i < m; ++i) {
    minHeap.emplace(i, 0);
  }

  while (!minHeap.empty() && ans.size() < k) {
    auto [i, j] = minHeap.top();
    minHeap.pop();
    ans.push_back({nums1[i], nums2[j]});
    if (j + 1 < n) {
      minHeap.emplace(i, j + 1);
    }
  }

  return ans;
}

package main

import "container/heap"

func kSmallestPairs(nums1, nums2 []int, k int) (ans [][]int) {
	h := hp{nums1: nums1, nums2: nums2}
	m, n := len(nums1), len(nums2)
	for i := 0; i < k && i < m; i++ {
		heap.Push(&h, pair{i, 0})
	}
	for h.Len() > 0 && len(ans) < k {
		p := heap.Pop(&h).(pair)
		i, j := p.i, p.j
		ans = append(ans, []int{nums1[i], nums2[j]})
		if j+1 < n {
			heap.Push(&h, pair{i, j + 1})
		}
	}
	return
}

type hp struct {
	data         []pair
	nums1, nums2 []int
}

type pair struct {
	i, j int
}

func (h hp) Len() int {
	return len(h.data)
}

func (h hp) Less(i, j int) bool {
	p1, p2 := h.data[i], h.data[j]
	return h.nums1[p1.i]+h.nums2[p1.j] < h.nums1[p2.i]+h.nums2[p2.j]
}

func (h hp) Swap(i, j int) {
	h.data[i], h.data[j] = h.data[j], h.data[i]
}

func (h *hp) Push(val interface{}) {
	h.data = append(h.data, val.(pair))
}

func (h *hp) Pop() interface{} {
	data := h.data
	val := data[len(data)-1]
	h.data = data[:len(data)-1]
	return val
}

62、

剑指 Offer II 062. 实现前缀树

设计一个前缀树，提供数据插入，数据搜索，判断是否存在某个前缀

#include <string>
#include <vector>

class Trie {
public:
  Trie() : children(26, nullptr), isEnd(false) {}

  void Insert(const std::string &word) {
    Trie *node = this;
    for (char ch : word) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        node->children[ch] = new Trie();
      }
      node = node->children[ch];
    }
    node->isEnd = true;
  }

  bool Search(const std::string &word) {
    Trie *node = SearchPrefix(word);
    return node != nullptr && node->isEnd;
  }

  bool StartsWith(const std::string &prefix) {
    return SearchPrefix(prefix) != nullptr;
  }

private:
  std::vector<Trie *> children;
  bool isEnd;

  Trie *SearchPrefix(const std::string &prefix) {
    Trie *node = this;
    for (char ch : prefix) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        return nullptr;
      }
      node = node->children[ch];
    }
    return node;
  }
};

package main

type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func Constructor() Trie {
	return Trie{}
}

func (t *Trie) Insert(word string) {
	node := t
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &Trie{}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
	node := t
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return nil
		}
		node = node.children[ch]
	}
	return node
}

func (t *Trie) Search(word string) bool {
	node := t.SearchPrefix(word)
	return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
	return t.SearchPrefix(prefix) != nil
}

63、

剑指 Offer II 063. 替换单词

当一个词为另一个词的前缀那么称其为词根，后者称为继承词

给定一个词根数组，一个句子，将句子中的所有词语，如果存在其词根，那么就用词根进行替换

#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Trie {
public:
  unordered_map<char, Trie *> children;
  bool isEnd = false;

  void insert(const string &word) {
    Trie *node = this;
    for (char c : word) {
      if (node->children.find(c) == node->children.end()) {
        node->children[c] = new Trie();
      }
      node = node->children[c];
    }
    node->isEnd = true;
  }

  string searchRoot(const string &word) {
    Trie *node = this;
    for (int i = 0; i < word.size(); ++i) {
      char c = word[i];
      if (node->isEnd) {
        return word.substr(0, i);
      }
      if (node->children.find(c) == node->children.end()) {
        break;
      }
      node = node->children[c];
    }
    return word;
  }
};

string replaceWords(vector<string> &dictionary, const string &sentence) {
  Trie root;
  for (const string &word : dictionary) {
    root.insert(word);
  }

  istringstream iss(sentence);
  string word;
  string result;
  while (iss >> word) {
    if (!result.empty()) {
      result += " ";
    }
    result += root.searchRoot(word);
  }

  return result;
}

package main

import "strings"

func replaceWords(dictionary []string, sentence string) string {
	type trie map[rune]trie
	root := trie{}
	for _, s := range dictionary {
		cur := root
		for _, c := range s {
			if cur[c] == nil {
				cur[c] = trie{}
			}
			cur = cur[c]
		}
		cur['#'] = trie{}
	}

	words := strings.Split(sentence, " ")
	for i, word := range words {
		cur := root
		for j, c := range word {
			if cur['#'] != nil {
				words[i] = word[:j]
				break
			}
			if cur[c] == nil {
				break
			}
			cur = cur[c]
		}
	}
	return strings.Join(words, " ")
}

64、

剑指 Offer II 064. 神奇的字典

一个初始字符串列表，提供一个搜索方法，判断需要搜索的字符串进行一次字符替换后是否出现在初始字符串列表。

#include <string>
#include <vector>

class Trie {
public:
  Trie *children[26] = {nullptr};
  bool isEnd = false;
};

class MagicDictionary {
public:
  MagicDictionary() { root = new Trie(); }

  void BuildDict(const std::vector<std::string> &dictionary) {
    for (const std::string &word : dictionary) {
      Trie *node = root;
      for (char ch : word) {
        int idx = ch - 'a';
        if (node->children[idx] == nullptr) {
          node->children[idx] = new Trie();
        }
        node = node->children[idx];
      }
      node->isEnd = true;
    }
  }

  bool Search(const std::string &searchWord) {
    return dfs(root, searchWord, 0, false);
  }

private:
  Trie *root;

  bool dfs(Trie *node, const std::string &word, int index, bool modified) {
    if (index == word.size()) {
      return modified && node->isEnd;
    }
    int c = word[index] - 'a';
    if (node->children[c] != nullptr &&
        dfs(node->children[c], word, index + 1, modified)) {
      return true;
    }
    if (!modified) {
      for (int i = 0; i < 26; ++i) {
        if (i != c && node->children[i] != nullptr &&
            dfs(node->children[i], word, index + 1, true)) {
          return true;
        }
      }
    }
    return false;
  }
};

package main

type MagicDictionary struct {
	trie *trie
}

type trie struct {
	children [26]*trie
	isEnd    bool
}

/** Initialize your data structure here. */
func NewMagicDictionary() MagicDictionary {
	return MagicDictionary{trie: &trie{}}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	for _, word := range dictionary {
		cur := this.trie
		for _, ch := range word {
			idx := ch - 'a'
			if cur.children[idx] == nil {
				cur.children[idx] = &trie{}
			}
			cur = cur.children[idx]
		}
		cur.isEnd = true
	}
}

func (this *MagicDictionary) Search(searchWord string) bool {
	var dfs func(node *trie, searchWord string, modified bool) bool
	dfs = func(node *trie, searchWord string, modified bool) bool {
		if searchWord == "" {
			return modified && node.isEnd
		}
		c := searchWord[0] - 'a'
		if node.children[c] != nil && dfs(node.children[c], searchWord[1:], modified) {
			return true
		}
		if !modified {
			for i, child := range node.children {
				if i != int(c) && child != nil && dfs(child, searchWord[1:], true) {
					return true
				}
			}
		}
		return false
	}
	return dfs(this.trie, searchWord, false)
}

65、

剑指 Offer II 065. 最短的单词编码

暂时没理解到含义，详情查看https://leetcode.cn/problems/iSwD2y/?favorite=e8X3pBZi

#include <algorithm>
#include <functional>
#include <string>
#include <vector>

class Trie {
public:
  Trie *child[26] = {nullptr};
  int depth = 1;

  Trie() = default;

  void Insert(const std::string &word) {
    Trie *curr = this;
    int n = word.size();
    for (int i = n - 1; i >= 0; --i) {
      int c = word[i] - 'a';
      if (curr->child[c] == nullptr) {
        curr->child[c] = new Trie();
      }
      curr->child[c]->depth = curr->depth + 1;
      curr = curr->child[c];
    }
  }
};

int minimumLengthEncoding(std::vector<std::string> &words) {
  Trie *root = new Trie();
  for (const std::string &word : words) {
    root->Insert(word);
  }

  int res = 0;
  std::function<void(Trie *)> dfs = [&](Trie *node) -> void {
    bool hasChild = false;
    for (int i = 0; i < 26; ++i) {
      if (node->child[i] != nullptr) {
        hasChild = true;
        dfs(node->child[i]);
      }
    }
    if (!hasChild) {
      res += node->depth;
    }
  };
  dfs(root);
  return res;
}

package main

type WordEncodeTrie struct {
	child [26]*WordEncodeTrie
	depth int
}

func NewTrie() *WordEncodeTrie {
	return &WordEncodeTrie{
		child: [26]*WordEncodeTrie{},
		depth: 1,
	}
}

func (t *WordEncodeTrie) Insert(word string) {
	curr := t
	n := len(word)
	for i := n - 1; i >= 0; i-- {
		c := word[i] - 'a'
		if curr.child[c] == nil {
			curr.child[c] = NewTrie()
		}
		curr.child[c].depth = curr.depth + 1
		curr = curr.child[c]
	}
}

func minimumLengthEncoding(words []string) int {
	t := NewTrie()
	for _, w := range words {
		t.Insert(w)
	}
	var res int
	var dfs func(node *WordEncodeTrie)
	dfs = func(node *WordEncodeTrie) {
		var hasChild bool
		for i := 0; i < 26; i++ {
			if node.child[i] != nil {
				hasChild = true
				dfs(node.child[i])
			}
		}
		if !hasChild {
			res += node.depth
		}
	}
	dfs(t)
	return res
}

66、

剑指 Offer II 066. 单词之和

提供两个方法，插入字符串以及个数，查询一个前缀所包含的值的大小。

如果该key已经存在则进行替换，给定一个字符串查询以该字符串为前缀的元素总和

#include <string>
#include <unordered_map>
#include <vector>

class TrieNode {
public:
  TrieNode *children[26] = {nullptr};
  int val = 0;
};

class MapSum {
public:
  MapSum() { root = new TrieNode(); }

  void Insert(const std::string &key, int val) {
    int delta = val;
    if (cnt.find(key) != cnt.end()) {
      delta -= cnt[key];
    }
    cnt[key] = val;
    TrieNode *node = root;
    for (char ch : key) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        node->children[ch] = new TrieNode();
      }
      node = node->children[ch];
      node->val += delta;
    }
  }

  int Sum(const std::string &prefix) {
    TrieNode *node = root;
    for (char ch : prefix) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        return 0;
      }
      node = node->children[ch];
    }
    return node->val;
  }

private:
  TrieNode *root;
  std::unordered_map<std::string, int> cnt;
};

package main

type TrieNode struct {
	children [26]*TrieNode
	val      int
}

type MapSum struct {
	root *TrieNode
	cnt  map[string]int
}

func NewMapSum() MapSum {
	return MapSum{
		&TrieNode{},
		map[string]int{},
	}
}

func (m *MapSum) Insert(key string, val int) {
	delta := val
	if m.cnt[key] > 0 {
		delta -= m.cnt[key]
	}
	m.cnt[key] = val
	node := m.root
	for _, ch := range key {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &TrieNode{}
		}
		node = node.children[ch]
		node.val += delta
	}
}

func (m *MapSum) Sum(prefix string) int {
	node := m.root
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.val
}

67、

剑指 Offer II 067. 最大的异或

给定一个整数数组，两两元素进行异或，找到最大值

#include <algorithm>
#include <vector>

const int highBit = 30;

class Trie {
public:
  Trie *left = nullptr;
  Trie *right = nullptr;

  void add(int num) {
    Trie *cur = this;
    for (int i = highBit; i >= 0; --i) {
      int bit = (num >> i) & 1;
      if (bit == 0) {
        if (cur->left == nullptr) {
          cur->left = new Trie();
        }
        cur = cur->left;
      } else {
        if (cur->right == nullptr) {
          cur->right = new Trie();
        }
        cur = cur->right;
      }
    }
  }

  int check(int num) {
    Trie *cur = this;
    int x = 0;
    for (int i = highBit; i >= 0; --i) {
      int bit = (num >> i) & 1;
      if (bit == 0) {
        if (cur->right != nullptr) {
          cur = cur->right;
          x = x * 2 + 1;
        } else {
          cur = cur->left;
          x = x * 2;
        }
      } else {
        if (cur->left != nullptr) {
          cur = cur->left;
          x = x * 2 + 1;
        } else {
          cur = cur->right;
          x = x * 2;
        }
      }
    }
    return x;
  }
};

int findMaximumXOR(const std::vector<int> &nums) {
  Trie *root = new Trie();
  int x = 0;
  for (int i = 1; i < nums.size(); ++i) {
    root->add(nums[i - 1]);
    x = std::max(x, root->check(nums[i]));
  }
  return x;
}

package main

const highBit = 30

type xor_trie struct {
	left, right *xor_trie
}

func (t *xor_trie) add(num int) {
	cur := t
	for i := highBit; i >= 0; i-- {
		bit := num >> i & 1
		if bit == 0 {
			if cur.left == nil {
				cur.left = &xor_trie{}
			}
			cur = cur.left
		} else {
			if cur.right == nil {
				cur.right = &xor_trie{}
			}
			cur = cur.right
		}
	}
}

func (t *xor_trie) check(num int) (x int) {
	cur := t
	for i := highBit; i >= 0; i-- {
		bit := num >> i & 1
		if bit == 0 {
			// a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走
			if cur.right != nil {
				cur = cur.right
				x = x*2 + 1
			} else {
				cur = cur.left
				x = x * 2
			}
		} else {
			// a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走
			if cur.left != nil {
				cur = cur.left
				x = x*2 + 1
			} else {
				cur = cur.right
				x = x * 2
			}
		}
	}
	return
}

func findMaximumXOR(nums []int) (x int) {
	root := &xor_trie{}
	for i := 1; i < len(nums); i++ {
		// 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中
		root.add(nums[i-1])
		// 将 nums[i] 看作 ai，找出最大的 x 更新答案
		x = max(x, root.check(nums[i]))
	}
	return
}

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

68、

剑指 Offer II 068. 查找插入位置

往一个有序数组中进行数据插入，查找数据的插入位置，要求使用O(logn)复杂度

#include <vector>

int searchInsert(const std::vector<int> &nums, int target) {
  int n = nums.size();
  int left = 0, right = n - 1;
  int ans = n;
  while (left <= right) {
    int mid = (right - left) / 2 + left;
    if (target <= nums[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
}

package main

func searchInsert(nums []int, target int) int {
	n := len(nums)
	left, right := 0, n-1
	ans := n
	for left <= right {
		mid := (right-left)>>1 + left
		if target <= nums[mid] {
			ans = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return ans
}

69、

剑指 Offer II 069. 山峰数组的顶部

找到下标i，在i之前是递增数据，在i之后是递减数据

题目保证满足存在这样的i

#include <algorithm>
#include <vector>

int peakIndexInMountainArray(const std::vector<int> &arr) {
  return std::distance(arr.begin(), std::find_if(
                                        arr.begin(), arr.end() - 1,
                                        &{ return arr[i] > arr[i + 1]; }));
}

package main

import "sort"

func peakIndexInMountainArray(arr []int) int {
	return sort.Search(len(arr)-1, func(i int) bool { return arr[i] > arr[i+1] })
}

70、

剑指 Offer II 070. 排序数组中只出现一次的数字

一个有序数组，有一个元素只出现一次，其他元素出现了两次，找到这个只出现了一次的元素，满足O(logn)时间复杂度，O(1)空间复杂度

#include <vector>

int singleNonDuplicate(const std::vector<int> &nums) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    int mid = low + (high - low) / 2;
    if (nums[mid] == nums[mid ^ 1]) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return nums[low];
}

package main

func singleNonDuplicate(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		mid := low + (high-low)/2
		if nums[mid] == nums[mid^1] {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return nums[low]
}

71、

剑指 Offer II 071. 按权重生成随机数

按照值的大小作为权重占比进行随机数获取，返回其数据下标

#include <algorithm>
#include <cstdlib>
#include <vector>

class Solution {
public:
  Solution(std::vector<int> &w) {
    for (int i = 1; i < w.size(); ++i) {
      w[i] += w[i - 1];
    }
    pre = w;
  }

  int PickIndex() {
    int x = rand() % pre.back() + 1;
    return std::lower_bound(pre.begin(), pre.end(), x) - pre.begin();
  }

private:
  std::vector<int> pre;
};

package main

import (
	"math/rand"
	"sort"
)

type WeightRandom struct {
	pre []int
}

func NewWeightRandom(w []int) WeightRandom {
	for i := 1; i < len(w); i++ {
		w[i] += w[i-1]
	}
	return WeightRandom{w}
}

func (s *WeightRandom) PickIndex() int {
	x := rand.Intn(s.pre[len(s.pre)-1]) + 1
	return sort.SearchInts(s.pre, x)
}

72、

剑指 Offer II 072. 求平方根

计算一个整数的开平方根，只取正数那一个

int mySqrt(int x) {
  int l = 0, r = x;
  int ans = -1;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (mid * mid <= x) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return ans;
}

package main

func mySqrt(x int) int {
	l, r := 0, x
	ans := -1
	for l <= r {
		mid := l + (r-l)/2
		if mid*mid <= x {
			ans = mid
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return ans
}

73、

剑指 Offer II 073. 狒狒吃香蕉

n堆香蕉，在h小时内要吃完，选择要吃完所有香蕉的最小速度，不过需要注意如果选择了一堆香蕉后，小于k个也会等待下一个小时才会继续吃。

#include <algorithm>
#include <vector>

int minEatingSpeed(const std::vector<int> &piles, int h) {
  int maxPile = *std::max_element(piles.begin(), piles.end());
  return 1 + std::lower_bound(1, maxPile - 1, [&](int speed) -> bool {
           int time = 0;
           for (int pile : piles) {
             time += (pile + speed - 1) / speed;
           }
           return time <= h;
         });
}

package main

import "sort"

func minEatingSpeed(piles []int, h int) int {
	max := 0
	for _, pile := range piles {
		if pile > max {
			max = pile
		}
	}
	return 1 + sort.Search(max-1, func(speed int) bool {
		speed++
		time := 0
		for _, pile := range piles {
			time += (pile + speed - 1) / speed
		}
		return time <= h
	})
}

74、

剑指 Offer II 074. 合并区间

给定一个元组数组，其中的元素即为一个左右区间，将所有重叠的区间进行合并，并返回一个不重叠的区间数组

#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> merge(vector<vector<int>> &intervals) {
  sort(intervals.begin(), intervals.end(),
       [](const vector<int> &a, const vector<int> &b) {
         return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
       });

  vector<vector<int>> res;
  for (const auto &interval : intervals) {
    if (res.empty() || res.back()[1] < interval[0]) {
      res.push_back(interval);
    } else {
      res.back()[1] = max(res.back()[1], interval[1]);
    }
  }
  return res;
}

int max(int a, int b) { return (a > b) ? a : b; }

package main

import "sort"

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0] || (intervals[i][0] == intervals[j][0] && intervals[i][1] < intervals[j][1])
	})
	var res [][]int
	for _, interval := range intervals {
		if len(res) == 0 || res[len(res)-1][1] < interval[0] {
			res = append(res, interval)
		} else {
			res[len(res)-1][1] = max(res[len(res)-1][1], interval[1])
		}
	}
	return res
}

75

剑指 Offer II 075. 数组相对排序

给定两个数组arr1和arr2，将arr1按照arr2的顺序进行排序，未出现过的就按照升序之后放在arr1的末尾。

#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

class ZSet {
public:
  void insert(int key) { data[key]++; }

  void erase(int key) { data.erase(key); }

  vector<int> keys() const {
    vector<int> res;
    for (const auto &[key, _] : data) {
      res.push_back(key);
    }
    sort(res.begin(), res.end());
    return res;
  }

  int count(int key) const {
    auto it = data.find(key);
    return it != data.end() ? it->second : 0;
  }

private:
  unordered_map<int, int> data;
};

vector<int> relativeSortArray(vector<int> &arr1, const vector<int> &arr2) {
  ZSet zs;
  for (int val : arr1) {
    zs.insert(val);
  }

  vector<int> res;
  for (int val : arr2) {
    int count = zs.count(val);
    res.insert(res.end(), count, val);
    zs.erase(val);
  }

  vector<int> remainingKeys = zs.keys();
  for (int key : remainingKeys) {
    int count = zs.count(key);
    res.insert(res.end(), count, key);
  }

  return res;
}

package main

import "sort"

type zset map[int]int

func (zs *zset) keys() []int {
	res := []int{}
	for key := range *zs {
		res = append(res, key)
	}
	sort.Ints(res)
	return res
}

func relativeSortArray(arr1 []int, arr2 []int) []int {
	zs := zset{}
	for _, val := range arr1 {
		zs[val]++
	}

	res := make([]int, 0, len(arr1))
	for _, val := range arr2 {
		for i := 0; i < zs[val]; i++ {
			res = append(res, val)
		}
		delete(zs, val)
	}
	for _, key := range zs.keys() {
		for i := 0; i < zs[key]; i++ {
			res = append(res, key)
		}
	}
	return res
}

76

剑指 Offer II 076. 数组中的第 k 大的数字

给定一个整数数组和整数，返回数组中第k个最大的元素

#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;

int partition(vector<int> &a, int l, int r) {
  int x = a[r];
  int i = l - 1;
  for (int j = l; j < r; ++j) {
    if (a[j] <= x) {
      ++i;
      swap(a[i], a[j]);
    }
  }
  swap(a[i + 1], a[r]);
  return i + 1;
}

int randomPartition(vector<int> &a, int l, int r) {
  int i = rand() % (r - l + 1) + l;
  swap(a[i], a[r]);
  return partition(a, l, r);
}

int quickSelect(vector<int> &a, int l, int r, int index) {
  int q = randomPartition(a, l, r);
  if (q == index) {
    return a[q];
  } else if (q < index) {
    return quickSelect(a, q + 1, r, index);
  }
  return quickSelect(a, l, q - 1, index);
}

int findKthLargest(vector<int> &nums, int k) {
  srand(time(0));
  return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}

package main

import (
	"math/rand"
	"time"
)

func findKthLargest(nums []int, k int) int {
	rand.Seed(time.Now().UnixNano())
	return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(a []int, l, r, index int) int {
	q := randomPartition(a, l, r)
	if q == index {
		return a[q]
	} else if q < index {
		return quickSelect(a, q+1, r, index)
	}
	return quickSelect(a, l, q-1, index)
}

func randomPartition(a []int, l, r int) int {
	i := rand.Int()%(r-l+1) + l
	a[i], a[r] = a[r], a[i]
	return partition(a, l, r)
}

func partition(a []int, l, r int) int {
	x := a[r]
	i := l - 1
	for j := l; j < r; j++ {
		if a[j] <= x {
			i++
			a[i], a[j] = a[j], a[i]
		}
	}
	a[i+1], a[r] = a[r], a[i+1]
	return i + 1
}

77

剑指 Offer II 077. 链表排序

对链表节点进行升序排序

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

ListNode *merge(ListNode *head1, ListNode *head2) {
  ListNode dummyHead(0);
  ListNode *temp = &dummyHead;
  ListNode *temp1 = head1;
  ListNode *temp2 = head2;

  while (temp1 != nullptr && temp2 != nullptr) {
    if (temp1->val <= temp2->val) {
      temp->next = temp1;
      temp1 = temp1->next;
    } else {
      temp->next = temp2;
      temp2 = temp2->next;
    }
    temp = temp->next;
  }

  if (temp1 != nullptr) {
    temp->next = temp1;
  } else if (temp2 != nullptr) {
    temp->next = temp2;
  }

  return dummyHead.next;
}

ListNode *sort(ListNode *head, ListNode *tail) {
  if (head == nullptr) {
    return head;
  }

  if (head->next == tail) {
    head->next = nullptr;
    return head;
  }

  ListNode *slow = head;
  ListNode *fast = head;
  while (fast != tail) {
    slow = slow->next;
    fast = fast->next;
    if (fast != tail) {
      fast = fast->next;
    }
  }

  ListNode *mid = slow;
  return merge(sort(head, mid), sort(mid, tail));
}

ListNode *sortList(ListNode *head) { return sort(head, nullptr); }

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func MergeList(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	temp, temp1, temp2 := dummyHead, head1, head2
	for temp1 != nil && temp2 != nil {
		if temp1.Val <= temp2.Val {
			temp.Next = temp1
			temp1 = temp1.Next
		} else {
			temp.Next = temp2
			temp2 = temp2.Next
		}
		temp = temp.Next
	}
	if temp1 != nil {
		temp.Next = temp1
	} else if temp2 != nil {
		temp.Next = temp2
	}
	return dummyHead.Next
}

func SortList(head, tail *ListNode) *ListNode {
	if head == nil {
		return head
	}

	if head.Next == tail {
		head.Next = nil
		return head
	}

	slow, fast := head, head
	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}

	mid := slow
	return MergeList(SortList(head, mid), SortList(mid, tail))
}

func sortList(head *ListNode) *ListNode {
	return SortList(head, nil)
}

78

剑指 Offer II 078. 合并排序链表

#include <queue>
#include <vector>

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
  ListNode dummyHead(0);
  ListNode *p = &dummyHead;
  ListNode *p1 = list1;
  ListNode *p2 = list2;

  while (p1 != nullptr && p2 != nullptr) {
    if (p1->val > p2->val) {
      p->next = p2;
      p2 = p2->next;
    } else {
      p->next = p1;
      p1 = p1->next;
    }
    p = p->next;
  }

  if (p1 != nullptr) {
    p->next = p1;
  }
  if (p2 != nullptr) {
    p->next = p2;
  }

  return dummyHead.next;
}

ListNode *mergeKLists(std::vector<ListNode *> &lists) {
  ListNode *res = nullptr;
  for (ListNode *list : lists) {
    res = mergeTwoLists(res, list);
  }
  return res;
}

package main

// 合并K个升序链表
func mergeKLists(lists []*ListNode) (res *ListNode) {
	for _, v := range lists {
		res = mergeTwoLists(res, v)
	}
	return res
}

// 合并两个升序链表
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	//初始化一个虚拟的头节点
	newList := &ListNode{}
	p := newList
	p1 := list1
	p2 := list2
	//遍历对比两个指针值的大小，有一个走完了就停止
	for p1 != nil && p2 != nil {
		//将值小的节点接到p指针后面
		if p1.Val > p2.Val {
			p.Next = p2
			p2 = p2.Next
		} else {
			p.Next = p1
			p1 = p1.Next
		}
		//p指针前进
		p = p.Next
	}
	//将未比较的剩余节点都放到p指针后面
	if p1 != nil {
		p.Next = p1
	}
	if p2 != nil {
		p.Next = p2
	}
	//返回虚拟头节点的下一个节点就是真正的头节点
	return newList.Next
}

79

剑指 Offer II 079. 所有子集

给定一个元素各不相同的的数组，返回所有不重复的子集

#include <vector>

using namespace std;

vector<vector<int>> subsets(vector<int> &nums) {
  vector<vector<int>> ans;
  int n = nums.size();
  for (int mask = 0; mask < (1 << n); ++mask) {
    vector<int> set;
    for (int i = 0; i < n; ++i) {
      if (mask & (1 << i)) {
        set.push_back(nums[i]);
      }
    }
    ans.push_back(set);
  }
  return ans;
}

package main

func subsets(nums []int) (ans [][]int) {
	n := len(nums)
	for mask := 0; mask < 1<<n; mask++ {
		set := []int{}
		for i, v := range nums {
			if mask>>i&1 > 0 {
				set = append(set, v)
			}
		}
		ans = append(ans, append([]int(nil), set...))
	}
	return
}

80

剑指 Offer II 080. 含有 k 个元素的组合

给定整数n和k，返回1...n中所有可能的k个数的组合

#include <vector>

using namespace std;

void dfs(int cur, int n, int k, vector<int> &temp, vector<vector<int>> &ans) {
  // Pruning: if the remaining elements plus the current temp size is less than
  // k, return
  if (temp.size() + (n - cur + 1) < k) {
    return;
  }
  // Record valid answers
  if (temp.size() == k) {
    ans.push_back(temp);
    return;
  }
  // Consider the current position
  temp.push_back(cur);
  dfs(cur + 1, n, k, temp, ans);
  temp.pop_back();
  // Consider not choosing the current position
  dfs(cur + 1, n, k, temp, ans);
}

vector<vector<int>> combine(int n, int k) {
  vector<vector<int>> ans;
  vector<int> temp;
  dfs(1, n, k, temp, ans);
  return ans;
}

package main

func combine(n int, k int) (ans [][]int) {
	temp := []int{}
	var dfs func(int)
	dfs = func(cur int) {
		// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
		if len(temp)+(n-cur+1) < k {
			return
		}
		// 记录合法的答案
		if len(temp) == k {
			comb := make([]int, k)
			copy(comb, temp)
			ans = append(ans, comb)
			return
		}
		// 考虑选择当前位置
		temp = append(temp, cur)
		dfs(cur + 1)
		temp = temp[:len(temp)-1]
		// 考虑不选择当前位置
		dfs(cur + 1)
	}
	dfs(1)
	return
}

81

剑指 Offer II 081. 允许重复选择元素的组合

从数组中寻找和为目标值的组合，数组中的元素可以重复选择

下面这种题解是标准解法，不过不能去除重复的情况，详情看82

#include <vector>

using namespace std;

void dfs(const vector<int> &candidates, int target, int idx, vector<int> &comb,
         vector<vector<int>> &ans) {
  if (idx == candidates.size()) {
    return;
  }
  if (target == 0) {
    ans.push_back(comb);
    return;
  }
  // Skip the current number
  dfs(candidates, target, idx + 1, comb, ans);
  // Choose the current number
  if (target - candidates[idx] >= 0) {
    comb.push_back(candidates[idx]);
    dfs(candidates, target - candidates[idx], idx, comb, ans);
    comb.pop_back();
  }
}

vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
  vector<vector<int>> ans;
  vector<int> comb;
  dfs(candidates, target, 0, comb, ans);
  return ans;
}

package main

func combinationSum(candidates []int, target int) (ans [][]int) {
	comb := []int{}
	var dfs func(target, idx int)
	dfs = func(target, idx int) {
		if idx == len(candidates) {
			return
		}
		if target == 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		// 直接跳过
		dfs(target, idx+1)
		// 选择当前数
		if target-candidates[idx] >= 0 {
			comb = append(comb, candidates[idx])
			dfs(target-candidates[idx], idx)
			comb = comb[:len(comb)-1]
		}
	}
	dfs(target, 0)
	return
}

82

剑指 Offer II 082. 含有重复元素集合的组合

与81题类似，不过这里元素只能使用一次

#include <algorithm>
#include <vector>

using namespace std;

void dfs(int pos, int rest, const vector<pair<int, int>> &freq,
         vector<int> &sequence, vector<vector<int>> &ans) {
  if (rest == 0) {
    ans.push_back(sequence);
    return;
  }
  if (pos == freq.size() || rest < freq[pos].first) {
    return;
  }

  dfs(pos + 1, rest, freq, sequence, ans);

  int most = min(rest / freq[pos].first, freq[pos].second);
  for (int i = 1; i <= most; ++i) {
    sequence.push_back(freq[pos].first);
    dfs(pos + 1, rest - i * freq[pos].first, freq, sequence, ans);
  }
  sequence.resize(sequence.size() - most);
}

vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
  sort(candidates.begin(), candidates.end());
  vector<pair<int, int>> freq;
  for (int num : candidates) {
    if (freq.empty() || num != freq.back().first) {
      freq.emplace_back(num, 1);
    } else {
      ++freq.back().second;
    }
  }

  vector<vector<int>> ans;
  vector<int> sequence;
  dfs(0, target, freq, sequence, ans);
  return ans;
}

int min(int a, int b) { return (a < b) ? a : b; }

package main

import "sort"

func combinationSum2(candidates []int, target int) (ans [][]int) {
	sort.Ints(candidates)
	var freq [][2]int // [值，次数]
	for _, num := range candidates {
		if freq == nil || num != freq[len(freq)-1][0] {
			freq = append(freq, [2]int{num, 1})
		} else {
			freq[len(freq)-1][1]++
		}
	}

	var sequence []int
	var dfs func(pos, rest int)
	dfs = func(pos, rest int) {
		if rest == 0 {
			ans = append(ans, append([]int(nil), sequence...))
			return
		}
		if pos == len(freq) || rest < freq[pos][0] {
			return
		}

		dfs(pos+1, rest)

		most := min(rest/freq[pos][0], freq[pos][1])
		for i := 1; i <= most; i++ {
			sequence = append(sequence, freq[pos][0])
			dfs(pos+1, rest-i*freq[pos][0])
		}
		sequence = sequence[:len(sequence)-most]
	}
	dfs(0, target)
	return
}

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

83

剑指 Offer II 083. 没有重复元素集合的全排列

给定一个不包含重复数字的整数数组，返回所有可能的全排列

#include <vector>

using namespace std;

void dfs(vector<int> &nums, vector<bool> &vis, vector<int> &path,
         vector<vector<int>> &ans) {
  if (path.size() == nums.size()) {
    ans.push_back(path);
    return;
  }
  for (int i = 0; i < nums.size(); ++i) {
    if (!vis[i]) {
      vis[i] = true;
      path.push_back(nums[i]);
      dfs(nums, vis, path, ans);
      vis[i] = false;
      path.pop_back();
    }
  }
}

vector<vector<int>> permute(vector<int> &nums) {
  vector<vector<int>> ans;
  vector<int> path;
  vector<bool> vis(nums.size(), false);
  dfs(nums, vis, path, ans);
  return ans;
}

package main

func permute(nums []int) [][]int {
	n := len(nums)
	var ans [][]int
	var path []int
	vis := make([]bool, n)
	var dfs func()
	dfs = func() {
		if len(path) == n {
			ans = append(ans, append([]int{}, path...))
			return
		}
		for i := 0; i < n; i++ {
			if !vis[i] {
				vis[i] = true
				path = append(path, nums[i])
				dfs()
				vis[i] = false
				path = path[:len(path)-1]
			}
		}
	}
	dfs()
	return ans
}

84

剑指 Offer II 084. 含有重复元素集合的全排列

给定一个可包含重复数字的整数集合 nums ，按任意顺序返回它所有不重复的全排列。

#include <algorithm>
#include <vector>

using namespace std;

void backtrack(vector<int> &nums, vector<bool> &vis, vector<int> &perm,
               vector<vector<int>> &ans, int idx) {
  if (idx == nums.size()) {
    ans.push_back(perm);
    return;
  }
  for (int i = 0; i < nums.size(); ++i) {
    if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
      continue;
    }
    perm.push_back(nums[i]);
    vis[i] = true;
    backtrack(nums, vis, perm, ans, idx + 1);
    vis[i] = false;
    perm.pop_back();
  }
}

vector<vector<int>> permuteUnique(vector<int> &nums) {
  sort(nums.begin(), nums.end());
  vector<vector<int>> ans;
  vector<int> perm;
  vector<bool> vis(nums.size(), false);
  backtrack(nums, vis, perm, ans, 0);
  return ans;
}

package main

import "sort"

func permuteUnique(nums []int) (ans [][]int) {
	sort.Ints(nums)
	n := len(nums)
	perm := []int{}
	vis := make([]bool, n)
	var backtrack func(int)
	backtrack = func(idx int) {
		if idx == n {
			ans = append(ans, append([]int(nil), perm...))
			return
		}
		for i, v := range nums {
			if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
				continue
			}
			perm = append(perm, v)
			vis[i] = true
			backtrack(idx + 1)
			vis[i] = false
			perm = perm[:len(perm)-1]
		}
	}
	backtrack(0)
	return
}

85

剑指 Offer II 085. 生成匹配的括号

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且有效的括号组合。

#include <string>
#include <vector>

using namespace std;

vector<string> generateParenthesis(int n) {
  vector<vector<string>> dp(n + 1);
  dp[0] = {""};
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
      for (const string &left : dp[j]) {
        for (const string &right : dp[i - j - 1]) {
          dp[i].push_back("(" + left + ")" + right);
        }
      }
    }
  }
  return dp[n];
}

void dfs(int n, int leftCnt, int rightCnt, string &tmp, vector<string> &res) {
  if (tmp.size() == n * 2) {
    res.push_back(tmp);
    return;
  }
  if (leftCnt < n) {
    tmp.push_back('(');
    dfs(n, leftCnt + 1, rightCnt, tmp, res);
    tmp.pop_back();
  }
  if (leftCnt > rightCnt) {
    tmp.push_back(')');
    dfs(n, leftCnt, rightCnt + 1, tmp, res);
    tmp.pop_back();
  }
}

vector<string> generateParenthesisDFS(int n) {
  vector<string> res;
  string tmp;
  dfs(n, 0, 0, tmp, res);
  return res;
}

package main

// 动态规划版本
func generateParenthesisDP(n int) []string {
	dp := make([][]string, n+1)
	dp[0] = []string{""}
	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			for _, left := range dp[j] {
				for _, right := range dp[i-j-1] {
					dp[i] = append(dp[i], "("+left+")"+right)
				}
			}

		}
	}
	return dp[n]
}

// 递归版本
func generateParenthesisDFS(n int) []string {
	var res []string
	var leftCnt, rightCnt int
	var tmp []byte
	var dfs func(cnt int)
	dfs = func(cnt int) {
		if cnt == n*2 {
			res = append(res, string(tmp))
			return
		}
		if leftCnt < n {
			leftCnt++
			tmp = append(tmp, '(')
			dfs(cnt + 1)
			leftCnt--
			tmp = tmp[:len(tmp)-1]
		}
		if leftCnt > rightCnt {
			rightCnt++
			tmp = append(tmp, ')')
			dfs(cnt + 1)
			rightCnt--
			tmp = tmp[:len(tmp)-1]
		}
	}
	dfs(0)
	return res
}

86

剑指 Offer II 086. 分割回文子字符串

将字符串分割成回文串, 返回所有可能的方案

#include <functional>
#include <string>
#include <vector>

using namespace std;

vector<vector<string>> partition(string s) {
  int n = s.size();
  vector<vector<bool>> f(n, vector<bool>(n, true));
  for (int i = n - 1; i >= 0; --i) {
    for (int j = i + 1; j < n; ++j) {
      f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
    }
  }

  vector<vector<string>> ans;
  vector<string> splits;
  function<void(int)> dfs = [&](int i) {
    if (i == n) {
      ans.push_back(splits);
      return;
    }
    for (int j = i; j < n; ++j) {
      if (f[i][j]) {
        splits.push_back(s.substr(i, j - i + 1));
        dfs(j + 1);
        splits.pop_back();
      }
    };
  };
  dfs(0);
  return ans;
}

package main

func palindrome_partition(s string) (ans [][]string) {
	n := len(s)
	f := make([][]bool, n)
	for i := range f {
		f[i] = make([]bool, n)
		for j := range f[i] {
			f[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			f[i][j] = s[i] == s[j] && f[i+1][j-1]
		}
	}

	splits := []string{}
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, append([]string(nil), splits...))
			return
		}
		for j := i; j < n; j++ {
			if f[i][j] {
				splits = append(splits, s[i:j+1])
				dfs(j + 1)
				splits = splits[:len(splits)-1]
			}
		}
	}
	dfs(0)
	return
}

87

剑指 Offer II 087. 复原 IP

将字符串格式化成所有合法的ipv4地址

#include <string>
#include <vector>

using namespace std;

const int SEG_COUNT = 4;

vector<string> ans;
vector<int> segments(SEG_COUNT);

void dfs(const string &s, int segId, int segStart) {
  // If we have found 4 segments and traversed the entire string, it's a valid
  // IP address
  if (segId == SEG_COUNT) {
    if (segStart == s.size()) {
      string ipAddr;
      for (int i = 0; i < SEG_COUNT; ++i) {
        ipAddr += to_string(segments[i]);
        if (i != SEG_COUNT - 1) {
          ipAddr += ".";
        }
      }
      ans.push_back(ipAddr);
    }
    return;
  }

  // If we haven't found 4 segments but traversed the entire string, backtrack
  if (segStart == s.size()) {
    return;
  }

  // If the current number is 0, this segment can only be 0
  if (s[segStart] == '0') {
    segments[segId] = 0;
    dfs(s, segId + 1, segStart + 1);
    return;
  }

  // General case: enumerate each possibility and recurse
  int addr = 0;
  for (int segEnd = segStart; segEnd < s.size(); ++segEnd) {
    addr = addr * 10 + (s[segEnd] - '0');
    if (addr > 0 && addr <= 255) {
      segments[segId] = addr;
      dfs(s, segId + 1, segEnd + 1);
    } else {
      break;
    }
  }
}

vector<string> restoreIpAddresses(string s) {
  ans.clear();
  segments = vector<int>(SEG_COUNT);
  dfs(s, 0, 0);
  return ans;
}

package main

import "strconv"

const SEG_COUNT = 4

var (
	ans      []string
	segments []int
)

func restoreIpAddresses(s string) []string {
	segments = make([]int, SEG_COUNT)
	ans = []string{}
	dfs(s, 0, 0)
	return ans
}

func dfs(s string, segId, segStart int) {
	// 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
	if segId == SEG_COUNT {
		if segStart == len(s) {
			ipAddr := ""
			for i := 0; i < SEG_COUNT; i++ {
				ipAddr += strconv.Itoa(segments[i])
				if i != SEG_COUNT-1 {
					ipAddr += "."
				}
			}
			ans = append(ans, ipAddr)
		}
		return
	}

	// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
	if segStart == len(s) {
		return
	}
	// 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
	if s[segStart] == '0' {
		segments[segId] = 0
		dfs(s, segId+1, segStart+1)
	}
	// 一般情况，枚举每一种可能性并递归
	addr := 0
	for segEnd := segStart; segEnd < len(s); segEnd++ {
		addr = addr*10 + int(s[segEnd]-'0')
		if addr > 0 && addr <= 0xFF {
			segments[segId] = addr
			dfs(s, segId+1, segEnd+1)
		} else {
			break
		}
	}
}

88

剑指 Offer II 088. 爬楼梯的最少成本

给定一个一维数组表示爬楼梯需要的成本，并且每次支付一次就可以往上爬一个阶梯或者爬两个阶梯, 计算爬楼梯的最少成本。

#include <algorithm>
#include <vector>

using namespace std;

int minCostClimbingStairs(vector<int> &cost) {
  int n = cost.size();
  int pre = 0, cur = 0;
  for (int i = 2; i <= n; ++i) {
    int newCur = min(cur + cost[i - 1], pre + cost[i - 2]);
    pre = cur;
    cur = newCur;
  }
  return cur;
}

package main

func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	pre, cur := 0, 0
	for i := 2; i <= n; i++ {
		pre, cur = cur, min(cur+cost[i-1], pre+cost[i-2])
	}
	return cur
}

89

剑指 Offer II 089. 房屋偷盗

给定一个一维数组表示每间房子的价值，不能偷相邻的两家，问能够偷窃到的最高金额

#include <algorithm>
#include <vector>

using namespace std;

int rob(vector<int> &nums) {
  if (nums.empty()) {
    return 0;
  }
  if (nums.size() == 1) {
    return nums[0];
  }
  vector<int> dp(nums.size());
  dp[0] = nums[0];
  dp[1] = max(nums[0], nums[1]);
  for (int i = 2; i < nums.size(); ++i) {
    dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp.back();
}

int max(int x, int y) { return (x > y) ? x : y; }

package main

func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-1])
	}
	return dp[len(nums)-1]
}

90

剑指 Offer II 090. 环形房屋偷盗

与上一题类似，不过这一题房屋是首位相连的，问能够偷窃到的最大价值

#include <algorithm>
#include <vector>

using namespace std;

int _rob(const vector<int> &nums) {
  int first = nums[0], second = max(nums[0], nums[1]);
  for (int i = 2; i < nums.size(); ++i) {
    int v = nums[i];
    int newSecond = max(first + v, second);
    first = second;
    second = newSecond;
  }
  return second;
}

int rob(vector<int> &nums) {
  int n = nums.size();
  if (n == 1) {
    return nums[0];
  }
  if (n == 2) {
    return max(nums[0], nums[1]);
  }
  vector<int> nums1(nums.begin(), nums.end() - 1);
  vector<int> nums2(nums.begin() + 1, nums.end());
  return max(_rob(nums1), _rob(nums2));
}

int max(int a, int b) { return (a > b) ? a : b; }

package main

func _rob(nums []int) int {
	first, second := nums[0], max(nums[0], nums[1])
	for _, v := range nums[2:] {
		first, second = second, max(first+v, second)
	}
	return second
}

func robCircle(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}
	if n == 2 {
		return max(nums[0], nums[1])
	}
	return max(_rob(nums[:n-1]), _rob(nums[1:]))
}